RSA OPTIMAL ASYMMETRIC ENCRYPTION PADDING

Tecnologie per la Sicurezza LS

Anno 2007 / 2008

Alessio Della Motta

Optim

al A

sym

metric E

ncry

ptio

n P

addin

g

Tecn

olo

gie

per la

Sicu

rezza

LS

CARATTERISTICHE DI RSA

Cifrario asimmetrico deterministico A blocchi di testo in chiaro identici corrispondono

blocchi uguali di testo cifrato Occorre rendere il cifrario probabilistico Esistono due standard:

PKCS #1 v. 1.5 – Padding Casuale PKCS #1 v. 2.0 (OAEP) – Codifica più Complessa

Optim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

PKCS #1 V. 1.5

Lo standard impone di premettere al messaggio un padding di 88 bit Il formato è il seguente:

0x00 || 0x02 || r || 0x00 || m con r un numero casuale e m il messaggio da inviare.

Oggi è sconsigliato e si raccomanda l’uso di OAEP In [1] viene mostrato un attacco CCA2 in grado di

rompere il cifrario con PKCS #1 v. 1.5.

Optim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

CHOSEN CIPHERTEXT ATTACKO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

L’avversario dispone di un decryption oracle al quale può sottoporre testi cifrati a sua scelta; tuttavia, per non rendere banale l’attacco, si suppone che il malintenzionato non possa sottoporre all’oracolo il testo cifrato a cui è interessato.

Non è una prospettiva puramente di studio: ad esempio un attaccante può avere a disposizione una macchina a cui sono dati i permessi di decifrare solo certe tipologie di messaggi.

Questo attacco può essere svolto secondo due modalità: CCA1 – Indifferent Chosen Ciphertext Attack

Accesso all’oracolo prima di scegliere il testo cifrato di interesse

CCA2 – Adaptive Chosen Ciphertext Attack Accesso all’oracolo dopo aver scelto il testo cifrato di interesse

OPTIMAL ASYMMETRIC ENCRYPTION PADDING (OAEP)

Procedimento di codifica (EME – Encoding Method for Encryption) parametrizzabile

Garantisce una buona soglia di casualità Stesso messaggio codificato in modi diversi

Padding deterministico per il controllo dell’integrità

Sicuro a fronte di attacchi del tipo CCA2

Optim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

EME-OAEP-ENCODEO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

Primitiva di codifica:

EME-OAEP-Encode (M, P, emLen)

Opzioni: Hash – Hash Function MGF – Mask Generation Function

Ingressi:

M P

emLen

Uscita: EM – Messaggio codificato

– Messaggio da codificare– Parametri di codifica, ovvero una stringa di byte– Lunghezza totale in byte del messaggio codificato

MASK GENERATION FUNCTIONO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

MGF (Z, l)

Opzioni: Hash – Funzione Hash, con output lungo hLen byte

Ingressi:

Z l

Uscita: mask – Maschera di lunghezza l byte

Tale funzione accetta in ingresso una stringa e ne restituisce un’altra di lunghezza specificata in input. Il comportamento di questa funzione è deterministico, ovvero per stringhe in ingresso identiche, si ottengono maschere identiche in uscita. L’output deve essere pseudo-casuale, cioè, data una sua parte, non deve essere possibile prevedere il seguito.

– Seed dal quale verrà generata la maschera – Lunghezza in byte della maschera che verrà generata, al massimo 232 hLen

L’indice del ciclo non può essere contenuto nei registri macchina...

ALGORITMO MGFO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

string MGF (string Z, int l){

string T = “”;

if (l > exp (2, 32) * hLen) then {

generate_error(“mask too long”);exit(1);

}

for (int i = 0; i < sup_int(l div hLen); i++)T = T || Hash (Z || i);

return T;}

ENCODING PASSO PASSO... (1)O

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

1) Poiché la stringa di parametri andrà in input alla funzione hash scelta, se la sua lunghezza eccede quella prevista da tale funzione verrà generato il seguente errore:

2) Se: mLen > emLen – 2hLen – 1, genera il seguente errore e termina:

“message too long”

“parameter string too long”

Si vuole codificare tramite lo standard il seguente messaggio:

M = d4 36 e9 95 69 fd 32 a7 c8 a0 5b bc 90 d3 2c 49

Si suppone che non ci siano parametri di ingresso e di volere in uscita un messaggio codificato lungo 127 byte. Invochiamo la funzione in questo modo:

EME-OAEP-Encode (M, NULL, 127)

L’algoritmo di codifica prevede i seguenti passi:

ENCODING PASSO PASSO... (2)O

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

3) Si genera una stringa PS di byte nulli (con tutti i bit a zero). In particolare:

4) Si fa l’hash (SHA-1) dei parametri P: pHash = hash (P)

len (PS) = emLen – mLen – 2hLen – 1

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Nel nostro esempio: len (PS) = 127 – 16 – 2*20 – 1 = 70 NOTA: la lunghezza di PS può essere anche zero.

da 39 a3 ee 5e 6b 4b 0d 32 55 bf ef 95 60 18 90 af d8 07 09hash (NULL) =

La lunghezza dell’impronta è costante (dipendendo dalla funzione) e nel nostro caso pari a 20.

ENCODING PASSO PASSO... (3)O

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

5) Si forma un blocco di dati DB nella maniera seguente:

DB = pHash || PS || 01 || M

Proseguendo con i dati dell’esempio si ottiene il seguente blocco dati:da 39 a3 ee 5e 6b 4b 0d 32 55 bf ef 95 60 18 90 af d8 07 09 00 00 00 0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 d4 36 e9 95 69fd 32 a7 c8 a0 5b bc 90 d3 2c 49

NOTE: • Il byte 01 è necessario nel caso in cui M iniziasse per 00;• PS serve per avere in uscita un messaggio esattamente lungo quanto specificato in ingresso.

ENCODING PASSO PASSO... (4)O

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

6) Si genera un seed casuale di lunghezza hLen:

aa fd 12 f6 59 ca e6 34 89 b4 79 e5 07 6d de c2 f0 6c b5 8f

Il seed garantisce una codifica differente anche per messaggi identici.

seed =

7) Si calcola: dbMask = MGF (seed, emLen – hLen)

06 e1 de b2 36 9a a5 a5 c7 07 d8 2c 8e 4e 93 24 8a c7 83 de e0 b2 c0 4626 f5 af f9 3e dc fb 25 c9 c2 b3 ff 8a e1 0e 83 9a 2d db 4c dc fe 4f f477 28 b4 a1 b7 c1 36 2b aa d2 9a b4 8d 28 69 d5 02 41 21 43 58 11 59 1be3 92 f9 82 fb 3e 87 d0 95 ae b4 04 48 db 97 2f 3a c1 4e af f4 9c 8c 3b7c fc 95 1a 51 ec d1 dd e6 12 64

Proseguendo l’esempio: dbMask = MGF (seed, 107)

ENCODING PASSO PASSO... (5)O

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

8) Si calcola: maskedDB = XOR (DB, dbMask)

dc d8 7d 5c 68 f1 ee a8 f5 52 67 c3 1b 2e 8b b4 25 1f 84 d7 e0 b2 c0 4626 f5 af f9 3e dc fb 25 c9 c2 b3 ff 8a e1 0e 83 9a 2d db 4c dc fe 4f f477 28 b4 a1 b7 c1 36 2b aa d2 9a b4 8d 28 69 d5 02 41 21 43 58 11 59 1be3 92 f9 82 fb 3e 87 d0 95 ae b4 04 48 db 97 2f 3a c1 4f 7b c2 75 19 5281 ce 32 d2 f1 b7 6d 4d 35 3e 2d

9) Si calcola:seedMask = MGF (maskedDB, hLen) = MGF (maskedDB, 20)

41 87 0b 5a b0 29 e6 57 d9 57 50 b5 4c 28 3c 08 72 5d be a9

10) Si calcola: maskedSeed = XOR (seed, seedMask)

eb 7a 19 ac e9 e3 00 63 50 e3 29 50 4b 45 e2 ca 82 31 0b 26

ENCODING PASSO PASSO... (6)O

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

11) Si ottiene il messaggio finale codificato nel modo seguente:

EM = maskedSeed || maskedDB

eb 7a 19 ac e9 e3 00 63 50 e3 29 50 4b 45 e2 ca 82 31 0b 26 dc d8 7d 5c68 f1 ee a8 f5 52 67 c3 1b 2e 8b b4 25 1f 84 d7 e0 b2 c0 46 26 f5 af f93e dc fb 25 c9 c2 b3 ff 8a e1 0e 83 9a 2d db 4c dc fe 4f f4 77 28 b4 a1b7 c1 36 2b aa d2 9a b4 8d 28 69 d5 02 41 21 43 58 11 59 1b e3 92 f9 82fb 3e 87 d0 95 ae b4 04 48 db 97 2f 3a c1 4f 7b c2 75 19 52 81 ce 32 d2f1 b7 6d 4d 35 3e 2d

Tale messaggio andrà quindi cifrato con la chiave pubblica di RSA {e, n} e quindi trasmesso al diretto interessato.

SCHEMA DI CODIFICAO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

seedseedpHashpHash PSPS

MM

DBDB

MGFMGF XORXOR

maskedDBmaskedDB

MGFMGFXORXOR

maskedSeed

maskedSeed

EMEM

EME-OAEP-DECODEO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

Primitiva di decodifica:

EME-OAEP-Decode (EM, P)

Opzioni: Hash – Hash Function MGF – Mask Generation Function

Ingressi:

EM – Messaggio codificato P – Parametri di codifica, ovvero una stringa di byte

Uscita: M – Messaggio ripristinato

DECODINGO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS1) Se P è maggiore della limitazione in input della funzione Hash

genera un errore “decoding error” e termina2) Se emLen < 2hLen + 1 genera un errore “decoding error” e

termina3) I primi venti byte di EM costituiscono il maskedSeed, mentre il

resto costituisce il maskedDB 4) Calcola: seedMask = MGF (maskedDB, hLen)5) Ottieni: seed = XOR (maskedSeed, seedMask)6) Calcola: dbMask = MGF (seed, emLen – hLen)7) Calcola: DB = XOR (maskedDB, dbMask)8) Calcola: pHash = Hash (P)9) Separa DB nelle stringhe: pHash’ || PS || 01 || M

Se non c’è il byte 01 genera un errore “decoding error” e termina

10)Se pHash ≠ pHash’ genera un errore “decoding error” e termina

11)Restituisci il messaggio originale M

La procedura di decoding è speculare a quella di encoding. Questi sono i passi dell’algoritmo:

SCHEMA DI DECODIFICAO

ptim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

seedseed

pHashpHash PSPS MM

DBDB

MGFMGF XORXOR

maskedDBmaskedDB

MGFMGFXORXOR

maskedSeedmaskedSeed

EMEM

CARATTERISTICHE RSA-OAEP

Introduce elementi di casualità È in grado di prevenire decifrazioni parziali

del testo cifrato Per ottenere il testo in chiaro, l’attaccante deve

necessariamente invertire completamente la funzione pseudo-unidirezionale di RSA

Si ha sicurezza a fronte di attacchi di tipo CCA2 se si utilizzano determinati accorgimenti [2]

Shoup [3] ha mostrato altre vulnerabilità dello standard ed ha proposto una versione più sicura, denominata OAEP+.

Optim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS

RIFERIMENTI

[1] D. Bleichenbacher, “Chosen Ciphertext Attacks Against Protocols Based on RSA Encryption Standard PKCS#1”, Advances in Cryptology—CRYPTO ’98 Proceedings, Springer-Verlag, 1998, pp. 1–12.

[2] J. Manger, “A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0”, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, Springer-Verlag, 2001, pp. 230 – 238.

[3] V. Shoup, “OAEP Reconsidered”. In J. Kilian, editor, Advances in Cryptology - Crypto 2001, volume 2139 of Lecture Notes in Computer Science, pp. 239 - 259. Springer Verlag, 2001.

Optim

al A

sym

metric E

ncry

ptio

n

Paddin

g T

ecn

olo

gie

per la

Sicu

rezza

LS