keccak.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473
  1. /*
  2. * An implementation of the SHA3 (Keccak) hash function family.
  3. *
  4. * Algorithm specifications: http://keccak.noekeon.org/
  5. * NIST Announcement:
  6. * http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html
  7. *
  8. * Written in 2013 by Fabrizio Tarizzo <fabrizio@fabriziotarizzo.org>
  9. *
  10. * ===================================================================
  11. * The contents of this file are dedicated to the public domain. To
  12. * the extent that dedication to the public domain is not available,
  13. * everyone is granted a worldwide, perpetual, royalty-free,
  14. * non-exclusive license to exercise all rights associated with the
  15. * contents of this file for any purpose whatsoever.
  16. * No rights are reserved.
  17. *
  18. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19. * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20. * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21. * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  22. * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  23. * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24. * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  25. * SOFTWARE.
  26. * ===================================================================
  27. */
  28. #include "pycrypto_common.h"
  29. #include <string.h>
  30. #include <assert.h>
  31. FAKE_INIT(keccak)
  32. typedef struct
  33. {
  34. uint64_t state[25];
  35. /* The buffer is as long as the state,
  36. * but only 'rate' bytes will be used.
  37. */
  38. uint8_t buf[200];
  39. /* When absorbing, this is the number of bytes in buf that
  40. * are coming from the message and outstanding.
  41. * When squeezing, this is the remaining number of bytes
  42. * that can be used as digest.
  43. */
  44. size_t valid_bytes;
  45. /* All values in bytes */
  46. uint16_t security;
  47. uint16_t capacity;
  48. uint16_t rate;
  49. uint8_t squeezing;
  50. uint8_t padding;
  51. } keccak_state;
  52. #undef ROL64
  53. #define ROL64(x,y) ((((x) << (y)) | (x) >> (64-(y))) & 0xFFFFFFFFFFFFFFFFULL)
  54. static inline int little_endian(void) {
  55. const int test = 1;
  56. return *((uint8_t*)&test) == 1;
  57. }
  58. static inline uint64_t load64_le(const uint8_t p[])
  59. {
  60. union {
  61. int64_t dw;
  62. uint8_t b[8];
  63. } result;
  64. if (little_endian()) {
  65. memcpy(&result, p, sizeof result);
  66. } else {
  67. result.b[0] = p[7];
  68. result.b[1] = p[6];
  69. result.b[2] = p[5];
  70. result.b[3] = p[4];
  71. result.b[4] = p[3];
  72. result.b[5] = p[2];
  73. result.b[6] = p[1];
  74. result.b[7] = p[0];
  75. }
  76. return result.dw;
  77. }
  78. static inline void store64_le(uint8_t dest[], uint64_t src)
  79. {
  80. union t {
  81. int64_t dw;
  82. uint8_t b[8];
  83. } *result = (void*) &src;
  84. if (little_endian()) {
  85. memcpy(dest, &src, sizeof src);
  86. } else {
  87. dest[0] = result->b[7];
  88. dest[1] = result->b[6];
  89. dest[2] = result->b[5];
  90. dest[3] = result->b[4];
  91. dest[4] = result->b[3];
  92. dest[5] = result->b[2];
  93. dest[6] = result->b[1];
  94. dest[7] = result->b[0];
  95. }
  96. }
  97. static void keccak_function (uint64_t *state);
  98. static void keccak_absorb_internal (keccak_state *self)
  99. {
  100. short i,j;
  101. uint64_t d;
  102. for (i = j = 0; j < self->rate; ++i, j += 8) {
  103. d = load64_le(self->buf + j);
  104. self->state[i] ^= d;
  105. }
  106. }
  107. static void
  108. keccak_squeeze_internal (keccak_state *self)
  109. {
  110. short i, j;
  111. for (i = j = 0; j < self->rate; ++i, j += 8) {
  112. store64_le(self->buf+j, self->state[i]);
  113. }
  114. }
  115. EXPORT_SYM int keccak_init (keccak_state **state,
  116. size_t capacity_bytes,
  117. uint8_t padding)
  118. {
  119. keccak_state *ks;
  120. if (NULL == state) {
  121. return ERR_NULL;
  122. }
  123. *state = ks = (keccak_state*) calloc(1, sizeof(keccak_state));
  124. if (NULL == ks)
  125. return ERR_MEMORY;
  126. ks->capacity = capacity_bytes;
  127. if (ks->capacity >= 200)
  128. return ERR_DIGEST_SIZE;
  129. ks->rate = 200 - ks->capacity;
  130. ks->squeezing = 0;
  131. ks->padding = padding;
  132. return 0;
  133. }
  134. EXPORT_SYM int keccak_destroy(keccak_state *state)
  135. {
  136. free(state);
  137. return 0;
  138. }
  139. static inline unsigned minAB(unsigned a, unsigned b)
  140. {
  141. return a<b ? a :b;
  142. }
  143. EXPORT_SYM int keccak_absorb (keccak_state *self,
  144. const uint8_t *in,
  145. size_t length)
  146. {
  147. if (NULL==self || NULL==in)
  148. return ERR_NULL;
  149. if (self->squeezing)
  150. return ERR_UNKNOWN;
  151. while (length > 0) {
  152. unsigned bytestocopy;
  153. bytestocopy = minAB(length, self->rate - self->valid_bytes);
  154. memcpy(self->buf + self->valid_bytes, in, bytestocopy);
  155. self->valid_bytes += bytestocopy;
  156. in += bytestocopy;
  157. length -= bytestocopy;
  158. if (self->valid_bytes == self->rate) {
  159. keccak_absorb_internal (self);
  160. keccak_function (self->state);
  161. self->valid_bytes = 0;
  162. }
  163. }
  164. return 0;
  165. }
  166. static void keccak_finish (keccak_state *self)
  167. {
  168. assert(self->squeezing == 0);
  169. assert(self->valid_bytes < self->rate);
  170. /* Padding */
  171. memset(self->buf + self->valid_bytes, 0, self->rate - self->valid_bytes);
  172. self->buf[self->valid_bytes] = self->padding;
  173. self->buf[self->rate-1] |= 0x80;
  174. /* Final absorb */
  175. keccak_absorb_internal (self);
  176. keccak_function (self->state);
  177. /* First squeeze */
  178. self->squeezing = 1;
  179. keccak_squeeze_internal (self);
  180. self->valid_bytes = self->rate;
  181. }
  182. EXPORT_SYM int keccak_squeeze (keccak_state *self, uint8_t *out, size_t length)
  183. {
  184. if ((NULL == self) || (NULL == out))
  185. return ERR_NULL;
  186. if (!self->squeezing) {
  187. keccak_finish (self);
  188. }
  189. assert(self->valid_bytes > 0);
  190. assert(self->valid_bytes <= self->rate);
  191. while (length > 0) {
  192. unsigned bytestocopy;
  193. bytestocopy = minAB(self->valid_bytes, length);
  194. memcpy(out, self->buf + (self->rate - self->valid_bytes), bytestocopy);
  195. self->valid_bytes -= bytestocopy;
  196. out += bytestocopy;
  197. length -= bytestocopy;
  198. if (self->valid_bytes == 0) {
  199. keccak_function (self->state);
  200. keccak_squeeze_internal (self);
  201. self->valid_bytes = self->rate;
  202. }
  203. }
  204. return 0;
  205. }
  206. EXPORT_SYM int keccak_digest(keccak_state *state, uint8_t *digest, size_t len)
  207. {
  208. keccak_state tmp;
  209. if ((NULL==state) || (NULL==digest))
  210. return ERR_NULL;
  211. if (2*len != state->capacity)
  212. return ERR_UNKNOWN;
  213. tmp = *state;
  214. return keccak_squeeze(&tmp, digest, len);
  215. }
  216. /* Keccak core function */
  217. #define KECCAK_ROUNDS 24
  218. #define ROT_01 36
  219. #define ROT_02 3
  220. #define ROT_03 41
  221. #define ROT_04 18
  222. #define ROT_05 1
  223. #define ROT_06 44
  224. #define ROT_07 10
  225. #define ROT_08 45
  226. #define ROT_09 2
  227. #define ROT_10 62
  228. #define ROT_11 6
  229. #define ROT_12 43
  230. #define ROT_13 15
  231. #define ROT_14 61
  232. #define ROT_15 28
  233. #define ROT_16 55
  234. #define ROT_17 25
  235. #define ROT_18 21
  236. #define ROT_19 56
  237. #define ROT_20 27
  238. #define ROT_21 20
  239. #define ROT_22 39
  240. #define ROT_23 8
  241. #define ROT_24 14
  242. static const uint64_t roundconstants[KECCAK_ROUNDS] = {
  243. 0x0000000000000001ULL,
  244. 0x0000000000008082ULL,
  245. 0x800000000000808aULL,
  246. 0x8000000080008000ULL,
  247. 0x000000000000808bULL,
  248. 0x0000000080000001ULL,
  249. 0x8000000080008081ULL,
  250. 0x8000000000008009ULL,
  251. 0x000000000000008aULL,
  252. 0x0000000000000088ULL,
  253. 0x0000000080008009ULL,
  254. 0x000000008000000aULL,
  255. 0x000000008000808bULL,
  256. 0x800000000000008bULL,
  257. 0x8000000000008089ULL,
  258. 0x8000000000008003ULL,
  259. 0x8000000000008002ULL,
  260. 0x8000000000000080ULL,
  261. 0x000000000000800aULL,
  262. 0x800000008000000aULL,
  263. 0x8000000080008081ULL,
  264. 0x8000000000008080ULL,
  265. 0x0000000080000001ULL,
  266. 0x8000000080008008ULL
  267. };
  268. void keccak_function (uint64_t *state)
  269. {
  270. short i;
  271. /* Temporary variables to avoid indexing overhead */
  272. uint64_t a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12;
  273. uint64_t a13, a14, a15, a16, a17, a18, a19, a20, a21, a22, a23, a24;
  274. uint64_t b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12;
  275. uint64_t b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24;
  276. uint64_t c0, c1, c2, c3, c4, d;
  277. a0 = state[0];
  278. a1 = state[1];
  279. a2 = state[2];
  280. a3 = state[3];
  281. a4 = state[4];
  282. a5 = state[5];
  283. a6 = state[6];
  284. a7 = state[7];
  285. a8 = state[8];
  286. a9 = state[9];
  287. a10 = state[10];
  288. a11 = state[11];
  289. a12 = state[12];
  290. a13 = state[13];
  291. a14 = state[14];
  292. a15 = state[15];
  293. a16 = state[16];
  294. a17 = state[17];
  295. a18 = state[18];
  296. a19 = state[19];
  297. a20 = state[20];
  298. a21 = state[21];
  299. a22 = state[22];
  300. a23 = state[23];
  301. a24 = state[24];
  302. for (i = 0; i < KECCAK_ROUNDS; ++i) {
  303. /*
  304. Uses temporary variables and loop unrolling to
  305. avoid array indexing and inner loops overhead
  306. */
  307. /* Prepare column parity for Theta step */
  308. c0 = a0 ^ a5 ^ a10 ^ a15 ^ a20;
  309. c1 = a1 ^ a6 ^ a11 ^ a16 ^ a21;
  310. c2 = a2 ^ a7 ^ a12 ^ a17 ^ a22;
  311. c3 = a3 ^ a8 ^ a13 ^ a18 ^ a23;
  312. c4 = a4 ^ a9 ^ a14 ^ a19 ^ a24;
  313. /* Theta + Rho + Pi steps */
  314. d = c4 ^ ROL64(c1, 1);
  315. b0 = d ^ a0;
  316. b16 = ROL64(d ^ a5, ROT_01);
  317. b7 = ROL64(d ^ a10, ROT_02);
  318. b23 = ROL64(d ^ a15, ROT_03);
  319. b14 = ROL64(d ^ a20, ROT_04);
  320. d = c0 ^ ROL64(c2, 1);
  321. b10 = ROL64(d ^ a1, ROT_05);
  322. b1 = ROL64(d ^ a6, ROT_06);
  323. b17 = ROL64(d ^ a11, ROT_07);
  324. b8 = ROL64(d ^ a16, ROT_08);
  325. b24 = ROL64(d ^ a21, ROT_09);
  326. d = c1 ^ ROL64(c3, 1);
  327. b20 = ROL64(d ^ a2, ROT_10);
  328. b11 = ROL64(d ^ a7, ROT_11);
  329. b2 = ROL64(d ^ a12, ROT_12);
  330. b18 = ROL64(d ^ a17, ROT_13);
  331. b9 = ROL64(d ^ a22, ROT_14);
  332. d = c2 ^ ROL64(c4, 1);
  333. b5 = ROL64(d ^ a3, ROT_15);
  334. b21 = ROL64(d ^ a8, ROT_16);
  335. b12 = ROL64(d ^ a13, ROT_17);
  336. b3 = ROL64(d ^ a18, ROT_18);
  337. b19 = ROL64(d ^ a23, ROT_19);
  338. d = c3 ^ ROL64(c0, 1);
  339. b15 = ROL64(d ^ a4, ROT_20);
  340. b6 = ROL64(d ^ a9, ROT_21);
  341. b22 = ROL64(d ^ a14, ROT_22);
  342. b13 = ROL64(d ^ a19, ROT_23);
  343. b4 = ROL64(d ^ a24, ROT_24);
  344. /* Chi + Iota steps */
  345. a0 = b0 ^ (~b1 & b2) ^ roundconstants[i];
  346. a1 = b1 ^ (~b2 & b3);
  347. a2 = b2 ^ (~b3 & b4);
  348. a3 = b3 ^ (~b4 & b0);
  349. a4 = b4 ^ (~b0 & b1);
  350. a5 = b5 ^ (~b6 & b7);
  351. a6 = b6 ^ (~b7 & b8);
  352. a7 = b7 ^ (~b8 & b9);
  353. a8 = b8 ^ (~b9 & b5);
  354. a9 = b9 ^ (~b5 & b6);
  355. a10 = b10 ^ (~b11 & b12);
  356. a11 = b11 ^ (~b12 & b13);
  357. a12 = b12 ^ (~b13 & b14);
  358. a13 = b13 ^ (~b14 & b10);
  359. a14 = b14 ^ (~b10 & b11);
  360. a15 = b15 ^ (~b16 & b17);
  361. a16 = b16 ^ (~b17 & b18);
  362. a17 = b17 ^ (~b18 & b19);
  363. a18 = b18 ^ (~b19 & b15);
  364. a19 = b19 ^ (~b15 & b16);
  365. a20 = b20 ^ (~b21 & b22);
  366. a21 = b21 ^ (~b22 & b23);
  367. a22 = b22 ^ (~b23 & b24);
  368. a23 = b23 ^ (~b24 & b20);
  369. a24 = b24 ^ (~b20 & b21);
  370. }
  371. state[0] = a0;
  372. state[1] = a1;
  373. state[2] = a2;
  374. state[3] = a3;
  375. state[4] = a4;
  376. state[5] = a5;
  377. state[6] = a6;
  378. state[7] = a7;
  379. state[8] = a8;
  380. state[9] = a9;
  381. state[10] = a10;
  382. state[11] = a11;
  383. state[12] = a12;
  384. state[13] = a13;
  385. state[14] = a14;
  386. state[15] = a15;
  387. state[16] = a16;
  388. state[17] = a17;
  389. state[18] = a18;
  390. state[19] = a19;
  391. state[20] = a20;
  392. state[21] = a21;
  393. state[22] = a22;
  394. state[23] = a23;
  395. state[24] = a24;
  396. }