DJB: attacco alle S-box

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
"Cache-timing attacks on AES", Daniel J. Bernstein
14/04/2005 (versione NON definitiva)

Tutti i cifrari che hanno gareggiato per diventare AES basano una loro
implementazione efficiente  sull'uso di S-box precalcolate  e molti di
loro utilizzano l'S-box come principale (per Rijndael, unica) fonte di
non-linearità  nell'intero  algoritmo.  Questo  è  stato  perfino  uno
dei  motivi di  scelta di  Rijndael, particolarmente  adatto a  essere
implementato  con  S-box e  poco  altro  e,  quindi, molto  veloce  da
implementare in modo "sicuro".

Tutto questo,  ovviamente, considerando l'accesso a  una S-box (ovvero
l'accesso ad un array di valori precalcolati con indice dipendente dal
dato) una operazione tempo-costante.

Questo paper di  DJB si "limita" a dire con  prepotenza quello che già
da oltre un decennio altri avevano  accennato: un accesso ad array con
indice dipendente dal dato NON è da considerarsi tempo costante.

Questo permette di  fare svariate analisi basate  sul tempo necessario
per eseguire l'algoritmo crittografico (Bernstein si concentra su AES,
dato che è "lo standard", ma  sottintende che le sue argomentazioni si
applicano alla  maggior parte degli  altri cifrari) e,  in definitiva,
capire la chiave utilizzata.

La piacevole novità di questo paper,  inoltre, è che DJB non lavora in
quell'ambito  da crittografo/matematico  professionista  che  è a  lui
congeniale  ma  a  tanti  altri poco  accessibile:  l'intero  paper  è
leggibilissimo  (per mio  giudizio) da  chiunque abbia  una conoscenza
base dell'informatica e del funzionamento delle moderne CPU.

Il tutto,  infine, è  corredato da  un set di  piccoli programmi  in C
(poche  pagine  in tutto!)  che  in  modo *sorprendentemente*  facile,
applicano  quanto detto  e -voila-  recuperano  una chiave  AES da  un
processo remoto che  utilizza OpenSSL. (ma DJB specifica  che tutte le
implementazioni  che ha  provato hanno  questo problema,  non è  certo
specifico a OpenSSL)

In  definitiva? In  definitiva AES  (e con  lui la  MAGGIOR PARTE  dei
cifrari moderni) ha  subito un brutto colpo, qualcosa  di difficile da
"rappezzare"  in  software  (se  non  perdendo  straordinariamente  in
prestazioni),  qualcosa che,  fondamentalmente,  dovrebbe spingere  il
NIST  (o chi  per lui)  a un  nuovo turno  di scelte,  per trovare  il
successore  di AES,  aggiungendo  come ovvio  pre-requisito (oltre  ai
pre-esistenti,  come ad  esempio  resistere a  crittanalisi lineare  e
differenziale) anche di non utilizzare array con indice dipendente dal
dato: fino a oggi considerati tempo costanti e quindi "sicuri", ma ora
non più.

O  il  NIST  si  muoverà  a proporre  un  nuovo  standard  "de  iure",
possibilmente con  l'illuminato processo "aperto" che  ha portato alla
scelta di AES  (XES? eXtreme Encryption System? oggi le  X vanno tanto
di moda...)  o probabilmente  gli implementatori inizieranno  ad avere
"sufficienti motivi" per spingere qualche altro standard "de facto"...

Tra questo  e i recenti  attacchi cinesi all'intero gruppo  degli hash
oggi in uso.. come dire: viviamo in tempi interessanti.

    Lapo

- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQIcBAEBCAAGBQJCZub5AAoJELBiMTth2oCDOuwP/igkcZm2ytrWIlWkdCyEDzsA
EihFSAVTTlgVHqJmA7jJ/Lt7vOhPI3AJ3LjooigrB9C9BvtscBvtLfsLKaR/Fgbv
mhj9DtSDi9LZSOKXatbtKX8Zk9ySZ1PD+pOCJp18MOvYp/3cfeEu5E4qBkBxU/I6
fMEPGNhWdombcS1YMyznArEp2B4rhJmGpZ8rHVp+/q12z0dkv/OLxPqu9IIa6m/y
nZ4wxBcQmqbO0MA7SvljBmqYPf1/Pu14nsAdP2yto0OTlOYQjkDYhZkapOZzFqF6
mvxj9mlvEov3K7lwxH1Euy7UEPN9tqHFfheXiJHq05jWymhYgMrAnBOlzLabR0Gp
PFsTecO1kY+2OoV69294c+Mkf4RRZnsg6B5XTj0Nv1feL489K9gECO0wHeuW2nMq
zsbUi2qPvrJzJ+VEoeZxNywGWIZiXExRdEAGSVqc6WTA/XLu/WoLHb2XZbrNvHCF
/tgmFc/0HLOJrDBnKt4TE6MsehtQ6O6attaXQ2uhxFNQ5BldCrH7KRj99Ta47+46
y+cJqCZO/Yh5RLdm58tGgA2wdfxcr7P8xRUWHncallzDoV8k7WXKdvaJzNXST+Zi
WUvdOsbtBoZlXrAcEFFWE/cuZeP0jDT2moTvzQREW0r9aV074k9EeDNy/2nekUQU
cjU211f+KGgeZAFhD3Uf
=dIm6
-----END PGP SIGNATURE-----

________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List