tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

rsa_blind.c (13172B)

      1 /* This Source Code Form is subject to the terms of the Mozilla Public
      2 * License, v. 2.0. If a copy of the MPL was not distributed with this
      3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      4 
      5 /*
      6 * Implementation of RSA Blind Signatures.
      7 * (https://datatracker.ietf.org/doc/draft-irtf-cfrg-rsa-blind-signatures/)
      8 */
      9 #ifdef FREEBL_NO_DEPEND
     10 #include "stubs.h"
     11 #endif
     12 
     13 #include "secerr.h"
     14 #include "blapi.h"
     15 #include "mpi.h"
     16 #include "secitem.h"
     17 #include "prerr.h"
     18 #include "blapii.h"
     19 #include "secmpi.h"
     20 #include "mpi-priv.h"
     21 #include "pqg.h"
     22 
     23 /*#define RSA_DEBUG*/
     24 
     25 #define MP_DIGIT_BYTE (MP_DIGIT_BIT / PR_BITS_PER_BYTE)
     26 
     27 #ifdef RSA_DEBUG
     28 
     29 void
     30 rsaBlind_Print(PRUint8* m, size_t t)
     31 {
     32    for (int i = 0; i < t; i++) {
     33        if (i % 16 == 0)
     34            printf("\n");
     35        printf("%02x ", m[i]);
     36    }
     37    printf("\n \n");
     38 }
     39 
     40 void
     41 mp_print_buf(mp_int* mp)
     42 {
     43    for (int i = MP_USED(mp) - 1; i >= 0; i--) {
     44        if (i % 2 == 1)
     45            printf("\n");
     46        printf("%016lx  ", (long unsigned int)MP_DIGIT(mp, i));
     47    }
     48    printf("\n \n");
     49 }
     50 #endif
     51 
     52 /*
     53 * 4.1. Prepare
     54 * There are two types of preparation functions:
     55 * an identity preparation function, and a randomized preparation function.
     56 * The identity preparation function returns the input message without transformation,
     57 * i.e., msg = PrepareIdentity(msg).
     58 * The randomized preparation function augments the input message with fresh randomness.
     59 *
     60 * Inputs:
     61 * - msg, message to be signed, a byte string
     62 *
     63 * Outputs:
     64 * - input_msg, a byte string that is 32 bytes longer than msg
     65 
     66 * Steps:
     67 *  1. msgPrefix = random(32)
     68 *  2. input_msg = concat(msgPrefix, msg)
     69 *  3. output input_msg
     70 */
     71 
     72 SECStatus
     73 RSABlinding_Prepare(PRUint8* preparedMessage, size_t preparedMessageLen, const PRUint8* msg,
     74                    size_t msgLen, PRBool isDeterministic)
     75 {
     76    if (!preparedMessage || !msg) {
     77        PORT_SetError(SEC_ERROR_INVALID_ARGS);
     78        return SECFailure;
     79    }
     80 
     81    /* The identity preparation function: */
     82    if (isDeterministic) {
     83        if (preparedMessageLen < msgLen) {
     84            PORT_SetError(SEC_ERROR_INVALID_ARGS);
     85            return SECFailure;
     86        }
     87        PORT_Memcpy(preparedMessage, msg, msgLen);
     88    }
     89    /* The randomized preparation function: */
     90    else {
     91        /* 1. msgPrefix = random(32)*/
     92        PRUint8 lenRandom = 32;
     93        if (msgLen > UINT32_MAX - lenRandom) {
     94            PORT_SetError(SEC_ERROR_INPUT_LEN);
     95            return SECFailure;
     96        }
     97        if (preparedMessageLen < msgLen + lenRandom) {
     98            PORT_SetError(SEC_ERROR_INVALID_ARGS);
     99            return SECFailure;
    100        }
    101 
    102        RNG_GenerateGlobalRandomBytes(preparedMessage, lenRandom);
    103        /* 2. input_msg = concat(msgPrefix, msg)*/
    104        PORT_Memcpy(preparedMessage + lenRandom, msg, msgLen);
    105    }
    106 
    107    return SECSuccess;
    108 }
    109 
    110 /* RSA Blind Signatures
    111 * Blind(pkS, msg)
    112 * Parameters:
    113 * - kLen, the length in bytes of the RSA modulus n
    114 * - Hash, the hash function used to hash the message
    115 * - MGF, the mask generation function
    116 * - sLen, the length in bytes of the salt
    117 *
    118 * Inputs:
    119 * - pkS, server public key (n, e)
    120 * - msg, message to be signed, a byte string
    121 *
    122 * Outputs:
    123 * - blinded_msg, a byte string of length kLen
    124 * - inv, an integer used to unblind the signature in Finalize
    125 */
    126 
    127 /* The length of the random buffer is n. */
    128 SECStatus
    129 RSABlinding_Blind(HASH_HashType hashAlg, PRUint8* blindedMsg, size_t blindedMsgLen,
    130                  PRUint8* inv, size_t invLen, const PRUint8* msg, size_t msgLen,
    131                  const PRUint8* salt, size_t saltLen,
    132                  RSAPublicKey* pkS, const PRUint8* randomBuf, size_t randomBufLen)
    133 {
    134    if (!blindedMsgLen || !inv || !msg || !pkS) {
    135        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    136        return SECFailure;
    137    }
    138 
    139    mp_err err = MP_OKAY;
    140    const size_t modulus_len = pkS->modulus.len;
    141 
    142    if (blindedMsgLen != modulus_len || invLen != modulus_len) {
    143        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    144        return SECFailure;
    145    }
    146 
    147    if (randomBufLen != 0 && randomBufLen != modulus_len) {
    148        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    149        return SECFailure;
    150    }
    151 
    152    if ((PRUint64)pkS->modulus.len * PR_BITS_PER_BYTE - 1 > UINT32_MAX) {
    153        PORT_SetError(SEC_ERROR_INPUT_LEN);
    154        return SECFailure;
    155    }
    156 
    157    PRUint8* encoded_msg = PORT_ZAlloc(modulus_len);
    158    PRUint8* rBuf = PORT_ZAlloc(modulus_len);
    159    PRUint8* xBuf = PORT_ZAlloc(modulus_len);
    160 
    161    mp_int m, n, r, mask, invR, rsavp1, blindSign;
    162    MP_DIGITS(&m) = 0;
    163    MP_DIGITS(&invR) = 0;
    164    MP_DIGITS(&rsavp1) = 0;
    165    MP_DIGITS(&blindSign) = 0;
    166    MP_DIGITS(&n) = 0;
    167    MP_DIGITS(&r) = 0;
    168    MP_DIGITS(&mask) = 0;
    169 
    170    CHECK_MPI_OK(mp_init(&m));
    171    CHECK_MPI_OK(mp_init(&invR));
    172    CHECK_MPI_OK(mp_init(&rsavp1));
    173    CHECK_MPI_OK(mp_init(&blindSign));
    174    CHECK_MPI_OK(mp_init(&r));
    175    CHECK_MPI_OK(mp_init(&n));
    176    CHECK_MPI_OK(mp_init(&mask));
    177 
    178    CHECK_MPI_OK(mp_read_unsigned_octets(&n, pkS->modulus.data, pkS->modulus.len));
    179    SECStatus rv = SECFailure;
    180    size_t bit_len_n = pkS->modulus.len * PR_BITS_PER_BYTE - 1;
    181 
    182    if (!randomBuf || randomBufLen == 0) {
    183        CHECK_MPI_OK(mp_2expt(&mask, bit_len_n + 1));
    184        CHECK_MPI_OK(mp_sub_d(&mask, 1, &mask));
    185        do {
    186            CHECK_MPI_OK(mpp_random_secure(&r));
    187            for (size_t i = 0; i < mask.alloc; i++) {
    188                r.dp[i] = mask.dp[i] & r.dp[i];
    189            }
    190        } while (mp_cmp(&r, &n) != MP_LT);
    191        CHECK_MPI_OK(mp_init_copy(&r, &mask));
    192    } else {
    193        CHECK_MPI_OK(mp_read_unsigned_octets(&r, randomBuf, pkS->modulus.len));
    194    }
    195 
    196    /* 1. encoded_msg = EMSA-PSS-ENCODE(msg, bit_len(n)). */
    197    PRUint8 msgHash[HASH_LENGTH_MAX] = { 0 };
    198    rv = PQG_HashBuf(hashAlg, msgHash, msg, msgLen);
    199    if (rv != SECSuccess) {
    200        goto cleanup;
    201    }
    202 
    203    rv = RSA_EMSAEncodePSS(encoded_msg, pkS->modulus.len, bit_len_n, msgHash, hashAlg, hashAlg, salt, saltLen);
    204 
    205    /* 2. If EMSA-PSS-ENCODE raises an error, raise the error and stop. */
    206    if (rv != SECSuccess) {
    207        PORT_SetError(SEC_ERROR_FAILED_TO_ENCODE_DATA);
    208        goto cleanup;
    209    }
    210 
    211 #ifdef RSA_DEBUG
    212    printf("encoded_msg: \n");
    213    rsaBlind_Print(encoded_msg, modulus_len);
    214 #endif
    215 
    216    /* 3. m = bytes_to_int(encoded_msg). */
    217    CHECK_MPI_OK(mp_read_unsigned_octets(&m, encoded_msg, pkS->modulus.len));
    218 
    219    /* 4. c = mp_is_coprime(m, n).
    220     ** 5. If c is false, raise an "invalid input" error and stop.
    221     ** 7. inv = inverse_mod(r, n)
    222     */
    223    err = mp_invmod(&r, &n, &invR);
    224    if (err == MP_UNDEF) {
    225        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    226        goto cleanup;
    227    } else if (err) {
    228        goto cleanup;
    229    }
    230 
    231 #ifdef RSA_DEBUG
    232    printf("inverse r: \n");
    233    mp_print_buf(&invR);
    234 #endif
    235 
    236    /* 9. x = RSAVP1(pkS, r)*/
    237    CHECK_MPI_OK(mp_to_fixlen_octets(&r, rBuf, pkS->modulus.len));
    238    rv = RSA_PublicKeyOp(pkS, xBuf, rBuf);
    239    if (rv != SECSuccess) {
    240        goto cleanup;
    241    }
    242    CHECK_MPI_OK(mp_read_unsigned_octets(&rsavp1, xBuf, pkS->modulus.len));
    243 
    244 #ifdef RSA_DEBUG
    245    printf("x (RSAVP1): \n");
    246    mp_print_buf(&rsavp1);
    247 #endif
    248 
    249    /* 10. z = m * x mod n*/
    250    CHECK_MPI_OK(mp_mulmod(&m, &rsavp1, &n, &blindSign));
    251 
    252 #ifdef RSA_DEBUG
    253    printf("blindSign: \n");
    254    mp_print_buf(&blindSign);
    255 #endif
    256 
    257    CHECK_MPI_OK(mp_to_fixlen_octets(&blindSign, blindedMsg, blindedMsgLen));
    258    CHECK_MPI_OK(mp_to_fixlen_octets(&invR, inv, invLen));
    259 
    260 cleanup:
    261    mp_clear(&m);
    262    mp_clear(&n);
    263    mp_clear(&r);
    264    mp_clear(&invR);
    265    mp_clear(&rsavp1);
    266    mp_clear(&blindSign);
    267    mp_clear(&mask);
    268 
    269    PORT_Free(encoded_msg);
    270    PORT_Free(rBuf);
    271    PORT_Free(xBuf);
    272 
    273    if (err) {
    274        MP_TO_SEC_ERROR(err);
    275        return SECFailure;
    276    }
    277 
    278    return rv;
    279 }
    280 
    281 /* 4.3. BlindSign
    282 * BlindSign(skS, blinded_msg)
    283 *
    284 * Parameters:
    285 *  - kLen, the length in bytes of the RSA modulus n
    286 *
    287 * Inputs:
    288 *  - skS, server private key
    289 *  - blinded_msg, encoded and blinded message to be signed, a byte string
    290 */
    291 
    292 SECStatus
    293 RSABlinding_BlindSign(PRUint8* blindSig, size_t blindSigLen,
    294                      const PRUint8* blindedMsg, size_t blindedMsgLen, RSAPrivateKey* skS, RSAPublicKey* pkS)
    295 {
    296    SECStatus rv = SECSuccess;
    297    if (!blindSig || !blindedMsg || !skS) {
    298        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    299        return SECFailure;
    300    }
    301 
    302    if ((blindSigLen != skS->modulus.len) || (skS->modulus.len != pkS->modulus.len) || (blindedMsgLen != skS->modulus.len)) {
    303        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    304        return SECFailure;
    305    }
    306 
    307    PRUint8* sBuf = (PRUint8*)PORT_Alloc(skS->modulus.len);
    308    PRUint8* mPrimeBuf = (PRUint8*)PORT_Alloc(pkS->modulus.len);
    309 
    310    mp_err err = MP_OKAY;
    311    mp_int z, mPrime;
    312    MP_DIGITS(&z) = 0;
    313    MP_DIGITS(&mPrime) = 0;
    314 
    315    CHECK_MPI_OK(mp_init(&z));
    316    CHECK_MPI_OK(mp_init(&mPrime));
    317 
    318    CHECK_MPI_OK(mp_read_unsigned_octets(&z, blindedMsg, skS->modulus.len));
    319 
    320    /* 2. s = rsasp1(skS, z). */
    321    rv = RSA_PrivateKeyOp(skS, sBuf, blindedMsg);
    322    if (rv != SECSuccess) {
    323        goto cleanup;
    324    }
    325 
    326 #ifdef RSA_DEBUG
    327    printf("Blinded Signature: \n");
    328    mp_print_buf(&s);
    329 #endif
    330 
    331    /* 3. mPrime = rsavp1(pkS, s). */
    332    rv = RSA_PublicKeyOp(pkS, mPrimeBuf, sBuf);
    333    if (rv != SECSuccess) {
    334        goto cleanup;
    335    }
    336 
    337    CHECK_MPI_OK(mp_read_unsigned_octets(&mPrime, mPrimeBuf, skS->modulus.len));
    338 
    339 #ifdef RSA_DEBUG
    340    printf("mPrime: \n");
    341    mp_print_buf(&mPrime);
    342 #endif
    343 
    344    /* 4. If m != m', raise "signing failure" and stop. */
    345    PRBool isBlindedMsgCorrect = mp_cmp(&mPrime, &z) == 0;
    346 
    347    /* 5. blind_sig = int_to_bytes(s, kLen). */
    348    if (isBlindedMsgCorrect) {
    349        PORT_Memcpy(blindSig, sBuf, skS->modulus.len);
    350    }
    351 
    352 cleanup:
    353    mp_clear(&z);
    354    mp_clear(&mPrime);
    355 
    356    PORT_Free(sBuf);
    357    PORT_Free(mPrimeBuf);
    358 
    359    if (err) {
    360        MP_TO_SEC_ERROR(err);
    361        return SECFailure;
    362    }
    363    if (rv != SECSuccess) {
    364        return SECFailure;
    365    }
    366 
    367    return SECSuccess;
    368 }
    369 
    370 /*
    371 * 4.4. Finalize.
    372 * Finalize validates the server's response, unblinds the message to produce a signature,
    373 * verifies it for correctness, and outputs the signature upon success.
    374 *
    375 *  Parameters:
    376 * - kLen, the length in bytes of the RSA modulus n
    377 * - Hash, the hash function used to hash the message
    378 * - MGF, the mask generation function
    379 * - sLen, the length in bytes of the salt
    380 *
    381 * Inputs:
    382 * - pkS, server public key (n, e)
    383 * - msg, message to be signed, a byte string
    384 * - blind_sig, signed and blinded element, a byte string of
    385 *   length kLen
    386 * - inv, inverse of the blind, an integer
    387 *
    388 * Outputs:
    389 * - sig, a byte string of length kLen
    390 *
    391 * Blinded Signature Len should be the same as modulus len.
    392 */
    393 
    394 SECStatus
    395 RSABlinding_Finalize(HASH_HashType hashAlg, PRUint8* signature, const PRUint8* msg, PRUint32 msgLen,
    396                     const PRUint8* blindSig, size_t blindSigLen,
    397                     const PRUint8* inv, size_t invLen, RSAPublicKey* pkS, size_t saltLen)
    398 {
    399    if (!signature || !msg || !blindSig || !inv || !pkS || msgLen == 0) {
    400        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    401        return SECFailure;
    402    }
    403 
    404    if (blindSigLen != pkS->modulus.len || invLen != pkS->modulus.len) {
    405        PORT_SetError(SEC_ERROR_INVALID_ARGS);
    406        return SECFailure;
    407    }
    408 
    409    mp_err err = MP_OKAY;
    410    SECStatus rv = SECFailure;
    411 
    412    mp_int inv_mp, blindSig_mp, n_mp, sig_mp;
    413    MP_DIGITS(&inv_mp) = 0;
    414    MP_DIGITS(&blindSig_mp) = 0;
    415    MP_DIGITS(&n_mp) = 0;
    416    MP_DIGITS(&sig_mp) = 0;
    417 
    418    CHECK_MPI_OK(mp_init(&n_mp));
    419    CHECK_MPI_OK(mp_init(&inv_mp));
    420    CHECK_MPI_OK(mp_init(&blindSig_mp));
    421    CHECK_MPI_OK(mp_init(&sig_mp));
    422 
    423    CHECK_MPI_OK(mp_read_unsigned_octets(&n_mp, pkS->modulus.data, pkS->modulus.len));
    424    CHECK_MPI_OK(mp_read_unsigned_octets(&blindSig_mp, blindSig, pkS->modulus.len));
    425    CHECK_MPI_OK(mp_read_unsigned_octets(&inv_mp, inv, pkS->modulus.len));
    426 
    427    /* 3. s = z * inv mod n. */
    428    CHECK_MPI_OK(mp_mulmod(&blindSig_mp, &inv_mp, &n_mp, &sig_mp));
    429 
    430 #ifdef RSA_DEBUG
    431    printf("Computed Signature : \n");
    432    mp_print_buf(&sig_mp);
    433 #endif
    434 
    435    CHECK_MPI_OK(mp_to_fixlen_octets(&sig_mp, signature, pkS->modulus.len));
    436 
    437    PRUint8 mHash[HASH_LENGTH_MAX] = { 0 };
    438    rv = PQG_HashBuf(hashAlg, mHash, msg, msgLen);
    439    if (rv != SECSuccess) {
    440        PORT_SetError(SEC_ERROR_BAD_DATA);
    441        goto cleanup;
    442    }
    443 
    444    /* 5. result = RSASSA-PSS-VERIFY(pkS, msg, sig) with Hash, MGF, and sLen as defined in the parameters. */
    445    rv = RSA_CheckSignPSS(pkS, hashAlg, hashAlg, saltLen, signature, sig_mp.used * MP_DIGIT_BYTE, mHash, 0);
    446 
    447    /* If result = "valid signature", output sig, else raise "invalid signature" and stop. */
    448    if (rv != SECSuccess) {
    449        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
    450    }
    451 
    452 #ifdef RSA_DEBUG
    453    if (rv == SECFailure) {
    454        printf("%s\n", "RSA CheckSignPSS has failed. ");
    455    } else {
    456        printf("%s\n", "RSA CheckSignPSS has succeeded. ");
    457    }
    458 #endif
    459 
    460 cleanup:
    461    mp_clear(&inv_mp);
    462    mp_clear(&blindSig_mp);
    463    mp_clear(&n_mp);
    464    mp_clear(&sig_mp);
    465    if (err) {
    466        MP_TO_SEC_ERROR(err);
    467        return SECFailure;
    468    }
    469 
    470    return rv;
    471 }