From: Felix Fietkau Date: Mon, 6 Apr 2015 14:00:52 +0000 (+0200) Subject: Initial import X-Git-Url: http://git.openwrt.org/?p=project%2Fusign.git;a=commitdiff_plain;h=8a974da5e11ae0afad10834ea4ea6f1383cefbc2 Initial import Signed-off-by: Felix Fietkau --- 8a974da5e11ae0afad10834ea4ea6f1383cefbc2 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..84ca526 --- /dev/null +++ b/.gitignore @@ -0,0 +1,9 @@ +Makefile +CMakeCache.txt +CMakeFiles +*.cmake +*.a +*.so +*.dylib +install_manifest.txt +usign diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..8361171 --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,11 @@ +cmake_minimum_required(VERSION 2.8) + +PROJECT(usign C) +ADD_DEFINITIONS(-O2 -Wall -Werror --std=gnu99 -g3 -Wmissing-declarations) + +SET(SOURCES ed25519.c edsign.c f25519.c fprime.c sha512.c base64.c main.c) +ADD_EXECUTABLE(usign ${SOURCES}) + +INSTALL(TARGETS usign + RUNTIME DESTINATION bin +) diff --git a/base64.c b/base64.c new file mode 100644 index 0000000..27acf40 --- /dev/null +++ b/base64.c @@ -0,0 +1,305 @@ +/* $OpenBSD: base64.c,v 1.7 2013/12/31 02:32:56 tedu Exp $ */ + +/* + * Copyright (c) 1996 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* + * Portions Copyright (c) 1995 by International Business Machines, Inc. + * + * International Business Machines, Inc. (hereinafter called IBM) grants + * permission under its copyrights to use, copy, modify, and distribute this + * Software with or without fee, provided that the above copyright notice and + * all paragraphs of this notice appear in all copies, and that the name of IBM + * not be used in connection with the marketing of any product incorporating + * the Software or modifications thereof, without specific, written prior + * permission. + * + * To the extent it has a right to do so, IBM grants an immunity from suit + * under its patents, if any, for the use, sale or manufacture of products to + * the extent that such products are used for performing Domain Name System + * dynamic updates in TCP/IP networks by means of the Software. No immunity is + * granted for any product per se or for any other function of any product. + * + * THE SOFTWARE IS PROVIDED "AS IS", AND IBM DISCLAIMS ALL WARRANTIES, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, + * DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER ARISING + * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE, EVEN + * IF IBM IS APPRISED OF THE POSSIBILITY OF SUCH DAMAGES. + */ + +#include +#include +#include +#include +#include +#include "base64.h" + +static const char Base64[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; +static const char Pad64 = '='; + +/* (From RFC1521 and draft-ietf-dnssec-secext-03.txt) + The following encoding technique is taken from RFC 1521 by Borenstein + and Freed. It is reproduced here in a slightly edited form for + convenience. + + A 65-character subset of US-ASCII is used, enabling 6 bits to be + represented per printable character. (The extra 65th character, "=", + is used to signify a special processing function.) + + The encoding process represents 24-bit groups of input bits as output + strings of 4 encoded characters. Proceeding from left to right, a + 24-bit input group is formed by concatenating 3 8-bit input groups. + These 24 bits are then treated as 4 concatenated 6-bit groups, each + of which is translated into a single digit in the base64 alphabet. + + Each 6-bit group is used as an index into an array of 64 printable + characters. The character referenced by the index is placed in the + output string. + + Table 1: The Base64 Alphabet + + Value Encoding Value Encoding Value Encoding Value Encoding + 0 A 17 R 34 i 51 z + 1 B 18 S 35 j 52 0 + 2 C 19 T 36 k 53 1 + 3 D 20 U 37 l 54 2 + 4 E 21 V 38 m 55 3 + 5 F 22 W 39 n 56 4 + 6 G 23 X 40 o 57 5 + 7 H 24 Y 41 p 58 6 + 8 I 25 Z 42 q 59 7 + 9 J 26 a 43 r 60 8 + 10 K 27 b 44 s 61 9 + 11 L 28 c 45 t 62 + + 12 M 29 d 46 u 63 / + 13 N 30 e 47 v + 14 O 31 f 48 w (pad) = + 15 P 32 g 49 x + 16 Q 33 h 50 y + + Special processing is performed if fewer than 24 bits are available + at the end of the data being encoded. A full encoding quantum is + always completed at the end of a quantity. When fewer than 24 input + bits are available in an input group, zero bits are added (on the + right) to form an integral number of 6-bit groups. Padding at the + end of the data is performed using the '=' character. + + Since all base64 input is an integral number of octets, only the + ------------------------------------------------- + following cases can arise: + + (1) the final quantum of encoding input is an integral + multiple of 24 bits; here, the final unit of encoded + output will be an integral multiple of 4 characters + with no "=" padding, + (2) the final quantum of encoding input is exactly 8 bits; + here, the final unit of encoded output will be two + characters followed by two "=" padding characters, or + (3) the final quantum of encoding input is exactly 16 bits; + here, the final unit of encoded output will be three + characters followed by one "=" padding character. + */ + +int b64_ntop(const void *_src, size_t srclength, + void *dest, size_t targsize) +{ + const unsigned char *src = _src; + char *target = dest; + size_t datalength = 0; + u_char input[3]; + u_char output[4]; + int i; + + while (2 < srclength) { + input[0] = *src++; + input[1] = *src++; + input[2] = *src++; + srclength -= 3; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + output[3] = input[2] & 0x3f; + + if (datalength + 4 > targsize) + return (-1); + target[datalength++] = Base64[output[0]]; + target[datalength++] = Base64[output[1]]; + target[datalength++] = Base64[output[2]]; + target[datalength++] = Base64[output[3]]; + } + + /* Now we worry about padding. */ + if (0 != srclength) { + /* Get what's left. */ + input[0] = input[1] = input[2] = '\0'; + for (i = 0; i < srclength; i++) + input[i] = *src++; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + + if (datalength + 4 > targsize) + return (-1); + target[datalength++] = Base64[output[0]]; + target[datalength++] = Base64[output[1]]; + if (srclength == 1) + target[datalength++] = Pad64; + else + target[datalength++] = Base64[output[2]]; + target[datalength++] = Pad64; + } + if (datalength >= targsize) + return (-1); + target[datalength] = '\0'; /* Returned value doesn't count \0. */ + return (datalength); +} + +/* skips all whitespace anywhere. + converts characters, four at a time, starting at (or after) + src from base - 64 numbers into three 8 bit bytes in the target area. + it returns the number of data bytes stored at the target, or -1 on error. + */ + +int b64_pton(const void *_src, void *dest, size_t targsize) +{ + const char *src = _src; + unsigned char *target = dest; + int tarindex, state, ch; + u_char nextbyte; + char *pos; + + state = 0; + tarindex = 0; + + while ((ch = (unsigned char)*src++) != '\0') { + if (isspace(ch)) /* Skip whitespace anywhere. */ + continue; + + if (ch == Pad64) + break; + + pos = strchr(Base64, ch); + if (pos == 0) /* A non-base64 character. */ + return (-1); + + switch (state) { + case 0: + if (target) { + if (tarindex >= targsize) + return (-1); + target[tarindex] = (pos - Base64) << 2; + } + state = 1; + break; + case 1: + if (target) { + if (tarindex >= targsize) + return (-1); + target[tarindex] |= (pos - Base64) >> 4; + nextbyte = ((pos - Base64) & 0x0f) << 4; + if (tarindex + 1 < targsize) + target[tarindex+1] = nextbyte; + else if (nextbyte) + return (-1); + } + tarindex++; + state = 2; + break; + case 2: + if (target) { + if (tarindex >= targsize) + return (-1); + target[tarindex] |= (pos - Base64) >> 2; + nextbyte = ((pos - Base64) & 0x03) << 6; + if (tarindex + 1 < targsize) + target[tarindex+1] = nextbyte; + else if (nextbyte) + return (-1); + } + tarindex++; + state = 3; + break; + case 3: + if (target) { + if (tarindex >= targsize) + return (-1); + target[tarindex] |= (pos - Base64); + } + tarindex++; + state = 0; + break; + } + } + + /* + * We are done decoding Base-64 chars. Let's see if we ended + * on a byte boundary, and/or with erroneous trailing characters. + */ + + if (ch == Pad64) { /* We got a pad char. */ + ch = (unsigned char)*src++; /* Skip it, get next. */ + switch (state) { + case 0: /* Invalid = in first position */ + case 1: /* Invalid = in second position */ + return (-1); + + case 2: /* Valid, means one byte of info */ + /* Skip any number of spaces. */ + for (; ch != '\0'; ch = (unsigned char)*src++) + if (!isspace(ch)) + break; + /* Make sure there is another trailing = sign. */ + if (ch != Pad64) + return (-1); + ch = (unsigned char)*src++; /* Skip the = */ + /* Fall through to "single trailing =" case. */ + /* FALLTHROUGH */ + + case 3: /* Valid, means two bytes of info */ + /* + * We know this char is an =. Is there anything but + * whitespace after it? + */ + for (; ch != '\0'; ch = (unsigned char)*src++) + if (!isspace(ch)) + return (-1); + + /* + * Now make sure for cases 2 and 3 that the "extra" + * bits that slopped past the last full byte were + * zeros. If we don't check them, they become a + * subliminal channel. + */ + if (target && tarindex < targsize && + target[tarindex] != 0) + return (-1); + } + } else { + /* + * We ended by seeing the end of the string. Make sure we + * have no partial bytes lying around. + */ + if (state != 0) + return (-1); + } + + return (tarindex); +} diff --git a/base64.h b/base64.h new file mode 100644 index 0000000..2625721 --- /dev/null +++ b/base64.h @@ -0,0 +1,12 @@ +#ifndef __BASE64_H +#define __BASE64_H + +int b64_ntop(const void *src, size_t src_len, + void *dest, size_t dest_len); + +int b64_pton(const void *src, void *dest, size_t dest_len); + +#define B64_DECODE_LEN(_len) (((_len) / 4) * 3 + 1) +#define B64_ENCODE_LEN(_len) ((((_len) / 3) + 1) * 4 + 1) + +#endif diff --git a/ed25519.c b/ed25519.c new file mode 100644 index 0000000..1fff1f4 --- /dev/null +++ b/ed25519.c @@ -0,0 +1,320 @@ +/* Edwards curve operations + * Daniel Beer , 9 Jan 2014 + * + * This file is in the public domain. + */ + +#include "ed25519.h" + +/* Base point is (numbers wrapped): + * + * x = 151122213495354007725011514095885315114 + * 54012693041857206046113283949847762202 + * y = 463168356949264781694283940034751631413 + * 07993866256225615783033603165251855960 + * + * y is derived by transforming the original Montgomery base (u=9). x + * is the corresponding positive coordinate for the new curve equation. + * t is x*y. + */ +const struct ed25519_pt ed25519_base = { + .x = { + 0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, + 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69, + 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0, + 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21 + }, + .y = { + 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, + 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66 + }, + .t = { + 0xa3, 0xdd, 0xb7, 0xa5, 0xb3, 0x8a, 0xde, 0x6d, + 0xf5, 0x52, 0x51, 0x77, 0x80, 0x9f, 0xf0, 0x20, + 0x7d, 0xe3, 0xab, 0x64, 0x8e, 0x4e, 0xea, 0x66, + 0x65, 0x76, 0x8b, 0xd7, 0x0f, 0x5f, 0x87, 0x67 + }, + .z = {1, 0} +}; + +static const struct ed25519_pt ed25519_neutral = { + .x = {0}, + .y = {1, 0}, + .t = {0}, + .z = {1, 0} +}; + +/* Conversion to and from projective coordinates */ +void ed25519_project(struct ed25519_pt *p, + const uint8_t *x, const uint8_t *y) +{ + f25519_copy(p->x, x); + f25519_copy(p->y, y); + f25519_load(p->z, 1); + f25519_mul__distinct(p->t, x, y); +} + +void ed25519_unproject(uint8_t *x, uint8_t *y, + const struct ed25519_pt *p) +{ + uint8_t z1[F25519_SIZE]; + + f25519_inv__distinct(z1, p->z); + f25519_mul__distinct(x, p->x, z1); + f25519_mul__distinct(y, p->y, z1); + + f25519_normalize(x); + f25519_normalize(y); +} + +/* Compress/uncompress points. We compress points by storing the x + * coordinate and the parity of the y coordinate. + * + * Rearranging the curve equation, we obtain explicit formulae for the + * coordinates: + * + * x = sqrt((y^2-1) / (1+dy^2)) + * y = sqrt((x^2+1) / (1-dx^2)) + * + * Where d = (-121665/121666), or: + * + * d = 370957059346694393431380835087545651895 + * 42113879843219016388785533085940283555 + */ + +static const uint8_t ed25519_d[F25519_SIZE] = { + 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, + 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00, + 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, + 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52 +}; + +void ed25519_pack(uint8_t *c, const uint8_t *x, const uint8_t *y) +{ + uint8_t tmp[F25519_SIZE]; + uint8_t parity; + + f25519_copy(tmp, x); + f25519_normalize(tmp); + parity = (tmp[0] & 1) << 7; + + f25519_copy(c, y); + f25519_normalize(c); + c[31] |= parity; +} + +uint8_t ed25519_try_unpack(uint8_t *x, uint8_t *y, const uint8_t *comp) +{ + const int parity = comp[31] >> 7; + uint8_t a[F25519_SIZE]; + uint8_t b[F25519_SIZE]; + uint8_t c[F25519_SIZE]; + + /* Unpack y */ + f25519_copy(y, comp); + y[31] &= 127; + + /* Compute c = y^2 */ + f25519_mul__distinct(c, y, y); + + /* Compute b = (1+dy^2)^-1 */ + f25519_mul__distinct(b, c, ed25519_d); + f25519_add(a, b, f25519_one); + f25519_inv__distinct(b, a); + + /* Compute a = y^2-1 */ + f25519_sub(a, c, f25519_one); + + /* Compute c = a*b = (y^2-1)/(1-dy^2) */ + f25519_mul__distinct(c, a, b); + + /* Compute a, b = +/-sqrt(c), if c is square */ + f25519_sqrt(a, c); + f25519_neg(b, a); + + /* Select one of them, based on the compressed parity bit */ + f25519_select(x, a, b, (a[0] ^ parity) & 1); + + /* Verify that x^2 = c */ + f25519_mul__distinct(a, x, x); + f25519_normalize(a); + f25519_normalize(c); + + return f25519_eq(a, c); +} + +/* k = 2d */ +static const uint8_t ed25519_k[F25519_SIZE] = { + 0x59, 0xf1, 0xb2, 0x26, 0x94, 0x9b, 0xd6, 0xeb, + 0x56, 0xb1, 0x83, 0x82, 0x9a, 0x14, 0xe0, 0x00, + 0x30, 0xd1, 0xf3, 0xee, 0xf2, 0x80, 0x8e, 0x19, + 0xe7, 0xfc, 0xdf, 0x56, 0xdc, 0xd9, 0x06, 0x24 +}; + +void ed25519_add(struct ed25519_pt *r, + const struct ed25519_pt *p1, const struct ed25519_pt *p2) +{ + /* Explicit formulas database: add-2008-hwcd-3 + * + * source 2008 Hisil--Wong--Carter--Dawson, + * http://eprint.iacr.org/2008/522, Section 3.1 + * appliesto extended-1 + * parameter k + * assume k = 2 d + * compute A = (Y1-X1)(Y2-X2) + * compute B = (Y1+X1)(Y2+X2) + * compute C = T1 k T2 + * compute D = Z1 2 Z2 + * compute E = B - A + * compute F = D - C + * compute G = D + C + * compute H = B + A + * compute X3 = E F + * compute Y3 = G H + * compute T3 = E H + * compute Z3 = F G + */ + uint8_t a[F25519_SIZE]; + uint8_t b[F25519_SIZE]; + uint8_t c[F25519_SIZE]; + uint8_t d[F25519_SIZE]; + uint8_t e[F25519_SIZE]; + uint8_t f[F25519_SIZE]; + uint8_t g[F25519_SIZE]; + uint8_t h[F25519_SIZE]; + + /* A = (Y1-X1)(Y2-X2) */ + f25519_sub(c, p1->y, p1->x); + f25519_sub(d, p2->y, p2->x); + f25519_mul__distinct(a, c, d); + + /* B = (Y1+X1)(Y2+X2) */ + f25519_add(c, p1->y, p1->x); + f25519_add(d, p2->y, p2->x); + f25519_mul__distinct(b, c, d); + + /* C = T1 k T2 */ + f25519_mul__distinct(d, p1->t, p2->t); + f25519_mul__distinct(c, d, ed25519_k); + + /* D = Z1 2 Z2 */ + f25519_mul__distinct(d, p1->z, p2->z); + f25519_add(d, d, d); + + /* E = B - A */ + f25519_sub(e, b, a); + + /* F = D - C */ + f25519_sub(f, d, c); + + /* G = D + C */ + f25519_add(g, d, c); + + /* H = B + A */ + f25519_add(h, b, a); + + /* X3 = E F */ + f25519_mul__distinct(r->x, e, f); + + /* Y3 = G H */ + f25519_mul__distinct(r->y, g, h); + + /* T3 = E H */ + f25519_mul__distinct(r->t, e, h); + + /* Z3 = F G */ + f25519_mul__distinct(r->z, f, g); +} + +static void ed25519_double(struct ed25519_pt *r, const struct ed25519_pt *p) +{ + /* Explicit formulas database: dbl-2008-hwcd + * + * source 2008 Hisil--Wong--Carter--Dawson, + * http://eprint.iacr.org/2008/522, Section 3.3 + * compute A = X1^2 + * compute B = Y1^2 + * compute C = 2 Z1^2 + * compute D = a A + * compute E = (X1+Y1)^2-A-B + * compute G = D + B + * compute F = G - C + * compute H = D - B + * compute X3 = E F + * compute Y3 = G H + * compute T3 = E H + * compute Z3 = F G + */ + uint8_t a[F25519_SIZE]; + uint8_t b[F25519_SIZE]; + uint8_t c[F25519_SIZE]; + uint8_t e[F25519_SIZE]; + uint8_t f[F25519_SIZE]; + uint8_t g[F25519_SIZE]; + uint8_t h[F25519_SIZE]; + + /* A = X1^2 */ + f25519_mul__distinct(a, p->x, p->x); + + /* B = Y1^2 */ + f25519_mul__distinct(b, p->y, p->y); + + /* C = 2 Z1^2 */ + f25519_mul__distinct(c, p->z, p->z); + f25519_add(c, c, c); + + /* D = a A (alter sign) */ + /* E = (X1+Y1)^2-A-B */ + f25519_add(f, p->x, p->y); + f25519_mul__distinct(e, f, f); + f25519_sub(e, e, a); + f25519_sub(e, e, b); + + /* G = D + B */ + f25519_sub(g, b, a); + + /* F = G - C */ + f25519_sub(f, g, c); + + /* H = D - B */ + f25519_neg(h, b); + f25519_sub(h, h, a); + + /* X3 = E F */ + f25519_mul__distinct(r->x, e, f); + + /* Y3 = G H */ + f25519_mul__distinct(r->y, g, h); + + /* T3 = E H */ + f25519_mul__distinct(r->t, e, h); + + /* Z3 = F G */ + f25519_mul__distinct(r->z, f, g); +} + +void ed25519_smult(struct ed25519_pt *r_out, const struct ed25519_pt *p, + const uint8_t *e) +{ + struct ed25519_pt r; + int i; + + ed25519_copy(&r, &ed25519_neutral); + + for (i = 255; i >= 0; i--) { + const uint8_t bit = (e[i >> 3] >> (i & 7)) & 1; + struct ed25519_pt s; + + ed25519_double(&r, &r); + ed25519_add(&s, &r, p); + + f25519_select(r.x, r.x, s.x, bit); + f25519_select(r.y, r.y, s.y, bit); + f25519_select(r.z, r.z, s.z, bit); + f25519_select(r.t, r.t, s.t, bit); + } + + ed25519_copy(r_out, &r); +} diff --git a/ed25519.h b/ed25519.h new file mode 100644 index 0000000..cd07042 --- /dev/null +++ b/ed25519.h @@ -0,0 +1,80 @@ +/* Edwards curve operations + * Daniel Beer , 9 Jan 2014 + * + * This file is in the public domain. + */ + +#ifndef ED25519_H_ +#define ED25519_H_ + +#include "f25519.h" + +/* This is not the Ed25519 signature system. Rather, we're implementing + * basic operations on the twisted Edwards curve over (Z mod 2^255-19): + * + * -x^2 + y^2 = 1 - (121665/121666)x^2y^2 + * + * With the positive-x base point y = 4/5. + * + * These functions will not leak secret data through timing. + * + * For more information, see: + * + * Bernstein, D.J. & Lange, T. (2007) "Faster addition and doubling on + * elliptic curves". Document ID: 95616567a6ba20f575c5f25e7cebaf83. + * + * Hisil, H. & Wong, K K. & Carter, G. & Dawson, E. (2008) "Twisted + * Edwards curves revisited". Advances in Cryptology, ASIACRYPT 2008, + * Vol. 5350, pp. 326-343. + */ + +/* Projective coordinates */ +struct ed25519_pt { + uint8_t x[F25519_SIZE]; + uint8_t y[F25519_SIZE]; + uint8_t t[F25519_SIZE]; + uint8_t z[F25519_SIZE]; +}; + +extern const struct ed25519_pt ed25519_base; + +/* Convert between projective and affine coordinates (x/y in F25519) */ +void ed25519_project(struct ed25519_pt *p, + const uint8_t *x, const uint8_t *y); + +void ed25519_unproject(uint8_t *x, uint8_t *y, + const struct ed25519_pt *p); + +/* Compress/uncompress points. try_unpack() will check that the + * compressed point is on the curve, returning 1 if the unpacked point + * is valid, and 0 otherwise. + */ +#define ED25519_PACK_SIZE F25519_SIZE + +void ed25519_pack(uint8_t *c, const uint8_t *x, const uint8_t *y); +uint8_t ed25519_try_unpack(uint8_t *x, uint8_t *y, const uint8_t *c); + +/* Add, double and scalar multiply */ +#define ED25519_EXPONENT_SIZE 32 + +/* Prepare an exponent by clamping appropriate bits */ +static inline void ed25519_prepare(uint8_t *e) +{ + e[0] &= 0xf8; + e[31] &= 0x7f; + e[31] |= 0x40; +} + +/* Order of the group generated by the base point */ +static inline void ed25519_copy(struct ed25519_pt *dst, + const struct ed25519_pt *src) +{ + memcpy(dst, src, sizeof(*dst)); +} + +void ed25519_add(struct ed25519_pt *r, + const struct ed25519_pt *a, const struct ed25519_pt *b); +void ed25519_smult(struct ed25519_pt *r, const struct ed25519_pt *a, + const uint8_t *e); + +#endif diff --git a/edsign.c b/edsign.c new file mode 100644 index 0000000..37a52a0 --- /dev/null +++ b/edsign.c @@ -0,0 +1,158 @@ +/* Edwards curve signature system + * Daniel Beer , 22 Apr 2014 + * + * This file is in the public domain. + */ + +#include "ed25519.h" +#include "sha512.h" +#include "fprime.h" +#include "edsign.h" + +#define EXPANDED_SIZE 64 + +static const uint8_t ed25519_order[FPRIME_SIZE] = { + 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, + 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 +}; + +static void expand_key(uint8_t *expanded, const uint8_t *secret) +{ + struct sha512_state s; + + sha512_init(&s); + sha512_add(&s, secret, EDSIGN_SECRET_KEY_SIZE); + sha512_final(&s, expanded); + + ed25519_prepare(expanded); +} + +static uint8_t upp(struct ed25519_pt *p, const uint8_t *packed) +{ + uint8_t x[F25519_SIZE]; + uint8_t y[F25519_SIZE]; + uint8_t ok = ed25519_try_unpack(x, y, packed); + + ed25519_project(p, x, y); + return ok; +} + +static void pp(uint8_t *packed, const struct ed25519_pt *p) +{ + uint8_t x[F25519_SIZE]; + uint8_t y[F25519_SIZE]; + + ed25519_unproject(x, y, p); + ed25519_pack(packed, x, y); +} + +static void sm_pack(uint8_t *r, const uint8_t *k) +{ + struct ed25519_pt p; + + ed25519_smult(&p, &ed25519_base, k); + pp(r, &p); +} + +void edsign_sec_to_pub(void *pub, const void *secret) +{ + uint8_t expanded[EXPANDED_SIZE]; + + expand_key(expanded, secret); + sm_pack(pub, expanded); +} + +static void save_hash(struct sha512_state *s, uint8_t *out) +{ + void *hash; + + hash = sha512_final_get(s); + fprime_from_bytes(out, hash, SHA512_HASH_SIZE, ed25519_order); +} + +static void generate_k(uint8_t *k, const uint8_t *kgen_key, + const uint8_t *message, size_t len) +{ + struct sha512_state s; + + sha512_init(&s); + sha512_add(&s, kgen_key, 32); + sha512_add(&s, message, len); + save_hash(&s, k); +} + +static void hash_message(uint8_t *z, const uint8_t *r, const uint8_t *a, + const uint8_t *m, size_t len) +{ + struct sha512_state s; + + sha512_init(&s); + sha512_add(&s, r, 32); + sha512_add(&s, a, 32); + sha512_add(&s, m, len); + save_hash(&s, z); +} + +void edsign_sign(uint8_t *signature, const uint8_t *pub, + const uint8_t *secret, + const uint8_t *message, size_t len) +{ + uint8_t expanded[EXPANDED_SIZE]; + uint8_t e[FPRIME_SIZE]; + uint8_t s[FPRIME_SIZE]; + uint8_t k[FPRIME_SIZE]; + uint8_t z[FPRIME_SIZE]; + + expand_key(expanded, secret); + + /* Generate k and R = kB */ + generate_k(k, expanded + 32, message, len); + sm_pack(signature, k); + + /* Compute z = H(R, A, M) */ + hash_message(z, signature, pub, message, len); + + /* Obtain e */ + fprime_from_bytes(e, expanded, 32, ed25519_order); + + /* Compute s = ze + k */ + fprime_mul(s, z, e, ed25519_order); + fprime_add(s, k, ed25519_order); + memcpy(signature + 32, s, 32); +} + +void edsign_verify_init(struct edsign_verify_state *st, const void *sig, + const void *pub) +{ + sha512_init(&st->sha); + sha512_add(&st->sha, sig, 32); + sha512_add(&st->sha, pub, 32); +} + +bool edsign_verify(struct edsign_verify_state *st, const void *sig, const void *pub) +{ + struct ed25519_pt p; + struct ed25519_pt q; + uint8_t lhs[F25519_SIZE]; + uint8_t rhs[F25519_SIZE]; + uint8_t z[FPRIME_SIZE]; + uint8_t ok = 1; + + /* Compute z = H(R, A, M) */ + save_hash(&st->sha, z); + + /* sB = (ze + k)B = ... */ + sm_pack(lhs, sig + 32); + + /* ... = zA + R */ + ok &= upp(&p, pub); + ed25519_smult(&p, &p, z); + ok &= upp(&q, sig); + ed25519_add(&p, &p, &q); + pp(rhs, &p); + + /* Equal? */ + return ok & f25519_eq(lhs, rhs); +} diff --git a/edsign.h b/edsign.h new file mode 100644 index 0000000..6def058 --- /dev/null +++ b/edsign.h @@ -0,0 +1,64 @@ +/* Edwards curve signature system + * Daniel Beer , 22 Apr 2014 + * + * This file is in the public domain. + */ + +#ifndef EDSIGN_H_ +#define EDSIGN_H_ + +#include +#include +#include "sha512.h" + +/* This is the Ed25519 signature system, as described in: + * + * Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin + * Yang. High-speed high-security signatures. Journal of Cryptographic + * Engineering 2 (2012), 77–89. Document ID: + * a1a62a2f76d23f65d622484ddd09caf8. URL: + * http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26. + * + * The format and calculation of signatures is compatible with the + * Ed25519 implementation in SUPERCOP. Note, however, that our secret + * keys are half the size: we don't store a copy of the public key in + * the secret key (we generate it on demand). + */ + +/* Any string of 32 random bytes is a valid secret key. There is no + * clamping of bits, because we don't use the key directly as an + * exponent (the exponent is derived from part of a key expansion). + */ +#define EDSIGN_SECRET_KEY_SIZE 32 + +/* Given a secret key, produce the public key (a packed Edwards-curve + * point). + */ +#define EDSIGN_PUBLIC_KEY_SIZE 32 + +void edsign_sec_to_pub(void *pub, const void *secret); + +/* Produce a signature for a message. */ +#define EDSIGN_SIGNATURE_SIZE 64 + +void edsign_sign(uint8_t *signature, const uint8_t *pub, + const uint8_t *secret, + const uint8_t *message, size_t len); + +struct edsign_verify_state { + struct sha512_state sha; +}; + +void edsign_verify_init(struct edsign_verify_state *st, const void *sig, + const void *pub); + +static inline void +edsign_verify_add(struct edsign_verify_state *st, const void *data, int len) +{ + sha512_add(&st->sha, data, len); +} + +/* Verify a message signature. Returns non-zero if ok. */ +bool edsign_verify(struct edsign_verify_state *st, const void *sig, const void *pub); + +#endif diff --git a/f25519.c b/f25519.c new file mode 100644 index 0000000..6ce9bdb --- /dev/null +++ b/f25519.c @@ -0,0 +1,307 @@ +/* Arithmetic mod p = 2^255-19 + * Daniel Beer , 5 Jan 2014 + * + * This file is in the public domain. + */ + +#include "f25519.h" + +const uint8_t f25519_one[F25519_SIZE] = {1}; + +void f25519_load(uint8_t *x, uint32_t c) +{ + int i; + + for (i = 0; i < sizeof(c); i++) { + x[i] = c; + c >>= 8; + } + + for (; i < F25519_SIZE; i++) + x[i] = 0; +} + +void f25519_normalize(uint8_t *x) +{ + uint8_t minusp[F25519_SIZE]; + uint16_t c; + int i; + + /* Reduce using 2^255 = 19 mod p */ + c = (x[31] >> 7) * 19; + x[31] &= 127; + + for (i = 0; i < F25519_SIZE; i++) { + c += x[i]; + x[i] = c; + c >>= 8; + } + + /* The number is now less than 2^255 + 18, and therefore less than + * 2p. Try subtracting p, and conditionally load the subtracted + * value if underflow did not occur. + */ + c = 19; + + for (i = 0; i + 1 < F25519_SIZE; i++) { + c += x[i]; + minusp[i] = c; + c >>= 8; + } + + c += ((uint16_t)x[i]) - 128; + minusp[31] = c; + + /* Load x-p if no underflow */ + f25519_select(x, minusp, x, (c >> 15) & 1); +} + +uint8_t f25519_eq(const uint8_t *x, const uint8_t *y) +{ + uint8_t sum = 0; + int i; + + for (i = 0; i < F25519_SIZE; i++) + sum |= x[i] ^ y[i]; + + sum |= (sum >> 4); + sum |= (sum >> 2); + sum |= (sum >> 1); + + return (sum ^ 1) & 1; +} + +void f25519_select(uint8_t *dst, + const uint8_t *zero, const uint8_t *one, + uint8_t condition) +{ + const uint8_t mask = -condition; + int i; + + for (i = 0; i < F25519_SIZE; i++) + dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i])); +} + +void f25519_add(uint8_t *r, const uint8_t *a, const uint8_t *b) +{ + uint16_t c = 0; + int i; + + /* Add */ + for (i = 0; i < F25519_SIZE; i++) { + c >>= 8; + c += ((uint16_t)a[i]) + ((uint16_t)b[i]); + r[i] = c; + } + + /* Reduce with 2^255 = 19 mod p */ + r[31] &= 127; + c = (c >> 7) * 19; + + for (i = 0; i < F25519_SIZE; i++) { + c += r[i]; + r[i] = c; + c >>= 8; + } +} + +void f25519_sub(uint8_t *r, const uint8_t *a, const uint8_t *b) +{ + uint32_t c = 0; + int i; + + /* Calculate a + 2p - b, to avoid underflow */ + c = 218; + for (i = 0; i + 1 < F25519_SIZE; i++) { + c += 65280 + ((uint32_t)a[i]) - ((uint32_t)b[i]); + r[i] = c; + c >>= 8; + } + + c += ((uint32_t)a[31]) - ((uint32_t)b[31]); + r[31] = c & 127; + c = (c >> 7) * 19; + + for (i = 0; i < F25519_SIZE; i++) { + c += r[i]; + r[i] = c; + c >>= 8; + } +} + +void f25519_neg(uint8_t *r, const uint8_t *a) +{ + uint32_t c = 0; + int i; + + /* Calculate 2p - a, to avoid underflow */ + c = 218; + for (i = 0; i + 1 < F25519_SIZE; i++) { + c += 65280 - ((uint32_t)a[i]); + r[i] = c; + c >>= 8; + } + + c -= ((uint32_t)a[31]); + r[31] = c & 127; + c = (c >> 7) * 19; + + for (i = 0; i < F25519_SIZE; i++) { + c += r[i]; + r[i] = c; + c >>= 8; + } +} + +void f25519_mul__distinct(uint8_t *r, const uint8_t *a, const uint8_t *b) +{ + uint32_t c = 0; + int i; + + for (i = 0; i < F25519_SIZE; i++) { + int j; + + c >>= 8; + for (j = 0; j <= i; j++) + c += ((uint32_t)a[j]) * ((uint32_t)b[i - j]); + + for (; j < F25519_SIZE; j++) + c += ((uint32_t)a[j]) * + ((uint32_t)b[i + F25519_SIZE - j]) * 38; + + r[i] = c; + } + + r[31] &= 127; + c = (c >> 7) * 19; + + for (i = 0; i < F25519_SIZE; i++) { + c += r[i]; + r[i] = c; + c >>= 8; + } +} + +static void f25519_mul_c(uint8_t *r, const uint8_t *a, uint32_t b) +{ + uint32_t c = 0; + int i; + + for (i = 0; i < F25519_SIZE; i++) { + c >>= 8; + c += b * ((uint32_t)a[i]); + r[i] = c; + } + + r[31] &= 127; + c >>= 7; + c *= 19; + + for (i = 0; i < F25519_SIZE; i++) { + c += r[i]; + r[i] = c; + c >>= 8; + } +} + +void f25519_inv__distinct(uint8_t *r, const uint8_t *x) +{ + uint8_t s[F25519_SIZE]; + int i; + + /* This is a prime field, so by Fermat's little theorem: + * + * x^(p-1) = 1 mod p + * + * Therefore, raise to (p-2) = 2^255-21 to get a multiplicative + * inverse. + * + * This is a 255-bit binary number with the digits: + * + * 11111111... 01011 + * + * We compute the result by the usual binary chain, but + * alternate between keeping the accumulator in r and s, so as + * to avoid copying temporaries. + */ + + /* 1 1 */ + f25519_mul__distinct(s, x, x); + f25519_mul__distinct(r, s, x); + + /* 1 x 248 */ + for (i = 0; i < 248; i++) { + f25519_mul__distinct(s, r, r); + f25519_mul__distinct(r, s, x); + } + + /* 0 */ + f25519_mul__distinct(s, r, r); + + /* 1 */ + f25519_mul__distinct(r, s, s); + f25519_mul__distinct(s, r, x); + + /* 0 */ + f25519_mul__distinct(r, s, s); + + /* 1 */ + f25519_mul__distinct(s, r, r); + f25519_mul__distinct(r, s, x); + + /* 1 */ + f25519_mul__distinct(s, r, r); + f25519_mul__distinct(r, s, x); +} + +/* Raise x to the power of (p-5)/8 = 2^252-3, using s for temporary + * storage. + */ +static void exp2523(uint8_t *r, const uint8_t *x, uint8_t *s) +{ + int i; + + /* This number is a 252-bit number with the binary expansion: + * + * 111111... 01 + */ + + /* 1 1 */ + f25519_mul__distinct(r, x, x); + f25519_mul__distinct(s, r, x); + + /* 1 x 248 */ + for (i = 0; i < 248; i++) { + f25519_mul__distinct(r, s, s); + f25519_mul__distinct(s, r, x); + } + + /* 0 */ + f25519_mul__distinct(r, s, s); + + /* 1 */ + f25519_mul__distinct(s, r, r); + f25519_mul__distinct(r, s, x); +} + +void f25519_sqrt(uint8_t *r, const uint8_t *a) +{ + uint8_t v[F25519_SIZE]; + uint8_t i[F25519_SIZE]; + uint8_t x[F25519_SIZE]; + uint8_t y[F25519_SIZE]; + + /* v = (2a)^((p-5)/8) [x = 2a] */ + f25519_mul_c(x, a, 2); + exp2523(v, x, y); + + /* i = 2av^2 - 1 */ + f25519_mul__distinct(y, v, v); + f25519_mul__distinct(i, x, y); + f25519_load(y, 1); + f25519_sub(i, i, y); + + /* r = avi */ + f25519_mul__distinct(x, v, a); + f25519_mul__distinct(r, x, i); +} diff --git a/f25519.h b/f25519.h new file mode 100644 index 0000000..95b01d5 --- /dev/null +++ b/f25519.h @@ -0,0 +1,82 @@ +/* Arithmetic mod p = 2^255-19 + * Daniel Beer , 8 Jan 2014 + * + * This file is in the public domain. + */ + +#ifndef F25519_H_ +#define F25519_H_ + +#include +#include + +/* Field elements are represented as little-endian byte strings. All + * operations have timings which are independent of input data, so they + * can be safely used for cryptography. + * + * Computation is performed on un-normalized elements. These are byte + * strings which fall into the range 0 <= x < 2p. Use f25519_normalize() + * to convert to a value 0 <= x < p. + * + * Elements received from the outside may greater even than 2p. + * f25519_normalize() will correctly deal with these numbers too. + */ +#define F25519_SIZE 32 + +/* Identity constants */ +extern const uint8_t f25519_one[F25519_SIZE]; + +/* Load a small constant */ +void f25519_load(uint8_t *x, uint32_t c); + +/* Copy two points */ +static inline void f25519_copy(uint8_t *x, const uint8_t *a) +{ + memcpy(x, a, F25519_SIZE); +} + +/* Normalize a field point x < 2*p by subtracting p if necessary */ +void f25519_normalize(uint8_t *x); + +/* Compare two field points in constant time. Return one if equal, zero + * otherwise. This should be performed only on normalized values. + */ +uint8_t f25519_eq(const uint8_t *x, const uint8_t *y); + +/* Conditional copy. If condition == 0, then zero is copied to dst. If + * condition == 1, then one is copied to dst. Any other value results in + * undefined behaviour. + */ +void f25519_select(uint8_t *dst, + const uint8_t *zero, const uint8_t *one, + uint8_t condition); + +/* Add/subtract two field points. The three pointers are not required to + * be distinct. + */ +void f25519_add(uint8_t *r, const uint8_t *a, const uint8_t *b); +void f25519_sub(uint8_t *r, const uint8_t *a, const uint8_t *b); + +/* Unary negation */ +void f25519_neg(uint8_t *r, const uint8_t *a); + +/* Multiply two field points. The __distinct variant is used when r is + * known to be in a different location to a and b. + */ +void f25519_mul__distinct(uint8_t *r, const uint8_t *a, const uint8_t *b); + +/* Take the reciprocal of a field point. The __distinct variant is used + * when r is known to be in a different location to x. + */ +void f25519_inv__distinct(uint8_t *r, const uint8_t *x); + +/* Compute one of the square roots of the field element, if the element + * is square. The other square is -r. + * + * If the input is not square, the returned value is a valid field + * element, but not the correct answer. If you don't already know that + * your element is square, you should square the return value and test. + */ +void f25519_sqrt(uint8_t *r, const uint8_t *x); + +#endif diff --git a/fprime.c b/fprime.c new file mode 100644 index 0000000..50e1a08 --- /dev/null +++ b/fprime.c @@ -0,0 +1,140 @@ +/* Arithmetic in prime fields + * Daniel Beer , 10 Jan 2014 + * + * This file is in the public domain. + */ + +#include "fprime.h" + +static void raw_add(uint8_t *x, const uint8_t *p) +{ + uint16_t c = 0; + int i; + + for (i = 0; i < FPRIME_SIZE; i++) { + c += ((uint16_t)x[i]) + ((uint16_t)p[i]); + x[i] = c; + c >>= 8; + } +} + +static void raw_try_sub(uint8_t *x, const uint8_t *p) +{ + uint8_t minusp[FPRIME_SIZE]; + uint16_t c = 0; + int i; + + for (i = 0; i < FPRIME_SIZE; i++) { + c = ((uint16_t)x[i]) - ((uint16_t)p[i]) - c; + minusp[i] = c; + c = (c >> 8) & 1; + } + + fprime_select(x, minusp, x, c); +} + +/* Warning: this function is variable-time */ +static int prime_msb(const uint8_t *p) +{ + int i; + uint8_t x; + + for (i = FPRIME_SIZE - 1; i >= 0; i--) + if (p[i]) + break; + + x = p[i]; + i <<= 3; + + while (x) { + x >>= 1; + i++; + } + + return i - 1; +} + +/* Warning: this function may be variable-time in the argument n */ +static void shift_n_bits(uint8_t *x, int n) +{ + uint16_t c = 0; + int i; + + for (i = 0; i < FPRIME_SIZE; i++) { + c |= ((uint16_t)x[i]) << n; + x[i] = c; + c >>= 8; + } +} + +static inline int min_int(int a, int b) +{ + return a < b ? a : b; +} + +void fprime_from_bytes(uint8_t *n, + const uint8_t *x, size_t len, + const uint8_t *modulus) +{ + const int preload_total = min_int(prime_msb(modulus) - 1, len << 3); + const int preload_bytes = preload_total >> 3; + const int preload_bits = preload_total & 7; + const int rbits = (len << 3) - preload_total; + int i; + + memset(n, 0, FPRIME_SIZE); + + for (i = 0; i < preload_bytes; i++) + n[i] = x[len - preload_bytes + i]; + + if (preload_bits) { + shift_n_bits(n, preload_bits); + n[0] |= x[len - preload_bytes - 1] >> (8 - preload_bits); + } + + for (i = rbits - 1; i >= 0; i--) { + const uint8_t bit = (x[i >> 3] >> (i & 7)) & 1; + + shift_n_bits(n, 1); + n[0] |= bit; + raw_try_sub(n, modulus); + } +} + +void fprime_select(uint8_t *dst, + const uint8_t *zero, const uint8_t *one, + uint8_t condition) +{ + const uint8_t mask = -condition; + int i; + + for (i = 0; i < FPRIME_SIZE; i++) + dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i])); +} + +void fprime_add(uint8_t *r, const uint8_t *a, const uint8_t *modulus) +{ + raw_add(r, a); + raw_try_sub(r, modulus); +} + +void fprime_mul(uint8_t *r, const uint8_t *a, const uint8_t *b, + const uint8_t *modulus) +{ + int i; + + memset(r, 0, FPRIME_SIZE); + + for (i = prime_msb(modulus); i >= 0; i--) { + const uint8_t bit = (b[i >> 3] >> (i & 7)) & 1; + uint8_t plusa[FPRIME_SIZE]; + + shift_n_bits(r, 1); + raw_try_sub(r, modulus); + + fprime_copy(plusa, r); + fprime_add(plusa, a, modulus); + + fprime_select(r, r, plusa, bit); + } +} diff --git a/fprime.h b/fprime.h new file mode 100644 index 0000000..67012f1 --- /dev/null +++ b/fprime.h @@ -0,0 +1,56 @@ +/* Arithmetic in prime fields + * Daniel Beer , 10 Jan 2014 + * + * This file is in the public domain. + */ + +#ifndef FPRIME_H_ +#define FPRIME_H_ + +#include +#include + +/* Maximum size of a field element (or a prime). Field elements are + * always manipulated and stored in normalized form, with 0 <= x < p. + * You can use normalize() to convert a denormalized bitstring to normal + * form. + * + * Operations are constant with respect to the value of field elements, + * but not with respect to the modulus. + * + * The modulus is a number p, such that 2p-1 fits in FPRIME_SIZE bytes. + */ +#define FPRIME_SIZE 32 + +/* Load a large constant */ +void fprime_from_bytes(uint8_t *x, + const uint8_t *in, size_t len, + const uint8_t *modulus); + +/* Copy an element */ +static inline void fprime_copy(uint8_t *x, const uint8_t *a) +{ + memcpy(x, a, FPRIME_SIZE); +} + +/* Compare two field points in constant time. Return one if equal, zero + * otherwise. This should be performed only on normalized values. + */ +uint8_t fprime_eq(const uint8_t *x, const uint8_t *y); + +/* Conditional copy. If condition == 0, then zero is copied to dst. If + * condition == 1, then one is copied to dst. Any other value results in + * undefined behaviour. + */ +void fprime_select(uint8_t *dst, + const uint8_t *zero, const uint8_t *one, + uint8_t condition); + +/* Add one value to another. The two pointers must be distinct. */ +void fprime_add(uint8_t *r, const uint8_t *a, const uint8_t *modulus); + +/* Multiply two values to get a third. r must be distinct from a and b */ +void fprime_mul(uint8_t *r, const uint8_t *a, const uint8_t *b, + const uint8_t *modulus); + +#endif diff --git a/main.c b/main.c new file mode 100644 index 0000000..d177e97 --- /dev/null +++ b/main.c @@ -0,0 +1,423 @@ +/* + * usign - tiny signify replacement + * + * Copyright (C) 2015 Felix Fietkau + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "base64.h" +#include "edsign.h" +#include "ed25519.h" + +struct pubkey { + char pkalg[2]; + uint8_t fingerprint[8]; + uint8_t pubkey[EDSIGN_PUBLIC_KEY_SIZE]; +}; + +struct seckey { + char pkalg[2]; + char kdfalg[2]; + uint32_t kdfrounds; + uint8_t salt[16]; + uint8_t checksum[8]; + uint8_t fingerprint[8]; + uint8_t seckey[64]; +}; + +struct sig { + char pkalg[2]; + uint8_t fingerprint[8]; + uint8_t sig[EDSIGN_SIGNATURE_SIZE]; +}; + +static const char *pubkeyfile; +static const char *pubkeydir; +static const char *sigfile; +static const char *seckeyfile; +static bool quiet; +static enum { + CMD_NONE, + CMD_VERIFY, + CMD_SIGN, + CMD_FINGERPRINT, + CMD_GENERATE, +} cmd = CMD_NONE; + +static uint64_t fingerprint_u64(uint8_t *data) +{ + uint64_t val = 0; + +#define ADD(_v) val = (val << 8) | _v + ADD(data[0]); + ADD(data[1]); + ADD(data[2]); + ADD(data[3]); + ADD(data[4]); + ADD(data[5]); + ADD(data[6]); + ADD(data[7]); +#undef ADD + + return val; +} + +static void +file_error(const char *filename, bool _read) +{ + if (!quiet || cmd != CMD_VERIFY) + fprintf(stderr, "Cannot open file '%s' for %s\n", filename, + _read ? "reading" : "writing"); + exit(1); +} + +static FILE * +open_file(const char *filename, bool _read) +{ + FILE *f; + + if (!strcmp(filename, "-")) + return _read ? stdin : stdout; + + f = fopen(filename, _read ? "r" : "w"); + if (!f) + file_error(filename, _read); + + return f; +} + +static void +get_file(const char *filename, char *buf, int buflen) +{ + FILE *f = open_file(filename, true); + int len; + + while (1) { + char *cur = fgets(buf, buflen, f); + + if (!cur) { + fprintf(stderr, "Premature end of file\n"); + exit(1); + } + + if (strchr(buf, '\n')) + break; + } + + len = fread(buf, 1, buflen - 1, f); + buf[len] = 0; +} + +static bool +get_base64_file(const char *file, void *dest, int size, void *buf, int buflen) +{ + get_file(file, buf, buflen - 1); + return b64_pton(buf, dest, size) == size; +} + +static int verify(const char *msgfile) +{ + struct pubkey pkey; + struct sig sig; + struct edsign_verify_state vst; + FILE *f; + char buf[512]; + + f = open_file(msgfile, true); + if (!f) { + fprintf(stderr, "Cannot open message file\n"); + return 1; + } + + if (!get_base64_file(sigfile, &sig, sizeof(sig), buf, sizeof(buf)) || + memcmp(sig.pkalg, "Ed", 2) != 0) { + fprintf(stderr, "Failed to decode signature\n"); + return 1; + } + + if (!pubkeyfile) { + snprintf(buf, sizeof(buf), "%s/%"PRIx64, pubkeydir, + fingerprint_u64(sig.fingerprint)); + pubkeyfile = buf; + } + + if (!get_base64_file(pubkeyfile, &pkey, sizeof(pkey), buf, sizeof(buf)) || + memcmp(pkey.pkalg, "Ed", 2) != 0) { + fprintf(stderr, "Failed to decode public key\n"); + return 1; + } + + edsign_verify_init(&vst, sig.sig, pkey.pubkey); + + while (!feof(f)) { + int len = fread(buf, 1, sizeof(buf), f); + edsign_verify_add(&vst, buf, len); + } + fclose(f); + + if (!edsign_verify(&vst, sig.sig, pkey.pubkey)) { + if (!quiet) + fprintf(stderr, "verification failed\n"); + return 1; + } + + if (!quiet) + fprintf(stderr, "OK\n"); + return 0; +} + +static int sign(const char *msgfile) +{ + struct seckey skey; + struct sig sig = { + .pkalg = "Ed", + }; + struct stat st; + char buf[512]; + void *pubkey = buf; + long mlen; + void *m; + int mfd; + FILE *out; + + if (!get_base64_file(seckeyfile, &skey, sizeof(skey), buf, sizeof(buf)) || + memcmp(skey.pkalg, "Ed", 2) != 0) { + fprintf(stderr, "Failed to decode secret key\n"); + return 1; + } + + if (skey.kdfrounds) { + fprintf(stderr, "Password protected secret keys are not supported\n"); + return 1; + } + + mfd = open(msgfile, O_RDONLY, 0); + if (mfd < 0 || fstat(mfd, &st) < 0 || + (m = mmap(0, st.st_size, PROT_READ, MAP_PRIVATE, mfd, 0)) == MAP_FAILED) { + if (mfd >= 0) + close(mfd); + perror("Cannot open message file"); + return 1; + } + mlen = st.st_size; + + memcpy(sig.fingerprint, skey.fingerprint, sizeof(sig.fingerprint)); + edsign_sec_to_pub(pubkey, skey.seckey); + edsign_sign(sig.sig, pubkey, skey.seckey, m, mlen); + munmap(m, mlen); + close(mfd); + + if (b64_ntop(&sig, sizeof(sig), buf, sizeof(buf)) < 0) + return 1; + + out = open_file(sigfile, false); + fprintf(out, "untrusted comment: signed by key %"PRIx64"\n%s\n", fingerprint_u64(sig.fingerprint), buf); + fclose(out); + + return 0; +} + +static int fingerprint(void) +{ + struct seckey skey; + struct pubkey pkey; + struct sig sig; + char buf[512]; + uint8_t *fp; + + if (seckeyfile && + get_base64_file(seckeyfile, &skey, sizeof(skey), buf, sizeof(buf))) + fp = skey.fingerprint; + else if (pubkeyfile && + get_base64_file(pubkeyfile, &pkey, sizeof(pkey), buf, sizeof(buf))) + fp = pkey.fingerprint; + else if (sigfile && + get_base64_file(sigfile, &sig, sizeof(sig), buf, sizeof(buf))) + fp = sig.fingerprint; + else + return 1; + + fprintf(stdout, "%"PRIx64"\n", fingerprint_u64(fp)); + return 0; +} + +static int generate(void) +{ + struct seckey skey = { + .pkalg = "Ed", + .kdfalg = "BK", + .kdfrounds = 0, + }; + struct pubkey pkey = { + .pkalg = "Ed", + }; + struct sha512_state s; + char buf[512]; + FILE *f; + + f = fopen("/dev/urandom", "r"); + if (!f || + fread(skey.fingerprint, sizeof(skey.fingerprint), 1, f) != 1 || + fread(skey.seckey, EDSIGN_SECRET_KEY_SIZE, 1, f) != 1 || + fread(skey.salt, sizeof(skey.salt), 1, f) != 1) { + fprintf(stderr, "Can't read data from /dev/urandom\n"); + return 1; + } + if (f) + fclose(f); + + ed25519_prepare(skey.seckey); + edsign_sec_to_pub(skey.seckey + 32, skey.seckey); + + sha512_init(&s); + sha512_add(&s, skey.seckey, sizeof(skey.seckey)); + memcpy(skey.checksum, sha512_final_get(&s), sizeof(skey.checksum)); + + if (b64_ntop(&skey, sizeof(skey), buf, sizeof(buf)) < 0) + return 1; + + f = open_file(seckeyfile, false); + fprintf(f, "untrusted comment: secret key %"PRIx64"\n%s\n", fingerprint_u64(skey.fingerprint), buf); + fclose(f); + + memcpy(pkey.fingerprint, skey.fingerprint, sizeof(pkey.fingerprint)); + memcpy(pkey.pubkey, skey.seckey + 32, sizeof(pkey.pubkey)); + + if (b64_ntop(&pkey, sizeof(pkey), buf, sizeof(buf)) < 0) + return 1; + + f = open_file(pubkeyfile, false); + fprintf(f, "untrusted comment: public key %"PRIx64"\n%s\n", fingerprint_u64(pkey.fingerprint), buf); + fclose(f); + + return 0; +} + +static int usage(const char *cmd) +{ + fprintf(stderr, + "Usage: %s \n" + "Commands:\n" + " -V: verify (needs at least -m and -p|-P)\n" + " -S: sign (needs at least -m and -s)\n" + " -F: print key fingerprint of public/secret key or signature\n" + " -G: generate a new keypair\n" + "Options:\n" + " -m : message file\n" + " -p : public key file (verify/fingerprint only)\n" + " -P : public key directory (verify only)\n" + " -q: quiet (do not print verification result, use return code only)\n" + " -s : secret key file (sign/fingerprint only)\n" + " -x : signature file (defaults to .sig)\n" + "\n", + cmd); + return 1; +} + +static void set_cmd(const char *prog, int val) +{ + if (cmd != CMD_NONE) + exit(usage(prog)); + + cmd = val; +} + +int main(int argc, char **argv) +{ + const char *msgfile = NULL; + int ch; + + while ((ch = getopt(argc, argv, "FGSVm:P:p:qs:x:")) != -1) { + switch (ch) { + case 'V': + set_cmd(argv[0], CMD_VERIFY); + break; + case 'S': + set_cmd(argv[0], CMD_SIGN); + break; + case 'F': + set_cmd(argv[0], CMD_FINGERPRINT); + break; + case 'G': + set_cmd(argv[0], CMD_GENERATE); + break; + case 'm': + msgfile = optarg; + break; + case 'P': + pubkeydir = optarg; + break; + case 'p': + pubkeyfile = optarg; + break; + case 's': + seckeyfile = optarg; + break; + case 'x': + sigfile = optarg; + break; + case 'q': + quiet = true; + break; + default: + return usage(argv[0]); + } + } + + if (!sigfile && msgfile) { + char *buf = alloca(strlen(msgfile) + 5); + + if (!strcmp(msgfile, "-")) { + fprintf(stderr, "Need signature file when reading message from stdin\n"); + return 1; + } + + sprintf(buf, "%s.sig", msgfile); + sigfile = buf; + } + + switch (cmd) { + case CMD_VERIFY: + if ((!pubkeyfile && !pubkeydir) || !msgfile) + return usage(argv[0]); + return verify(msgfile); + case CMD_SIGN: + if (!seckeyfile || !msgfile || !sigfile) + return usage(argv[0]); + return sign(msgfile); + case CMD_FINGERPRINT: + if (!!seckeyfile + !!pubkeyfile + !!sigfile != 1) { + fprintf(stderr, "Need one secret/public key or signature\n"); + return usage(argv[0]); + } + return fingerprint(); + case CMD_GENERATE: + if (!seckeyfile || !pubkeyfile) + return usage(argv[0]); + return generate(); + default: + return usage(argv[0]); + } +} diff --git a/sha512.c b/sha512.c new file mode 100644 index 0000000..68a9e65 --- /dev/null +++ b/sha512.c @@ -0,0 +1,258 @@ +/* + * Copyright (C) 2015 Felix Fietkau + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* SHA512 + * Daniel Beer , 22 Apr 2014 + * + * This file is in the public domain. + */ + +#include "sha512.h" + +static const uint64_t sha512_initial_state[8] = { + 0x6a09e667f3bcc908LL, 0xbb67ae8584caa73bLL, + 0x3c6ef372fe94f82bLL, 0xa54ff53a5f1d36f1LL, + 0x510e527fade682d1LL, 0x9b05688c2b3e6c1fLL, + 0x1f83d9abfb41bd6bLL, 0x5be0cd19137e2179LL, +}; + +static const uint64_t round_k[80] = { + 0x428a2f98d728ae22LL, 0x7137449123ef65cdLL, + 0xb5c0fbcfec4d3b2fLL, 0xe9b5dba58189dbbcLL, + 0x3956c25bf348b538LL, 0x59f111f1b605d019LL, + 0x923f82a4af194f9bLL, 0xab1c5ed5da6d8118LL, + 0xd807aa98a3030242LL, 0x12835b0145706fbeLL, + 0x243185be4ee4b28cLL, 0x550c7dc3d5ffb4e2LL, + 0x72be5d74f27b896fLL, 0x80deb1fe3b1696b1LL, + 0x9bdc06a725c71235LL, 0xc19bf174cf692694LL, + 0xe49b69c19ef14ad2LL, 0xefbe4786384f25e3LL, + 0x0fc19dc68b8cd5b5LL, 0x240ca1cc77ac9c65LL, + 0x2de92c6f592b0275LL, 0x4a7484aa6ea6e483LL, + 0x5cb0a9dcbd41fbd4LL, 0x76f988da831153b5LL, + 0x983e5152ee66dfabLL, 0xa831c66d2db43210LL, + 0xb00327c898fb213fLL, 0xbf597fc7beef0ee4LL, + 0xc6e00bf33da88fc2LL, 0xd5a79147930aa725LL, + 0x06ca6351e003826fLL, 0x142929670a0e6e70LL, + 0x27b70a8546d22ffcLL, 0x2e1b21385c26c926LL, + 0x4d2c6dfc5ac42aedLL, 0x53380d139d95b3dfLL, + 0x650a73548baf63deLL, 0x766a0abb3c77b2a8LL, + 0x81c2c92e47edaee6LL, 0x92722c851482353bLL, + 0xa2bfe8a14cf10364LL, 0xa81a664bbc423001LL, + 0xc24b8b70d0f89791LL, 0xc76c51a30654be30LL, + 0xd192e819d6ef5218LL, 0xd69906245565a910LL, + 0xf40e35855771202aLL, 0x106aa07032bbd1b8LL, + 0x19a4c116b8d2d0c8LL, 0x1e376c085141ab53LL, + 0x2748774cdf8eeb99LL, 0x34b0bcb5e19b48a8LL, + 0x391c0cb3c5c95a63LL, 0x4ed8aa4ae3418acbLL, + 0x5b9cca4f7763e373LL, 0x682e6ff3d6b2b8a3LL, + 0x748f82ee5defb2fcLL, 0x78a5636f43172f60LL, + 0x84c87814a1f0ab72LL, 0x8cc702081a6439ecLL, + 0x90befffa23631e28LL, 0xa4506cebde82bde9LL, + 0xbef9a3f7b2c67915LL, 0xc67178f2e372532bLL, + 0xca273eceea26619cLL, 0xd186b8c721c0c207LL, + 0xeada7dd6cde0eb1eLL, 0xf57d4f7fee6ed178LL, + 0x06f067aa72176fbaLL, 0x0a637dc5a2c898a6LL, + 0x113f9804bef90daeLL, 0x1b710b35131c471bLL, + 0x28db77f523047d84LL, 0x32caab7b40c72493LL, + 0x3c9ebe0a15c9bebcLL, 0x431d67c49c100d4cLL, + 0x4cc5d4becb3e42b6LL, 0x597f299cfc657e2aLL, + 0x5fcb6fab3ad6faecLL, 0x6c44198c4a475817LL, +}; + +static inline uint64_t load64(const uint8_t *x) +{ + uint64_t r; + + r = *(x++); + r = (r << 8) | *(x++); + r = (r << 8) | *(x++); + r = (r << 8) | *(x++); + r = (r << 8) | *(x++); + r = (r << 8) | *(x++); + r = (r << 8) | *(x++); + r = (r << 8) | *(x++); + + return r; +} + +static inline void store64(uint8_t *x, uint64_t v) +{ + x += 7; + *(x--) = v; + v >>= 8; + *(x--) = v; + v >>= 8; + *(x--) = v; + v >>= 8; + *(x--) = v; + v >>= 8; + *(x--) = v; + v >>= 8; + *(x--) = v; + v >>= 8; + *(x--) = v; + v >>= 8; + *(x--) = v; +} + +static inline uint64_t rot64(uint64_t x, int bits) +{ + return (x >> bits) | (x << (64 - bits)); +} + +static void +sha512_block(struct sha512_state *s, const uint8_t *blk) +{ + uint64_t w[16]; + uint64_t a, b, c, d, e, f, g, h; + int i; + + for (i = 0; i < 16; i++) { + w[i] = load64(blk); + blk += 8; + } + + /* Load state */ + a = s->h[0]; + b = s->h[1]; + c = s->h[2]; + d = s->h[3]; + e = s->h[4]; + f = s->h[5]; + g = s->h[6]; + h = s->h[7]; + + for (i = 0; i < 80; i++) { + /* Compute value of w[i + 16]. w[wrap(i)] is currently w[i] */ + const uint64_t wi = w[i & 15]; + const uint64_t wi15 = w[(i + 1) & 15]; + const uint64_t wi2 = w[(i + 14) & 15]; + const uint64_t wi7 = w[(i + 9) & 15]; + const uint64_t s0 = + rot64(wi15, 1) ^ rot64(wi15, 8) ^ (wi15 >> 7); + const uint64_t s1 = + rot64(wi2, 19) ^ rot64(wi2, 61) ^ (wi2 >> 6); + + /* Round calculations */ + const uint64_t S0 = rot64(a, 28) ^ rot64(a, 34) ^ rot64(a, 39); + const uint64_t S1 = rot64(e, 14) ^ rot64(e, 18) ^ rot64(e, 41); + const uint64_t ch = (e & f) ^ ((~e) & g); + const uint64_t temp1 = h + S1 + ch + round_k[i] + wi; + const uint64_t maj = (a & b) ^ (a & c) ^ (b & c); + const uint64_t temp2 = S0 + maj; + + /* Update round state */ + h = g; + g = f; + f = e; + e = d + temp1; + d = c; + c = b; + b = a; + a = temp1 + temp2; + + /* w[wrap(i)] becomes w[i + 16] */ + w[i & 15] = wi + s0 + wi7 + s1; + } + + /* Store state */ + s->h[0] += a; + s->h[1] += b; + s->h[2] += c; + s->h[3] += d; + s->h[4] += e; + s->h[5] += f; + s->h[6] += g; + s->h[7] += h; +} + +void sha512_init(struct sha512_state *s) +{ + memcpy(s->h, &sha512_initial_state, sizeof(s->h)); + s->len = 0; +} + +void sha512_add(struct sha512_state *s, const void *data, size_t len) +{ + unsigned int partial = s->len & (SHA512_BLOCK_SIZE - 1); + + if (partial) { + unsigned int cur = SHA512_BLOCK_SIZE - partial; + + if (cur > len) + cur = len; + + memcpy(&s->partial[partial], data, cur); + + s->len += cur; + data += cur; + len -= cur; + + partial = s->len & (SHA512_BLOCK_SIZE - 1); + if (!partial) + sha512_block(s, s->partial); + } + + while (len >= SHA512_BLOCK_SIZE) { + sha512_block(s, data); + + s->len += SHA512_BLOCK_SIZE; + data += SHA512_BLOCK_SIZE; + len -= SHA512_BLOCK_SIZE; + } + + if (!len) + return; + + memcpy(s->partial, data, len); + s->len += len; +} + +void sha512_final(struct sha512_state *s, uint8_t *hash) +{ + size_t last_size = s->len & (SHA512_BLOCK_SIZE - 1); + unsigned int len = SHA512_HASH_SIZE; + int i = 0; + + s->partial[last_size++] = 0x80; + if (last_size < SHA512_BLOCK_SIZE) + memset(&s->partial[last_size], 0, + SHA512_BLOCK_SIZE - last_size); + + if (last_size > 110) { + sha512_block(s, s->partial); + memset(s->partial, 0, sizeof(s->partial)); + } + + /* Note: we assume total_size fits in 61 bits */ + store64(s->partial + SHA512_BLOCK_SIZE - 8, s->len << 3); + sha512_block(s, s->partial); + + /* Read out whole words */ + while (len >= 8) { + store64(hash, s->h[i++]); + hash += 8; + len -= 8; + } + + /* Read out bytes */ + if (len) { + uint8_t tmp[8]; + + store64(tmp, s->h[i]); + memcpy(hash, tmp, len); + } +} diff --git a/sha512.h b/sha512.h new file mode 100644 index 0000000..7fb0054 --- /dev/null +++ b/sha512.h @@ -0,0 +1,63 @@ +/* + * Copyright (C) 2015 Felix Fietkau + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* SHA512 + * Daniel Beer , 22 Apr 2014 + * + * This file is in the public domain. + */ + +#ifndef SHA512_H_ +#define SHA512_H_ + +#include +#include +#include +#include + +/* Feed a full block in */ +#define SHA512_BLOCK_SIZE 128 + +/* SHA512 state. State is updated as data is fed in, and then the final + * hash can be read out in slices. + * + * Data is fed in as a sequence of full blocks terminated by a single + * partial block. + */ +struct sha512_state { + uint64_t h[8]; + uint8_t partial[SHA512_BLOCK_SIZE]; + size_t len; +}; + +/* Set up a new context */ +void sha512_init(struct sha512_state *s); + +void sha512_add(struct sha512_state *s, const void *data, size_t len); + +/* Fetch a slice of the hash result. */ +#define SHA512_HASH_SIZE 64 + +void sha512_final(struct sha512_state *s, uint8_t *hash); + +static inline void * +sha512_final_get(struct sha512_state *s) +{ + sha512_final(s, s->partial); + return s->partial; +} + +#endif