Commit | Line | Data |
---|---|---|
d4bb7fde MW |
1 | /* -*-c-*- |
2 | * | |
3 | * Constant-time operations | |
4 | * | |
5 | * (c) 2013 Straylight/Edgeware | |
6 | */ | |
7 | ||
8 | /*----- Licensing notice --------------------------------------------------* | |
9 | * | |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software; you can redistribute it and/or modify | |
13 | * it under the terms of the GNU Library General Public License as | |
14 | * published by the Free Software Foundation; either version 2 of the | |
15 | * License, or (at your option) any later version. | |
16 | * | |
17 | * Catacomb is distributed in the hope that it will be useful, | |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | * GNU Library General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Library General Public | |
23 | * License along with Catacomb; if not, write to the Free | |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
28 | /*----- Header files ------------------------------------------------------*/ | |
29 | ||
30 | #include <mLib/bits.h> | |
31 | ||
32 | #include "ct.h" | |
33 | ||
34 | /*----- Main code ---------------------------------------------------------*/ | |
35 | ||
36 | #define MASK(a) (U32(~((a) - 1))) | |
37 | ||
38 | /* --- @ct_inteq@ --- * | |
39 | * | |
40 | * Arguments: @uint32 x, y@ = two 32-bit unsigned integers | |
41 | * | |
42 | * Returns: One if @x@ and @y@ are equal, zero if they differ. | |
43 | * | |
44 | * Use: Answers whether two integers are equal, in constant time. | |
45 | */ | |
46 | ||
47 | int ct_inteq(uint32 x, uint32 y) | |
48 | { | |
49 | uint32 a = U32(~(x ^ y)); | |
50 | ||
51 | a &= a >> 16; | |
52 | a &= a >> 8; | |
53 | a &= a >> 4; | |
54 | a &= a >> 2; | |
55 | a &= a >> 1; | |
56 | return (a & 1); | |
57 | } | |
58 | ||
59 | /* --- @ct_intle@ --- * | |
60 | * | |
61 | * Arguments: @uint32 x, y@ = two 32-bit unsigned integers | |
62 | * | |
c4377d0e | 63 | * Returns: One if %$x \le y$%, zero if @x@ is greater. |
d4bb7fde MW |
64 | * |
65 | * Use: Answers whether two integers are ordered, in constant time. | |
66 | */ | |
67 | ||
68 | int ct_intle(uint32 x, uint32 y) | |
69 | { | |
70 | /* --- This bit's a little fiddly --- * | |
71 | * | |
72 | * If the top bits of @x@ and @y@ are the same then %$x \le y$% if and only | |
73 | * if %$y - x$% has its top bit clear; otherwise, %$x \le y$% if and only | |
74 | * if the top bit of @x@ is clear and the top bit of @y@ is set. | |
75 | * | |
76 | * This assumes we can do subtraction in constant time, which seems like a | |
77 | * safe enough bet. | |
78 | */ | |
79 | ||
80 | uint32 xx = x >> 31, yy = y >> 31, zz = (y - x) >> 31; | |
81 | return ((~xx&yy) | (~(xx^yy)&~zz)) & 1; | |
82 | } | |
83 | ||
84 | /* --- @ct_pick@ --- * | |
85 | * | |
86 | * Arguments: @uint32 a@ = a switch, either zero or one | |
87 | * @uint32 x0, x1@ = two 32-bit unsigned integers | |
88 | * | |
89 | * Returns: @x0@ if @a@ is zero; @x1@ if @a@ is one. Other values of @a@ | |
90 | * will give you unhelpful results. | |
91 | * | |
92 | * Use: Picks one of two results according to a switch variable, in | |
93 | * constant time. | |
94 | */ | |
95 | ||
96 | int ct_pick(uint32 a, uint32 x0, uint32 x1) | |
97 | { uint32 m = MASK(a); return (x0&~m) | (x1&m); } | |
98 | ||
99 | /* --- @ct_condcopy@ --- * | |
100 | * | |
101 | * Arguments: @uint32 a@ = a switch, either zero or one | |
102 | * @void *d@ = destination pointer | |
103 | * @const void *s@ = source pointer | |
104 | * @size_t n@ amount to copy | |
105 | * | |
106 | * Returns: --- | |
107 | * | |
108 | * Use: If @a@ is one then copy the @n@ bytes starting at @s@ to | |
109 | * @d@; if @a@ is zero then leave @d@ unchanged (but it will | |
110 | * still be written). All of this is done in constant time. | |
111 | */ | |
112 | ||
113 | void ct_condcopy(uint32 a, void *d, const void *s, size_t n) | |
114 | { | |
115 | octet *dd = d; | |
116 | const octet *ss = s; | |
117 | uint32 m = MASK(a); | |
118 | ||
119 | while (n--) { | |
120 | *dd = (*ss++&m) | (*dd&~m); | |
121 | dd++; | |
122 | } | |
123 | } | |
124 | ||
125 | /* --- @ct_memeq@ --- | |
126 | * | |
127 | * Arguments: @const void *p, *q@ = two pointers to buffers | |
128 | * @size_t n@ = the (common) size of the buffers | |
129 | * | |
130 | * Returns: One if the two buffers are equal, zero if they aren't. | |
131 | * | |
132 | * Use: Compares two chunks of memory, in constant time. | |
133 | */ | |
134 | ||
135 | int ct_memeq(const void *p, const void *q, size_t n) | |
136 | { | |
137 | const octet *pp = p, *qq = q; | |
138 | octet a = 0; | |
139 | ||
140 | while (n--) a |= *pp++ ^ *qq++; | |
141 | return (ct_inteq(a, 0)); | |
142 | } | |
143 | ||
144 | /*----- That's all, folks -------------------------------------------------*/ |