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

[f***@keemail.me]

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

[Jan Hrach]

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.

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
https://lists.srlabs.de/cgi-bin/mailman/listinfo/a51

[f***@keemail.me]

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

Post by Jan Hrach
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.

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
https://lists.srlabs.de/cgi-bin/mailman/listinfo/a51

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

[Jan Hrach]

Yes.

(actually, it's done 16320 times -- 51 samples * 8 colors * 40 rainbow tables)

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
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.
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
https://lists.srlabs.de/cgi-bin/mailman/listinfo/a51
--
Jan Hrach | http://jenda.hrach.eu <http://jenda.hrach.eu/>
GPG CD98 5440 4372 0C6D 164D A24D F019 2F8E 6527 282E

[f***@keemail.me]

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

Post by Jan Hrach
Yes.
(actually, it's done 16320 times -- 51 samples * 8 colors * 40 rainbow tables)

Post by f***@keemail.me
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

Post by Jan Hrach
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.
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

Post by Jan Hrach
https://lists.srlabs.de/cgi-bin/mailman/listinfo/a51

--
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

[Jan Hrach]

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.

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
Yes.
(actually, it's done 16320 times -- 51 samples * 8 colors * 40 rainbow tables)
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
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.
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
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