sha3.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 array of Long. The first subscript (x) defines the
         * sheet, the second (y) defines the plane, together they define a lane. Slices, columns,
         * and individual bits are obtained by bit operations on the hi,lo components of the Long
         * representing the lane.
         */
        const state = [ [], [], [], [], [] ];
        for (let x=0; x<5; x++) {
            for (let y=0; y<5; y++) {
                state[x][y] = new Sha3.Long(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);
                state[x][y].lo = state[x][y].lo ^ lo;
                state[x][y].hi = state[x][y].hi ^ hi;
            }
            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(plane => plane.map(lane => lane.toString().match(/.{2}/g).reverse().join('')).join('')).join('').slice(0, l/4);

        // 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 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 {Long[][]} a - State to be permuted (5 × 5 array of Long).
     *
     * @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 = [
            '0000000000000001', '0000000000008082', '800000000000808a',
            '8000000080008000', '000000000000808b', '0000000080000001',
            '8000000080008081', '8000000000008009', '000000000000008a',
            '0000000000000088', '0000000080008009', '000000008000000a',
            '000000008000808b', '800000000000008b', '8000000000008089',
            '8000000000008003', '8000000000008002', '8000000000000080',
            '000000000000800a', '800000008000000a', '8000000080008081',
            '8000000000008080', '0000000080000001', '8000000080008008',
        ].map(c => Sha3.Long.fromString(c));


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

            // θ [Keccak §2.3.2]
            const C = [], D = []; // intermediate sub-states
            for (let x=0; x<5; x++) {
                C[x] = a[x][0].clone();
                for (let y=1; y<5; y++) {
                    C[x].hi = C[x].hi ^ a[x][y].hi;
                    C[x].lo = C[x].lo ^ a[x][y].lo;
                }
            }
            for (let x=0; x<5; x++) {
                // D[x] = C[x−1] ⊕ ROT(C[x+1], 1)
                const hi = C[(x+4)%5].hi ^ ROT(C[(x+1)%5], 1).hi;
                const lo = C[(x+4)%5].lo ^ ROT(C[(x+1)%5], 1).lo;
                D[x] = new Sha3.Long(hi, lo);
                // a[x,y] = a[x,y] ⊕ D[x]
                for (let y=0; y<5; y++) {
                    a[x][y].hi = a[x][y].hi ^ D[x].hi;
                    a[x][y].lo = a[x][y].lo ^ D[x].lo;
                }
            }

            // ρ + π [Keccak §2.3.4]
            let [ x, y ] = [ 1, 0 ];
            let current = a[x][y].clone();
            for (let t=0; t<24; t++) {
                const [ X, Y ] = [ y, (2*x + 3*y) % 5 ];
                const tmp = a[X][Y].clone();
                a[X][Y] = ROT(current, ((t+1)*(t+2)/2) % 64);
                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

            // χ [Keccak §2.3.1]
            for (let y=0; y<5; y++) {
                const C = [];  // take a copy of the plane
                for (let x=0; x<5; x++) C[x] = a[x][y].clone();
                for (let x=0; x<5; x++) {
                    a[x][y].hi = (C[x].hi ^ ((~C[(x+1)%5].hi) & C[(x+2)%5].hi)) >>> 0;
                    a[x][y].lo = (C[x].lo ^ ((~C[(x+1)%5].lo) & C[(x+2)%5].lo)) >>> 0;
                }
            }

            // ι [Keccak §2.3.5]
            a[0][0].hi = (a[0][0].hi ^ RC[r].hi) >>> 0;
            a[0][0].lo = (a[0][0].lo ^ RC[r].lo) >>> 0;
        }

        function ROT(a, d) {
            return a.rotl(d);
        }

        function debugNist(s) { // debug of state s in NIST format
            const d = transpose(s).map(plane => plane.join('')).join('')
                .match(/.{2}/g).join(' ')
                .match(/.{23,48}/g).join('\n');
            console.log(d);
        }

        function debug5x5(s) { // debug of state s in 5×5 format 64-bit words
            const d = transpose(s).map(plane => plane.join(' ')).join('\n');
            console.log(d);
        }

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

}


/**
 * JavaScript has no support for 64-bit integers; this class provides methods required to support
 * 64-bit unsigned integers within Keccak.
 */
Sha3.Long = class {

    constructor(hi, lo) {
        this.hi = hi;
        this.lo = lo;
    }

    /**
     * Construct Long from string representation.
     */
    static fromString(str) {
        const [ hi, lo ] = str.match(/.{8}/g).map(i32 => parseInt(i32, 16));
        return new Sha3.Long(hi, lo);
    }

    /**
     * Copy 'this' Long.
     */
    clone() {
        return new Sha3.Long(this.hi, this.lo);
    }

    /**
     * Rotate left by n bits.
     */
    rotl(n) {
        if (n < 32) {
            const m = 32 - n;
            const lo = this.lo<<n | this.hi>>>m;
            const hi = this.hi<<n | this.lo>>>m;
            return new Sha3.Long(hi, lo);
        }
        if (n == 32) {
            return new Sha3.Long(this.lo, this.hi);
        }
        if (n > 32) {
            n -= 32;
            const m = 32 - n;
            const lo = this.hi<<n | this.lo>>>m;
            const hi = this.lo<<n | this.hi>>>m;
            return new Sha3.Long(hi, lo);
        }
    }

    /**
     * Representation of this Long as a hex string.
     */
    toString() {
        const hi = ('00000000'+this.hi.toString(16)).slice(-8);
        const lo = ('00000000'+this.lo.toString(16)).slice(-8);

        return hi + lo;
    }

};


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

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