Last active
August 29, 2015 14:00
-
-
Save defuse/11273034 to your computer and use it in GitHub Desktop.
Constant Time Array Lookup?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // WARNING! This code is untested and experimental. DO NOT USE IT. | |
| // NOTE: If I knew of a way to do the "shift and OR" thing reliably with unsigned ints, the code could be simplified a lot. | |
| // Will always be compiled with -std=c99 | |
| // Returns UINT32_MAX if a == b, 0 otherwise. | |
| uint32_t invariant_time_integer_compare(uint32_t a, uint32_t b) | |
| { | |
| /* z will be zero if and only if a == b. */ | |
| uint32_t z = a ^ b; | |
| /* OR every bit into the LSb of z so that the LSb is zero iff a == b. */ | |
| z |= z >> 16; | |
| z |= z >> 8; | |
| z |= z >> 4; | |
| z |= z >> 2; | |
| z |= z >> 1; | |
| /* z will be 1 if a != b, or 0 if a == b. */ | |
| z = z & 1; | |
| /* Flip the LSB, so that z is 1 if a == b and z is 0 if a != b */ | |
| z = 1u - z; | |
| /* If a != b, z is 0 and the result of the subtraction is 0. */ | |
| /* If a == b, z is 1 and the result of the subtraction is UINT32_MAX. */ | |
| z = 0u - z; | |
| /* What is the type of 0u? It's the first unsigned type it fits in, | |
| * beginning with unsigned int, so it will be unsigned int. | |
| * | |
| * Now there are three possibilities: | |
| * | |
| * 1. unsigned int is wider than uint32_t: | |
| * | |
| * In this case, z gets converted to unsigned int, and the subtraction | |
| * results in UINT_MAX, which is by assumption greater than UINT32_MAX, | |
| * so the result will get truncated to UINT32_MAX. | |
| * | |
| * 2. uint32_t is the same type as unsigned int: | |
| * | |
| * They are the same type, so there's no conversion, and the result is | |
| * UINT_MAX, which is UINT32_MAX. | |
| * | |
| * 3. uint32_t is wider than unsigned int: | |
| * | |
| * 0u gets promoted to a zero uint32_t, and the result is UINT32_MAX. | |
| * | |
| */ | |
| return z; | |
| } | |
| char invariant_time_lookup(const char *array, uint32_t length, uint32_t index) | |
| { | |
| char result = 0; | |
| for (uint32_t i = 0; i < length; i++) { | |
| /* If the index is wrong, mask will be zero, and we'll OR zero into the | |
| * result (which has no effect). If the index is right, the mask will be | |
| * all 1 bits, so we'll OR the contents of the array into the result. */ | |
| uint32_t mask = invariant_time_integer_compare(i, index); | |
| result |= array[index] & mask; | |
| // XXX: I'm not so sure about this... array[index] is signed, and result is signed... | |
| } | |
| return result; | |
| } | |
| /* | |
| 0000000000400c67 <invariant_time_integer_compare>: | |
| 400c67: 55 push rbp | |
| 400c68: 48 89 e5 mov rbp,rsp | |
| 400c6b: 89 7d ec mov DWORD PTR [rbp-0x14],edi | |
| 400c6e: 89 75 e8 mov DWORD PTR [rbp-0x18],esi | |
| 400c71: 8b 45 e8 mov eax,DWORD PTR [rbp-0x18] | |
| 400c74: 8b 55 ec mov edx,DWORD PTR [rbp-0x14] | |
| 400c77: 31 d0 xor eax,edx | |
| 400c79: 89 45 fc mov DWORD PTR [rbp-0x4],eax | |
| 400c7c: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] | |
| 400c7f: c1 e8 10 shr eax,0x10 | |
| 400c82: 09 45 fc or DWORD PTR [rbp-0x4],eax | |
| 400c85: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] | |
| 400c88: c1 e8 08 shr eax,0x8 | |
| 400c8b: 09 45 fc or DWORD PTR [rbp-0x4],eax | |
| 400c8e: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] | |
| 400c91: c1 e8 04 shr eax,0x4 | |
| 400c94: 09 45 fc or DWORD PTR [rbp-0x4],eax | |
| 400c97: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] | |
| 400c9a: c1 e8 02 shr eax,0x2 | |
| 400c9d: 09 45 fc or DWORD PTR [rbp-0x4],eax | |
| 400ca0: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] | |
| 400ca3: d1 e8 shr eax,1 | |
| 400ca5: 09 45 fc or DWORD PTR [rbp-0x4],eax | |
| 400ca8: 83 65 fc 01 and DWORD PTR [rbp-0x4],0x1 | |
| 400cac: b8 01 00 00 00 mov eax,0x1 | |
| 400cb1: 2b 45 fc sub eax,DWORD PTR [rbp-0x4] | |
| 400cb4: 89 45 fc mov DWORD PTR [rbp-0x4],eax | |
| 400cb7: f7 5d fc neg DWORD PTR [rbp-0x4] | |
| 400cba: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] | |
| 400cbd: 5d pop rbp | |
| 400cbe: c3 ret | |
| 0000000000400cbf <invariant_time_lookup>: | |
| 400cbf: 55 push rbp | |
| 400cc0: 48 89 e5 mov rbp,rsp | |
| 400cc3: 48 83 ec 20 sub rsp,0x20 | |
| 400cc7: 48 89 7d e8 mov QWORD PTR [rbp-0x18],rdi | |
| 400ccb: 89 75 e4 mov DWORD PTR [rbp-0x1c],esi | |
| 400cce: 89 55 e0 mov DWORD PTR [rbp-0x20],edx | |
| 400cd1: c6 45 ff 00 mov BYTE PTR [rbp-0x1],0x0 | |
| 400cd5: c7 45 f8 00 00 00 00 mov DWORD PTR [rbp-0x8],0x0 | |
| 400cdc: eb 33 jmp 400d11 <invariant_time_lookup+0x52> | |
| 400cde: 8b 55 e0 mov edx,DWORD PTR [rbp-0x20] | |
| 400ce1: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8] | |
| 400ce4: 89 d6 mov esi,edx | |
| 400ce6: 89 c7 mov edi,eax | |
| 400ce8: e8 7a ff ff ff call 400c67 <invariant_time_integer_compare> | |
| 400ced: 89 45 f4 mov DWORD PTR [rbp-0xc],eax | |
| 400cf0: 8b 55 e0 mov edx,DWORD PTR [rbp-0x20] | |
| 400cf3: 48 8b 45 e8 mov rax,QWORD PTR [rbp-0x18] | |
| 400cf7: 48 01 d0 add rax,rdx | |
| 400cfa: 0f b6 00 movzx eax,BYTE PTR [rax] | |
| 400cfd: 89 c2 mov edx,eax | |
| 400cff: 8b 45 f4 mov eax,DWORD PTR [rbp-0xc] | |
| 400d02: 21 c2 and edx,eax | |
| 400d04: 0f b6 45 ff movzx eax,BYTE PTR [rbp-0x1] | |
| 400d08: 09 d0 or eax,edx | |
| 400d0a: 88 45 ff mov BYTE PTR [rbp-0x1],al | |
| 400d0d: 83 45 f8 01 add DWORD PTR [rbp-0x8],0x1 | |
| 400d11: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8] | |
| 400d14: 3b 45 e4 cmp eax,DWORD PTR [rbp-0x1c] | |
| 400d17: 72 c5 jb 400cde <invariant_time_lookup+0x1f> | |
| 400d19: 0f b6 45 ff movzx eax,BYTE PTR [rbp-0x1] | |
| 400d1d: c9 leave | |
| 400d1e: c3 ret | |
| */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment