//

// scsTools.c   Support tools for writing side-channel safe code

//

// Copyright (c) Microsoft Corporation. Licensed under the MIT license.

//

#include "precomp.h"

//

// This code needs to process data in words, and we'd like to use 32-bit words on 32-bit

// architectures and 64-bit words on 64-bit architectures. So we use NATIVE_UINT & friends.

//

// Buffer limits for SymCryptScsRotateBuffer

#define MIN_BUFFER_SIZE (32)

//

// Masking functions

// Masking functions can be more efficient if the inputs are restricted to values that can

// be represented in the signed data types.

// This is why we have some functions that take 31-bit inputs.

//

// 31-bit inputs

UINT32

SYMCRYPT_CALL

SymCryptMask32IsNonzeroU31( UINT32 v )

{

    SYMCRYPT_ASSERT( v < (1UL<<31) );

    return (-(INT32) v) >> 31;

}

UINT32

SYMCRYPT_CALL

SymCryptMask32IsZeroU31( UINT32 v )

{

    return ~SymCryptMask32IsNonzeroU31( v );

}

UINT32

SYMCRYPT_CALL

SymCryptMask32NeqU31( UINT32 a, UINT32 b )

{

    SYMCRYPT_ASSERT( a < (1UL<<31) );

    SYMCRYPT_ASSERT( b < (1UL<<31) );

    return SymCryptMask32IsNonzeroU31( a ^ b );

}

UINT32

SYMCRYPT_CALL

SymCryptMask32LtU31( UINT32 a, UINT32 b )

{

    SYMCRYPT_ASSERT( a < (1UL<<31) );

    SYMCRYPT_ASSERT( b < (1UL<<31) );

    // Casting to INT32 is defined as a and b are < 2^31

    return ((INT32) a - (INT32) b) >> 31;

}

// 32-bit inputs

UINT32

SYMCRYPT_CALL

SymCryptMask32EqU32( UINT32 a, UINT32 b )

{

    return ~(UINT32) ( (-(INT64)(a^b)) >> 32);

}

// Other helper functions

SIZE_T

SYMCRYPT_CALL

SymCryptRoundUpPow2Sizet( SIZE_T v )

{

    SIZE_T res;

    SYMCRYPT_ASSERT( v <= (SIZE_T_MAX / 2) + 1);

    // If v is very large, then the result res might overflow.

    // As SIZE_T is an unsigned type, the overflow is defined to

    // be modulo 2^n for some n, and therefore we'll get res==0

    // which will terminate the loop.

    res = 1;

    while( res < v )

    {

        res += res;

        // Catch any overflows; should never happen but break to avoid infinite loop

        if( res == 0 )

        {

            break;

        }

    }

    return res;

}

//

// Copy data

//

VOID

SYMCRYPT_CALL

SymCryptScsCopy(

    _In_reads_( cbDst )     PCBYTE  pbSrc,

                            SIZE_T  cbSrc,

    _Out_writes_( cbDst )   PBYTE   pbDst,

                            SIZE_T  cbDst )

// Copy cbSrc bytes of pbSrc into pbDst without revealing cbSrc

// through side channels.

// - pbSrc/cbSrc: buffer to copy data from

// - pbDst/cbDst: buffer that receives the data

// Equivalent to:

//      n = min( cbSrc, cbDst )

//      pbDst[ 0.. n-1 ] = pbSrc[ 0 .. n - 1 ]

// cbSrc is protected from side-channels; cbDst is public.

// Note that pbSrc must be cbDst bytes long, not cbSrc bytes.

{

    UINT32 i;

    SYMCRYPT_ASSERT( cbSrc <= (1UL << 31) && cbDst <= (1UL << 31) );

    // Loop over the destination buffer and update each byte with the source data (if appropriate)

    // We round-robin loop over the source buffer

    for( i = 0; i < cbDst; i++ )

    {

        pbDst[ i ] ^= (pbSrc[ i ] ^ pbDst[ i ]) & SymCryptMask32LtU31( i, (UINT32) cbSrc );

    }

}

//

// Buffer rotation

// To recover a message from an encoding with variable data position we have to do a copy from a

// variable memory location. But our memory access pattern cannot depend on the secret location.

// This code rotates a given buffer by a variable # bytes without revealing the shift amount.

//

// For efficiency we do this using NATIVE_UINT values so that we get the best performance on each platform.

//

// The first step is to rotate the array between 0 and NATIVE_BYTES-1 bytes to get the proper word alignment.

// After that we only have to rotate the words.

// We do this using a sequence of swaps.

// Notation:

//  W[i]    array of words, 0 <= i < n where n is the # words, a power of 2.

//  s       Rotation amount (to the left). The value in W[s] at the start should appear in W[0] at the end.

//

// We use masked swaps as they seem to be more efficient then masked multiplexers.

// We can split this problem down recursively

//

// Function Rotate( W, n, s)

//  - Rotate W[0..n/2-1] by s mod n/2

//  - Rotate W[n/2..n-1] by s mod n/2

// for i in 0..n/2-1:

//      swap W[i] and W[i+n/2] if (i+s) % n >= n/2

//

// After the two half-sized rotates, each word is in the right position modulo n/2, so all that needs to be

// done in possibly swap (W[i],W[i+n/2]) pairs.

// Let W' be the array after the half-sized rotates. We have

// W'[i] = W[ (i + s) % (n/2) ] for i in 0..n/2

// In the final array W'' we should have W''[i] = W[ (i+s)%n ]

// So W''[i] = W'[i] when (i+s) % n = (i+s) % n/2 which is equivalent to (i+s)%n < n/2.

//

// We turn this into a non-recursive algorithm.

// First we do rotations on 2 words,

// then the fixups to make it 4-word rotations,

// then on to 8-words, etc.

// At each level we compute the masks for the swaps once, and re-use them for each copy

// As a further optimization, we merge the 1st and 2nd pass into one to reduce the # read/writes

//

// We avoid using / and % throughout to avoid any time-dependent instructions.

//

VOID

SYMCRYPT_CALL

SymCryptScsRotateBuffer(

    _Inout_updates_( cbBuffer ) PBYTE   pbBuffer,

                                SIZE_T  cbBuffer,

                                SIZE_T  lshift )

{

    NATIVE_UINT * pBuf;

    UINT32 n;

    UINT32 a;

    UINT32 b;

    UINT32 i;

    UINT32 j;

    UINT32 blockSize;

    UINT32 blockSizeLog;

    UINT32 blockSizeLimit;

    NATIVE_UINT V;

    NATIVE_UINT T;

    NATIVE_UINT A;

    NATIVE_UINT B;

    NATIVE_UINT C;

    NATIVE_UINT D;

    NATIVE_UINT M;

    NATIVE_UINT M0;

    NATIVE_UINT M1;

    NATIVE_UINT Mask[ 16 ];      // Size must be a power of 2

    SYMCRYPT_ASSERT( (cbBuffer & (cbBuffer - 1)) == 0 && cbBuffer >= MIN_BUFFER_SIZE );

    SYMCRYPT_ASSERT( lshift < cbBuffer );

    pBuf = (NATIVE_UINT *) pbBuffer;

    n = (UINT32)cbBuffer / NATIVE_BYTES;

    // First a rotate left by lshift % NATIVE_BYTES

    // This is more complex because shifting by NATIVE_BITS is not a defined operation, and behavior is different

    // on different CPUs.

    // Compute the shift amounts & mask

    // M = 0 if lshift % NATIVE_BYTES == 0, -1 otherwise

    a = 8 * (lshift & (NATIVE_BYTES-1));            // Core shift

    M = (-(NATIVE_INT)a) >> (NATIVE_BITS - 1);      // mask

    b = (NATIVE_BITS - a) & (UINT32) M;         // complementary shift, or 0 if it would be equal to NATIVE_BITS

    i = n;

    V = pBuf[0];

    do{

        // Loop invariant: i > 0 && v = pBuf[i] from before any changes;

        i--;

        T = pBuf[i];

        pBuf[i] = T >> a | ((V << b) & M);

        V = T;

    } while( i > 0 );

    // Now that the rotation is word-aligned, we can start our word rotation

    lshift >>= NATIVE_BYTES_LOG2;           // convert to # words to rotate.

    // We know we have at least 4 words, so we start with a pass do do 4-word rotations

    SYMCRYPT_ASSERT( n >= 4 );

    M = -(NATIVE_INT)(lshift & 1);

    M0 = -(NATIVE_INT)( ((lshift + 0) >> 1) & 1 );      // s + 0 mod 4 >= 2

    M1 = -(NATIVE_INT)( ((lshift + 1) >> 1) & 1 );      // s + 1 mod 4 >= 2

    for( i=0; i<n; i+=4 )

    {

        A = pBuf[i];

        B = pBuf[i+1];

        C = pBuf[i+2];

        D = pBuf[i+3];

        T = (A ^ B) & M;

        A ^= T;

        B ^= T;

        T = (C ^ D) & M;

        C ^= T;

        D ^= T;

        T = (A ^ C) & M0;

        A ^= T;

        C ^= T;

        T = (B ^ D) & M1;

        B ^= T;

        D ^= T;

        pBuf[i  ] = A;

        pBuf[i+1] = B;

        pBuf[i+2] = C;

        pBuf[i+3] = D;

    }

    // Do the swaps using the mask array

    blockSize = 4;  // size of rotated blocks

    blockSizeLog = 2;

    //

    // Using the mask array is beneficial as long as the array is used twice or more

    // Each swap loop processes 2 * blockSize of data, so the block size should never

    // be larger than n/4

    blockSizeLimit = SYMCRYPT_MIN( SYMCRYPT_ARRAY_SIZE( Mask ), n/4 );

    while( blockSize <= blockSizeLimit )

    {

        // Compute the masks for this level

        for( i=0; i<blockSize; i++ )

        {

            Mask[i] =-(NATIVE_INT)( ((i + lshift) >> blockSizeLog) & 1);

        }

        // Now swap the elements of pairs of blocks according to the masks

        for( i=0; i < n; i += 2 * blockSize )

        {

            for( j=0; j < blockSize; j++ )

            {

                A = pBuf[ i + j ];

                B = pBuf[ i + j + blockSize ];

                T = (A ^ B) & Mask[j];

                A ^= T;

                B ^= T;

                pBuf[ i + j ] = A;

                pBuf[ i + j + blockSize ] = B;

            }

        }

        blockSize *= 2;

        blockSizeLog += 1;

    }

    // Do the rest without using a mask array, either because we are only

    // going to use each mask value once, or because we don't have a large-enough

    // array

    while( blockSize < n  )

    {

        // Now swap the elements of pairs of blocks according to the masks

        for( i=0; i < n; i += 2 * blockSize )

        {

            for( j=0; j < blockSize; j++ )

            {

                M = -(NATIVE_INT)( ((j + lshift) >> blockSizeLog) & 1);

                A = pBuf[ i + j ];

                B = pBuf[ i + j + blockSize ];

                T = (A ^ B) & M;

                A ^= T;

                B ^= T;

                pBuf[ i + j ] = A;

                pBuf[ i + j + blockSize ] = B;

            }

        }

        blockSize *= 2;

        blockSizeLog += 1;

    }

}

//

// Map values in a side-channel safe way, typically used for mapping error codes.

//

// (pcMap, nMap) point to an array of nMap entries of type SYMCRYPT_UINT32_MAP;

// each entry specifies a single mapping. If u32Input matches the

// 'from' field, the return value will be the 'to' field value.

// If u32Input is not equal to any 'from' field values, the return value is u32Default.

// Both u32Input and the return value are treated as secrets w.r.t. side channels.

//

// If multiple map entries have the same 'from' field value, then the return value

// is one of the several 'to' field values; which one is not defined.

//

// This function is particularly useful when mapping error codes in situations where

// the actual error cannot be revealed through side channels.

//

UINT32

SYMCRYPT_CALL

SymCryptMapUint32(

                        UINT32                  u32Input,

                        UINT32                  u32Default,

    _In_reads_(nMap)    PCSYMCRYPT_UINT32_MAP   pcMap,

                        SIZE_T                  nMap)

{

    UINT32 mask;

    UINT32 u32Output    = u32Default;

    for (SIZE_T i = 0; i < nMap; ++i)

    {

        mask = SymCryptMask32EqU32(u32Input, pcMap[i].from);

        u32Output ^= (u32Output ^ pcMap[i].to) & mask;

    }

    return u32Output;

}