| 1 | /* -*-c-*- |
| 2 | * |
| 3 | * The SHA256 hash function (compact edition) |
| 4 | * |
| 5 | * (c) 2020 Mark Wooding |
| 6 | */ |
| 7 | |
| 8 | /*----- Licensing notice --------------------------------------------------* |
| 9 | * |
| 10 | * This file is part of Runlisp, a tool for invoking Common Lisp scripts. |
| 11 | * |
| 12 | * Runlisp is free software: you can redistribute it and/or modify it |
| 13 | * under the terms of the GNU General Public License as published by the |
| 14 | * Free Software Foundation; either version 3 of the License, or (at your |
| 15 | * option) any later version. |
| 16 | * |
| 17 | * Runlisp is distributed in the hope that it will be useful, but WITHOUT |
| 18 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 19 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 20 | * for more details. |
| 21 | * |
| 22 | * You should have received a copy of the GNU General Public License |
| 23 | * along with Runlisp. If not, see <https://www.gnu.org/licenses/>. |
| 24 | */ |
| 25 | |
| 26 | /*----- Header files ------------------------------------------------------*/ |
| 27 | |
| 28 | #include <string.h> |
| 29 | |
| 30 | #include "sha256.h" |
| 31 | |
| 32 | /*----- Preliminary definitions -------------------------------------------*/ |
| 33 | |
| 34 | /* The initial values of the state variables. These are in reverse order -- |
| 35 | * see the note in `compress'. |
| 36 | */ |
| 37 | static const u32 iv[8] = { |
| 38 | 0x5be0cd19, 0x1f83d9ab, 0x9b05688c, 0x510e527f, |
| 39 | 0xa54ff53a, 0x3c6ef372, 0xbb67ae85, 0x6a09e667 |
| 40 | }; |
| 41 | |
| 42 | /* The round constants. */ |
| 43 | static const u32 rc[64] = { |
| 44 | 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, |
| 45 | 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, |
| 46 | 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, |
| 47 | 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, |
| 48 | 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, |
| 49 | 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, |
| 50 | 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, |
| 51 | 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, |
| 52 | 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, |
| 53 | 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, |
| 54 | 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, |
| 55 | 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, |
| 56 | 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, |
| 57 | 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, |
| 58 | 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, |
| 59 | 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 |
| 60 | }; |
| 61 | |
| 62 | /* Standard bithacking operations on 32-bit words. |
| 63 | * |
| 64 | * Note that this code assumes that a `u32' is /at least/ 32 bits wide, but |
| 65 | * may be longer, so we must do some work to keep cruft in the top bits from |
| 66 | * messing things up. |
| 67 | */ |
| 68 | #define M32 0xffffffff |
| 69 | #define LSL32(x, n) ((x) << ((n))) |
| 70 | #define LSR32(x, n) (((x)&M32) >> ((n))) |
| 71 | #define ROR32(x, n) (LSL32((x), 32 - (n)) | LSR32((x), (n))) |
| 72 | |
| 73 | /* Reading and writing 32-bit words. */ |
| 74 | #define LOAD32_B(p) \ |
| 75 | (((u32)(((const unsigned char *)(p))[0]&0xff) << 24) | \ |
| 76 | ((u32)(((const unsigned char *)(p))[1]&0xff) << 16) | \ |
| 77 | ((u32)(((const unsigned char *)(p))[2]&0xff) << 8) | \ |
| 78 | ((u32)(((const unsigned char *)(p))[3]&0xff) << 0)) |
| 79 | #define STORE32_B(p, x) do { \ |
| 80 | (void)sizeof(memmove((p), (p), 1)); \ |
| 81 | ((unsigned char *)(p))[0] = ((x) >> 24)&0xff; \ |
| 82 | ((unsigned char *)(p))[1] = ((x) >> 16)&0xff; \ |
| 83 | ((unsigned char *)(p))[2] = ((x) >> 8)&0xff; \ |
| 84 | ((unsigned char *)(p))[3] = ((x) >> 0)&0xff; \ |
| 85 | } while (0) |
| 86 | |
| 87 | /* SHA256's balanced ternary operators. */ |
| 88 | #define CH(x, y, z) (((x)&(y)) | (~(x)&(z))) |
| 89 | #define MAJ(x, y, z) (((x)&(y)) | ((y)&(z)) | ((z)&(x))) |
| 90 | |
| 91 | /* The SHA256 Σ and σ functions. */ |
| 92 | #define S0(x) (ROR32((x), 2) ^ ROR32((x), 13) ^ ROR32((x), 22)) |
| 93 | #define S1(x) (ROR32((x), 6) ^ ROR32((x), 11) ^ ROR32((x), 25)) |
| 94 | #define s0(x) (ROR32((x), 7) ^ ROR32((x), 18) ^ LSR32((x), 3)) |
| 95 | #define s1(x) (ROR32((x), 17) ^ ROR32((x), 19) ^ LSR32((x), 10)) |
| 96 | |
| 97 | /*----- Main code ---------------------------------------------------------*/ |
| 98 | |
| 99 | /* Compress a 64-byte buffer at P, updating the hash state S. */ |
| 100 | static void compress(struct sha256_state *s, const unsigned char *p) |
| 101 | { |
| 102 | u32 t, u, a[8], m[16]; |
| 103 | const u32 *r = rc; |
| 104 | size_t i; |
| 105 | |
| 106 | /* This is a mostly straightforward implementation of the specification, as |
| 107 | * a rolled-up loop, one iteration per round. The only wrinkle is that the |
| 108 | * vector of state variables, conventionally named a, b, ..., h, are |
| 109 | * maintained in our state structure in reverse order, so h is in S->a[0], |
| 110 | * b is in S->a[6], and a is in S->a[7]. We do this so that we advance |
| 111 | * through our vector in the correct direction from round to round: this |
| 112 | * avoids making the indexing arithmetic too complicated. |
| 113 | */ |
| 114 | |
| 115 | /* Move the state and message data into our internal vectors. */ |
| 116 | for (i = 0; i < 8; i++) a[i] = s->a[i]; |
| 117 | for (i = 0; i < 16; i++, p += 4) m[i] = LOAD32_B(p); |
| 118 | |
| 119 | /* Perform 64 rounds of update. Update the message schedule as we go. The |
| 120 | * last 16 rounds of message-schedule update are pointless: doing the |
| 121 | * message-schedule update conditionally would make the loop messier, and |
| 122 | * running the message schedule separately would add a second loop and |
| 123 | * require more intermediate storage. |
| 124 | */ |
| 125 | for (i = 0; i < 64; i++) { |
| 126 | #define A(j) (a[(i + (j))%8]) |
| 127 | #define M(j) (m[(i + (j))%16]) |
| 128 | t = A(0) + S1(A(3)) + CH(A(3), A(2), A(1)) + M(0) + *r++; |
| 129 | u = S0(A(7)) + MAJ(A(7), A(6), A(5)); |
| 130 | A(4) += t; A(0) = t + u; |
| 131 | M(0) += s1(M(14)) + M(9) + s0(M(1)); |
| 132 | #undef A |
| 133 | #undef M |
| 134 | } |
| 135 | |
| 136 | /* Write out the updated state. */ |
| 137 | for (i = 0; i < 8; i++) s->a[i] += a[i]; |
| 138 | } |
| 139 | |
| 140 | /* Initialize the hash state S. */ |
| 141 | void sha256_init(struct sha256_state *s) |
| 142 | { size_t i; s->n = s->nblk = 0; for (i = 0; i < 8; i++) s->a[i] = iv[i]; } |
| 143 | |
| 144 | /* Append SZ bytes of data starting at M to the hash state S. */ |
| 145 | void sha256_hash(struct sha256_state *s, const void *m, size_t sz) |
| 146 | { |
| 147 | const unsigned char *p = m; |
| 148 | size_t r = SHA256_BLKSZ - s->n; |
| 149 | |
| 150 | /* Feed the input data into the hash function. Our buffer-management |
| 151 | * policy is to empty the buffer by calling the compression function as |
| 152 | * soon as the buffer fills completely. |
| 153 | */ |
| 154 | if (sz < r) { |
| 155 | /* The whole input will fit into the buffer, with space to spare. We |
| 156 | * just copy it in and update the occupancy counter. |
| 157 | */ |
| 158 | |
| 159 | memcpy(s->buf + s->n, p, sz); |
| 160 | s->n += sz; |
| 161 | } else { |
| 162 | /* We're going to fill the buffer at least once. */ |
| 163 | |
| 164 | /* If the buffer contains any data already then copy the initial portion |
| 165 | * of the new input chunk into the buffer and compress it there. |
| 166 | * Otherwise, if the buffer is entirely empty, then we can compress the |
| 167 | * initial block from the input directly. |
| 168 | */ |
| 169 | if (!s->n) { compress(s, p); p += SHA256_BLKSZ; sz -= SHA256_BLKSZ; } |
| 170 | else { memcpy(s->buf + s->n, p, r); compress(s, s->buf); p += r; sz -= r; } |
| 171 | s->nblk++; |
| 172 | |
| 173 | /* Continue compressing complete blocks from the input while enough |
| 174 | * material remains. |
| 175 | */ |
| 176 | while (sz >= SHA256_BLKSZ) |
| 177 | { compress(s, p); s->nblk++; p += SHA256_BLKSZ; sz -= SHA256_BLKSZ; } |
| 178 | |
| 179 | /* Copy the tail end into the buffer and record how much there is. */ |
| 180 | s->n = sz; if (sz) memcpy(s->buf, p, sz); |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | /* Write the final hash of state S to buffer H. */ |
| 185 | void sha256_done(struct sha256_state *s, unsigned char *h) |
| 186 | { |
| 187 | size_t i, n, r; |
| 188 | u32 lo, hi; |
| 189 | |
| 190 | /* Add the end-of-data marker to the buffer. There must be at least one |
| 191 | * byte spare, or we'd have compressed already. |
| 192 | */ |
| 193 | n = s->n; s->buf[n++] = 0x80; r = SHA256_BLKSZ - n; |
| 194 | |
| 195 | /* If there's enough space for the message length, then fill the gap |
| 196 | * between with zeros. Otherwise, fill the whole of the remaining space, |
| 197 | * compress, and then refill the initial portion of the buffer. Either |
| 198 | * way, after this, there's just eight bytes left at the end of the buffer, |
| 199 | * into which we can drop the length. |
| 200 | */ |
| 201 | if (r >= 8) |
| 202 | memset(s->buf + n, 0, r - 8); |
| 203 | else { |
| 204 | if (r) memset(s->buf + n, 0, r); |
| 205 | compress(s, s->buf); |
| 206 | memset(s->buf, 0, SHA256_BLKSZ - 8); |
| 207 | } |
| 208 | |
| 209 | /* Convert the length into two 32-bit halves measuring the total input |
| 210 | * length in bits, and run the compression function one last time. There |
| 211 | * can be no carry, since S->n is always less than 64. |
| 212 | */ |
| 213 | lo = ((s->nblk << 9) | (s->n << 3))&M32; hi = (s->nblk >> 23)&M32; |
| 214 | STORE32_B(s->buf + 56, hi); STORE32_B(s->buf + 60, lo); |
| 215 | compress(s, s->buf); |
| 216 | |
| 217 | /* Write out the final hash value. We must compensate here because the |
| 218 | * state variables are in reverse order. |
| 219 | */ |
| 220 | for (i = 8; i-- > 0; h += 4) STORE32_B(h, s->a[i]); |
| 221 | } |
| 222 | |
| 223 | /*----- That's all, folks -------------------------------------------------*/ |