So what is the encryption in 3G/4G networks?
So what is the encryption in 3G/4G networks?
So should you use WhatsApp or your mobile phone network to make calls? Well, WhatsApp uses proper end-to-end encryption, but your 3G/4G network only supports encryption from phone to the base station, along with the possibility of it using a weak encryption cipher. With WhatsApp we have a proper key exchange using ECDH (Elliptic Curve Diffie-Hellman) and 126-bit/256-bit AES encryption, but what do we have on a 3G/4G network?
The advice of many industry experts would be that you should avoid using the mobile phone network if you want to make sure that your call cannot be tapped into. The major problem of the 3G/4G network is thus that the encryption is only applicable between the phone and the base station, and there is no encryption applied to the data when it reaches the wired network. To be fully secure, we must overlay our security with SSL/TLS, SSH, or a VPN tunnel.
A5/1 and A5/2
While we all concentrate on the core IP network, and which has relatively good protection in the transmission over the air, it is the GSM/3G network that could be at risk. The mobile phone network typically uses the A5/1 or A5/2 stream encryption method, but almost on its first day of operation it has been a target for crackers, and the source code to crack A5/2 was released within one month of being made public. While blocked ciphers like AES are robust, the A5/1 stream cipher has been shown to be weak against certain types of attack [2].
In the past, there has been two main choices for countries with their encryption on mobile networks: A5/1 and A5/2. A5/2 is intentionally weak, so that nation-states can easily crack the cipher, but was cracked generally within a month of it being publicly released. A5/1 was meant to be stronger, but, as it has a relatively short key, it can be cracked with powerful computers. Currently there are billions of devices around the world using A5/1 for their security, and it is likely that they can be cracked by the NSA.
With A5/1 we use three shift registers with feedback (Figure 1). With a stream cipher, we often generate an infinitely long keystream which is then EX-OR’ed with the data stream.
In the first shift register, the bits at positions 18, 17, 16 and 13 are X-OR’ed together to produce a new bit which is put at the end. This pushes all the bits to move one position to the left. The last bit (the one at Position 18) will then be pushed off and X-OR with the output from the other shift registers. The shift registers are 19, 22 and 23 bits long, thus the key used is 64-bits long (19+22+23). In the diagram, the bits 8, 10 and 10 are highlighted and are the clocking bits. These are examined each cycle. In these are will either be more 1’s than 0’s or more 0’s than 1’s. The registers with the most popular bit value will advance their bits, and the other will not advance.
Figure 1: [1]
The algorithm itself was kept secret while it was installed in 100 million mobile phones, and was part of the GSM (Global System and Mobile Communications) standard, and has since become a standard with 3G (even though it is seen as weak). The US and Europe adopted the strong A5/1 algorithm, but many selected the weaker one. It was finally made public in August 1999, and within a month the A5/2 method had been cracked. For A5/1 it is thought that the NSA can crack it (as they have the computing power to crack 64-bit keys).
The attack typically use known plaintext attacks, but new ones now allow the cipher stream to be decrypted in real-time. When first proposed, in 1982, it is thought that that the A5/1 key would be 128-bits long, but it finalised ended up with a 64-bit key (which can be cracked on expensive hardware using brute force). It is likely that government pressure forced the key to be much shorter. In fact it is thought that the UK wanted just 48 bits, while the West German government of the time pushed for larger key sizes (as they were worried that the East German government would be able to break their ciphers).
A stream cipher allows for automatic synchronisation, and where each bit can be decoded as it is received. A demo is here:
The attack typically use known plaintext attacks, but new ones now allow the cipher stream to be decrypted in…asecuritysite.com
SRLabs (Security Research Labs) focus on the capture of data from the mobile phone network and the cracking of A5/1 encryption. They take two encrypted known plaintext messages from the communications, and then use their Kraken utility to find the secret key for a 90% success rate with within seconds, using a set of rainbow tables (40 tables of 2TB in total size) [here].
Gendrullis et al [2] cracked A5/1 within hours using a parallel processing system, but these days NVIDIA GPUs running in the Cloud could achieve the same result, but significantly less expensive.
A5/3
The A5/3 encryption system — known as KASUMI — the Japanese word for “mist” — is the upgrade to A5/1 and uses a block cipher. A5/1 is designed to be used for the GSM network, whereas A5/3 is for 3GPP, and is based on the MISTY1 cipher created (and patented) by Mitsubishi, but was modified to reduce processing restrictions on mobile devices.
Key should be 32 characters (128 bits) and data should be in multiples of 16 characters (64-bits). In 2010, researchers (Orr Dunkelman, Nathan Keller and Adi Shamir) showed that Kasumi could be cracked with a related key attack. If the standards organisation has stuck with the original MISTY1 specification, the attack would not have been possible. KASUMI uses a 16x32 S-box approach to operations on the data, and has a 128-bit initialisation vector.
A newer attack — a sandwich attack — on A5/3 has shown that it is possible to crack A5/3 using an “unoptimised PC”, with 96 key bits recovered in a few minutes, and the rest of the 128-bit key within two hours.
A demo is here, and is based on the Python code at https://github.com/bozhu/KASUMI-Python:
key = 0x9900aabbccddeeff1122334455667788
text = 0xfedcba0987654321
def _bitlen(x):
assert x >= 0
return len(bin(x)) - 2
def _shift(x, s):
assert _bitlen(x) <= 16
return ((x << s) & 0xFFFF) | (x >> (16 - s))
def _mod(x):
return ((x - 1) % 8) + 1
S7 = (
54, 50, 62, 56, 22, 34, 94, 96, 38, 6, 63, 93, 2, 18,123, 33,
55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81,
53, 9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43,
20,122, 72, 61, 23,109, 13,100, 77, 1, 16, 7, 82, 10,105, 98,
117,116, 76, 11, 89,106, 0,125,118, 99, 86, 69, 30, 57,126, 87,
112, 51, 17, 5, 95, 14, 90, 84, 91, 8, 35,103, 32, 97, 28, 66,
102, 31, 26, 45, 75, 4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44,
64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59, 3,
)
S9 = (
167,239,161,379,391,334, 9,338, 38,226, 48,358,452,385, 90,397,
183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177,
175,241,489, 37,206, 17, 0,333, 44,254,378, 58,143,220, 81,400,
95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,
165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,
501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163,
232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135,
344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27,
487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124,
475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364,
363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229,
439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277,
465,416,252,287,246, 6, 83,305,420,345,153,502, 65, 61,244,282,
173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330,
280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454,
132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374,
35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285,
50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32,
72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355,
185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190,
1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111,
336,318, 4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18,
47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84,
414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201,
266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133,
311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404,
485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127,
312,377, 7,468,194, 2,117,295,463,258,224,447,247,187, 80,398,
284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451,
97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402,
438,477,387,122,192, 42,381, 5,145,118,180,449,293,323,136,380,
43, 66, 60,455,341,445,202,432, 8,237, 15,376,436,464, 59,461,
)
class Kasumi:
def __init__(self):
self.key_KL1 = [None] * 9
self.key_KL2 = [None] * 9
self.key_KO1 = [None] * 9
self.key_KO2 = [None] * 9
self.key_KO3 = [None] * 9
self.key_KI1 = [None] * 9
self.key_KI2 = [None] * 9
self.key_KI3 = [None] * 9
def set_key(self, master_key):
assert _bitlen(master_key) <= 128
key = [None] * 9
key_prime = [None] * 9
master_key_prime = master_key ^ 0x0123456789ABCDEFFEDCBA9876543210
for i in range(1, 9):
key[i] = (master_key >> (16 * (8 - i))) & 0xFFFF
key_prime[i] = (master_key_prime >> (16 * (8 - i))) & 0xFFFF
for i in range(1, 9):
self.key_KL1[i] = _shift(key[_mod(i + 0)], 1)
self.key_KL2[i] = key_prime[_mod(i + 2)]
self.key_KO1[i] = _shift(key[_mod(i + 1)], 5)
self.key_KO2[i] = _shift(key[_mod(i + 5)], 8)
self.key_KO3[i] = _shift(key[_mod(i + 6)], 13)
self.key_KI1[i] = key_prime[_mod(i + 4)]
self.key_KI2[i] = key_prime[_mod(i + 3)]
self.key_KI3[i] = key_prime[_mod(i + 7)]
def fun_FI(self, input, round_key):
# assert _bitlen(input) <= 16
left = input >> 7
right = input & 0b1111111
round_key_1 = round_key >> 9
round_key_2 = round_key & 0b111111111
tmp_l = right
# assert _bitlen(left) <= 9
tmp_r = S9[left] ^ right
left = tmp_r ^ round_key_2
# assert _bitlen(tmp_l) <= 7
right = S7[tmp_l] ^ (tmp_r & 0b1111111) ^ round_key_1
tmp_l = right
# assert _bitlen(left) <= 9
tmp_r = S9[left] ^ right
# assert _bitlen(tmp_l) <= 7
left = S7[tmp_l] ^ (tmp_r & 0b1111111)
right = tmp_r
# assert _bitlen(left) <= 7
# assert _bitlen(right) <= 9
return (left << 9) | right
def fun_FO(self, input, round_i):
# assert _bitlen(input) <= 32
# assert round_i >= 1 and round_i <= 8
in_left = input >> 16
in_right = input & 0xFFFF
out_left = in_right # this is not Feistel at all, maybe not reversible
out_right = self.fun_FI(in_left ^ self.key_KO1[round_i],
self.key_KI1[round_i]) ^ in_right
in_left = out_right # use in_* as temp variables
in_right = self.fun_FI(out_left ^ self.key_KO2[round_i],
self.key_KI2[round_i]) ^ out_right
out_left = in_right
out_right = self.fun_FI(in_left ^ self.key_KO3[round_i],
self.key_KI3[round_i]) ^ in_right
# assert _bitlen(out_left) <= 16
# assert _bitlen(out_right) <= 16
return (out_left << 16) | out_right
def fun_FL(self, input, round_i):
# assert _bitlen(input) <= 32
# assert round_i >= 1 and round_i <= 8
in_left = input >> 16
in_right = input & 0xFFFF
out_right = in_right ^ _shift(in_left & self.key_KL1[round_i], 1)
out_left = in_left ^ _shift(out_right | self.key_KL2[round_i], 1)
# assert _bitlen(out_left) <= 16
# assert _bitlen(out_right) <= 16
return (out_left << 16) | out_right
def fun_f(self, input, round_i):
# assert _bitlen(input) <= 32
# assert round_i >= 1 and round_i <= 8
if round_i % 2 == 1:
state = self.fun_FL(input, round_i)
output = self.fun_FO(state, round_i)
else:
state = self.fun_FO(input, round_i)
output = self.fun_FL(state, round_i)
# assert _bitlen(output) <= 32
return output
def enc_1r(self, in_left, in_right, round_i):
# assert _bitlen(in_left) <= 32
# assert _bitlen(in_right) <= 32
# assert round_i >= 1 and round_i <= 8
out_right = in_left # note this is different from normal Feistel
out_left = in_right ^ self.fun_f(in_left, round_i)
# assert _bitlen(out_left) <= 32
# assert _bitlen(out_right) <= 32
return out_left, out_right
def dec_1r(self, in_left, in_right, round_i):
# assert _bitlen(in_left) <= 32
# assert _bitlen(in_right) <= 32
# assert round_i >= 1 and round_i <= 8
out_left = in_right
out_right = self.fun_f(in_right, round_i) ^ in_left
# assert _bitlen(out_left) <= 32
# assert _bitlen(out_right) <= 32
return out_left, out_right
def enc(self, plaintext):
assert _bitlen(plaintext) <= 64
left = plaintext >> 32
right = plaintext & 0xFFFFFFFF
for i in range(1, 9):
left, right = self.enc_1r(left, right, i)
return (left << 32) | right
def dec(self, ciphertext):
assert _bitlen(ciphertext) <= 64
left = ciphertext >> 32
right = ciphertext & 0xFFFFFFFF
for i in range(8, 0, -1):
left, right = self.dec_1r(left, right, i)
return (left << 32) | right
print "Data is "+hex(text)
print "Key is "+hex(key)
my_kasumi = Kasumi()
my_kasumi.set_key(key)
encrypted = my_kasumi.enc(text)
print 'encrypted', hex(encrypted)
for i in range(99): # for testing
encrypted = my_kasumi.enc(encrypted)
for i in range(99):
encrypted = my_kasumi.dec(encrypted)
decrypted = my_kasumi.dec(encrypted)
print 'decrypted', hex(decrypted)
With 4G LTE (and which replaces the legacy Signalling System no. 7 (SS7) protocol), the encryption method used is SNOW 1.0/2.0/3G. These are synchronous stream ciphers developed by Thomas Johansson and Patrik Ekdahl (Lund University). SNOW 3G has been selected for the 3GPP encryption algorithms UEA2 and UIA2. The following shows the outline operation of Snow 3G. It uses a 128-bit key and a 128-bit IV. Snow 3G is a stream cipher and uses a LFSR with 16 cells of 8 bits each, along with a finite state machine (FSM).
The following shows the outline operation of Snow 3G. It uses a 128-bit key and a 128-bit IV. Snow 3G is a stream…asecuritysite.com
Conclusions
If you can, encrypt at the data layer. If you can, overlay your security.
References
[1] https://en.wikipedia.org/wiki/A5/1
[2] Gendrullis, Timo, Martin Novotný, and Andy Rupp. “A real-world attack breaking A5/1 within hours.” Cryptographic Hardware and Embedded Systems–CHES 2008. Springer Berlin Heidelberg, 2008. 266–282.