|
|
> Very interesting! I haven't heard anything about ORYX...
> Was it already implemented in any cellular network?
> For which cellular system was it originally intended (IS-54, IS-136,
> CDMA, GSM ?)
So far as I know, it hasn't been implemented anywhere yet. I don't
know what it was intended for -- it was described in the Common Cryptographic
Algorithms specification (which describes crypto-primitives which are
common to many or all of the North American cellular standards).
It definitely wasn't intended for GSM -- this was by the North American
standards body (TIA/CTIA/etc.), which has nothing to do with GSM.
> I mean how many values of A-key exist for any given RANDU/AUTHU pair?
Well, the A-key is 64 bits, so there are 2^64 possible A-key values.
(The A-key checksum is only for use when typing in the A-key by hand
on the keypad of the cellular handset; it adds a few additional digits.
Those additional checksum digits are then securely erased after entry
of the A-key. Typically the A-key should be entered before the customer
even sees the cellphone, or entered once by the customer when they start
service. The A-key checksum is merely intended to detect typing errors,
from what I can tell.)
Therefore, I don't think the A-key checksum will help in determining
the A-key.
Now if you have a RAND/AUTHU pair, I believe the AUTHU value is 18 bits
long, so in theory this means that we can eliminate all but 1 out of
every 2^18 possibilities for the A-key. In other words, 2^{64-18} = 2^46
possibilities will remain. With two RAND/AUTHU pairs, 2^28 possibilities
will remain, etc. With four RAND/AUTHU pairs, the A-key will (theoretically)
be determined uniquely.
However, even though the A-key will be determined uniquely, actually
finding that unique value is very difficult -- it requires much computation.
The most straightforward approach, brute force exhaustive key search,
would require 2^64 computations, which is probably too much to be feasible
today.
> Perhaps if we know both RANDU and AUTHU as a shortcut, and
> we could use the A-key checksum as another shortcut, it would
> take less than 100 hours of Pentium 200 to calculate all the possible
> (not 2^64, probably 2^8 or less) values of A-key. That's what I want
> to know. However, I'm not an expert in crypto, unfortunately :)
Well, that's the $64,000 question. I'm not aware of any shortcuts which
let you recover the A-key quickly given a few known RANDU/AUTHU values.
There are a number of cryptographers who have looked for such a shortcut;
it's not known whether one exists. This is the subject of active research.
I can say that CAVE appears to be cryptographically more secure than
any of the other cryptographic primitives used in the North American
cellphones. (That shouldn't be too surprising, since the industry
has a lot of money riding on the security of CAVE.)
> I understand that the CAVE is factory built-in in all newer AMPS/DAMPS
> cellular phones. Upon reception of RANDU (24 bit argument) it calculates
> AUTHU (18 bit function) according to one-way hash CAVE algorithm using
> additional arguments MIN1 (24 bit), MIN2 (8 bit), ESN (32 bit) and SSD-A
> (64 bit).
Right.
I do know this. Suppose we could get the full output (all 16 bytes) of
CAVE after hashing MIN1,MIN2,ESN,SSD-A, instead of just 18 bits (AUTHU)
selected from the output. Then there is a partial shortcut which lets
you reduce the amount of work required from 2^64 to 2^56. That would
mean that one could recover an SSD-A-key in about the same amount of time
that it took to break DES recently.
> I'm interested in the reverse process: knowing RANDU, AUTHU, MIN1, MIN2
> and ESN can anybody write a PC program to calculate all the values of
> A-key (how many such values do exist and how long will it take to
> calculate all of them with Pentium 200?). What if we know SSD-A as well?
SSD-A is generated (if I remember correctly) as the output of CAVE
applied to some different inputs, including the A-key. So it seems
that if you could find a shortcut to quickly recover SSD-A knowing
just RANDU,AUTHU,MIN1,MIN2,ESN... then the same shortcut might very
well also let you recover the A-key konwing SSD-A,MIN1,MIN2,ESN.
New!
A-Key Calculator (Win32) program for cellular industry
Description: this is an indispensable tool for cellular industry staff including technicians and security managers, as well as cellular shops and dealers. Now generating a valid A-Key with 6-digit checksum can be done on the spot, provided you know the phone's ESN number. This is sometimes required for testing the phone's A-Key entry function as well as for the phone's activation. It used to be possible to obtain a valid A-Key with cheksum only from the cellular operator itself, now everyone can easily generate the secret checksum value, enter those magic numbers into the phone just using the phone's own keypad and see how the phone is accepting the new A-Key by displaying "VALID". The A-Key Calculator program is not free, a single computer license costs US$49.00. The evaluation period is 30 days.
- Download A-Key Calculator (Win32, 613 kb)
