[PATCH] Add A5/3 support.

Max Max.Suraev at fairwaves.ru
Thu Nov 29 14:07:27 UTC 2012


---
 include/osmocom/gsm/a5.h |    4 +-
 src/gsm/a5.c             |  246 ++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 239 insertions(+), 11 deletions(-)

diff --git a/include/osmocom/gsm/a5.h b/include/osmocom/gsm/a5.h
index 649dbab..46cf4fb 100644
--- a/include/osmocom/gsm/a5.h
+++ b/include/osmocom/gsm/a5.h
@@ -54,10 +54,10 @@ osmo_a5_fn_count(uint32_t fn)
 	 *  - fn is the _real_ GSM frame number.
 	 *    (converted internally to fn_count)
 	 */
-void osmo_a5(int n, const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul);
+int osmo_a5(int n, const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul);
 void osmo_a5_1(const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul);
 void osmo_a5_2(const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul);
-
+void osmo_a5_3(const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul);
 /*! @} */
 
 #endif /* __OSMO_A5_H__ */
diff --git a/src/gsm/a5.c b/src/gsm/a5.c
index 356060a..d95283e 100644
--- a/src/gsm/a5.c
+++ b/src/gsm/a5.c
@@ -33,9 +33,10 @@
 /*! \file gsm/a5.c
  *  \brief Osmocom GSM A5 ciphering algorithm implementation
  */
-
+#include <stdio.h>
 #include <string.h>
-
+#include <errno.h>
+#include <osmocom/core/bits.h>
 #include <osmocom/gsm/a5.h>
 
 /*! \brief Main method to generate a A5/x cipher stream
@@ -45,10 +46,10 @@
  *  \param[out] dl Pointer to array of ubits to return Downlink cipher stream
  *  \param[out] ul Pointer to array of ubits to return Uplink cipher stream
  *
- * Currently A5/[0-2] are supported.
+ * Currently A5/[0-2] are supported: -ENOTSUP returned in this case, 0 returned for supported ciphers.
  * Either (or both) of dl/ul can be NULL if not needed.
  */
-void
+int
 osmo_a5(int n, const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
 {
 	switch (n)
@@ -58,20 +59,25 @@ osmo_a5(int n, const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
 			memset(dl, 0x00, 114);
 		if (ul)
 			memset(ul, 0x00, 114);
-		break;
+		return 0;
 
 	case 1:
 		osmo_a5_1(key, fn, dl, ul);
-		break;
+		return 0;
 
 	case 2:
 		osmo_a5_2(key, fn, dl, ul);
-		break;
+		return 0;
+
+	case 3:
+		osmo_a5_3(key, fn, dl, ul);
+		return 0;
 
 	default:
-		/* a5/[3..7] not supported here/yet */
-		break;
+		/* a5/[4..7] not supported here/yet */
+		return -ENOTSUP;
 	}
+	return -ENOTSUP; /* make compiler happy */
 }
 
 
@@ -364,4 +370,226 @@ osmo_a5_2(const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
 	}
 }
 
+/* ------------------------------------------------------------------------ */
+/* A5/3                                                                     */
+/* ------------------------------------------------------------------------ */
+
+uint16_t _rol16(uint16_t in, unsigned shift)
+{
+    return (in << shift) | (in >> (16 - shift));
+}
+
+uint16_t osmo_get2bytes(uint8_t *a)
+{ /* UNSAFE! Do NOT use unless you know what you are doing! */
+    return (uint16_t)((((uint16_t)a[0]) << 8) + (uint16_t)a[1]);
+}
+
+void osmo_64pack2pbit(uint64_t in, pbit_t *out)
+{
+    int i;
+    for (i = 7; i >=0; i--) {
+	out[i] = in & 0xFF;
+	in >>= 8;
+    }
+}
+
+uint16_t
+_a5_3_kasumi_FI(uint16_t I, uint16_t skey)
+{
+    static uint16_t 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
+    };
+    static uint16_t 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
+    };
+    uint16_t L, R;
+
+    /* Split 16 bit input into two unequal halves: 9 and 7 bits, same for subkey */
+    L  = I >> 7; /* take 9 bits */
+    R = I & 0x7F; /* take 7 bits */
+
+    L  = S9[L]  ^ R;
+    R = S7[R] ^ (L & 0x7F);
+
+    L  ^= (skey & 0x1FF);
+    R ^= (skey >> 9);
+
+    L  = S9[L]  ^ R;
+    R = S7[R] ^ (L & 0x7F);
+
+    return (R << 9) + L;
+}
+
+uint32_t
+_a5_3_kasumi_FO(uint32_t I, uint16_t *KOi1, uint16_t *KOi2, uint16_t *KOi3, uint16_t *KIi1, uint16_t *KIi2, uint16_t *KIi3, unsigned i)
+{
+    uint16_t L = I >> 16, R = I; /* Split 32 bit input into Left and Right parts */
+
+    L ^= KOi1[i];
+    L = _a5_3_kasumi_FI(L, KIi1[i]);
+    L ^= R;
+
+    R ^= KOi2[i];
+    R =_a5_3_kasumi_FI(R, KIi2[i]);
+    R ^= L;
+
+    L ^= KOi3[i];
+    L = _a5_3_kasumi_FI(L, KIi3[i]);
+    L ^= R;
+
+    return (((uint32_t)R) << 16) + L;
+}
+
+uint32_t
+_a5_3_kasumi_FL(uint32_t I, uint16_t *KLi1, uint16_t *KLi2, unsigned i)
+{
+    uint16_t L = I >> 16, R = I, tmp; /* Split 32 bit input into Left and Right parts */
+
+    tmp = L & KLi1[i];
+    R ^= _rol16(tmp, 1);
+
+    tmp = R | KLi2[i];
+    L ^= _rol16(tmp, 1);
+
+    return (((uint32_t)L) << 16) + R;
+}
+
+uint64_t
+_a5_3_kasumi(uint64_t P, uint16_t *KLi1, uint16_t *KLi2, uint16_t *KOi1, uint16_t *KOi2, uint16_t *KOi3, uint16_t *KIi1, uint16_t *KIi2, uint16_t *KIi3)
+{
+    uint32_t i, L = P >> 32, R = P; /* Split 64 bit input into Left and Right parts */
+
+    for (i = 0; i < 8; i++)
+    {
+	R ^= _a5_3_kasumi_FO(_a5_3_kasumi_FL(L, KLi1, KLi2, i), KOi1, KOi2, KOi3, KIi1, KIi2, KIi3, i); /* odd round */
+	i++;
+	L ^= _a5_3_kasumi_FL(_a5_3_kasumi_FO(R, KOi1, KOi2, KOi3, KIi1, KIi2, KIi3, i), KLi1, KLi2, i); /* even round */
+    }
+    return (((uint64_t)L) << 32) + R; /* Concatenate Left and Right 32 bits into 64 bit ciphertext */
+}
+
+/*! \brief Expand key into set of subkeys
+ *  \param[in] key (128 bits) as array of bytes
+ *  \param[out] arrays of round-specific subkeys - see TS 135 202 for details
+ */
+void
+_a5_3_key_expand(uint8_t *key, uint16_t *KLi1, uint16_t *KLi2, uint16_t *KOi1, uint16_t *KOi2, uint16_t *KOi3, uint16_t *KIi1, uint16_t *KIi2, uint16_t *KIi3)
+{
+    uint16_t i, C[] = { 0x0123, 0x4567, 0x89AB, 0xCDEF, 0xFEDC, 0xBA98, 0x7654, 0x3210 };
+
+    for (i = 0; i < 8; i++) /* Work with 16 bit subkeys and create prime subkeys */
+    {
+	C[i] ^= osmo_get2bytes(key + i * 2);
+    }
+    /* C[] now stores K-prime[] */
+    for (i = 0; i < 8; i++) /* Create round-specific subkeys */
+    {
+	KLi1[i] = _rol16(osmo_get2bytes(key + i * 2), 1);
+	KLi2[i] = C[(i + 2) & 0x7];
+
+	KOi1[i] = _rol16(osmo_get2bytes(key + ((2 * (i + 1)) & 0xE)), 5);
+	KOi2[i] = _rol16(osmo_get2bytes(key + ((2 * (i + 5)) & 0xE)), 8);
+	KOi3[i] = _rol16(osmo_get2bytes(key + ((2 * (i + 6)) & 0xE)), 13);
+
+	KIi1[i] = C[(i + 4) & 0x7];
+	KIi2[i] = C[(i + 3) & 0x7];
+	KIi3[i] = C[(i + 7) & 0x7];
+    }
+}
+
+void
+_a5_3_kgcore_gsm(uint8_t CA, uint8_t cb, uint32_t cc, uint8_t cd, uint8_t *ck, uint8_t *co, uint16_t cl)
+{
+    uint16_t KLi1[8], KLi2[8], KOi1[8], KOi2[8], KOi3[8], KIi1[8], KIi2[8], KIi3[8], i;
+    uint64_t A = ((uint64_t)cc) << 32, BLK = 0, _ca = ((uint64_t)CA << 16) ;
+    A |= _ca;
+    _ca = (uint64_t)((cb << 3) | (cd << 2)) << 24;
+    A |= _ca;
+    /* Register loading complete: see TR 55.919 8.2 and TS 55.216 3.2 */
+
+    uint8_t ck_km[16];
+    for (i = 0; i < 16; i++) ck_km[i] = ck[i] ^ 0x55; /* Modified key established */
+
+    /* preliminary round with modified key */
+    _a5_3_key_expand(ck_km, KLi1, KLi2, KOi1, KOi2, KOi3, KIi1, KIi2, KIi3);
+    A = _a5_3_kasumi(A, KLi1, KLi2, KOi1, KOi2, KOi3, KIi1, KIi2, KIi3);
+
+    /* Run Kasumi in OFB to obtain enough data for gamma. */
+    _a5_3_key_expand(ck, KLi1, KLi2, KOi1, KOi2, KOi3, KIi1, KIi2, KIi3);
+    for (i = 0; i < cl / 64 + 1; i++) /* i is a block counter */
+    {
+	BLK = _a5_3_kasumi(A ^ i ^ BLK, KLi1, KLi2, KOi1, KOi2, KOi3, KIi1, KIi2, KIi3);
+	osmo_64pack2pbit(BLK, co + (i * 8));
+    }
+}
+
+/*! \brief Generate a GSM A5/3 cipher stream
+ *  \param[in] key 8 byte array for the key (as received from the SIM)
+ *  \param[in] fn Frame number
+ *  \param[out] dl Pointer to array of ubits to return Downlink cipher stream
+ *  \param[out] ul Pointer to array of ubits to return Uplink cipher stream
+ *
+ * Either (or both) of dl/ul should be NULL if not needed.
+ *
+ * Implementation based on specifications from 3GPP TS 55.216, 3GPP TR 55.919 and ETSI TS 135 202
+ * with slight simplifications (CE hardcoded to 0).
+ */
+void
+osmo_a5_3(const uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
+{
+    /* internal function require 128 bit key so we expand by concatenating supplied 64 bit key */
+    uint8_t i, ck[16], gamma[32];
+    memcpy(ck, key, 8);
+    memcpy(ck + 8, key, 8);
+    uint32_t fn_count = osmo_a5_fn_count(fn); /* Frame count load */
+    if (dl) {
+	_a5_3_kgcore_gsm(0xF, 0, fn_count, 0, ck, gamma, 114);
+	osmo_pbit2ubit(dl, gamma, 114);
+    }
+    if (ul) {
+	_a5_3_kgcore_gsm(0xF, 0, fn_count, 0, ck, gamma, 228);
+	uint8_t uplink[15];
+	for(i = 0; i < 15; i++) uplink[i] = (gamma[i + 14] << 2) + (gamma[i + 15] >> 6);
+	osmo_pbit2ubit(ul, uplink, 114);
+    }
+}
+
 /*! @} */
-- 
1.7.10.4


--------------080507080909000101000702--




More information about the baseband-devel mailing list