src/gsm/a5.c

   1 /*
   2  * a5.c
   3  *
   4  * Full reimplementation of A5/1,2 (split and threadsafe)
   5  *
   6  * The logic behind the algorithm is taken from "A pedagogical implementation
   7  * of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms." by
   8  * Marc Briceno, Ian Goldberg, and David Wagner.
   9  *
  10  * Copyright (C) 2011  Sylvain Munaut <tnt@246tNt.com>
  11  *
  12  * All Rights Reserved
  13  *
  14  * This program is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * This program is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License along
  25  * with this program; if not, write to the Free Software Foundation, Inc.,
  26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  27  */
  28
  29 #include <string.h>
  30
  31 #include <osmocom/gsm/a5.h>
  32
  33 void
  34 osmo_a5(int n, uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
  35 {
  36         switch (n)
  37         {
  38         case 0:
  39                 if (dl)
  40                         memset(dl, 0x00, 114);
  41                 if (ul)
  42                         memset(ul, 0x00, 114);
  43                 break;
  44
  45         case 1:
  46                 osmo_a5_1(key, fn, dl, ul);
  47                 break;
  48
  49         case 2:
  50                 osmo_a5_2(key, fn, dl, ul);
  51                 break;
  52
  53         default:
  54                 /* a5/[3..7] not supported here/yet */
  55                 break;
  56         }
  57 }
  58
  59
  60 /* ------------------------------------------------------------------------ */
  61 /* A5/1&2 common stuff                                                                     */
  62 /* ------------------------------------------------------------------------ */
  63
  64 #define A5_R1_LEN       19
  65 #define A5_R2_LEN       22
  66 #define A5_R3_LEN       23
  67 #define A5_R4_LEN       17      /* A5/2 only */
  68
  69 #define A5_R1_MASK      ((1<<A5_R1_LEN)-1)
  70 #define A5_R2_MASK      ((1<<A5_R2_LEN)-1)
  71 #define A5_R3_MASK      ((1<<A5_R3_LEN)-1)
  72 #define A5_R4_MASK      ((1<<A5_R4_LEN)-1)
  73
  74 #define A5_R1_TAPS      0x072000 /* x^19 + x^5 + x^2 + x + 1 */
  75 #define A5_R2_TAPS      0x300000 /* x^22 + x + 1 */
  76 #define A5_R3_TAPS      0x700080 /* x^23 + x^15 + x^2 + x + 1 */
  77 #define A5_R4_TAPS      0x010800 /* x^17 + x^5 + 1 */
  78
  79 static inline uint32_t
  80 _a5_12_parity(uint32_t x)
  81 {
  82         x ^= x >> 16;
  83         x ^= x >> 8;
  84         x ^= x >> 4;
  85         x ^= x >> 2;
  86         x ^= x >> 1;
  87         return x & 1;
  88 }
  89
  90 static inline uint32_t
  91 _a5_12_majority(uint32_t v1, uint32_t v2, uint32_t v3)
  92 {
  93         return (!!v1 + !!v2 + !!v3) >= 2;
  94 }
  95
  96 static inline uint32_t
  97 _a5_12_clock(uint32_t r, uint32_t mask, uint32_t taps)
  98 {
  99         return ((r << 1) & mask) | _a5_12_parity(r & taps);
 100 }
 101
 102
 103 /* ------------------------------------------------------------------------ */
 104 /* A5/1                                                                     */
 105 /* ------------------------------------------------------------------------ */
 106
 107 #define A51_R1_CLKBIT   0x000100
 108 #define A51_R2_CLKBIT   0x000400
 109 #define A51_R3_CLKBIT   0x000400
 110
 111 static inline void
 112 _a5_1_clock(uint32_t r[], int force)
 113 {
 114         int cb[3], maj;
 115
 116         cb[0] = !!(r[0] & A51_R1_CLKBIT);
 117         cb[1] = !!(r[1] & A51_R2_CLKBIT);
 118         cb[2] = !!(r[2] & A51_R3_CLKBIT);
 119
 120         maj = _a5_12_majority(cb[0], cb[1], cb[2]);
 121
 122         if (force || (maj == cb[0]))
 123                 r[0] = _a5_12_clock(r[0], A5_R1_MASK, A5_R1_TAPS);
 124
 125         if (force || (maj == cb[1]))
 126                 r[1] = _a5_12_clock(r[1], A5_R2_MASK, A5_R2_TAPS);
 127
 128         if (force || (maj == cb[2]))
 129                 r[2] = _a5_12_clock(r[2], A5_R3_MASK, A5_R3_TAPS);
 130 }
 131
 132 static inline uint8_t
 133 _a5_1_get_output(uint32_t r[])
 134 {
 135         return  (r[0] >> (A5_R1_LEN-1)) ^
 136                 (r[1] >> (A5_R2_LEN-1)) ^
 137                 (r[2] >> (A5_R3_LEN-1));
 138 }
 139
 140 void
 141 osmo_a5_1(uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
 142 {
 143         uint32_t r[3] = {0, 0, 0};
 144         uint32_t fn_count;
 145         uint32_t b;
 146         int i;
 147
 148         /* Key load */
 149         for (i=0; i<64; i++)
 150         {
 151                 b = ( key[7 - (i>>3)] >> (i&7) ) & 1;
 152
 153                 _a5_1_clock(r, 1);
 154
 155                 r[0] ^= b;
 156                 r[1] ^= b;
 157                 r[2] ^= b;
 158         }
 159
 160         /* Frame count load */
 161         fn_count = osmo_a5_fn_count(fn);
 162
 163         for (i=0; i<22; i++)
 164         {
 165                 b = (fn_count >> i) & 1;
 166
 167                 _a5_1_clock(r, 1);
 168
 169                 r[0] ^= b;
 170                 r[1] ^= b;
 171                 r[2] ^= b;
 172         }
 173
 174         /* Mix */
 175         for (i=0; i<100; i++)
 176         {
 177                 _a5_1_clock(r, 0);
 178         }
 179
 180         /* Output */
 181         for (i=0; i<114; i++) {
 182                 _a5_1_clock(r, 0);
 183                 if (dl)
 184                         dl[i] = _a5_1_get_output(r);
 185         }
 186
 187         for (i=0; i<114; i++) {
 188                 _a5_1_clock(r, 0);
 189                 if (ul)
 190                         ul[i] = _a5_1_get_output(r);
 191         }
 192 }
 193
 194
 195 /* ------------------------------------------------------------------------ */
 196 /* A5/2                                                                     */
 197 /* ------------------------------------------------------------------------ */
 198
 199 #define A52_R4_CLKBIT0  0x000400
 200 #define A52_R4_CLKBIT1  0x000008
 201 #define A52_R4_CLKBIT2  0x000080
 202
 203 static inline void
 204 _a5_2_clock(uint32_t r[], int force)
 205 {
 206         int cb[3], maj;
 207
 208         cb[0] = !!(r[3] & A52_R4_CLKBIT0);
 209         cb[1] = !!(r[3] & A52_R4_CLKBIT1);
 210         cb[2] = !!(r[3] & A52_R4_CLKBIT2);
 211
 212         maj = (cb[0] + cb[1] + cb[2]) >= 2;
 213
 214         if (force || (maj == cb[0]))
 215                 r[0] = _a5_12_clock(r[0], A5_R1_MASK, A5_R1_TAPS);
 216
 217         if (force || (maj == cb[1]))
 218                 r[1] = _a5_12_clock(r[1], A5_R2_MASK, A5_R2_TAPS);
 219
 220         if (force || (maj == cb[2]))
 221                 r[2] = _a5_12_clock(r[2], A5_R3_MASK, A5_R3_TAPS);
 222
 223         r[3] = _a5_12_clock(r[3], A5_R4_MASK, A5_R4_TAPS);
 224 }
 225
 226 static inline uint8_t
 227 _a5_2_get_output(uint32_t r[], uint8_t *db)
 228 {
 229         uint8_t cb, tb;
 230
 231         tb =    (r[0] >> (A5_R1_LEN-1)) ^
 232                 (r[1] >> (A5_R2_LEN-1)) ^
 233                 (r[2] >> (A5_R3_LEN-1));
 234
 235         cb = *db;
 236
 237         *db = ( tb ^
 238                 _a5_12_majority( r[0] & 0x08000, ~r[0] & 0x04000,  r[0] & 0x1000) ^
 239                 _a5_12_majority(~r[1] & 0x10000,  r[1] & 0x02000,  r[1] & 0x0200) ^
 240                 _a5_12_majority( r[2] & 0x40000,  r[2] & 0x10000, ~r[2] & 0x2000)
 241         );
 242
 243         return cb;
 244 }
 245
 246 void
 247 osmo_a5_2(uint8_t *key, uint32_t fn, ubit_t *dl, ubit_t *ul)
 248 {
 249         uint32_t r[4] = {0, 0, 0, 0};
 250         uint32_t fn_count;
 251         uint32_t b;
 252         uint8_t db = 0, o;
 253         int i;
 254
 255         /* Key load */
 256         for (i=0; i<64; i++)
 257         {
 258                 b = ( key[7 - (i>>3)] >> (i&7) ) & 1;
 259
 260                 _a5_2_clock(r, 1);
 261
 262                 r[0] ^= b;
 263                 r[1] ^= b;
 264                 r[2] ^= b;
 265                 r[3] ^= b;
 266         }
 267
 268         /* Frame count load */
 269         fn_count = osmo_a5_fn_count(fn);
 270
 271         for (i=0; i<22; i++)
 272         {
 273                 b = (fn_count >> i) & 1;
 274
 275                 _a5_2_clock(r, 1);
 276
 277                 r[0] ^= b;
 278                 r[1] ^= b;
 279                 r[2] ^= b;
 280                 r[3] ^= b;
 281         }
 282
 283         r[0] |= 1 << 15;
 284         r[1] |= 1 << 16;
 285         r[2] |= 1 << 18;
 286         r[3] |= 1 << 10;
 287
 288         /* Mix */
 289         for (i=0; i<100; i++)
 290         {
 291                 _a5_2_clock(r, 0);
 292         }
 293
 294         _a5_2_get_output(r, &db);
 295
 296
 297         /* Output */
 298         for (i=0; i<114; i++) {
 299                 _a5_2_clock(r, 0);
 300                 o = _a5_2_get_output(r, &db);
 301                 if (dl)
 302                         dl[i] = o;
 303         }
 304
 305         for (i=0; i<114; i++) {
 306                 _a5_2_clock(r, 0);
 307                 o = _a5_2_get_output(r, &db);
 308                 if (ul)
 309                         ul[i] = o;
 310         }
 311 }