Skip to content

Commit 02c37be

Browse files
committed
Merged PR 15184356: Add upper bounds to probabilistic sampling loops in ML-DSA
This change adds loop bounds to ML-DSA functions which use probabilistic sampling, as defense-in-depth against denial of service by maliciously formed keys. There is no known vulnerability associated with this, but adding upper bounds provides additional hardening. Also fixes [#55](#55); thanks to Sunwoo Lee and Seunghyun Yoon, Korea Institute of Energy Technology (KENTECH) for reporting that issue. Related work items: #56920238
1 parent 2864ff0 commit 02c37be

4 files changed

Lines changed: 138 additions & 29 deletions

File tree

‎CHANGELOG.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,10 @@
22
New changes will be listed here as they are developed. The version number is determined
33
prior to the creation of a new release, based on the changes contained in that release.
44

5+
- Add loop bounds to ML-DSA functions which use probabilistic sampling, as defense-in-depth against denial of service by maliciously formed keys
6+
- There is no known vulnerability associated with this, but adding upper bounds provides additional hardening
7+
- Also fixes [#55](https://github.com/microsoft/SymCrypt/issues/55); thanks to Sunwoo Lee and Seunghyun Yoon, Korea Institute of Energy Technology (KENTECH) for filing this issue
8+
59
# Version 103.11.0
610

711
- Add Composite ML-KEM implementation

‎lib/mldsa.c‎

Lines changed: 37 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -107,14 +107,22 @@ SymCryptMlDsaKeyGenerateEx(
107107
SymCryptShake256Extract( pShakeState, pkMlDsakey->privateSigningSeed, sizeof(pkMlDsakey->privateSigningSeed), FALSE); // Wiped when pTemps is freed
108108
}
109109

110-
SymCryptMlDsaExpandA( pkMlDsakey->publicSeed, sizeof(pkMlDsakey->publicSeed), pkMlDsakey->pmA );
110+
scError = SymCryptMlDsaExpandA( pkMlDsakey->publicSeed, sizeof(pkMlDsakey->publicSeed), pkMlDsakey->pmA );
111+
if( scError != SYMCRYPT_NO_ERROR )
112+
{
113+
goto cleanup;
114+
}
111115

112-
SymCryptMlDsaExpandS(
116+
scError = SymCryptMlDsaExpandS(
113117
pkMlDsakey->pParams,
114118
privateVectorSeed,
115119
sizeof(privateVectorSeed),
116120
pkMlDsakey->pvs1,
117121
pkMlDsakey->pvs2 );
122+
if( scError != SYMCRYPT_NO_ERROR )
123+
{
124+
goto cleanup;
125+
}
118126

119127
// Convert s1 and s2 to NTT form
120128
SymCryptMlDsaVectorNTT( pkMlDsakey->pvs1 );
@@ -458,22 +466,25 @@ SymCryptMlDsaSignEx(
458466

459467
PBYTE pbW1Encoded = pTemps->pbScratch;
460468

461-
UINT16 k = 0;
462-
while( TRUE )
469+
// kappa is the counter for ExpandMask, incremented by nCols (l in FIPS 204) each iteration.
470+
// Since kappa increments by nCols each iteration, the upper bound on kappa is
471+
// SYMCRYPT_MLDSA_SIGN_INTERNAL_MAX_ITERATIONS * nCols.
472+
//
473+
// It's okay to leak how many iterations this loop takes because the SHAKE inputs and
474+
// outputs are still unpredictable; this does not leak information about the private key
475+
const UINT32 kappaLimit = (SYMCRYPT_MLDSA_SIGN_INTERNAL_MAX_ITERATIONS * pParams->nCols);
476+
SYMCRYPT_ASSERT( kappaLimit <= UINT16_MAX );
477+
478+
for( UINT16 kappa = 0; kappa < (UINT16) kappaLimit; kappa += (UINT16) pParams->nCols )
463479
{
464480
SymCryptMlDsaExpandMask(
465481
pParams,
466482
pShakeState,
467483
privateRandom,
468484
sizeof(privateRandom),
469-
k,
485+
kappa,
470486
pvMask );
471487

472-
// Increment k early so we can continue to the next loop iteration when validity checks fail
473-
// It's okay to leak how many iterations this loop takes because the SHAKE inputs and
474-
// outputs are still unpredictable; this does not leak information about the private key
475-
k += (UINT16) pParams->nCols;
476-
477488
SymCryptMlDsaMatrixVectorMontMul( pkMlDsakey->pmA, pvMask, pvW, pTemps->pePolyElements[0] );
478489

479490
for(UINT8 i = 0; i < pvW->nElems; ++i)
@@ -498,7 +509,11 @@ SymCryptMlDsaSignEx(
498509
// Calculate challenge
499510
// Reusing poly element 0 for challenge (previously temp space for multiplication)
500511
PSYMCRYPT_MLDSA_POLYELEMENT peC = pTemps->pePolyElements[0];
501-
SymCryptMlDsaSampleInBall( pParams, commitmentHash, pParams->cbCommitmentHash, peC );
512+
scError = SymCryptMlDsaSampleInBall( pParams, commitmentHash, pParams->cbCommitmentHash, peC );
513+
if( scError != SYMCRYPT_NO_ERROR )
514+
{
515+
goto cleanup;
516+
}
502517

503518
SymCryptMlDsaPolyElementNTT( peC );
504519
SymCryptMlDsaPolyElementMulR( peC );
@@ -568,7 +583,12 @@ SymCryptMlDsaSignEx(
568583
break;
569584
}
570585

571-
SYMCRYPT_ASSERT( pvHint != NULL );
586+
if( pvHint == NULL )
587+
{
588+
// If we do not have a hint here, we exceeded the maximum number of iterations
589+
scError = SYMCRYPT_EXTERNAL_FAILURE;
590+
goto cleanup;
591+
}
572592

573593
SymCryptMlDsaSigEncode(
574594
pParams,
@@ -855,11 +875,15 @@ SymCryptMlDsaVerifyEx(
855875
goto cleanup;
856876
}
857877

858-
SymCryptMlDsaSampleInBall(
878+
scError = SymCryptMlDsaSampleInBall(
859879
pParams,
860880
commitmentHash,
861881
pParams->cbCommitmentHash,
862882
peC );
883+
if( scError != SYMCRYPT_NO_ERROR )
884+
{
885+
goto cleanup;
886+
}
863887

864888
SymCryptMlDsaVectorNTT( pvResponse );
865889

‎lib/mldsa_primitives.c‎

Lines changed: 79 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -834,13 +834,16 @@ SymCryptMlDsaMatrixVectorMontMul(
834834
}
835835

836836
_Use_decl_annotations_
837-
VOID
837+
SYMCRYPT_ERROR
838838
SYMCRYPT_CALL
839839
SymCryptMlDsaRejNttPoly(
840840
PCBYTE pbRejNttPolySeed,
841841
SIZE_T cbRejNttPolySeed,
842842
PSYMCRYPT_MLDSA_POLYELEMENT peDst )
843843
{
844+
SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
845+
UINT32 nIterations = 0;
846+
844847
SYMCRYPT_ASSERT( cbRejNttPolySeed == SYMCRYPT_MLDSA_REJNTTPOLY_SEED_SIZE );
845848

846849
SYMCRYPT_SHAKE128_STATE shakeState;
@@ -857,23 +860,34 @@ SymCryptMlDsaRejNttPoly(
857860
// CoeffFromThreeBytes from FIPS 204
858861
do
859862
{
863+
if( nIterations >= SYMCRYPT_MLDSA_REJNTTPOLY_MAX_ITERATIONS )
864+
{
865+
scError = SYMCRYPT_EXTERNAL_FAILURE;
866+
goto cleanup;
867+
}
860868
SymCryptShake128Extract( &shakeState, shakeBytes, 3, FALSE );
861869
shakeBytes[2] &= 0x7F; // if b2 > 127, b2 -= 128
862870
coeff = SYMCRYPT_LOAD_LSBFIRST32( shakeBytes );
871+
nIterations++;
863872
} while (coeff >= SYMCRYPT_MLDSA_Q);
864873

865874
peDst->coeffs[i] = coeff;
866875
}
876+
877+
cleanup:
878+
return scError;
867879
}
868880

869881
_Use_decl_annotations_
870-
VOID
882+
SYMCRYPT_ERROR
871883
SYMCRYPT_CALL
872884
SymCryptMlDsaExpandA(
873885
PCBYTE pbPublicSeed,
874886
SIZE_T cbPublicSeed,
875887
PSYMCRYPT_MLDSA_MATRIX pmA )
876888
{
889+
SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
890+
877891
SYMCRYPT_ASSERT( cbPublicSeed == SYMCRYPT_MLDSA_PUBLIC_SEED_SIZE );
878892
C_ASSERT( SYMCRYPT_MLDSA_REJNTTPOLY_SEED_SIZE == SYMCRYPT_MLDSA_PUBLIC_SEED_SIZE + 2 );
879893

@@ -890,10 +904,16 @@ SymCryptMlDsaExpandA(
890904
rejNttSeed[SYMCRYPT_MLDSA_REJNTTPOLY_SEED_SIZE - 1] = i;
891905

892906
#pragma prefast( suppress: 6385, "False warning - reading invalid data from rejNttSeed" );
893-
SymCryptMlDsaRejNttPoly( rejNttSeed, sizeof(rejNttSeed), SYMCRYPT_INTERNAL_MLDSA_MATRIX_ELEMENT( i, j, pmA ) );
894-
907+
scError = SymCryptMlDsaRejNttPoly( rejNttSeed, sizeof(rejNttSeed), SYMCRYPT_INTERNAL_MLDSA_MATRIX_ELEMENT( i, j, pmA ) );
908+
if( scError != SYMCRYPT_NO_ERROR )
909+
{
910+
goto cleanup;
911+
}
895912
}
896913
}
914+
915+
cleanup:
916+
return scError;
897917
}
898918

899919
_Use_decl_annotations_
@@ -922,14 +942,16 @@ SymCryptMlDsaCoeffFromHalfByte(
922942
}
923943

924944
_Use_decl_annotations_
925-
VOID
945+
SYMCRYPT_ERROR
926946
SYMCRYPT_CALL
927947
SymCryptMlDsaRejBoundedPoly(
928948
PCSYMCRYPT_MLDSA_INTERNAL_PARAMS pParams,
929949
PCBYTE pbRejBoundedPolySeed,
930950
SIZE_T cbRejBoundedPolySeed,
931951
PSYMCRYPT_MLDSA_POLYELEMENT peDst )
932952
{
953+
SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
954+
933955
SYMCRYPT_ASSERT( cbRejBoundedPolySeed == SYMCRYPT_MLDSA_REJBOUNDEDPOLY_SEED_SIZE );
934956

935957
SYMCRYPT_SHAKE256_STATE shakeState;
@@ -940,8 +962,16 @@ SymCryptMlDsaRejBoundedPoly(
940962
UINT32 i = 0;
941963
INT8 z0, z1;
942964

965+
UINT32 nIterations = 0;
966+
943967
do
944968
{
969+
if( nIterations >= SYMCRYPT_MLDSA_REJBOUNDEDPOLY_MAX_ITERATIONS )
970+
{
971+
scError = SYMCRYPT_EXTERNAL_FAILURE;
972+
goto cleanup;
973+
}
974+
945975
// Note on sidechannel safety: the rejection sampling here can leak which bytes of the SHAKE
946976
// output are used and which are rejected. However, bytes themselves are not leaked. This
947977
// may allow the attacker to more quickly eliminate incorrect seed values when doing an
@@ -950,6 +980,7 @@ SymCryptMlDsaRejBoundedPoly(
950980
SymCryptShake256Extract( &shakeState, &shakeByte, sizeof(shakeByte), FALSE );
951981
z0 = SymCryptMlDsaCoeffFromHalfByte( pParams, shakeByte & 0x0F );
952982
z1 = SymCryptMlDsaCoeffFromHalfByte( pParams, shakeByte >> 4 );
983+
nIterations++;
953984

954985
SYMCRYPT_ASSERT( z0 == INT8_MIN || (( z0 + pParams->privateKeyRange >= 0 ) && ( z0 + pParams->privateKeyRange <= 2 * pParams->privateKeyRange )) );
955986
SYMCRYPT_ASSERT( z1 == INT8_MIN || (( z1 + pParams->privateKeyRange >= 0 ) && ( z1 + pParams->privateKeyRange <= 2 * pParams->privateKeyRange )) );
@@ -968,11 +999,14 @@ SymCryptMlDsaRejBoundedPoly(
968999

9691000
} while( i < SYMCRYPT_MLWE_POLYNOMIAL_COEFFICIENTS );
9701001

1002+
cleanup:
9711003
SymCryptWipeKnownSize( &shakeState, sizeof(shakeState) );
1004+
1005+
return scError;
9721006
}
9731007

9741008
_Use_decl_annotations_
975-
VOID
1009+
SYMCRYPT_ERROR
9761010
SYMCRYPT_CALL
9771011
SymCryptMlDsaExpandS(
9781012
PCSYMCRYPT_MLDSA_INTERNAL_PARAMS pParams,
@@ -981,6 +1015,8 @@ SymCryptMlDsaExpandS(
9811015
PSYMCRYPT_MLDSA_VECTOR pvs1,
9821016
PSYMCRYPT_MLDSA_VECTOR pvs2 )
9831017
{
1018+
SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
1019+
9841020
SYMCRYPT_ASSERT( cbPrivateVectorSeed == SYMCRYPT_MLDSA_PRIVATE_VECTOR_SEED_SIZE );
9851021
C_ASSERT( SYMCRYPT_MLDSA_REJBOUNDEDPOLY_SEED_SIZE == SYMCRYPT_MLDSA_PRIVATE_VECTOR_SEED_SIZE + 2 );
9861022

@@ -995,30 +1031,44 @@ SymCryptMlDsaExpandS(
9951031
for(UINT16 i = 0; i < nCols; ++i)
9961032
{
9971033
SYMCRYPT_STORE_LSBFIRST16( rejBoundedPolySeed + SYMCRYPT_MLDSA_REJBOUNDEDPOLY_SEED_SIZE - sizeof(UINT16), i );
998-
SymCryptMlDsaRejBoundedPoly( pParams, rejBoundedPolySeed, sizeof(rejBoundedPolySeed),
1034+
scError = SymCryptMlDsaRejBoundedPoly( pParams, rejBoundedPolySeed, sizeof(rejBoundedPolySeed),
9991035
SYMCRYPT_INTERNAL_MLDSA_VECTOR_ELEMENT( i, pvs1 ) );
1036+
if( scError != SYMCRYPT_NO_ERROR )
1037+
{
1038+
goto cleanup;
1039+
}
10001040
}
10011041

10021042
for(UINT16 i = 0; i < nRows; ++i)
10031043
{
10041044
SYMCRYPT_STORE_LSBFIRST16( rejBoundedPolySeed + SYMCRYPT_MLDSA_REJBOUNDEDPOLY_SEED_SIZE - sizeof(UINT16), (UINT16) nCols + i );
10051045
#pragma prefast( suppress: 6385, "False warning - reading invalid data from rejBoundedPolySeed" ); // Doesn't trigger in previous loop for some reason
1006-
SymCryptMlDsaRejBoundedPoly( pParams, rejBoundedPolySeed, sizeof(rejBoundedPolySeed),
1046+
scError = SymCryptMlDsaRejBoundedPoly( pParams, rejBoundedPolySeed, sizeof(rejBoundedPolySeed),
10071047
SYMCRYPT_INTERNAL_MLDSA_VECTOR_ELEMENT( i, pvs2 ) );
1048+
if( scError != SYMCRYPT_NO_ERROR )
1049+
{
1050+
goto cleanup;
1051+
}
10081052
}
10091053

1054+
cleanup:
10101055
SymCryptWipeKnownSize( rejBoundedPolySeed, sizeof(rejBoundedPolySeed) );
1056+
1057+
return scError;
10111058
}
10121059

10131060
_Use_decl_annotations_
1014-
VOID
1061+
SYMCRYPT_ERROR
10151062
SYMCRYPT_CALL
10161063
SymCryptMlDsaSampleInBall(
10171064
PCSYMCRYPT_MLDSA_INTERNAL_PARAMS pParams,
10181065
PCBYTE pbCommitmentHash,
10191066
SIZE_T cbCommitmentHash,
10201067
PSYMCRYPT_MLDSA_POLYELEMENT peChallenge )
10211068
{
1069+
SYMCRYPT_ERROR scError = SYMCRYPT_NO_ERROR;
1070+
1071+
10221072
SymCryptMlDsaPolyElementSetZero( peChallenge );
10231073

10241074
SYMCRYPT_SHAKE256_STATE shakeState;
@@ -1038,9 +1088,16 @@ SymCryptMlDsaSampleInBall(
10381088
++i)
10391089
{
10401090
BYTE j = 0;
1091+
UINT32 nIterations = 0;
10411092
do
10421093
{
1094+
if( nIterations >= SYMCRYPT_MLDSA_SAMPLEINBALL_MAX_ITERATIONS )
1095+
{
1096+
scError = SYMCRYPT_EXTERNAL_FAILURE;
1097+
goto cleanup;
1098+
}
10431099
SymCryptShake256Extract( &shakeState, &j, sizeof(j), FALSE );
1100+
nIterations++;
10441101
} while( j > i );
10451102

10461103
peChallenge->coeffs[i] = peChallenge->coeffs[j];
@@ -1052,7 +1109,10 @@ SymCryptMlDsaSampleInBall(
10521109
peChallenge->coeffs[j] = ((SYMCRYPT_MLDSA_Q - 1) & negativeMask) | (1 & ~negativeMask);
10531110
}
10541111

1112+
cleanup:
10551113
SymCryptWipeKnownSize( &shakeState, sizeof(shakeState) );
1114+
1115+
return scError;
10561116
}
10571117

10581118
_Use_decl_annotations_
@@ -1342,10 +1402,14 @@ SymCryptMlDsaPkDecode(
13421402

13431403
SymCryptMlDsaVectorNTT( pkMlDsakey->pvt1 );
13441404

1345-
SymCryptMlDsaExpandA(
1405+
scError = SymCryptMlDsaExpandA(
13461406
pkMlDsakey->publicSeed,
13471407
SYMCRYPT_MLDSA_PUBLIC_SEED_SIZE,
13481408
pkMlDsakey->pmA );
1409+
if( scError != SYMCRYPT_NO_ERROR )
1410+
{
1411+
goto cleanup;
1412+
}
13491413

13501414
SymCryptShake256Result( pShakeState, pkMlDsakey->publicKeyHash );
13511415

@@ -1516,7 +1580,11 @@ SymCryptMlDsaSkDecode(
15161580
pbCurr += SYMCRYPT_MLDSA_PUBLIC_KEY_HASH_SIZE;
15171581

15181582
// Expand A matrix
1519-
SymCryptMlDsaExpandA( pkMlDsakey->publicSeed, SYMCRYPT_MLDSA_PUBLIC_SEED_SIZE, pkMlDsakey->pmA );
1583+
scError = SymCryptMlDsaExpandA( pkMlDsakey->publicSeed, SYMCRYPT_MLDSA_PUBLIC_SEED_SIZE, pkMlDsakey->pmA );
1584+
if( scError != SYMCRYPT_NO_ERROR )
1585+
{
1586+
goto cleanup;
1587+
}
15201588

15211589
scError = SymCryptMlDsaVectorDecode(
15221590
pbCurr,

0 commit comments

Comments
 (0)