Discussion:
Cracking uplink bursts
T
2011-09-12 21:21:50 UTC
Permalink
I have downloaded the tables from
http://opensource.srlabs.de/projects/a51-decrypt/files and the kracken
code from git://git.srlabs.de/kraken.git, compiled and installed
everything.
I have successfully run through the example at
www.ks.uni-freiburg.de/download/misc/practical_exercise_a51.pdf and
http://srlabs.de/uncategorized/airprobe-how-to/

I had a few questions I was hoping someone would be able to answer:

Can uplink bursts be cracked? It looks like find_kc will need to be
modified for uplink, are any other changes required? Has anyone tried
that?

Why are only some bursts able to be cracked?
What percentage of bursts is expected to be cracked?
Should at least one of the four bursts in a message always be cracked?

Thanks for any info you can provide.

-Todd

(sorry if this is a repost, I was having email issues)
Karsten Nohl
2011-09-13 06:01:05 UTC
Permalink
Post by T
Can uplink bursts be cracked? It looks like find_kc will need to be
modified for uplink, are any other changes required? Has anyone tried
that?
For uplink cracking, you need to add 114 back clocking steps in find_kc.
Post by T
Why are only some bursts able to be cracked?
The coverage of all tables combined is 0.04%.
Post by T
What percentage of bursts is expected to be cracked?
Each burst gives you 114-63 tries with 0.04% success probability each.
Post by T
Should at least one of the four bursts in a message always be cracked?
Four burst are cracked with 92% success.

Cheers,

-Karsten
T
2011-09-14 00:34:13 UTC
Permalink
Thanks for the info.
Post by Karsten Nohl
Post by T
Why are only some bursts able to be cracked?
The coverage of all tables combined is 0.04%.
Post by T
What percentage of bursts is expected to be cracked?
Each burst gives you 114-63 tries with 0.04% success probability each.
Post by T
Should at least one of the four bursts in a message always be cracked?
Four burst are cracked with 92% success.
How do you get to the 92% success rate for four bursts?

If I assume a 0.04% success rate for each try, I get:
p=0.04e-2;
Probability of success = 1 - (1-p)^(4*(114-63)) = 7.8%


Also, how does that compare to the success rate quoted here:
https://media.blackhat.com/bh-ad-10/Nohl/BlackHat-AD-2010-Nohl-Attacking-Phone-Privacy-wp.pdf
"Given two encrypted known plaintext messages (ie. Cipher mode complete and a
System Information message), the table set finds a secret key with
almost 90% probability."

-Todd
Karsten Nohl
2011-09-14 06:50:51 UTC
Permalink
Hi,
Post by T
Thanks for the info.
Post by Karsten Nohl
Post by T
Why are only some bursts able to be cracked?
The coverage of all tables combined is 0.04%.
Post by T
What percentage of bursts is expected to be cracked?
Each burst gives you 114-63 tries with 0.04% success probability each.
Post by T
Should at least one of the four bursts in a message always be cracked?
Four burst are cracked with 92% success.
How do you get to the 92% success rate for four bursts?
p=0.04e-2;
Probability of success = 1 - (1-p)^(4*(114-63)) = 7.8%
The calculation is not quiet as simple as the A5/1 state space is not uniformly distributed.

But you are right, there was a little inconsistency in my calculation: I was assuming 8 bursts, ie. 2 full messages.
Post by T
https://media.blackhat.com/bh-ad-10/Nohl/BlackHat-AD-2010-Nohl-Attacking-Phone-Privacy-wp.pdf
"Given two encrypted known plaintext messages (ie. Cipher mode complete and a
System Information message), the table set finds a secret key with
almost 90% probability."
2 messages => 92% success.

Cheers,

-Karsten
T
2011-09-22 06:22:40 UTC
Permalink
In trying to verify the setup, the following test was run repeatedly:
a) Generate a random Kc and 4 successive frame numbers
b) Use the Kc and frame number to generate the downlink and
uplink keystreams for 4 bursts.
c) Feed the uplink keystreams to Kraken and find_kc to determine success

This produced a success rate of about 40% (or 67 % for two messages)
When the same procedure was repeated except using downlink keystreams,
it gave a success rate of 85% for two messages.

Would you anticipate differences between the success probability on
uplink versus downlink?

Might it be caused by differences in Rainbow table coverage? If so,
could rainbow tables of the same size be generated in a manner that
favors the uplink?


-Todd
Post by Karsten Nohl
Hi,
Post by T
Thanks for the info.
Post by Karsten Nohl
Post by T
Why are only some bursts able to be cracked?
The coverage of all tables combined is 0.04%.
Post by T
What percentage of bursts is expected to be cracked?
Each burst gives you 114-63 tries with 0.04% success probability each.
Post by T
Should at least one of the four bursts in a message always be cracked?
Four burst are cracked with 92% success.
How do you get to the 92% success rate for four bursts?
p=0.04e-2;
Probability of success = 1 - (1-p)^(4*(114-63)) = 7.8%
The calculation is not quiet as simple as the A5/1 state space is not uniformly distributed.
But you are right, there was a little inconsistency in my calculation: I was assuming 8 bursts, ie. 2 full messages.
Post by T
https://media.blackhat.com/bh-ad-10/Nohl/BlackHat-AD-2010-Nohl-Attacking-Phone-Privacy-wp.pdf
"Given two encrypted known plaintext messages (ie. Cipher mode complete and a
System Information message), the table set finds a secret key with
almost 90% probability."
2 messages => 92% success.
Cheers,
  -Karsten
Loading...