SHA256WITHDSA verify problem

dominikkv commented 2 years ago

Hi,

I'm using your library to verify a DSA signature. Generally, this works fine, but I have one signature which causes trouble. When I call Signer.VerifySignature(sigBytes), I get a silent EArgumentCryptoLibException:

Value out of range, "x"

The result is then false, but it should be true. The same signature + content verifies successfully in a java project, so the signature + content are definately valid.

My analysis: When parsing the ASN.1 structure of the signature, the r value is a TBigInteger with a sign of -1. There is a ClpSignersEncodings.TStandardDsaEncoding.CheckValue(const n, x: TBigInteger) function which raises this exception when the sign is negative.

I have successfully validated the signature with this two dirty hacks:

ClpBigInteger.TBigInteger.ParseBytes(): When r gets created, there is a check if the first byte is negative. Go the else-branch (even it is indeed negative)!
ClpSignersEncodings.TStandardDsaEncoding.Decode(): In the end, exit this function as if the both arrays were equal (they are not).

Then the validation succeeds! I have no clue what I am doing, but maybe this helps you finding the bug :-)

To Reproduce Here is a short TestCase with two invocations. The first with a working signature, the second with the signature which causes trouble.

uses
  ClpIDsaPublicKeyParameters,
  ClpISigner,
  ClpSignerUtilities,
  ClpBigInteger,
  ClpDsaParameters,
  ClpDsaPublicKeyParameters,

  HlpConverters;

const
  SIGNATURE_FAIL =
    '3044022091481D2DD4902030BE5E941DC41D51051D38C8D6B52BD638F166AA0B285FD4540220729B054A4C1977D7F423FCCCE8531AB77DA4F4871415B948FA9FFC43B1653282';

  CONTENT_FAIL =
    '789C0B8D77F3718D30343630B4304FDAC4D0F690F7A05A4789A8204723AB4C8BF366ADB3338A5E2DE06A60E09B76E8C9B317A7EE70ACBB74E326238BCB753B4606A552898BEA218B3DCC7C2C5628275E3C1D27176BB4F8C2E7'+
    'DF17263B444573CF9EAD9D1825EDBDF8C422E3C9DCC5D1C6AB272F74CAE6F62EF404099EACDAECCD7991F16167E3C1C64F56AB8A16063A0969090639694D9A1964A41864A59554582555A59518945495941864E5E921C720C3'+
    'D0BA809391415572E3D487074F4E5D7AC6C0C0C2202CD4C010489B33A43030303032A9ADF431972861BF2051665BC4C0605B2C011465000972DC61E39528AB926B00722CB0A9B080AA10CA040088455F38';

  SIGNATURE_OK =
    '30440220782E2FE184A1D85E89E9338B298EC61AEBA248CE722056CA940A967C8A1D391202206E2C628C4FCEA91BA35216A0A350F894DE5EBD7B8909920FDE947FEEDE0E20C4';

  CONTENT_OK =
    '789C01BC0043FF555F464C455831333031383862B20086E10DC125EA2815110881051C844464D985668E23A00A80000E96C2E4E6E8CADC08AED2D8D9010444D7BE0100221CE610EA559B64364C38A82361D1CB5E1E5D32A3D0'+
    '979BD099C8426B0B7373432B4B6852932BABA3634B733B2B715AB34B09D101E18981C181F1424221521291521292A17A3A920A11525A095282314952B20A49529952826278083001A4C38AE5BB303ACE700380070014B00240'+
    '400F537570657220537061727072656973C41E4A03';

  PARAM_Y =
    '2071026581109650758038184064186458876296283481300943403866509942342382524620713451396343254114684899675018096590369661320483283915891166582478643454906082539533084932998847762533'+
    '5608491474738708319155141091176484174426011647105714888522392044284457605524311380058563471942453792467869956630831044794802346458000950850660797317292702519780588741916026340669'+
    '3620012965050922147558298228550935029104266071742567822000080296983419837677125515674745912823376511707389352243244256981176594257823975113333238642501605713186198500548884663216'+
    '55183209104790133727137773539483537009121119915647022479430130140834128010355366147';

  PARAM_P =
    '3017316225751025747816503856735074390137150438484287902337126460736744030289225070797062368697742354219140574539404572855291510404700630125513899004636916104465988521873694530966'+
    '1318177566530870929805256382987168067340008563174311414346376485783727860627287576374105590638940189925715546485395628902605554021519590402931608393003737437115405244576740720698'+
    '4835770992100788644604476304620720569870221703221752857037022257117195563165249290086072514593243867291836699225079470118050740478512600855228566314481165933907549303663373092953'+
    '25310946756575679469440910701253806730076290075220214443090215694678030619287443651';

  PARAM_Q =
    '89726923024951955097649575600463773741813068174113684889543146019116433923879';

  PARAM_G =
    '6682738806820039844008521695401888626604434767682364664746866004152999420930735095644239980782167926920540357506540943531558003772634839218334759316089889548468135218808036392037'+
    '2011689222919790333697690344631663740976611841320173892965305518127096861572682348179792158029674307464324521180906853686018459823737125128895604673978691732918869443789114925806'+
    '5472811992020860821346955758135422858848014563792522516932207263405005445975349224466539540552903706733887641939394032980403211285416125003974316524504106159538430710214970562737'+
    '4089518329951756701893447901613868789330561624574500181839826906305067813553340963';

function TestCase(const Content, Signature: string): Boolean;
   var
    Signer: ISigner;
    PubKey: IDSAPublicKeyParameters;
    msgBytes, sigBytes: TBytes;
   begin
    sigBytes := TConverters.ConvertHexStringToBytes(Signature);
    msgBytes := TConverters.ConvertHexStringToBytes(Content);

    PubKey := TDsaPublicKeyParameters.Create(
      TBigInteger.Create(PARAM_Y),
      TDsaParameters.Create(
        TBigInteger.Create(PARAM_P),
        TBigInteger.Create(PARAM_Q),
        TBigInteger.Create(PARAM_G)
      )
    );

    Signer := TSignerUtilities.GetSigner('SHA256WITHDSA');

    Signer.Init(False, PubKey);
    Signer.BlockUpdate(msgBytes, 0, Length(msgBytes));

    result := Signer.VerifySignature(sigBytes);
   end;

procedure TForm1.Button1Click(Sender: TObject);
   begin
    if not TestCase(CONTENT_OK, SIGNATURE_OK) then ShowMessage('Case 1 failed');
    if not TestCase(CONTENT_FAIL, SIGNATURE_FAIL) then ShowMessage('Case 2 failed');
   end;

Expected behavior The two TestCase invocations should both return true.

Environment:

OS: Win32 & Android
Compiler: Delphi 10.4
Package Version trunk

Thanks! Dominik

Xor-el commented 2 years ago

Hi, Thanks for your detailed explanation. However, I will like to indicate that this is not a bug. your failing signature is malformed and as per ASN-1 specs should not verify. However, some implementation like Sun's JDK Crypto and OpenJDK force r and s in such scenarios to be positive in order to validate those signatures internally for compatibility reasons. CryptoLib however does not do this internally as I consider it bad practice.

However, I did foresee such issues popping up here and there so I tried my best not to tightly couple certain implementations to allow experienced users override some subtle internal details.

I have written a demo below that will allow you achieve what you want.

program Demo;

{$APPTYPE CONSOLE}
{$R *.res}

uses

  ClpISigner,
  ClpBigInteger,
  ClpDsaParameters,
  ClpDsaPublicKeyParameters,
  HlpConverters,
  SysUtils,
   // additional imports
  ClpSignersEncodings,
  ClpIDsaPublicKeyParameters,
  ClpDsaDigestSigner,
  ClpDsaSigner,
  ClpIDsaSigner,
  ClpISignersEncodings,
  ClpDigestUtilities,
  ClpIDigest,
  ClpAsn1Objects,
  ClpIAsn1Objects,
  ClpCryptoLibTypes;

const
  SIGNATURE_FAIL =
    '3044022091481D2DD4902030BE5E941DC41D51051D38C8D6B52BD638F166AA0B285FD4540220729B054A4C1977D7F423FCCCE8531AB77DA4F4871415B948FA9FFC43B1653282';

  CONTENT_FAIL =
    '789C0B8D77F3718D30343630B4304FDAC4D0F690F7A05A4789A8204723AB4C8BF366ADB3338A5E2DE06A60E09B76E8C9B317A7EE70ACBB74E326238BCB753B4606A552898BEA218B3DCC7C2C5628275E3C1D27176BB4F8C2E7'
    + 'DF17263B444573CF9EAD9D1825EDBDF8C422E3C9DCC5D1C6AB272F74CAE6F62EF404099EACDAECCD7991F16167E3C1C64F56AB8A16063A0969090639694D9A1964A41864A59554582555A59518945495941864E5E921C720C3'
    + 'D0BA809391415572E3D487074F4E5D7AC6C0C0C2202CD4C010489B33A43030303032A9ADF431972861BF2051665BC4C0605B2C011465000972DC61E39528AB926B00722CB0A9B080AA10CA040088455F38';

  SIGNATURE_OK =
    '30440220782E2FE184A1D85E89E9338B298EC61AEBA248CE722056CA940A967C8A1D391202206E2C628C4FCEA91BA35216A0A350F894DE5EBD7B8909920FDE947FEEDE0E20C4';

  CONTENT_OK =
    '789C01BC0043FF555F464C455831333031383862B20086E10DC125EA2815110881051C844464D985668E23A00A80000E96C2E4E6E8CADC08AED2D8D9010444D7BE0100221CE610EA559B64364C38A82361D1CB5E1E5D32A3D0'
    + '979BD099C8426B0B7373432B4B6852932BABA3634B733B2B715AB34B09D101E18981C181F1424221521291521292A17A3A920A11525A095282314952B20A49529952826278083001A4C38AE5BB303ACE700380070014B00240'
    + '400F537570657220537061727072656973C41E4A03';

  PARAM_Y = '2071026581109650758038184064186458876296283481300943403866509942342382524620713451396343254114684899675018096590369661320483283915891166582478643454906082539533084932998847762533'
    + '5608491474738708319155141091176484174426011647105714888522392044284457605524311380058563471942453792467869956630831044794802346458000950850660797317292702519780588741916026340669'
    + '3620012965050922147558298228550935029104266071742567822000080296983419837677125515674745912823376511707389352243244256981176594257823975113333238642501605713186198500548884663216'
    + '55183209104790133727137773539483537009121119915647022479430130140834128010355366147';

  PARAM_P = '3017316225751025747816503856735074390137150438484287902337126460736744030289225070797062368697742354219140574539404572855291510404700630125513899004636916104465988521873694530966'
    + '1318177566530870929805256382987168067340008563174311414346376485783727860627287576374105590638940189925715546485395628902605554021519590402931608393003737437115405244576740720698'
    + '4835770992100788644604476304620720569870221703221752857037022257117195563165249290086072514593243867291836699225079470118050740478512600855228566314481165933907549303663373092953'
    + '25310946756575679469440910701253806730076290075220214443090215694678030619287443651';

  PARAM_Q = '89726923024951955097649575600463773741813068174113684889543146019116433923879';

  PARAM_G = '6682738806820039844008521695401888626604434767682364664746866004152999420930735095644239980782167926920540357506540943531558003772634839218334759316089889548468135218808036392037'
    + '2011689222919790333697690344631663740976611841320173892965305518127096861572682348179792158029674307464324521180906853686018459823737125128895604673978691732918869443789114925806'
    + '5472811992020860821346955758135422858848014563792522516932207263405005445975349224466539540552903706733887641939394032980403211285416125003974316524504106159538430710214970562737'
    + '4089518329951756701893447901613868789330561624574500181839826906305067813553340963';

type
  TCustomStandardDsaEncoding = class sealed(TStandardDsaEncoding)
  strict protected
    function CheckValue(const n, x: TBigInteger): TBigInteger; override;
    function EncodeValue(const n, x: TBigInteger): IDerInteger; override;
  end;

  { TCustomStandardDsaEncoding }

function TCustomStandardDsaEncoding.CheckValue(const n, x: TBigInteger)
  : TBigInteger;
begin
if (not n.IsInitialized) then
begin
   raise EArgumentCryptoLibException.Create('value not initialized');
end;

  if ((x.CompareTo(n) >= 0)) then
  begin
    raise EArgumentCryptoLibException.CreateResFmt(@SValueOutOfRange, ['x']);
  end;

  if (x.SignValue < 0) then
  begin
    result := TBigInteger.Create(1, x.ToByteArray()); // force r or s to be positive
    Exit;
  end;
  result := x;
end;

function TCustomStandardDsaEncoding.EncodeValue(const n, x: TBigInteger)
  : IDerInteger;
begin
// ensure we get the positive bytes before creating our DerInteger
  result := TDerInteger.Create(CheckValue(n, x).ToByteArrayUnsigned()); 
end;

function TestCase(const Content, Signature: string): Boolean;
var
  Signer: ISigner;
  PubKey: IDSAPublicKeyParameters;
  msgBytes, sigBytes: TBytes;
  DigestInstance: IDigest;
begin
  sigBytes := TConverters.ConvertHexStringToBytes(Signature);
  msgBytes := TConverters.ConvertHexStringToBytes(Content);

  PubKey := TDsaPublicKeyParameters.Create(TBigInteger.Create(PARAM_Y),
    TDsaParameters.Create(TBigInteger.Create(PARAM_P),
    TBigInteger.Create(PARAM_Q), TBigInteger.Create(PARAM_G)));

  DigestInstance := TDigestUtilities.GetDigest('SHA256');
  Signer := TDsaDigestSigner.Create(TDsaSigner.Create() as IDsaSigner,
    DigestInstance, TCustomStandardDsaEncoding.Create() as IDsaEncoding);

  Signer.Init(False, PubKey);
  Signer.BlockUpdate(msgBytes, 0, Length(msgBytes));

  result := Signer.VerifySignature(sigBytes);
end;

begin
  try
    { TODO -oUser -cConsole Main : Insert code here }
    if not TestCase(CONTENT_OK, SIGNATURE_OK) then
      Writeln('Case 1 failed');
    if not TestCase(CONTENT_FAIL, SIGNATURE_FAIL) then
      Writeln('Case 2 failed');
    Readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;

end.

Here is what I did above. I inherited the existing encoding class and overrode the implementation of some of it's methods. I hope this helps you.

dominikkv commented 2 years ago

Hi!

Thank you very much for your quick response and help!

So I was on the wrong path. Your library is fine, but the ASN.1 representation of the signature is wrong. The working Java project let me thought that the signature is correct.

As I am constructing the ASN.1 byte array by myself (I have r and s separately) I'd rather fix this on this side :-) It seems that I simply have to put another 0x00 byte in front of the integer when the most significant bit of the first byte is a 1.

It now works like a charm.

Thanks again! Dominik

Xor-el / CryptoLib4Pascal

SHA256WITHDSA verify problem #30