[166] | 1 | #include <iostream> |
---|
| 2 | #include <iomanip> |
---|
| 3 | #include <stdlib.h> |
---|
| 4 | #include <string.h> |
---|
| 5 | |
---|
| 6 | // which bits of a 32bit variable actually play a role |
---|
| 7 | #define R1MASK 0x07FFFF /* 19 bits, numbered 0..18 */ |
---|
| 8 | #define R2MASK 0x3FFFFF /* 22 bits, numbered 0..21 */ |
---|
| 9 | #define R3MASK 0x7FFFFF /* 23 bits, numbered 0..22 */ |
---|
| 10 | |
---|
| 11 | struct simple { |
---|
| 12 | // reverse the order of bits in a register. |
---|
| 13 | // the MSB becomes the new LSB and vice versa |
---|
| 14 | template <int N, typename T> |
---|
| 15 | static T d_register_reverse_bits(T r) { |
---|
| 16 | T res = 0; |
---|
| 17 | for (int i = 0; i < N; i++) { |
---|
| 18 | if (r & 1ULL << i) { |
---|
| 19 | res |= 1ULL << N - 1 - i; |
---|
| 20 | } |
---|
| 21 | } |
---|
| 22 | return res; |
---|
| 23 | } |
---|
| 24 | |
---|
| 25 | // majority bit |
---|
| 26 | /* Middle bit of each of the three shift registers, for clock control */ |
---|
| 27 | static const uint32_t R1MID = 0x000100; /* bit 8 */ |
---|
| 28 | static const uint32_t R2MID = 0x000400; /* bit 10 */ |
---|
| 29 | static const uint32_t R3MID = 0x000400; /* bit 10 */ |
---|
| 30 | |
---|
| 31 | /* Feedback taps, for clocking the shift registers. */ |
---|
| 32 | static const uint32_t R1TAPS = 0x072000; /* bits 18,17,16,13 */ |
---|
| 33 | static const uint32_t R2TAPS = 0x300000; /* bits 21,20 */ |
---|
| 34 | static const uint32_t R3TAPS = 0x700080; /* bits 22,21,20,7 */ |
---|
| 35 | |
---|
| 36 | /* Output taps, for output generation */ |
---|
| 37 | static const uint32_t R1OUT = 0x040000; /* bit 18 (the high bit) */ |
---|
| 38 | static const uint32_t R2OUT = 0x200000; /* bit 21 (the high bit) */ |
---|
| 39 | static const uint32_t R3OUT = 0x400000; /* bit 22 (the high bit) */ |
---|
| 40 | |
---|
| 41 | static int parity32(uint32_t x) { |
---|
| 42 | x ^= x>>16; |
---|
| 43 | x ^= x>>8; |
---|
| 44 | x ^= x>>4; |
---|
| 45 | x ^= x>>2; |
---|
| 46 | x ^= x>>1; |
---|
| 47 | return x&1; |
---|
| 48 | } |
---|
| 49 | static int majority(uint32_t R1, uint32_t R2, uint32_t R3) { |
---|
| 50 | int sum; |
---|
| 51 | sum = ((R1&R1MID) >> 8) + ((R2&R2MID) >> 10) + ((R3&R3MID) >> 10); |
---|
| 52 | if (sum >= 2) |
---|
| 53 | return 1; |
---|
| 54 | else |
---|
| 55 | return 0; |
---|
| 56 | } |
---|
| 57 | |
---|
| 58 | static int getbit(uint32_t R1, uint32_t R2, uint32_t R3) { |
---|
| 59 | return ((R1&R1OUT) >> 18) ^ ((R2&R2OUT) >> 21) ^ ((R3&R3OUT) >> 22); |
---|
| 60 | } |
---|
| 61 | |
---|
| 62 | static uint32_t clockone(uint32_t reg, uint32_t mask, uint32_t taps) { |
---|
| 63 | uint32_t t = reg & taps; |
---|
| 64 | reg = (reg << 1) & mask; |
---|
| 65 | reg |= parity32(t); |
---|
| 66 | return reg; |
---|
| 67 | } |
---|
| 68 | |
---|
| 69 | // calculate the new round function value |
---|
| 70 | // based on a 64bit xilinx PRNG |
---|
| 71 | // output of the shift operations is discarded. |
---|
| 72 | static uint64_t advance_rf_lfsr_buggy(uint64_t v) { |
---|
| 73 | for (int i = 0; i < 64; i++) { |
---|
| 74 | uint64_t fb = ( |
---|
| 75 | ~( |
---|
| 76 | ((v >> 63) & 1) ^ |
---|
| 77 | ((v >> 62) & 1) ^ |
---|
| 78 | ((v >> 60) & 1) ^ |
---|
| 79 | ((v >> 59) & 1) |
---|
| 80 | ) |
---|
| 81 | ) & 1; |
---|
| 82 | v >>= 1; |
---|
| 83 | v |= fb << 63; |
---|
| 84 | } |
---|
| 85 | return v; |
---|
| 86 | } |
---|
| 87 | |
---|
| 88 | // calculate the new round function value |
---|
| 89 | // based on a 64bit xilinx PRNG |
---|
| 90 | // output of the shift operations is discarded. |
---|
| 91 | static uint64_t advance_rf_lfsr(uint64_t v) { |
---|
| 92 | for (int i = 0; i < 64; i++) { |
---|
| 93 | uint64_t fb = ( |
---|
| 94 | ~( |
---|
| 95 | ((v >> 63) & 1) ^ |
---|
| 96 | ((v >> 62) & 1) ^ |
---|
| 97 | ((v >> 60) & 1) ^ |
---|
| 98 | ((v >> 59) & 1) |
---|
| 99 | ) |
---|
| 100 | ) & 1; |
---|
| 101 | v <<= 1; |
---|
| 102 | v |= fb; |
---|
| 103 | } |
---|
| 104 | return v; |
---|
| 105 | } |
---|
| 106 | |
---|
| 107 | // advance the state for the simple increment round function generator |
---|
| 108 | static uint64_t advance_rf_inc(uint64_t v) { |
---|
| 109 | return v + 1; |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | struct implementation { |
---|
| 113 | // input: 64bits of start value |
---|
| 114 | // index: ignore |
---|
| 115 | // nruns: max chain length |
---|
| 116 | // dpbits: number of bits of a distringuished point between round functions |
---|
| 117 | // rounds: number of round functions |
---|
| 118 | static uint64_t run(uint64_t input, uint32_t index, int nruns, int dpbits, int rounds, int rfgen_advance, bool buggy) { |
---|
| 119 | uint64_t result = input; |
---|
| 120 | uint64_t rfstate = 0; |
---|
| 121 | int i; |
---|
| 122 | int rfapplycount = 0; |
---|
| 123 | |
---|
| 124 | for (int i = 0; i < rfgen_advance; i++) { |
---|
| 125 | rfstate = advance_rf_lfsr(rfstate); |
---|
| 126 | std::cerr << "0x" << std::hex << std::setfill('0') << std::setw(16) << rfstate << "\n"; |
---|
| 127 | } |
---|
| 128 | // std::cerr << std::hex << rfstate << "\n"; |
---|
| 129 | |
---|
| 130 | // main loop: for each chain column |
---|
| 131 | |
---|
| 132 | for (int run = nruns; run > 0; --run) { |
---|
| 133 | // apply the round function |
---|
| 134 | result ^= rfstate; |
---|
| 135 | |
---|
| 136 | // test round function condition |
---|
| 137 | if ((result & (1 << dpbits) - 1) == 0) { |
---|
| 138 | // advance round function |
---|
| 139 | if (buggy) { |
---|
| 140 | rfstate = advance_rf_lfsr_buggy(rfstate); |
---|
| 141 | } else { |
---|
| 142 | rfstate = advance_rf_lfsr(rfstate); |
---|
| 143 | } |
---|
| 144 | rfapplycount++; |
---|
| 145 | } |
---|
| 146 | |
---|
| 147 | // check chain end condition |
---|
| 148 | if (rfapplycount == rounds) { |
---|
| 149 | std::cerr << "round function state: " << rfapplycount << " after " << nruns - run << " rounds\n"; |
---|
| 150 | return result; |
---|
| 151 | } |
---|
| 152 | |
---|
| 153 | // apply A5/1 to result, store in result |
---|
| 154 | // goes on till the end of the main loop |
---|
| 155 | |
---|
| 156 | // fill the registers with the keystream from the last round |
---|
| 157 | uint32_t R3 = result & R3MASK; |
---|
| 158 | uint32_t R2 = result >> 23 & R2MASK; |
---|
| 159 | uint32_t R1 = result >> 23 + 22 & R1MASK; |
---|
| 160 | |
---|
| 161 | // reverse the bit order to account for |
---|
| 162 | // the fpga and cuda optimizations |
---|
| 163 | R1 = d_register_reverse_bits<19>(R1); |
---|
| 164 | R2 = d_register_reverse_bits<22>(R2); |
---|
| 165 | R3 = d_register_reverse_bits<23>(R3); |
---|
| 166 | |
---|
| 167 | // produce result from R1,R2,R3 |
---|
| 168 | result = uint64_t(getbit(R1, R2, R3)) << 63; |
---|
| 169 | for(i=1;i<64;i++) { |
---|
| 170 | int maj = majority(R1, R2, R3); |
---|
| 171 | uint32_t T1 = clockone(R1, R1MASK, R1TAPS); |
---|
| 172 | uint32_t T2 = clockone(R2, R2MASK, R2TAPS); |
---|
| 173 | uint32_t T3 = clockone(R3, R3MASK, R3TAPS); |
---|
| 174 | |
---|
| 175 | if (((R1&R1MID)!=0) == maj) |
---|
| 176 | R1 = T1; |
---|
| 177 | if (((R2&R2MID)!=0) == maj) |
---|
| 178 | R2 = T2; |
---|
| 179 | if (((R3&R3MID)!=0) == maj) |
---|
| 180 | R3 = T3; |
---|
| 181 | |
---|
| 182 | result = result >> 1 | uint64_t(getbit(R1, R2, R3)) << 63; |
---|
| 183 | } |
---|
| 184 | // std::cout << std::hex << result << "\n"; |
---|
| 185 | } |
---|
| 186 | std::cerr << "round function state: " << rfapplycount << "\n"; |
---|
| 187 | return result; |
---|
| 188 | } |
---|
| 189 | }; |
---|
| 190 | }; |
---|
| 191 | |
---|
| 192 | int main(int argc, char ** argv) { |
---|
| 193 | uint64_t r1 = 123, r2 = 123, r3 = 123; |
---|
| 194 | uint64_t input; |
---|
| 195 | sscanf(argv[1], "%llX", &input); |
---|
| 196 | bool buggy = false; |
---|
| 197 | if (argc > 6 && strcmp(argv[6], "buggy") == 0) { |
---|
| 198 | buggy = true; |
---|
| 199 | } |
---|
| 200 | |
---|
| 201 | uint64_t startval = input; |
---|
| 202 | std::cout << "0x" << std::hex |
---|
| 203 | << std::setfill('0') << std::setw(16) |
---|
| 204 | << startval |
---|
| 205 | << " -> 0x" |
---|
| 206 | << std::setfill('0') << std::setw(16) |
---|
| 207 | << simple::implementation::run(startval, |
---|
| 208 | 0, |
---|
| 209 | atoi(argv[2]), |
---|
| 210 | atoi(argv[3]), |
---|
| 211 | atoi(argv[4]), |
---|
| 212 | atoi(argv[5]), buggy) << "\n"; |
---|
| 213 | } |
---|