[A51] Bit position , table structure and gpu in A51 tables

Jan Hrach jenda at yakumo.hrach.eu
Fri Mar 18 17:59:04 CET 2016


> Why the * 40 multiplications ? i tought that it was just one big tables splitted in 40 files based on the non zero values of the "distinguish end point" used for raw device indexing.

No, these are completely independent tables (e.g. with independent reduction functions).

> Btw, why choosing 8 colors and what it the max chain length ?

There used to be XLS from Karsten Nohl where they computed optimal parameters. I have uploaded a copy here: http://jenda.hrach.eu/brm/kraken_magic/Rainbow.Tables.xls

The max chain length is not limited, it is only probabilistically distributed. The expected length is 2**12, as the distinguished point has 12 bits zero.


On 18.3.2016 16:32, fritchkornia at keemail.me wrote:
> First of all , big thanks :) Those informations are hard to get for people trying to cover the inner working / structure of those tables. Hope it will help further people as well.
> 
> Regarding this calculation : 51 samples * 8 colors * 40 rainbow tables
> 
> Why the * 40 multiplications ? i tought that it was just one big tables splitted in 40 files based on the non zero values of the "distinguish end point" used for raw device indexing.
> 
> Does it means that the colors for same columns positions are differents in each tables ?
> 
> Btw, why choosing 8 colors and what it the max chain length ?
> 
> Best Regards
> 
> 
> 18. Mar 2016 15:48 by jenda at yakumo.hrach.eu <mailto:jenda at yakumo.hrach.eu>:
> 
>     Yes.
> 
>     (actually, it's done 16320 times -- 51 samples * 8 colors * 40 rainbow tables)
> 
>     On 18.3.2016 15:31, fritchkornia at keemail.me <mailto:fritchkornia at keemail.me> wrote:
> 
> 
>         If there is a "bit offset" this means that the "distinguish end point computing" before disk lookup will be done in fact 51 times as 64 consecutive bits can fit 51 times in 114bits ?
>         -- 
>         Securely sent with Tutanota. Claim your encrypted mailbox today!
>         https://tutanota.com
> 
>         18. Mar 2016 11:39 by jenda at yakumo.hrach.eu <mailto:jenda at yakumo.hrach.eu> <mailto:jenda at yakumo.hrach.eu <mailto:mailto:jenda at yakumo.hrach.eu>>:
> 
>         https://brmlab.cz/project/gsm/deka/attack-theory
>         https://brmlab.cz/project/gsm/deka/attack-implementation
> 
>         I tought after a quick reading that the plaintext equivalent of the tables was the LFSRs state after 122 clocking and the output the 64 first bit of keystream (after 64 further clocking) with a simple reduction function output = new plaintext
> 
> 
>         No, it's the last 64 bits of keystream after 99+64 clockings. The reduction functions are XORed constants generated using A5/1 itself (does anyone know if there is any special purpose in this, or if it is just convenient?)
> 
>         See http://jenda.hrach.eu/gitweb/?p=deka;a=blob;f=genkernel32.sh;h=96ec2fc0a6b540101f6f6e8fa418c7b385b460d8;hb=HEAD for the actual chain computation (which is unfortunately a bit hard to read, as it is a hand-vectorized code).
> 
>         However while testing there is a Bit position that poped up . Does it mean that the compute function differ for each steps or is it just different in each tables ?
> 
> 
>         By bit position, you probably mean the offset if the 64bit sample in the 114bit burst.
> 
>         Finally what is the purpose of the GPU when finding new KC ? Is it just for the compute/reduction step ?
> 
> 
>         The chain is computed to the nearest endpoint on the GPU, then the corresponding startpoint is looked up on disk, and then the chain is reconstructed from that startpoint on the GPU again.
> 
> 
>         On 18.3.2016 10:33, fritchkornia at keemail.me <mailto:fritchkornia at keemail.me> <mailto:fritchkornia at keemail.me <mailto:mailto:fritchkornia at keemail.me>> wrote:
> 
> 
>         Hi
> 
>         I have a few questions regarding the A5/1 tables. I tought after a quick reading that the plaintext equivalent of the tables was the LFSRs state after 122 clocking and the output the 64 first bit of keystream (after 64 further clocking) with a simple reduction function output = new plaintext
> 
>         However while testing there is a Bit position that poped up . Does it mean that the compute function differ for each steps or is it just different in each tables ?
> 
>         IS there a simple guide to understand the table structure somehow .
> 
>         Finally what is the purpose of the GPU when finding new KC ? Is it just for the compute/reduction step ?
> 
> 
>         Best Regards
> 
> 
> 
>         _______________________________________________
>         A51 mailing list
>         A51 at lists.srlabs.de <mailto:A51 at lists.srlabs.de> <mailto:A51 at lists.srlabs.de <mailto:mailto:A51 at lists.srlabs.de>>
>         https://lists.srlabs.de/cgi-bin/mailman/listinfo/a51
> 
> 
> 
>         -- 
>         Jan Hrach | http://jenda.hrach.eu <http://jenda.hrach.eu <http://jenda.hrach.eu/>>
>         GPG CD98 5440 4372 0C6D 164D A24D F019 2F8E 6527 282E
> 
> 
>     -- 
>     Jan Hrach | http://jenda.hrach.eu <http://jenda.hrach.eu/>
>     GPG CD98 5440 4372 0C6D 164D A24D F019 2F8E 6527 282E
> 


-- 
Jan Hrach | http://jenda.hrach.eu/
GPG CD98 5440 4372 0C6D 164D A24D F019 2F8E 6527 282E



More information about the A51 mailing list