Newsgroup: it.comp.sicurezza.crittografia
Titolo: 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
PS: avevo mandato questo post già un'ora fa, fa non lo vedo apparire e
ne vedo invece altri miei... scusate se poi arriva doppio!
- --
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
iQIcBAEBCAAGBQJCZmSWAAoJELBiMTth2oCDtO0P/2MIvGDQkLiL7RQmlxP1fyy2
uA1TlrUFgZGzzyFGOVbiFgQ4S8+pEUfBDkhKErkGvMvBblBHRVB7xnip3Nv45/AN
iW7I/LiZUE00xYqOLE7bBKbQcIkO2Udoku5gBW19/T1u7XekpklKPLASAuE3IpXx
VM3Pb0bV3XYBJWy/h1xN0GiUF4gNZHrUFyqZWd+LfnGLk9gOILo3eDPQ96we/wAx
wS9542vs9n7gFZHvyHZEFYdey8EVt0KrfjKoUFInIIZt+JlG5sX0hxx85uryIVfS
SiMe361CW64eio/ZtUqY8KULE0CXbPVWH+04IuqotGXfYFgWPzg9Br8hOGtylafu
lWdDNugf/6SwDsIUgPuE4b6mN7XmsoSFCBOR1qsRM8hbYdgtGQhDGMG06dxjJ4RY
GaarioOxf3A8r+Sjzsnj360n0triZX5KPDdIqjiyOGU/pF1mIWwnMRp1/MEQj4yg
a9oe14kTaCB+pxREC8iBtqF0fR1duAMvSZhZwuxVA2ApJz6cEgVkq94Ucsn8icvh
DfNZRh6r1g8RXUDgjtpLdyCpoODzZmTS8HcRfUtvn8fzxJTOLmDu8hLFRZi0zR+/
5FCEj+BgeDDskSlzXKIN1T2eyja5VNxdQOpoznRS2Aeg6nFs69JAQK4GIvkV5s3U
NqTevUHkTMPEd1Bj4Yad
=evBp
-----END PGP SIGNATURE-----
-- 
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 /

  [X.509 available]
Linux Reg. User: #263663 / Machine: #216144 (Arch Linux/Wombat)
On the Web: 
http://www.quagliata.eu.org
 - My GPG Key:0x5539D8E4
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it

  [X.509 available]
Linux Reg. User: #263663 / Machine: #216144 (Arch Linux/Wombat)
On the Web: 
http://www.quagliata.eu.org
 - My GPG Key:0x5539D8E4
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
iD8DBQFCZqM9ZXjZQFU52OQRAmvFAJ9qgC1Z9TCuY72KbO0YgLBxqxorbgCgwDfk
TCmjrXNRIDBzA2M09cFEkjg=
=IDP9
-----END PGP SIGNATURE-----

 successore  di AES, 
...
Vedo che ora sei abbastanza d'accordo con me :-)
E credo che prima di sostituire AES qualcuno dalle parti di baltimora 
debba *prima* trovare il modo di violare il nuovo "candidato", 
altrimenti non se ne fa nulla.

 Vedo che ora sei abbastanza d'accordo con me :-)
No, non lo sono.
Il fatto che la crittografia, come tutte le scienze, faccia sempre dei
passi avanti è solo una fortuna e comunicarlo non è certo equivalente al
concordare con una teoria del complotto.
- --
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
iEYEARECAAYFAkJq5DMACgkQaJiCLMjyUvvdVgCg7U4kk0NHu5eBCS4DVLb8P7rX
YJEAn2LdwiHqAuYbVMKxaZa3KqkaqCLS
=RmvI
-----END PGP SIGNATURE-----

 concordare con una teoria del complotto.
Quale complotto? Io non ho mai parlato di complotti.
Ho detto che si poteva _quasi sicuramente_ fare una cosa e adesso, 
lentamente, i fatti mi danno ragione.
Solo questo.
I crittanalisti esistono per verificare la bonta' di un crittogramma 
(inteso in senso lato) e per scardinarli. Mi sembra semplicemente naturale.

 lentamente, i fatti mi danno ragione.
I fatti "lentamente" ti daranno certamente ragione su tutto, per due
buoni motivi:
1. quello che hai detto non è falsificabile
2. "prima o poi" tutto viene "rotto", come è giusto che sia
  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
iEYEARECAAYFAkJreA4ACgkQaJiCLMjyUvvY2ACeKLN/xe2LtRbdrs9eZZP9tMbD
lNkAoKsg9WMOGXk7VaMogTOwclSvpsZu
=9OoA
-----END PGP SIGNATURE-----

 2. "prima o poi" tutto viene "rotto", come è giusto che sia
Lasciamo stare tutto il resto. Solo una cosa sul punto 2. Io uso *solo* 
(o quasi) cifrari Vernam con una chiave generata in maniera casuale (non 
voglio addentrarmi su come: fidati).
Voglio il tuo parere (e non lo sto dicendo con sarcasmo, anzi): sei 
d'accordo che questo e' *l'unico* sistema *sicuro* per trasmettersi 
informazioni da proteggere e che questo non verra' "rotto" ?

 informazioni da proteggere e che questo non verra' "rotto" ?
OTP è dimostrato matematicamente inattaccabile (da Shannon, se non erro?
ma francamente non ricordo).
Il suo unico (ED ENORME) punto debole lo stai accantonando con un
"fidati": io mi fido (son dati tuoi, mica miei, quindi mi importa fino
ad un certo punto se sono al sicuro ;-)), ma tieni conto che al
contrario di molti altri cipher, l'OTP ha la "perssima caratteristica"
di essere molto molto molto molto molto molto MOLTO fragile.
Con "fragile" intendo dire: se la chiave non è perfettamente casuale
(entropia VERA, non robaccia generata da algoritmi), MAI ripetuta, MAI
riusata, passa con fin troppa facilità da "matematicamente perfetto" a
"anche un bambino lo romperebbe".
Proprio per questo lo considero il cipher contemporaneamente "migliore"
(da un punto di vista squisitamente teorico) e "peggiore" (da un punto
di vista dell'uso comune).
  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
iEYEARECAAYFAkJrsIgACgkQaJiCLMjyUvsF4wCgxEb2rJwi/EYGB4yIVbhRrtYw
9TUAoI9h/rNWW+09G/9l74p12YGfb7ee
=gSBa
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Nota: ri-leggendomi mi sono trovato un po' troppo "duro" o almeno può
sembra.. chiarifico: non ho asoslutamente niente contro chi sostiene
ipotesi definibili "del complotto": sono assolutamente tesi sostenibili
(e, in alcuni casi, anche vere); voglio solo mettere una linea di
"demarcazione" tra cosa è, diciamo "dimostrato" (o comunque verificabile
con il metodo scientifico) e cosa non lo è.
Ripeto: non essere falsificabile NON rende una teoria falsa.
La rende più difficilmente difendibile, ma proprio per il fatto che i
discorsi "su un riguardo" non cambia la "realtà" di quel riguardo
setsso, questo ha ben poco a che vedere con la sua esattezza o meno.
Poi, nel caso specifico ("l'NSA è 20 anni avanti, non esiste
crittografia 'civile' che gli resista") io sono anche personamlente
convinto che la cosa non sia vera... ma proprio per il fatto che la
suddetta frase non è falsificabile, questa è una mia
impressione/sensazione/credenza, e neanche questa va presa per essere
più vera del suo contrario ;-)
insomma, a ognuno il suo ;-)
  Lapo e il "non sono d'accordo con quello che dici ma difenderò fino
alla morte la tua libertà di dirlo" di Wilde-iana memoria
- --
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
iEYEARECAAYFAkJtMY0ACgkQaJiCLMjyUvv6UwCgvvM4oQyNi5j2feaHrlGHAuX8
5EgAn3gbHkYNZJN2wCBoKfeA4WWiCf6P
=/rrC
-----END PGP SIGNATURE-----

 alla morte la tua libertà di dirlo" di Wilde-iana memoria
Gia', oggi non piu' cosi' comune...

  [X.509 available]
Linux Reg. User: #263663 / Machine: #216144 (Arch Linux/Wombat)
On the Web: 
http://www.quaqo.org
 - My OpenPGP KeyID: 0x5539D8E4
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
iD8DBQFCdBNkZXjZQFU52OQRArS2AJ9UtVGgHWgvd7TZdr5T+BeQo00rcQCgvrFd
PHV1FQuznuM1SMaDm671Rlg=
=YHvu
-----END PGP SIGNATURE-----

  [X.509 available]
Linux Reg. User: #263663 / Machine: #216144 (Arch Linux/Wombat)
On the Web: 
http://www.quaqo.org
 - My OpenPGP KeyID: 0x5539D8E4
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
iD8DBQFCdBtUZXjZQFU52OQRAvb5AKCZNwHJ9HGqrma3sOfjxaMeSDMZqwCg0Od/
fk1+6dRnygb3f/AsTLGMEsM=
=yJPW
-----END PGP SIGNATURE-----

 Federico
Non credo sia una buona idea: e se qualcuno ci credesse ? :-D

 
Questo e' proprio la questione che intendevo affrontare, ovvero come
stabilire che una sequenza casuale sia adatta allo OTP.
Ho del materiale del NIST che sto esaminando ma mi interesserebbe che mi
spiegassi meglio quello che hai scritto sopra.
Eventualmente, se ti posso disturbare, ti scrivero' in privato.
Ciao e grazie.

 mi spiegassi meglio quello che hai scritto sopra.
Ti riferisci al test per i bit casuali o ad altro?
Cristiano

 Ti riferisci al test per i bit casuali o ad altro?
LA pubblicazione e' :
A STATISTICAL TEST SUITE FOR RANDOM AND
PSEUDORANDOM NUMBER GENERATORS FOR
CRYPTOGRAPHIIC APPLICATIONS
NIST Special Publication 800-22
(with revisions dated May 15, 2001)
Ma non ricordo il link dove scaricarlo.

 stabilire che una sequenza casuale sia adatta allo OTP.
Ccome diceva anche Cristiano è "praticamente" impossibile stabilirlo a
posteriori, in genere lo si "assicura" analizzando il processo che l'ha
creata e NON la stringa "casuale" ottenuta.
Questo perché i test di casualità che si trovano in giro sono ancora
abbastanza "naive" (anche i più complessi) e non è difficile pensare un
algoritmo totalmente deterministico (e quindi con casualità 0) che li
"freghi" tutti facendogli dire "questo è casuale".
La mia personale scelta è di usare "quello che passa il convento" in
quanto a casualità vera, dividerlo a blocchi che contengono "sicuramente
più di 160 bit di entropia" e ognuno di questi blocchi "tritarlo" con
SHA1, in modo da essere ragionevolmente sicuri che i 160 bit di output
siano "puri". Quando si usano fonti con entropia incerta (ad esempio il
rumore di fondo di una scheda audio) conviene "esagerare" e raccogliere
dati che si stima avere MOLTO più di 160 bit, per essere sicuri che
almeno 160 li abbiano.
Oggi come oggi il modo più veloce per avere entropia "seria" pare essere
l'uso di un processore VIA C5 [1] che contiene hardware dedicato (due
oscillatori non in fase tra loro) e una microistruzione assembler apposita.
(nota: che SHA1 venga "rotto" o meno non cambia molto, in questo
contesto, perché se l'input è imprevedibile anche l'output lo è; con
"rotto" si intende che si può ricavare l'output solo se l'input è
prevedibile o noto)
Links:
1. 
http://www.via.com.tw/en/initiatives/padlock/hardware.jsp
- --
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
iEYEARECAAYFAkJ0rzgACgkQaJiCLMjyUvvQJACfcSX8HajS8hwkTqPz8rzaJqkE
hXEAoIwiE5zjFb2IvzTX0SCsLLrqMouM
=I36O
-----END PGP SIGNATURE-----

 Non credo sia una buona idea: e se qualcuno ci credesse ? :-D
Ma no, un po' di informazione vera, in mezzo al FUD, non fa certo male,
l'importante è diffondere abastanza versioni diverse da lasciare tutti
nel dubbio 0=)
- --
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
iEYEARECAAYFAkJ0rO8ACgkQaJiCLMjyUvsTdQCfWTBiQynHwj7WmClFs2K2Up7R
xa4AoJ6P4SoWQgZ7kt19DccrG12NF2de
=3Xis
-----END PGP SIGNATURE-----

 Ma non ricordo il link dove scaricarlo.
Sì, sì, la conosco bene... :-)
E` una suite con alcune limitazioni (sia dovute ai test che al metodo
d'impiego). Lo so, l'ha scritta il NIST, ma...
<Messaggio pubblicitario>
Io ti consiglierei RaBiGeTe:
http://www.webalice.it/cristiano.pi/rabigete/
che è molto flessibile e oltre ad includere test molto efficaci, include
anche la versione migliorata di alcuni test del NIST.
Ho già disponibile la nuova versione (che include il collision test e una
versione migliorata del runs test). Prima di pubblicarla dovrei ultimare la
documentazione, ma se tu già la volessi...
<Fine messaggio pubblicitario>
Cristiano

 Purtroppo nonm l'ho costruito io e qui nasce l'esigenza di verificare
i dati.
Se non hai controllo / possibilità di analisi sulla "scatola nera" che
li genera, secondo me, non hai motivo per fidartene... (dato che non hai
possibilità per verificarli)... è tanto facile costruire una scatola
nera che p un pessimo RNG e poi "mascherare" la cosa con uno stadio di
hash prima dell'uscita...
  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
iEYEARECAAYFAkJ0t28ACgkQaJiCLMjyUvvy/wCgr409SDhpuuNQ3fXIlOvWbLT5
V+UAmgMZa0ey9OqSbHSydUo0kgU2CSDM
=Lso0
-----END PGP SIGNATURE-----