==============================================================================
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
--------------------[ previous ]---[ index ]---[ next ]---------------------

浜様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様様
藩HACKiNG様様様様幼陳陳陳 C0ME FUNZi0NA L'ALG0RiTM0 陳陳陳陳様様様様様様様様夕
                         DATA ENCRiPTi0N STANDARD (DES)    

Breve introduzione:

L'algoritmo Data Encryption Standard (DES), adottato dal governo
americano nel 1977, e' un blocco di crittazione che trasforma blocchi
di dati a 64 bit in blocchi sotto una chiave di 56 bits tramite 
sostituzioni e scambi. E' ufficialmente descritto nel FIPS PUB 46.
L'algoritmo DES e' largamente utilizzato ed e' tutt'ora considerato sicuro
ed affidabile ;).
Vi spieghero' questo algoritmo inquanto viene utilizzato spesso da 
programmi quali john the ripper o star cracker. Questo algoritmo e'
infatti utilizzato in moltissimi sistemi Linux, *nix e altri main 
frame. Tramite questa spiegazione sarete in grado (se saro' abbastanza
chiaro) di creare un semplice programma c capace di creare stringhe
di 8 caratteri cryptate. Starete dicendo; e che me ne faccio???.
Molto semplice... se dovreste trovare un file passwd criptato in DES
riuscirete a creare criptazioni identiche e confrontando i risultati
scoprirete i veri login. 

Ecco la descrizione dettagliata dell'algoritmo:

 1  Elaborare la parola.

 1.1  Prende una parola di 64-bit dall'utente, questa parola puo'
essere immessa direttamente o provenire da qualche altra fonte, ma cio'
non cambia l'andamento dell'algoritmo. L'ottavo bit di ogni byte della
parola viene considerato un bit di parita'. Per avere una parola di 
corretta parita', ogni byte deve contenere un numero dispari di bit 
allo stato "1".

 1.2  Calcola il key schedule.

 1.2.1  Esegue le seguenti permutazioni sulla parola di 64-bit.
Il bit 1 cioe' il piu' significativo diventa il bit 57 del blocco
permutato della parola originale, il bit 2 divente il 49 del blocco 
permutato e cosi' via fino a quando il bit 56 diventa il bit 4 della
parola originale. In questo modo i bit di parita' della parola vengono
scartati.

                        
                      Scelta di permutazione 1 (PC-1)

                          57 49 41 33 25 17  9
                           1 58 50 42 34 26 18
                          10  2 59 51 43 35 27
                          19 11  3 60 52 44 36
                          63 55 47 39 31 23 15
                           7 62 54 46 38 30 22
                          14  6 61 53 45 37 29
                          21 13  5 28 20 12  4

 1.2.2  Divide la chiave permutata in 2 meta'. I primi 28 bits sono
chiamati C[0] e gli ultimi 28 bits sono chiamati D[0].

 1.2.3  Calcola 16 sottoparole. Incomincia con i = 1.

 1.2.3.1  Esegue uno o due shift a sinistra sia su C[i-1] che su
D[i-1] per arrivare a C[i] e D[i]. I numeri di shift necessari per
ogni esecuzione sono riportati in questa tabella.

  Esecuzione #       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
  Shift a sinistra   1  1  2  2  2  2  2  2  1  2  2  2  2  2  2  1

 1.2.3.2  Cambia la concatenazione C[i]D[i] come indicato sotto. Questo
crea K[i], che e' un blocco di 48 bits.

                     Scelta di permutazione 2 (PC-2)

                           14 17 11 24  1  5
                            3 28 15  6 21 10
                           23 19 12  4 26  8
                           16  7 27 20 13  2
                           41 52 31 37 47 55
                           30 40 51 45 33 48
                           44 49 39 56 34 53
                           46 42 50 36 29 32

 1.2.3.3  Ritorna a 1.2.3.1 fino a quando K[16] e' calcolato.

 2  Procedi con il blocco di 64 bits.

 2.1  Memorizza un blocco di 64 bits. Se il blocco e' inferiore a 64 bits,
deve essere sistemato correttamente per questa operazione.

 2.2  Esegue le seguenti permutazioni sul blocco.

                       Permutazione iniziale (IP)

                        58 50 42 34 26 18 10  2
                        60 52 44 36 28 20 12  4
                        62 54 46 38 30 22 14  6
                        64 56 48 40 32 24 16  8
                        57 49 41 33 25 17  9  1
                        59 51 43 35 27 19 11  3
                        61 53 45 37 29 21 13  5
                        63 55 47 39 31 23 15  7

 2.3  Dividi i 2 blocchi in 2 meta'. I primi 32 bits sono chiamati
L[0], mentre gli ultimi 32 bits R[0].

 2.4  Applica le 16 sottoparole al blocco. Inizia con i = 1.

 2.4.1  Espandi i 32 bits R[i-1] in 48 bits come si vede nella funzione
di selezione bit sottostante.

                             Espansione (E)

                           32  1  2  3  4  5
                            4  5  6  7  8  9
                            8  9 10 11 12 13
                           12 13 14 15 16 17
                           16 17 18 19 20 21
                           20 21 22 23 24 25
                           24 25 26 27 28 29
                           28 29 30 31 32  1

 2.4.2  Esegue un or esclusivo E(R[i-1]) with K[i].

 2.4.3  Suddivide E(R[i-1]) xor K[i] in 8 blocchi da 6 bits l'uno.
I bits 1-6 sono B[1],i bits 7-12 sono B[2], cosi' fino a quando i bits 43-48 
diventano B[8].

 2.4.4  Sostituisce tutti i valori trovati nei Sobstitution boxes per 
tutti B[j]. Iniziando con j = 1. Tutti i valori nei Sobstitution boxes
devono essere considerati lunghi 4 bits.

 2.4.4.1  Prende il primo e il sesto bit di B[j] assieme come un
valore a 2 bits (chiamandolo m) indicando la riga in S[j] da guardare per
la sostituzione.

 2.4.4.2  Prende il secondo e il quinto bit di B[j] assieme come un
valore a 4 bits (chiamandolo n) indicando la colonna in S[j] per trovare
la sostituzione.

 2.4.4.3  Sostituisce B[j] con S[j][m][n].

                       Substitution Box 1 (S[1])

            14  4 13  1  2 15 11  8  3 10  6 12  5  9  0  7
             0 15  7  4 14  2 13  1 10  6 12 11  9  5  3  8
             4  1 14  8 13  6  2 11 15 12  9  7  3 10  5  0
            15 12  8  2  4  9  1  7  5 11  3 14 10  0  6 13

                                  S[2]

            15  1  8 14  6 11  3  4  9  7  2 13 12  0  5 10
             3 13  4  7 15  2  8 14 12  0  1 10  6  9 11  5
             0 14  7 11 10  4 13  1  5  8 12  6  9  3  2 15
            13  8 10  1  3 15  4  2 11  6  7 12  0  5 14  9

                                  S[3]

            10  0  9 14  6  3 15  5  1 13 12  7 11  4  2  8
            13  7  0  9  3  4  6 10  2  8  5 14 12 11 15  1
            13  6  4  9  8 15  3  0 11  1  2 12  5 10 14  7
             1 10 13  0  6  9  8  7  4 15 14  3 11  5  2 12

                                  S[4]

             7 13 14  3  0  6  9 10  1  2  8  5 11 12  4 15
            13  8 11  5  6 15  0  3  4  7  2 12  1 10 14  9
            10  6  9  0 12 11  7 13 15  1  3 14  5  2  8  4
             3 15  0  6 10  1 13  8  9  4  5 11 12  7  2 14

                                  S[5]

             2 12  4  1  7 10 11  6  8  5  3 15 13  0 14  9
            14 11  2 12  4  7 13  1  5  0 15 10  3  9  8  6
             4  2  1 11 10 13  7  8 15  9 12  5  6  3  0 14
            11  8 12  7  1 14  2 13  6 15  0  9 10  4  5  3

                                  S[6]

            12  1 10 15  9  2  6  8  0 13  3  4 14  7  5 11
            10 15  4  2  7 12  9  5  6  1 13 14  0 11  3  8
             9 14 15  5  2  8 12  3  7  0  4 10  1 13 11  6
             4  3  2 12  9  5 15 10 11 14  1  7  6  0  8 13

                                  S[7]

             4 11  2 14 15  0  8 13  3 12  9  7  5 10  6  1
            13  0 11  7  4  9  1 10 14  3  5 12  2 15  8  6
             1  4 11 13 12  3  7 14 10 15  6  8  0  5  9  2
             6 11 13  8  1  4 10  7  9  5  0 15 14  2  3 12

                                  S[8]

            13  2  8  4  6 15 11  1 10  9  3 14  5  0 12  7
             1 15 13  8 10  3  7  4 12  5  6 11  0 14  9  2
             7 11  4  1  9 12 14  2  0  6 10 13 15  3  5  8
             2  1 14  7  4 10  8 13 15 12  9  0  3  5  6 11

 2.4.4.4  Ritorna a 2.4.4.1 fino a quando tutti gli 8 blocchi sono 
stati sostituiti.

 2.4.5  Cambia la concatenazione di B[1] fino a B[8] come indicato
nella seguente tabella.

                             Permutation P

                              16  7 20 21
                              29 12 28 17
                               1 15 23 26
                               5 18 31 10
                               2  8 24 14
                              32 27  3  9
                              19 13 30  6
                              22 11  4 25

 2.4.6  Or esclusivo dei valori risultanti con L[i-1]. Questi, tutti assieme,
il tuo R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), dove B[j] e' un blocco
a 6 bits di E(R[i-1]) xor K[i]. (La funzione di R[i] puo' essere scritta
semplicemente come: R[i] = L[i-1] xor f(R[i-1], K[i]).)

 2.4.7  Esegue L[i] = R[i-1].

 2.4.8  Ritorna a 2.4.1 fino a quando K[16] e' stato preso in considerazione.

 2.5  Esegue la seguente permutazione sul blocco R[16]L[16]. (nota che
questo blocco R precede il blocco L questa volta.)

                       Permutazione finale (IP^-1)

                        40  8 48 16 56 24 64 32
                        39  7 47 15 55 23 63 31
                        38  6 46 14 54 22 62 30
                        37  5 45 13 53 21 61 29
                        36  4 44 12 52 20 60 28
                        35  3 43 11 51 19 59 27
                        34  2 42 10 50 18 58 26
                        33  1 41  9 49 17 57 25


Questa  una descrizione sull'algoritmo DES per cryptare un blocco di
64 bits. Per decryptare si utilizza lo stesso processo semplicemente
utilizza le parole K[i] in ordine inverso. Praticamente, invece di 
utilizzare K[1] per la prima interazione utilizza K[16], e poi K[15]
per seocnda e cosi' via fino a K[1].

L'algoritmo puo' essere riassunto schematicamente nel seguente modo:

 Key schedule:
  C[0]D[0] = PC1(key)
  for 1 <= i <= 16
   C[i] = LS[i](C[i-1])
   D[i] = LS[i](D[i-1])
   K[i] = PC2(C[i]D[i])

 Encipherment:
  L[0]R[0] = IP(plain block)
  for 1 <= i <= 16
   L[i] = R[i-1]
   R[i] = L[i-1] xor f(R[i-1], K[i])
  cipher block = FP(R[16]L[16])

 Decipherment:
  R[16]L[16] = IP(cipher block)
  for 1 <= i <= 16
   R[i-1] = L[i]
   L[i-1] = R[i] xor f(L[i], K[i])
  plain block = FP(L[0]R[0])

Esempi e boxes tratti da Matthew Fischer.
                                                           |scacco|

--------------------[ previous ]---[ index ]---[ next ]---------------------
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
==============================================================================