lkml.org 
[lkml]   [2004]   [Feb]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [CRYPTO]: Miscompiling sha256.c by gcc 3.2.3 and arch pentium3,4
    If it helps anyone, here's a modified sha256.c file that takes 256 bytes
    off the stack and shrinks the main code loop by a factor of 8.

    The speed penalty is pretty minor, and might actually be negative due to
    better icache usage.

    Includes x86 stubs for standalone self-test using the NIST test vectors.
    Enable the #if 0 parts and remove the commented-out debug lines
    for production use.

    A few other additions:
    - Uses optimized unaligned-fetch and byte-swap routines.
    - Reordered the the Ch() and Maj() functions slightly to work better on
    2-address instruction sets.
    - Got rid of two temporaries in the round function
    - Removed the need to memset() 256 bytes on the stack every call to
    sha256_transform
    - Uses memset() rather than a padding array.

    A few questions:
    - Should we just use a u64 to count the bytes rather than doing carries by
    hand?
    - Do we actually need support for hashing more than 2^32 bytes in the first
    place?
    - This does the aligned/unaligned check at the outermost feasible loop
    position in the code, leading to quite a bit of duplication.
    If the processor supports unaligned loads natively, it isn't even
    necessary at all. An better ideas? I can understand:
    - Moving the test to once per call to sha256_transform, on the
    grounds that the latter outweights it by a large amount.
    - Always using the unaligned load, likewise.
    - Rolling my own unaligned block move-and-byte-swap (using aligned
    loads, shifts, and algned stores), since the existing unaligned code
    isn't quite what we want.
    - Just using memcpy and byte-swap in place, and letting the L1 cache
    take care of it.
    - The e() functions as written take a an temp register in addition to the
    input and output. Would it be better to rewrite them as e.g.
    better to rewrite them as e.g.
    static inline u32 e0(u32 x)
    {
    u32 y = x;
    y = RORu32(y, 22-13) ^ x;
    y = RORu32(y, 13-2) ^ x;
    return RORu32(y, 2);
    }
    to get rid of the need? (And can someone figure out a similar trick
    for the s() functions? I don't think it's as important because there's
    less register pressure when they're used.)

    (P.S. These modifications are in the public domain; copyright abandoned.)


    /*
    * Cryptographic API.
    *
    * SHA-256, as specified in
    * http://csrc.nist.gov/cryptval/shs/sha256-384-512.pdf
    *
    * SHA-256 code by Jean-Luc Cooke <jlcooke@certainkey.com>.
    *
    * Copyright (c) Jean-Luc Cooke <jlcooke@certainkey.com>
    * Copyright (c) Andrew McDonald <andrew@mcdonald.org.uk>
    * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
    *
    * This program is free software; you can redistribute it and/or modify it
    * under the terms of the GNU General Public License as published by the Free
    * Software Foundation; either version 2 of the License, or (at your option)
    * any later version.
    *
    */
    #if 0
    #include <linux/init.h>
    #include <linux/module.h>
    #include <linux/mm.h>
    #include <linux/crypto.h>
    #include <asm/scatterlist.h>
    #include <asm/byteorder.h>
    #else
    typedef unsigned int u32;
    typedef unsigned char u8;
    #include <string.h>
    #define get_unaligned(p) (*(p))
    #define be32_to_cpus(p) asm("bswap %0" : "+r" (*(p)));
    static inline u32
    be32_to_cpup(u32 const *p)
    {
    u32 x;
    asm("bswap %0" : "=r" (x) : "0" (*p));
    return x;
    }
    static inline u32
    be32_to_cpu(u32 x)
    {
    asm("bswap %0" : "+r" (x));
    return x;
    }
    #define cpu_to_be32s be32_to_cpus
    #define cpu_to_be32p be32_to_cpup
    #define cpu_to_be32 be32_to_cpu
    #endif


    #define SHA256_DIGEST_SIZE 32
    #define SHA256_HMAC_BLOCK_SIZE 64

    struct sha256_ctx {
    u32 count[2]; /* Bytes so far: Low, then high */
    u32 state[8];
    u32 W[64];
    };

    /* Bit-wise choose x ? y : z = (x & y) + (~x & z) = z ^ (x & (y ^ z)) */
    #define Ch(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))

    /*
    * Majority function. There's no really good way to optimize this,
    * although x is the most recently computed vaue, so put it later in
    * the dependency chain. Also use ^ in the OR so that the halves can
    * be merged with + which gives the compiler more flexibility to
    * rearrange the surrounding sum.
    * x&y | y&z | z&x = x&(y|z) | y&z = x&(y^z) + y&z
    */
    #define Maj(x, y, z) (((x) & ((y) ^ (z))) + ((y) & (z)))

    static inline u32 RORu32(u32 x, u32 y)
    {
    return (x >> y) | (x << (32 - y));
    }

    #define e0(x) (RORu32(x, 2) ^ RORu32(x,13) ^ RORu32(x,22))
    #define e1(x) (RORu32(x, 6) ^ RORu32(x,11) ^ RORu32(x,25))
    #define s0(x) (RORu32(x, 7) ^ RORu32(x,18) ^ (x >> 3))
    #define s1(x) (RORu32(x,17) ^ RORu32(x,19) ^ (x >> 10))

    #if __BYTE_ORDER == __BIG_ENDIAN
    #error WTF?
    # define loadin_inplace(w, len) (void)0
    #else
    static inline void
    loadin_inplace(u32 *W, unsigned i)
    {
    unsigned j;
    for (j = 0; j < i; j++)
    be32_to_cpus(W+j);
    }
    #endif

    static inline void
    loadin_aligned(u32 *W, u32 const *input, unsigned i)
    {
    unsigned j;
    for (j = 0; j < i; j++)
    W[j] = be32_to_cpup(input+j);
    }
    /*
    * This may be a bit bigger than we want an inline function, but
    * it's only called from one place.
    */
    static inline void
    loadin_unaligned(u32 *W, u8 const *input, unsigned i)
    {
    unsigned j;
    for (j = 0; j < i; j++)
    W[j] = be32_to_cpu(get_unaligned(input+4*j));
    }

    static inline void BLEND_OP(int I, u32 *W)
    {
    W[I] = s1(W[I-2]) + W[I-7] + s0(W[I-15]) + W[I-16];
    }

    /*
    * This expects input in the first 16 words of W[], and uses all
    * 64 words. Doing it this way avoinds the need to allocate
    * and zeroize a stack temporary each time.
    */
    static void sha256_transform(u32 state[8], u32 W[64])
    {
    u32 a, b, c, d, e, f, g, h;
    int i;
    static u32 const k[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
    0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
    0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
    0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
    0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
    0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
    0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
    0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
    0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
    };
    //printf("in: %08x %08x %08x %08x %08x %08x %08x %08x\n",W[0],W[1],W[2],W[3],W[4],W[5],W[6],W[7]);
    //printf("in: %08x %08x %08x %08x %08x %08x %08x %08x\n",W[8],W[9],W[10],W[11],W[12],W[13],W[14],W[15]);

    /* The first 16 words of W already contain the input - now blend */
    /* This is a sort of key-scheduling operation */
    for (i = 16; i < 64; i++)
    W[i] = s1(W[i-2]) + W[i-7] + s0(W[i-15]) + W[i-16];

    /* load the state into our registers */
    a=state[0]; b=state[1]; c=state[2]; d=state[3];
    e=state[4]; f=state[5]; g=state[6]; h=state[7];
    /*
    * Now iterate the actual round function. This is actually 64
    * copies of the same round function with the variables
    * rotated each time, but here we unroll it 8 times to
    * reduce the amount of data motion. You could roll it up
    * more if code size is a priority.
    */
    for (i = 0; i < 64; i += 8) {
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+0,a,b,c,d,e,f,g,h);
    d += h += e1(e) + Ch(e,f,g) + k[i+0] + W[i+0];
    h += e0(a) + Maj(a,b,c);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+1,h,a,b,c,d,e,f,g);
    c += g += e1(d) + Ch(d,e,f) + k[i+1] + W[i+1];
    g += e0(h) + Maj(h,a,b);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+2,g,h,a,b,c,d,e,f);
    b += f += e1(c) + Ch(c,d,e) + k[i+2] + W[i+2];
    f += e0(g) + Maj(g,h,a);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+3,f,g,h,a,b,c,d,e);
    a += e += e1(b) + Ch(b,c,d) + k[i+3] + W[i+3];
    e += e0(f) + Maj(f,g,h);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+4,e,f,g,h,a,b,c,d);
    h += d += e1(a) + Ch(a,b,c) + k[i+4] + W[i+4];
    d += e0(e) + Maj(e,f,g);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+5,d,e,f,g,h,a,b,c);
    g += c += e1(h) + Ch(h,a,b) + k[i+5] + W[i+5];
    c += e0(d) + Maj(d,e,f);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+6,c,d,e,f,g,h,a,b);
    f += b += e1(g) + Ch(g,h,a) + k[i+6] + W[i+6];
    b += e0(c) + Maj(c,d,e);
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+7,b,c,d,e,f,g,h,a);
    e += a += e1(f) + Ch(f,g,h) + k[i+7] + W[i+7];
    a += e0(b) + Maj(b,c,d);
    }
    //printf("%2u: %08x %08x %08x %08x %08x %08x %08x %08x\n", i+0,a,b,c,d,e,f,g,h);

    /* Add back to the state to make hash one-way */
    state[0] += a; state[1] += b; state[2] += c; state[3] += d;
    state[4] += e; state[5] += f; state[6] += g; state[7] += h;

    /* clear any sensitive info... */
    a = b = c = d = e = f = g = h = 0;
    }

    static void
    sha256_init(void *ctx)
    {
    struct sha256_ctx *sctx = ctx;
    static u32 const Hinit[SHA256_DIGEST_SIZE/4] = {
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
    };

    memcpy(sctx->state, Hinit, sizeof Hinit);
    sctx->count[0] = sctx->count[1] = 0;
    }

    static void
    sha256_update(void *ctx, const u8 *data, unsigned int len)
    {
    struct sha256_ctx *sctx = ctx;

    /* Compute number of bytes mod 63 */
    unsigned index = (unsigned)sctx->count[0] & (SHA256_HMAC_BLOCK_SIZE-1);

    //printf("sha256_update(%.*s)\n", (int)len, data);

    /* Add 32-bit len to 64-bit sctx->count */
    sctx->count[1] += ((sctx->count[0] += len) < len);

    if (len + index >= SHA256_HMAC_BLOCK_SIZE) {
    if (index) {
    memcpy((char *)sctx->W + index, data, len);
    loadin_inplace(sctx->W, 16);
    sha256_transform(sctx->state, sctx->W);
    index = SHA256_HMAC_BLOCK_SIZE-1-index;
    data += index;
    len -= index;
    index = 0;
    }
    /*
    * I wish there was a way to tell if unaligned loads
    * required a special instruction sequence and there
    * was a point to splitting this...
    */
    if ((unsigned)data % 4 == 0) {
    /* Aligned case */
    while (len >= SHA256_HMAC_BLOCK_SIZE) {
    loadin_aligned(sctx->W, (u32 const *)data, 16);
    sha256_transform(sctx->state, sctx->W);
    data += SHA256_HMAC_BLOCK_SIZE;
    len -= SHA256_HMAC_BLOCK_SIZE;
    }
    } else {
    /* Unaligned case */
    while (len >= SHA256_HMAC_BLOCK_SIZE) {
    loadin_unaligned(sctx->W, data, 16);
    sha256_transform(sctx->state, sctx->W);
    data += SHA256_HMAC_BLOCK_SIZE;
    len -= SHA256_HMAC_BLOCK_SIZE;
    }
    }
    }
    /* Buffer any leftover data */
    memcpy((char *)sctx->W + index, data, len);
    }

    static void
    sha256_final(void* ctx, u8 *out)
    {
    struct sha256_ctx *sctx = ctx;

    /* Next byte to store */
    unsigned index = (unsigned)sctx->count[0] & (SHA256_HMAC_BLOCK_SIZE-1);

    /* Add padding bit sequence 1000...; we're limited to 8-bit bytes. */
    ((u8 *)sctx->W)[index++] = 0x80;
    if (index > 56) {
    /* Wups, need a whole extra block to fit the 8-bit count */
    memset((u8 *)sctx->W + index, 0, 64-index);
    loadin_inplace(sctx->W, 16);
    sha256_transform(sctx->state, sctx->W);
    index = 0;
    }
    memset((u8 *)sctx->W + index, 0, 56-index);
    loadin_inplace(sctx->W, 14);

    /* Append number of bits in final 8 bytes, big-endian */
    /* QUESTION: Are we ever going to hash more than 256 MiB? */
    sctx->W[14] = (sctx->count[1] << 3) + (sctx->count[0] >> 29);
    sctx->W[15] = (sctx->count[0] << 3);

    sha256_transform(sctx->state, sctx->W);

    /* Output the state */
    for (index = 0; index < SHA256_DIGEST_SIZE/4; index++)
    cpu_to_be32s(sctx->state + index);
    memcpy(out, sctx->state, SHA256_DIGEST_SIZE);

    /* Zeroize sensitive information. */
    memset(sctx, 0, sizeof *sctx);
    }

    #if 0

    static struct crypto_alg alg = {
    .cra_name = "sha256",
    .cra_flags = CRYPTO_ALG_TYPE_DIGEST,
    .cra_blocksize = SHA256_HMAC_BLOCK_SIZE,
    .cra_ctxsize = sizeof(struct sha256_ctx),
    .cra_module = THIS_MODULE,
    .cra_list = LIST_HEAD_INIT(alg.cra_list),
    .cra_u = { .digest = {
    .dia_digestsize = SHA256_DIGEST_SIZE,
    .dia_init = sha256_init,
    .dia_update = sha256_update,
    .dia_final = sha256_final }
    }
    };

    static int __init init(void)
    {
    return crypto_register_alg(&alg);
    }

    static void __exit fini(void)
    {
    crypto_unregister_alg(&alg);
    }

    module_init(init);
    module_exit(fini);

    MODULE_LICENSE("GPL");
    MODULE_DESCRIPTION("SHA256 Secure Hash Algorithm");
    #else

    #include <stdio.h>

    static void
    dump_hash(u8 const buf[32])
    {
    unsigned i;
    for (i = 0; i < 32; i++) {
    if (i % 4 == 0)
    putchar(' ');
    printf("%02x", buf[i]);
    }
    }

    static int
    check_hash(u8 const buf[32], u8 const expected[32])
    {
    printf(" Result:");
    dump_hash(buf);
    if (memcmp(buf, expected, 32) != 0) {
    printf("Correct:");
    puts("*** MISMATCH ***");
    return 1;
    }
    return 0;
    }

    int
    main(void)
    {
    /* Test driver using the test vectors from FIPS 180-2 */
    char tv1[3] = "abc";
    static u8 const out1[32] = {
    0xba,0x78,0x16,0xbf, 0x8f,0x01,0xcf,0xea, 0x41,0x41,0x40,0xde,
    0x5d,0xae,0x22,0x23, 0xb0,0x03,0x61,0xa3, 0x96,0x17,0x7a,0x9c,
    0xb4,0x10,0xff,0x61, 0xf2,0x00,0x15,0xad
    };

    char tv2[56] = "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
    static u8 const out2[32] = {
    0x24,0x8d,0x6a,0x61, 0xd2,0x06,0x38,0xb8, 0xe5,0xc0,0x26,0x93,
    0x0c,0x3e,0x60,0x39, 0xa3,0x3c,0xe4,0x59, 0x64,0xff,0x21,0x67,
    0xf6,0xec,0xed,0xd4, 0x19,0xdb,0x06,0xc1
    };

    char tv3[1024];
    static u8 const out3[32] = {
    0xcd,0xc7,0x6e,0x5c, 0x99,0x14,0xfb,0x92, 0x81,0xa1,0xc7,0xe2,
    0x84,0xd7,0x3e,0x67, 0xf1,0x80,0x9a,0x48, 0xa4,0x97,0x20,0x0e,
    0x04,0x6d,0x39,0xcc, 0xc7,0x11,0x2c,0xd0
    };
    u8 hash[32];
    struct sha256_ctx ctx;
    unsigned i, j, errors = 0;

    /* tv1 */
    for (i = 1; i <= 3; i++) {
    sha256_init(&ctx);
    for (j = 0; j < 3-i; j += i)
    sha256_update(&ctx, tv1+j, i);
    sha256_update(&ctx, tv1+j, 3-j);
    sha256_final(&ctx, hash);
    printf("Hash computed %u bytes at a time:\n", i);
    errors += check_hash(hash, out1);
    }

    /* tv2 */
    for (i = 1; i <= 56; i++) {
    sha256_init(&ctx);
    for (j = 0; j < 56-i; j += i)
    sha256_update(&ctx, tv2+j, i);
    sha256_update(&ctx, tv2+j, 56-j);
    sha256_final(&ctx, hash);
    printf("Hash computed %u bytes at a time:\n", i);
    errors += check_hash(hash, out2);
    }

    /* tv3 */
    memset(tv3, 'a', sizeof tv3);
    for (i = 1; i <= sizeof tv3; i *= 2) {
    sha256_init(&ctx);
    for (j = 0; j < 1000000-i; j += i)
    sha256_update(&ctx, tv3, i);
    sha256_update(&ctx, tv3, 1000000-j);
    sha256_final(&ctx, hash);
    printf("Hash computed %u bytes at a time:\n", i);
    errors += check_hash(hash, out3);
    }
    printf("Check complete, %u errors\n", errors);
    return errors != 0;
    }

    #endif
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 14:00    [W:0.042 / U:0.540 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site