all-zero keys in cell phones

Greg Rose (ggr@qualcomm.com)
Thu, 30 Jul 1998 15:32:08 +1000

• Next message: Paulo Barreto: "Re: DSA alternative to RSA"
• Previous message: Vin McLellan: "Fortify (strong intl SSL) for the Mac? <fw>"

[Hmmm. I apologise in advance for posting this to both mailing lists... it has
both political and technical significance.]

In some recent mail by (I believe, it was on some other subject and I deleted
it before deciding to write this) John Gilmore <gnu@toad.com>, he mentioned
that many phones out there use all-zero keys. I heard Tsutomo Shimomura say
the
same thing at the security summit in New Jersey about two weeks ago. And in
between, as it happens, I was at the CTIA Authentication Seminar, so I got the
real gossip. We are talking here about North American (TIA IS-41 standard)
phones, not GSM phones... GSM phones (supposedly) have non-zero keys in their
SIM cards.

The top level key in the phone is called the A-key, and it is 64 bits and
symmetric, shared (supposedly) only between the phone and the service
provider.
There are a number of ways this key can get into the phone:
- it can be entered through the keypad using either proprietary keystrokes
or a
sub-standard called TSB-50; what to enter may be read out over the phone, or
printed out, or all sorts of insecure ways.
- it can be programmed in at manufacture time, and communicated by a number of
methods, like (often unencrypted) electronic commerce transactions, to the
carrier when they activate service;
- it can be created by a Diffie-Hellman key agreement (not many people have
implemented this yet).

Which of these actually happens depends a lot on the carrier/manufacturer
combination. A lot of the time, one or the other can't do it better, and the
phone ends up having a zero A-key about 70% of the time... note that for some
carriers that is 100%, and for others it is 0% -- that is there are carriers
who really do care about this. The industry does recognise this as a serious
problem, and they are attempting to address it, as fast as they can. Remember
that most phones out there are not *capable* of doing the authentication (or
holding an A-key) in the first place... only about 50% penetration so far.

Does this mean that the authentication (or key-generation for privacy
features)
is completely crippled? No, actually it doesn't; not completely....

The only thing the A-key is used for is calculation of Shared Secret Data.
There are two 64-bit things called SSD-A and SSD-B, used for authentication
and
key generation respectively, and these are calculated (and recalculated as
often as deemed necessary (which isn't very often :-( )) based on the A-key, a
unique random challenge, and the 32 bit ESN (serial number) of the phone.

So, even though the A-key may be known or guessed to be zero, there is still a
non-zero pair of keys being used for authentication and key generation. There
is no *secret* entropy in these, but unless you were around at the time the
last SSD-update was done, and know the 32 bit unique random challenge that was
given, the best cryptographic attack is to guess the unique random, and follow
through the calculations, to obtain 2^32 possible SSD-A's, which can be
checked
against the 18-bit authentication signatures generated by the phone... so
generally if you get two such signatures right, you have the correct SSD-A.
Note that these can't be precomputed, as they are phone specific, because of
the ESN involvement in the computation.

Of course a non-cryptographic attack would be to somehow get the carrier to
force an SSD-update, and snoop it. Then you can calculate the shared secret
data as easily as the phone itself can.

Please note that I am *not* attempting to justify the widespread lack of
diligence or security around A-key generation and distribution. And I do *not*
claim that this is acceptable. (If you heard me yelling at them you would know
this :-) ) I just thought people might be interested in the facts.

Greg.

Greg Rose INTERNET: ggr@Qualcomm.com
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C

• Next message: Paulo Barreto: "Re: DSA alternative to RSA"
• Previous message: Vin McLellan: "Fortify (strong intl SSL) for the Mac? <fw>"