32-bit version of SHA-3 (Keccak) algorithm using bit-interleaving

sha3-32bit.js

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
/* SHA-3 (FIPS 202) ‘Keccak’ reference implementation in JavaScript   (c) Chris Veness 2016-2017  */
/*                                                                                   MIT Licence  */
/* www.movable-type.co.uk/scripts/sha3.html                                                       */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

'use strict';


/**
 * SHA-3 (FIPS 202) ‘Keccak’ hash functions.
 *
 * This is an annotated reference implementation intended to aid understanding of the algorithm.
 * While it is fully tested, it is not at all optimised and is not recommended for production use.
 *
 * See keccak.noekeon.org/Keccak-reference-3.0.pdf
 *     nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
 */
class Sha3 {

    /*
     * Keccak-f[b] permutations:
     *  - ℓ:  0  1   2   3   4   5    6
     *  - w:  1  2   4   8  16  32   64 (2ˡ)
     *  - b: 25 50 100 200 400 800 1600 (25 × 2ˡ)
     * SHA-3 specifies Keccak-f[1600] only, hence ℓ=6, w=64, b=1600.
     */


    /**
     * Generates 224-bit SHA-3 / Keccak hash of message.
     *
     * @param   {string} message - String to be hashed (Unicode-safe).
     * @param   {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
     * @returns {string} Hash as hex-encoded string.
     */
    static hash224(message, options) {
        return Sha3.keccak1600(1152, 448, message, options);
    }

    /**
     * Generates 256-bit SHA-3 / Keccak hash of message.
     *
     * @param   {string} message - String to be hashed (Unicode-safe).
     * @param   {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
     * @returns {string} Hash as hex-encoded string.
     */
    static hash256(message, options) {
        return Sha3.keccak1600(1088, 512, message, options);
    }

    /**
     * Generates 384-bit SHA-3 / Keccak hash of message.
     *
     * @param   {string} message - String to be hashed (Unicode-safe).
     * @param   {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
     * @returns {string} Hash as hex-encoded string.
     */
    static hash384(message, options) {
        return Sha3.keccak1600(832, 768, message, options);
    }

    /**
     * Generates 512-bit SHA-3 / Keccak hash of message.
     *
     * @param   {string} message - String to be hashed (Unicode-safe).
     * @param   {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
     * @returns {string} Hash as hex-encoded string.
     */
    static hash512(message, options) {
        return Sha3.keccak1600(576, 1024, message, options);
    }


    /**
     * Generates SHA-3 / Keccak hash of message M.
     *
     * @param   {number} r - Bitrate 'r' (b−c)
     * @param   {number} c - Capacity 'c' (b−r), md length × 2
     * @param   {string} M - Message
     * @param   {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
     * @returns {string} Hash as hex-encoded string.
     *
     * @private
     */
    static keccak1600(r, c, M, options) {
        const defaults = { padding: 'sha-3', msgFormat: 'string', outFormat: 'hex' };
        const opt = Object.assign(defaults, options);

        const l = c / 2; // message digest output length in bits

        let msg = null;
        switch (opt.msgFormat) {
            default: // convert string to UTF-8 to ensure all characters fit within single byte
            case 'string':    msg = utf8Encode(M);       break;
            case 'hex-bytes': msg = hexBytesToString(M); break; // mostly for NIST test vectors
        }

        /**
         * Keccak state is a 5 × 5 x w array of bits (w=64 for keccak-f[1600] / SHA-3).
         *
         * Here, it is implemented as a 5 × 5 × 2 array of 32-bit numbers. The first subscript (x)
         * defines the sheet, the second (y) defines the plane, together they define a lane which
         * comprises two UInt32. Slices, columns, and individual bits are obtained by bit operations
         * on the array[2] representing the lane.
         */
        const state = [
            [ [0,0], [0,0], [0,0], [0,0], [0,0] ],
            [ [0,0], [0,0], [0,0], [0,0], [0,0] ],
            [ [0,0], [0,0], [0,0], [0,0], [0,0] ],
            [ [0,0], [0,0], [0,0], [0,0], [0,0] ],
            [ [0,0], [0,0], [0,0], [0,0], [0,0] ],
        ];

        // append padding (for SHA-3 the domain is 01 hence M||0110*1) [FIPS §B.2]
        const q = (r/8) - msg.length % (r/8);
        if (q == 1) {
            msg += String.fromCharCode(opt.padding=='keccak' ? 0x81 : 0x86);
        } else {
            msg += String.fromCharCode(opt.padding=='keccak' ? 0x01 : 0x06);
            msg += String.fromCharCode(0x00).repeat(q-2);
            msg += String.fromCharCode(0x80);
        }

        // absorbing phase: work through input message in blocks of r bits (r/64 Longs, r/8 bytes)

        const w = 64; // for keccak-f[1600]
        const blocksize = r / w * 8; // block size in bytes (≡ utf-8 characters)

        for (let i=0; i<msg.length; i+=blocksize) {
            for (let j=0; j<r/w; j++) {
                const lo = (msg.charCodeAt(i+j*8+0)<< 0) + (msg.charCodeAt(i+j*8+1)<< 8)
                         + (msg.charCodeAt(i+j*8+2)<<16) + (msg.charCodeAt(i+j*8+3)<<24);
                const hi = (msg.charCodeAt(i+j*8+4)<< 0) + (msg.charCodeAt(i+j*8+5)<< 8)
                         + (msg.charCodeAt(i+j*8+6)<<16) + (msg.charCodeAt(i+j*8+7)<<24);
                const x = j % 5;
                const y = Math.floor(j / 5);
                const w = toInterleaved([ lo, hi ]);
                state[x][y][0] = (state[x][y][0] ^ w[0]) >>> 0; // TODO: >>>0?
                state[x][y][1] = (state[x][y][1] ^ w[1]) >>> 0;
            }
            Sha3.keccak_f_1600(state);
        }

        // squeezing phase: first l bits of state are message digest

        // transpose state, concatenate (little-endian) hex values, & truncate to l bits
        let md = transpose(state).map(column => column.map(lane => fromInterleaved(lane).map(w32 => hex(w32).match(/.{2}/g).reverse().join('')).join('')).join('')).join('').slice(0, l/4);
        function hex(n) { return ('00000000'+n.toString(16)).slice(-8); }

        //  if required, group message digest into bytes or words
        if (opt.outFormat == 'hex-b') md = md.match(/.{2}/g).join(' ');
        if (opt.outFormat == 'hex-w') md = md.match(/.{8,16}/g).join(' ');

        return md;

        /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

        function toInterleaved(lane) { // convert (64-bit) lane[low,high] to [even,odd]
            let even = 0, odd = 0;
            for (let i=0; i<64; i++) {
                const bit = i<32 ? (lane[0] >> i) & 1 : (lane[1] >> (i-32)) & 1; // TODO: hi/lo?
                if (i%2 == 0) even |= bit << (i/2);
                if (i%2 == 1) odd  |= bit << ((i-1)/2);
            }
            return [ even, odd ];
        }

        function fromInterleaved(lane) { // convert (64-bit) lane[even,odd] to [high,low]
            let high = 0, low = 0;
            for (let i=0; i<64; i++) {
                const bit = (i%2 == 0) ? (lane[0] >>> (i/2)) & 1 : (lane[1] >>> ((i-1)/2)) & 1;
                if (i <  32) low  = (low | bit << i) >>> 0; // TODO: >>>0 needed?
                if (i >= 32) high = (high |bit << (i-32)) >>> 0;
            }
            return [ low>>>0, high>>>0 ];
        }

        /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

        function transpose(array) { // to iterate across y (columns) before x (rows)
            return array.map((row, r) => array.map(col => col[r]));
        }

        function utf8Encode(str) {
            try {
                return new TextEncoder().encode(str, 'utf-8').reduce((prev, curr) => prev + String.fromCharCode(curr), '');
            } catch (e) { // no TextEncoder available?
                return unescape(encodeURIComponent(str)); // monsur.hossa.in/2012/07/20/utf-8-in-javascript.html
            }
        }

        function hexBytesToString(hexStr) { // convert string of hex numbers to a string of chars (eg '616263' -> 'abc').
            const str = hexStr.replace(' ', ''); // allow space-separated groups
            return str=='' ? '' : str.match(/.{2}/g).map(byte => String.fromCharCode(parseInt(byte, 16))).join('');
        }
    }


    /**
     * Applies permutation Keccak-f[1600] to state a.
     *
     * @param {number[][][]} a - State to be permuted (5 × 5 × 2 array of UInt32).
     *
     * @private
     */
    static keccak_f_1600(a) {

        const nRounds = 24; // number of rounds nᵣ = 12 + 2ℓ, hence 24 for Keccak-f[1600] [[Keccak §1.2]

        /**
         * Round constants: output of a maximum-length linear feedback shift register (LFSR) for the
         * ι step [Keccak §1.2, §2.3.5], keccak.noekeon.org/specs_summary.html.
         *
         *   RC[iᵣ][0][0][2ʲ−1] = rc[j+7iᵣ] for 0 ≤ j ≤ l
         * where
         *   rc[t] = ( xᵗ mod x⁸ + x⁶ + x⁵ + x⁴ + 1 ) mod x in GF(2)[x].
         */
        const RC = [ // TODO: interleaved? word ordering? each word-pair is [even,odd]?
            [ 0x00000001, 0x00000000 ], [ 0x00000000, 0x00000089 ], [ 0x00000000, 0x8000008B ],
            [ 0x00000000, 0x80008080 ], [ 0x00000001, 0x0000008B ], [ 0x00000001, 0x00008000 ],
            [ 0x00000001, 0x80008088 ], [ 0x00000001, 0x80000082 ], [ 0x00000000, 0x0000000B ],
            [ 0x00000000, 0x0000000A ], [ 0x00000001, 0x00008082 ], [ 0x00000000, 0x00008003 ],
            [ 0x00000001, 0x0000808B ], [ 0x00000001, 0x8000000B ], [ 0x00000001, 0x8000008A ],
            [ 0x00000001, 0x80000081 ], [ 0x00000000, 0x80000081 ], [ 0x00000000, 0x80000008 ],
            [ 0x00000000, 0x00000083 ], [ 0x00000000, 0x80008003 ], [ 0x00000001, 0x80008088 ],
            [ 0x00000000, 0x80000088 ], [ 0x00000001, 0x00008000 ], [ 0x00000000, 0x80008082 ],
        ];


        // Keccak-f permutations
        for (let r=0; r<nRounds; r++) {
            // apply step mappings θ, ρ, π, χ, ι to the state 'a'
            //console.log('round', r); debug5x5(a);

            // θ [Keccak §2.3.2]
            const C = [ [0,0], [0,0], [0,0], [0,0], [0,0] ]; // intermediate sub-states
            const D = [ [0,0], [0,0], [0,0], [0,0], [0,0] ];
            for (let x=0; x<5; x++) {
                for (let y=0; y<5; y++) {
                    C[x][0] = (C[x][0] ^ a[x][y][0]) >>> 0;
                    C[x][1] = (C[x][1] ^ a[x][y][1]) >>> 0;
                }
            }
            for (let x=0; x<5; x++) {
                // D[x] = C[x−1] ⊕ ROT(C[x+1], 1)
                D[x][0] = (C[(x+4)%5][0] ^ ROT(C[(x+1)%5], 1)[0]) >>> 0;
                D[x][1] = (C[(x+4)%5][1] ^ ROT(C[(x+1)%5], 1)[1]) >>> 0;
            }
            for (let x=0; x<5; x++) {
                for (let y=0; y<5; y++) {
                    a[x][y][0] = (a[x][y][0] ^ D[x][0]) >>> 0;
                    a[x][y][1] = (a[x][y][1] ^ D[x][1]) >>> 0;
                }
            }
            //console.log('round', r, 'after θ'); debug5x5(a);

            // ρ + π [Keccak §2.3.4]
            let [ x, y ] = [ 1, 0 ];
            let current = a[x][y].slice(0); // Array.slice(0) clones the array
            for (let t=0; t<24; t++) {
                const [ X, Y ] = [ y, (2*x + 3*y) % 5 ];
                const tmp = a[X][Y].slice(0);
                a[X][Y] = ROT(current, ((t+1)*(t+2)/2) % 64);
                //console.log('ρπ', x, y, current, ((t+1)*(t+2)/2) % 64, X, Y, a[X][Y])
                current = tmp;
                [ x, y ] = [ X, Y ];
            }
            // note by folding the π step into the ρ step, it is only necessary to cache the current
            // lane; with π looping around x & y, it would be necessary to take a copy of the full
            // state for the A[X,Y] = a[x,y] operation
            //console.log('round', r, 'after ρπ'); debug5x5(a)

            // χ [Keccak §2.3.1]
            for (let y=0; y<5; y++) {
                const C = [ [0,0], [0,0], [0,0], [0,0], [0,0] ];  // take a copy of the plane
                for (let x=0; x<5; x++) {
                    C[x][0] = (a[x][y][0] ^ ((~a[(x+1)%5][y][0]) & a[(x+2)%5][y][0])) >>> 0;
                    C[x][1] = (a[x][y][1] ^ ((~a[(x+1)%5][y][1]) & a[(x+2)%5][y][1])) >>> 0;
                }
                for (let x=0; x<5; x++) {
                    a[x][y][0] = C[x][0];
                    a[x][y][1] = C[x][1];
                }
            }
            //console.log('round', r, 'after χ'); debug5x5(a);

            // ι [Keccak §2.3.5]
            //console.log(RC[r])
            a[0][0][0] = (a[0][0][0] ^ RC[r][0]) >>> 0;
            a[0][0][1] = (a[0][0][1] ^ RC[r][1]) >>> 0;
            //console.log('round', r, 'after ι'); debug5x5(a);
        }

        function ROT(a, d) { // rotate-left bit-interleaved lane 'a' by d bits
            if (d==0) return a;
            if (d==1) return [ (a[1] << 1 ^ a[1] >>> 31) >>> 0, a[0]>>>0 ]; // avoid invalid >>> 32! TODO: >>>0?
            //console.log('ROT >', a, '>>', d)

            let even=null, odd=null;

            if (d%2 == 0) {
                //d = d/2;
                even = ((a[0] << d/2) ^ (a[0] >>> (32-d/2))) >>> 0;
                odd  = ((a[1] << d/2) ^ (a[1] >>> (32-d/2))) >>> 0;
            } else {
                //d = (d+1)/2;
                even = ((a[1] << (d+1)/2) ^ (a[1] >>> (32-(d+1)/2))) >>> 0;
                odd  = ((a[0] << (d-1)/2) ^ (a[0] >>> (32-(d-1)/2))) >>> 0;
            }
            //console.log('ROT <', [ even, odd ])
            return [ even, odd ];
        }

        function debug5x5i(s) { // debug of state s, interleaved (even/odd) format
            const d = s.map((row, r) => s.map(col => col[r].map(w => hex(w)).join(':')).join(' ')).join('\n');
            console.log(d);
            function hex(n) { return ('00000000'+n.toString(16)).slice(-8); }
        }

        function debug5x5(s) { // debug of state s, high:low word format
            const d = transpose(s).map(row => row.map(w=>fromInterleaved2(w)).map(col => col.map(w => hex(w)).join(':')).join(' ')).join('\n');
            console.log(d);
            function hex(n) { return ('00000000'+n.toString(16)).slice(-8); }
        }

        function fromInterleaved2(lane) { // convert (64-bit) lane[even,odd] to [high,low]
            let high = 0, low = 0;
            for (let i=0; i<64; i++) {
                const bit = (i%2 == 0) ? (lane[0] >>> (i/2)) & 1 : (lane[1] >>> ((i-1)/2)) & 1;
                if (i <  32) low  = (low | bit << i) >>> 0; // TODO: >>>0 needed?
                if (i >= 32) high = (high |bit << (i-32)) >>> 0;
            }
            return [ low>>>0, high>>>0 ];
        }

        function transpose(array) { // TODO: why?
            return array.map((row, r) => array.map(col => col[r]));
        }
    }

}


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

if (typeof module != 'undefined' && module.exports) module.exports = Sha3; // ≡ export default Sha3

Q.v. github.com/chrisveness/crypto/blob/master/sha3.js.

See keccak.noekeon.org/Keccak-implementation-3.2.pdf, Chapter 2 Implementation techniques