Winner of Secure Hash Algorithm (SHA-3) Competition

[turnback]

The National Institute of Standards and Technology (NIST) today announced the winner of its five-year competition to select a new cryptographic hash algorithm, one of the fundamental tools of modern information security.

The winning algorithm, Keccak (pronounced “catch-ack”), was created by Guido Bertoni, Joan Daemen and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP Semiconductors. The team’s entry beat out 63 other submissions that NIST received after its open call for candidate algorithms in 2007, when it was thought that SHA-2, the standard secure hash algorithm, might be threatened. Keccak will now become NIST’s SHA-3 hash algorithm.

Hash algorithms are used widely for cryptographic applications that ensure the authenticity of digital documents, such as digital signatures and message authentication codes. These algorithms take an electronic file and generate a short "digest," a sort of digital fingerprint of the content. A good hash algorithm has a few vital characteristics. Any change in the original message, however small, must cause a change in the digest, and for any given file and digest, it must be infeasible for a forger to create a different file with the same digest.

The NIST team praised the Keccak algorithm for its many admirable qualities, including its elegant design and its ability to run well on many different computing devices. The clarity of Keccak’s construction lends itself to easy analysis (during the competition all submitted algorithms were made available for public examination and criticism), and Keccak has higher performance in hardware implementations than SHA-2 or any of the other finalists.

“Keccak has the added advantage of not being vulnerable in the same ways SHA-2 might be,” says NIST computer security expert Tim Polk. “An attack that could work on SHA-2 most likely would not work on Keccak because the two algorithms are designed so differently.”

Polk says that the two algorithms will offer security designers more flexibility. Despite the attacks that broke other somewhat similar but simpler hash algorithms in 2005 and 2006, SHA-2 has held up well and NIST considers SHA-2 to be secure and suitable for general use.

What then will SHA-3 be good for? While Polk says it may take years to identify all the possibilities for Keccak, it immediately provides an essential insurance policy in case SHA-2 is ever broken. He also speculates that the relatively compact nature of Keccak may make it useful for so-called “embedded” or smart devices that connect to electronic networks but are not themselves full-fledged computers. Examples include sensors in a building-wide security system and home appliances that can be controlled remotely.

“The Internet as we know it is expanding to link devices that many people do not ordinarily think of as being part of a network,” Polk says. “SHA-3 provides a new security tool for system and protocol designers, and that may create opportunities for security in networks that did not exist before.”

sursa: NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition

[Nytro]

// keccak.c
// 19-Nov-11  Markku-Juhani O. Saarinen <mjos@iki.fi>
// A baseline Keccak (3rd round) implementation.

#include "keccak.h"

const uint64_t keccakf_rndc[24] = 
{
    0x0000000000000001, 0x0000000000008082, 0x800000000000808a,
    0x8000000080008000, 0x000000000000808b, 0x0000000080000001,
    0x8000000080008081, 0x8000000000008009, 0x000000000000008a,
    0x0000000000000088, 0x0000000080008009, 0x000000008000000a,
    0x000000008000808b, 0x800000000000008b, 0x8000000000008089,
    0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 
    0x000000000000800a, 0x800000008000000a, 0x8000000080008081,
    0x8000000000008080, 0x0000000080000001, 0x8000000080008008
};

const int keccakf_rotc[24] = 
{
    1,  3,  6,  10, 15, 21, 28, 36, 45, 55, 2,  14, 
    27, 41, 56, 8,  25, 43, 62, 18, 39, 61, 20, 44
};

const int keccakf_piln[24] = 
{
    10, 7,  11, 17, 18, 3, 5,  16, 8,  21, 24, 4, 
    15, 23, 19, 13, 12, 2, 20, 14, 22, 9,  6,  1 
};

// update the state with given number of rounds

void keccakf(uint64_t st[25], int rounds)
{
    int i, j, round;
    uint64_t t, bc[5];

    for (round = 0; round < rounds; round++) {

        // Theta
        for (i = 0; i < 5; i++)     
            bc[i] = st[i] ^ st[i + 5] ^ st[i + 10] ^ st[i + 15] ^ st[i + 20];

        for (i = 0; i < 5; i++) {
            t = bc[(i + 4) % 5] ^ ROTL64(bc[(i + 1) % 5], 1);
            for (j = 0; j < 25; j += 5)
                st[j + i] ^= t;
        }

        // Rho Pi
        t = st[1];
        for (i = 0; i < 24; i++) {
            j = keccakf_piln[i];
            bc[0] = st[j];
            st[j] = ROTL64(t, keccakf_rotc[i]);
            t = bc[0];
        }

        //  Chi
        for (j = 0; j < 25; j += 5) {
            for (i = 0; i < 5; i++)
                bc[i] = st[j + i];
            for (i = 0; i < 5; i++)
                st[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
        }

        //  Iota
        st[0] ^= keccakf_rndc[round];
    }
}

// compute a keccak hash (md) of given byte length from "in"

int keccak(const uint8_t *in, int inlen, uint8_t *md, int mdlen)
{
    uint64_t st[25];    
    uint8_t temp[144];
    int i, rsiz, rsizw;

    rsiz = 200 - 2 * mdlen;
    rsizw = rsiz / 8;

    memset(st, 0, sizeof(st));

    for ( ; inlen >= rsiz; inlen -= rsiz, in += rsiz) {
        for (i = 0; i < rsizw; i++)
            st[i] ^= ((uint64_t *) in)[i];
        keccakf(st, KECCAK_ROUNDS);
    }

    // last block and padding
    memcpy(temp, in, inlen);
    temp[inlen++] = 1;
    memset(temp + inlen, 0, rsiz - inlen);
    temp[rsiz - 1] |= 0x80;

    for (i = 0; i < rsizw; i++)
        st[i] ^= ((uint64_t *) temp)[i];

    keccakf(st, KECCAK_ROUNDS);

    memcpy(md, st, mdlen);

    return 0;
}

Via:

[h=3]27 February 2012 — Readable C code for Keccak[/h] Markku-Juhani O. Saarinen posted an implementation of Keccak in C aimed at readability and clarity, as an alternative to our specifications summary. We appreciate Markku's support.