headers
nail | 12 Mar 2007 22:01

sicurezza di XEVRON

Forwardo manualmente questa mail, il cui contenuto e' comunque  
interessante, nell'attesa che l'autore
abbia la possibilita' di illuminarci maggiormente.
Pregasi leggere con un font monospaziato.

Alessio Orlandi
moderatore

============

Ok , avevo un attimo di pausa, quindi mi sono messo a meditare un po'  
algebricamente e quello che ne è uscito èquesto :

Ipotesi : assumo le specifiche Xevron T1 per semplicità di calcolo ,  
l' esempio è generalizzabileAssumo di conoscere MidA,MidB,Sh.
Tesi : XEVRON Ã rompibile attraverso il calcolo di una  
moltiplicazione tra interi , una divisione e una riduzione modulare  
modulo 10^n seguita da un' altra riduzione e sottrazione (ovverosia  
la formalizzazione del ""prendo le n cifre al centro)

esempio : assumo i numeri d' uso dei numeri di test del paper e  
attraverso una moltiplicazione ottengo

midb*mida=
68649215815345809894794524664582178043218794050295644619695039635107\
48464195461115232717448380115398847530277175035988375300402428264805\
568577400970218750
(il numero e' escaped per un comodo uso su terminale con bc)

a questo punto applico una divisione
(Continue reading)

Permalink | Reply |
headers
Andrea Pasquinucci | 13 Mar 2007 09:21
Picon

Re: sicurezza di XEVRON

Cerco di riassumere in parole quello che ho capito dalla discussione e 
dall'ultimo messaggio che spiega come fare l'algoritmo sul tipico 'back 
of an envelope' (non sarò molto preciso apposta).

Si tratta di moltiplicare 3 numeri (A, B, S), a due a due, ogni volta 
troncando le cifre più e meno significative. L'attaccante non conosce 2 
delle 3 cifre iniziali, ma conosce due prodotti troncati: A*S e B*S 
oltre a l'intero S. Come fare ad ottenere A*B*S troncato (la chiave 
segreta)?

La prima cosa da provare è (A*S)*(B*S)/S e vedere cosa ne viene fuori. 
Se non ci fosse il troncamento, il risultato sarebbe esatto. Troncando 
ovviamente mi perdo i riporti delle moltiplicazioni, come dicono anche 
gli stessi autori dell'algoritmo/protocollo. Quindi come attaccante mi 
mancano solo i riporti indipendentemente da quanto lunghi siano i 
numeri. L'attacco che proverei a fare è quello di individuare i riporti 
e fare un forza bruta su di essi. Quello che mi aspetto è che 
indipendentemente dalla lunghezza dei numeri in gioco, ci siano 
pochissimi riporti da provare per ottenere la chiave segreta.

Questo è solo un suggerimento, potrei aver sbagliato tutto...

Andrea

--
Andrea Pasquinucci                     liste@... - http://www.ucci.it/
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
(Continue reading)

Permalink | Reply |
headers
Theo Mora | 16 Mar 2007 18:50
Picon
Favicon

Dimostrazione di XEVRON

Ho guardato la loro dimostrazione.

A prima vista e` sbagliata
Usando la loro notazione, sembra che non si rendano conto che (in pag. 
5) "di solito"

a_1b_3+a_3b_1 > W^{h-k} per cui c'e' un "carry" che potrebbe sporcare la 
componente centrale.

OK, forse se qualcunoi fa scelte opportune su k,h e sul size accettabile 
per a,b il carry puo` essere evitato ma questo non e` discussoo da loro.

L'attacco (sbagliato) di Alessandro: spetta agli autori dimostrare 
ALMENO (una volta fissato il baco di cui sopra)
che l`attacco (mida*midb)/sh (magari modificato con un opportuno 
aggiustamento del carry) NON da mai il risultato

Conclusione: non e` snake-oil e` semplicemnte un risultato nella stessa 
compagnia delle infinite "dimostrazioni" del Teorema di Fermat e del 
Posulato di Euclide: ossia matematica in liberta`!

________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
Permalink | Reply |
headers
MultiTaskinG | 22 Mar 2007 16:43
Picon

Re: Dimostrazione di XEVRON

Il 16/03/07, Theo Mora<theomora@...> ha scritto:
> Ho guardato la loro dimostrazione.
>
> A prima vista e` sbagliata
> Usando la loro notazione, sembra che non si rendano conto che (in pag.
> 5) "di solito"
>
> a_1b_3+a_3b_1 > W^{h-k} per cui c'e' un "carry" che potrebbe sporcare la
> componente centra
le.

Mi scuso per aver risposto solo ora a causa di impegni precedentemente
presi, la discussione in ogni caso è proseguita in modo interessante
sui newsgroup di crittografia, matematica ed attualmente su sci.crypt

Buona l'osservazione di  Teo Mora sui "carry" provenienti dai termini
con potenze minori di 2h, questa particolarità era già nota a Xor Labs
group, anche se nella documentazione messa online sul sito non è
minimamente discussa.

L'argomento non è stato minimamente discusso perchè al pubblico sono
state proposte (al solo scopo di studio e quindi non in modo
definitivo) 4 tipi di implementazioni ben precise, in cui
statisticamente l'influenza dei resti è marginale.

La procedura XEVRON funziona anche con lunghezze "diverse tra loro" di
chiavi private e di troncamenti, in quel caso il calcolo dei resti
assume una rilevanza leggermente più alta, anche se rimane pur sempre
piuttosto marginale, grazie alla considerazione proposta anche da
Pasquinucci (che i resti sono limitati e "generalmente" influiscono
(Continue reading)

Permalink | Reply |
headers
Theo Mora | 23 Mar 2007 14:50
Picon
Favicon

Re: Dimostrazione di XEVRON


>
> Buona l'osservazione di  Teo Mora sui "carry" provenienti dai termini
> con potenze minori di 2h, questa particolarità era già nota a Xor Labs
> group, anche se nella documentazione messa online sul sito non è
> minimamente discussa.
>
> L'argomento non è stato minimamente discusso perchè al pubblico sono
> state proposte (al solo scopo di studio e quindi non in modo
> definitivo) 4 tipi di implementazioni ben precise, in cui
> statisticamente l'influenza dei resti è marginale.

Statisticamente marginale? 
Volete dire  che. nelle vostre quattro proposte,    c'e' un 10^{-e} 
possibilita` che le due chiavi costruite NON siano uguali?

>
> La procedura XEVRON funziona anche con lunghezze "diverse tra loro" di
> chiavi private e di troncamenti, in quel caso il calcolo dei resti
> assume una rilevanza leggermente più alta, anche se rimane pur sempre
> piuttosto marginale, grazie alla considerazione proposta anche da
> Pasquinucci (che i resti sono limitati e "generalmente" influiscono
> solo su un numero limitato di cifre).
>
> Posso garantire che nel testo ufficiale del brevetto depositato, viene
> fornita una formula apposita per il calcolo dei resti massimi, anche
> se questa per ora rimane parte del know-how interno di Xor Labs group.

OK, ma una dimostrazione che in quesi quattro casi il meccanismo 
funziona SEMPRE (o almeno QUASI sembre, una stima di quanto non puo`
(Continue reading)

Permalink | Reply |
headers
Stefano Zanero | 23 Mar 2007 11:16
Picon

Re: Dimostrazione di XEVRON

MultiTaskinG wrote:
> statisticamente l'influenza dei resti è marginale.

Per caso questo significa che "spesso", non sempre, la chiave scambiata
e' la stessa ?

--

-- 
Cordiali saluti,
Stefano Zanero

Politecnico di Milano - Dip. Elettronica e Informazione
Via Ponzio, 34/5 I-20133 Milano - ITALY
Tel.    +39 02 2399-4010
Fax.    +39 02 2399-3411
E-mail: zanero@...
Web:    www.elet.polimi.it/upload/zanero
________________________________________________________
http://www.sikurezza.org - Italian Security Mailing List
Permalink | Reply |
headers
nail | 23 Mar 2007 11:18

Re: Dimostrazione di XEVRON


On Mar 22, 2007, at 4:43 PM, MultiTaskinG wrote:

>
>
> Posso garantire che nel testo ufficiale del brevetto depositato, viene
> fornita una formula apposita per il calcolo dei resti massimi, anche
> se questa per ora rimane parte del know-how interno di Xor Labs group.

Per quanto un po' datato, ritengo ancora attuali le osservazioni  
contenute nell'articolo
di Bruce Schneier  sulla Open Source Cryptography:

http://www.schneier.com/crypto-gram-9909.html

senza comunque voler destare ulteirori discussioni sul conflitto tra  
la protezione
della proprieta' intellettuale e la necessita' di dimostrazione di  
sicurezza della
stessa:

Saluti,
   Alessio Orlandi


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

Gmane