Using home made crypto for a non-cryptographic problem
Stockholm C++ 20200123
"Don't make your own crypto"
Dont TRUST your own crypto.
Don't use home made crypto for cryptographic purposes
unless you write malware serious motivation01: int 02: count_set_bits(unsigned int v) 03: { 04: const int S[] = { 1, 2, 4, 8, 16 }; 05: const int B[] = { 0x55555555, 06: 0x33333333, 07: 0x0F0F0F0F, 08: 0x00FF00FF, 09: 0x0000FFFF }; 10: 11: unsigned int c; 12: c = v - ((v >> 1) & B[0]); 13: c = ((c >> S[1]) & B[1]) + (c & B[1]); 14: c = ((c >> S[2]) + c) & B[2]; 15: c = ((c >> S[3]) + c) & B[3]; 16: c = ((c >> S[4]) + c) & B[4]; 17: return c; 18: } 19:credit: https://graphics.stanford.edu/~seander/bithacks.html
1: int 2: main() 3: { 4: assert(count_set_bits(0) == 0); 5: assert(count_set_bits(1) == 1); 6: assert(count_set_bits(1 << 10) == 1); 7: assert(count_set_bits(0xF) == 4); 8: } 9:
1: void 2: exhaustive_test() 3: { 4: unsigned int = 0; 5: do { 6: // ....... 7: } while (++i); 8: } 9:
01: int 02: main() 03: { 04: unsigned int i = 0; 05: do { 06: auto actual = count_set_bits(i); 07: auto expected = __builtin_popcount(i); 08: assert(actual == expected); 09: } while (++i); 10: } 11:Demo
01: int 02: main() 03: { 04: unsigned int i = 0; 05: const unsigned int flip = std::random_device{}(); 06: do { 07: const unsigned int j = i ^ flip; 08: auto actual = count_set_bits(j); 09: auto expected = __builtin_popcount(j); 10: assert(actual == expected); 11: } while (++i); 12: } 13:Xor Demo
01: #include <random> 02: 03: int 04: main() 05: { 06: std::mt19937_64 gen; 07: gen.seed(42); 08: 09: for (;;) { 10: auto x = gen(); 11: auto actual = count_set_bits(x); 12: auto expected = __builtin_popcountl(x); 13: assert(actual == expected); 14: } 15: } 16:Random Demo
Only beaten by fuzzing tricks
M possible inputs ($M=2^{32}$ in the example)
We pick $k$ testcases, and get $Y$ distinct inputs
$Y$ is stochastic
1: std::vector<unsigned int> v(M); 2: std::iota(begin(v), end(v), 0); 3:Shuffle the order:
1: std::minstd_rand gen(42); 2: std::shuffle(begin(v), end(v), gen); 3:Use the data:
1: for (unsigned int i : v) { 2: auto actual = count_set_bits(i); 3: auto expected = __builtin_popcount(i); 4: assert(actual == expected); 5: } 6:
01: int 02: main(int argc, char* argv[]) 03: { 04: assert(argc > 1); 05: const std::size_t M = std::stoull(argv[1]); 06: 07: std::vector<unsigned int> v(M); 08: std::iota(begin(v), end(v), 0); 09: 10: std::minstd_rand gen(42); 11: std::shuffle(begin(v), end(v), gen); 12: 13: for (unsigned int i : v) { 14: auto actual = count_set_bits(i); 15: auto expected = __builtin_popcount(i); 16: assert(actual == expected); 17: } 18: } 19:
Method | cycles/sample |
---|---|
sequential | 4 |
xor | 5 |
random | 42 |
shuffle | 900 |
Note: random is the best of mt19937_64, mt19937 and minstd_rand
A crypto building block
01: struct BlockCipher32 02: { 03: unsigned encrypt(unsigned x) const; 04: unsigned decrypt(unsigned x) const; 05: 06: private: 07: SecretKey m_key; 08: }; 09: 10: int 11: main() 12: { 13: BlockCipher32 cipher; 14: unsigned int i = 0; 15: do { 16: f(cipher.encrypt(i)); 17: } while (++i); 18: } 19:
1: // example - 32 bit block cipher 2: using half = std::uint16_t; 3: 4: half 5: roundFunction(half x, Key k); 6:
01: struct BlockCipher32 02: { 03: uint32_t encrypt(uint32_t plain) 04: { 05: uint16_t left = plain >> 16; 06: uint16_t right = plain & 0xFFFF; 07: 08: for (int i = 0; i < rounds; ++i) { 09: uint16_t tmp = roundFunc(right, m_keys[i]); 10: left ^= tmp; 11: std::swap(left, right); 12: } 13: return (left << 16) | right; 14: } 15: 16: private: 17: static const int Nrounds = 10; 18: uint16_t roundFunc(uint16_t x, uint16_t key) 19: { 20: return (x ^ key) * 35; 21: } 22: std::array<uint16_t, Nrounds> m_keys; 23: } 24:
01: struct BlockCipher24 02: { 03: uint32_t encrypt(uint32_t plain) 04: { 05: uint16_t left = plain >> 12; 06: const uint16_t mask = 0xFFF; 07: uint16_t right = plain & mask; 08: 09: for (int i = 0; i < rounds; ++i) { 10: uint16_t tmp = roundFunc(right, m_keys[i]); 11: left ^= (tmp & mask); 12: std::swap(left, right); 13: } 14: return (left << 12) | right; 15: } 16: 17: private: 18: static const int Nrounds = 10; 19: uint16_t roundFunc(uint16_t x, uint16_t key) 20: { 21: return (x ^ key) * 35; 22: } 23: std::array<uint16_t, Nrounds> m_keys; 24: } 25:
01: template<typename Derived, 02: typename EncryptTypeFull, 03: typename EncryptTypeHalf> 04: class GenericFeistel 05: { 06: public: 07: EncryptTypeFull encrypt(EncryptTypeFull cleartext) 08: { 09: return commonEncryptAndDecrypt<Encrypt>(cleartext); 10: } 11: EncryptTypeFull decrypt(EncryptTypeFull ciphertext) 12: { 13: return commonEncryptAndDecrypt<Decrypt>(ciphertext); 14: } 15: 16: template<Direction direction> 17: EncryptTypeFull commonEncryptAndDecrypt( 18: EncryptTypeFull input); 19: 20: private: 21: const int m_Nbitshalf; 22: const EncryptTypeHalf m_mask; 23: }; 24:
01: template<Direction direction> 02: EncryptTypeFull 03: commonEncryptAndDecrypt(EncryptTypeFull input) 04: { 05: EncryptTypeHalf left = (input >> m_Nbitshalf) & m_mask; 06: EncryptTypeHalf right = input & m_mask; 07: int round; 08: for (int i = 0; i < rounds(); ++i) { 09: if constexpr (direction == Encrypt) 10: round = i; 11: else 12: round = rounds() - 1 - i; 13: EncryptTypeHalf Fresult = 14: This()->roundFunction(right, round); 15: left ^= Fresult; 16: left &= m_mask; 17: std::swap(left, right); 18: } 19: std::swap(left, right); 20: return (EncryptTypeFull{ left } << m_Nbitshalf) | right; 21: } 22:
01: class Dynamic32 02: : public GenericFeistel<Dynamic32, 03: std::uint32_t, 04: std::uint16_t> 05: { 06: public: 07: static constexpr int ROUNDS = 2; 08: using Base = GenericFeistel<Dynamic32, 09: std::uint32_t, 10: std::uint16_t>; 11: explicit Dynamic32(int Nbits) 12: : Base(Nbits){}; 13: 14: std::uint16_t roundFunction(const std::uint16_t x, 15: int round) const 16: { 17: return hashfnv1a(x) ^ m_key[round]; 18: } 19: 20: private: 21: std::array<std::uint16_t, ROUNDS> m_key; 22: }; 23:
algorithm fnv-1a is hash := FNV_offset_basis for each byte_of_data to be hashed do hash := hash XOR byte_of_data hash := hash × FNV_prime return hashExists for 32, 64, 128, 256, 512, 1024 bits
Method | cycles/sample |
---|---|
sequential | 4 |
xor | 5 |
fnv1a (truncated) | 10 |
fnv1a (proper) | 12.4 |
random | 42 |
shuffle | 900 |
1: std::uint16_t 2: roundFunction(const std::uint16_t x, int round) const 3: { 4: __m128i m = _mm_set1_epi16(x); 5: m = _mm_aesenc_si128(m, m_key); 6: return _mm_extract_epi16(m, 0); 7: } 8:
Method | cycles/sample |
---|---|
sequential | 4 |
xor | 5 |
AES intrinsic | 8.9 |
fnv1a (truncated) | 10 |
fnv1a (proper) | 12.4 |
random | 42 |
shuffle | 900 |
We have all the building blocks to iterate randomly now!
A range with M elements - not always a power of two
01: template<typename RandomAccessIterator, typename Callback> 02: void 03: random_for_each(RandomAccessIterator first, 04: RandomAccessIterator last, 05: Callback&& cb) 06: { 07: const auto M = std::distance(first, last); 08: const int N = ceil_log2(M); 09: if (M <= 32) { 10: Dynamic32 cipher(N); 11: unsigned generated = 0; 12: for (unsigned i = 0; generated < M; ++i) { 13: unsigned e = cipher.encrypt(i); 14: if (e >= M) { 15: continue; 16: } 17: ++generated; 18: cb(*(first + e)); 19: } 20: } else { 21: // .... use Dynamic64 etc 22: } 23: } 24: