search

LinusU / secure-remote-password

A modern SRP implementation for Node.js and Web Browsers
101 stars 22 forks source link

Padding of g #12

Open yallie opened 6 years ago

yallie commented 6 years ago

Hello,

I'd like to thank for the excellent SRP-6a implementation! Nice API, very clean code, so easy to follow 👍 I have a .NET backend, so I've converted the code to C#.

While porting the code I noticed that the library doesn't pad the value of g. RFC5054 specifies that g should be left-padded with zeros to be the same length as N.

The leads to the miscalculated value of the k multiplier: k = H(N | PAD(g)). As a result, the code doesn't pass the SRP test vectors (RFC5054, Appendix B). Namely, the values of k, B and S don't match.

The library works just fine without the padding as long as the same code is used on both client and server. But if the server code strictly follows the RFC, the client won't be able to authenticate because of the different values of k.

Shouldn't it be fixed?

yallie commented 6 years ago

A couple of notes:

  1. Fixing the padding of g won't affect existing credentials: k is not used to derive the private key.
  2. RFC5054 uses sha1, so the test vectors are not directly applicable (unless params.js also use sha1).
LinusU commented 6 years ago

Nice API, very clean code, so easy to follow

Thank you 🙌

RFC5054 specifies that g should be left-padded with zeros to be the same length as N.

Hmm, yeah this should probably be fixed. Although RFC5054 specifies specifically how to use SRP as an authentication strategy for the TLS protocol, it seems like most libraries are following it so that seems to be the de facto standard for SRP.

It also seems that A and B should be padded when calculating u.

I'm trying to look at a few other libraries to see what they are doing:

Libray k u M H(A, M, K) ping
RFC5054 padded padded
pysrp (rfc5054_enable) padded padded only g not
srp-client padded padded ? padded @symeapp
srp-rb padded padded padded padded @lamikae
go-srp not not not ? @opencoff
SRP.swift padded padded not not
srptools padded padded not not
srp-6a-demo (PHP) not not not not @RuslanZavacky
DragonSRP padded padded not not
srp4net padded padded not not
Eneter padded not not not not on Github

Feels quite clear that we should pad k and u.

I've pinged the authors of implementations that don't follow that here, feel free to chime into the discussion here!

It's going to be a pain to update this for me though, already have multiple clients in production that are distributed in different channels 😂

yallie commented 6 years ago

Thanks for the detailed analysis! 👍 My 2 cents:

Library k u M H(A, M, K)
srp4net padded padded not not
Eneter padded not not not

It also seems that A and B should be padded when calculating u.

Good catch, I missed that! I only looked at numbers that didn't match the test vectors.

It's going to be a pain to update this for me though, already have multiple clients in production

That's the problem :)

LinusU commented 6 years ago

My 2 cents

Awesome, adding them to the list!

That's the problem :)

I wrote a migration guide in #13, it's a bit inconvenient, but not too bad ☺️

LinusU commented 6 years ago

So I tried getting pysrp to output all the values, and then plug them in here to see that everything works. Turns out that they are doing another padding which makes it incompatible:

https://github.com/cocagne/pysrp/blob/9d43e9a35e354a1ff1c6abdf12276922cadef97e/srp/_pysrp.py#L196-L205

Instead of doing

M = H(H(N) xor H(g), H(I), s, A, B, K)

they are doing:

M = H(H(N) xor H(PAD(g)), H(I), s, A, B, K)

🤔

@yallie any idea which one is correct?

LinusU commented 6 years ago
Lib  
pysrp (rfc5054_enable) H(PAD(g))
SRP.swift H(g)
srptools H(g)
DragonSRP H(g)

Seems like maybe pysrp is the outlier here 🤔

ping @cocagne

yallie commented 6 years ago

Looks like RFC5054 doesn't specify how M is calculated. And the original SRP-RFC doesn't specify where padding is required. Too bad :confused:

I'd say that g should be padded anywhere its value is hashed. If k uses padded g, then M should also use padded g.

UPD. Wikipedia SRP example doesn't use padding:

print("6. client sends proof of session key to server") M_c = H(H(N) ^ H(g), H(I), s, A, B, K_c)

LinusU commented 6 years ago

Hmm, yeah potentially, although one other way to see it is that it was padded in the other case to make it as long as the other part of the concatenation...

🤔

I'm going to leave this open for a while to see if anyone of the pinged persons responds. Whatever we decide on, I could go and submit pull requests to all the linked repositories so that at least everyone uses the same.

also ping @Bouke, @idlesign, @slechta and @osorin

opencoff commented 6 years ago

I just saw this; let me do some additional reading of RFC5054. I will respond in the next few hours.

S

On 05/23/2018 09:09 AM, Linus Unnebäck wrote:

Hmm, yeah potentially, although one other way to see it is that it was padded in the other case to make it as long as the other part of the concatenation...

🤔

I'm going to leave this open for a while to see if anyone of the pinged persons responds. Whatever we decide on, I could go and submit pull requests to all the linked repositories so that at least everyone uses the same.

also ping @Bouke https://github.com/Bouke, @idlesign https://github.com/idlesign, @slechta https://github.com/slechta and @osorin https://github.com/osorin

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/LinusU/secure-remote-password/issues/12#issuecomment-391360905, or mute the thread https://github.com/notifications/unsubscribe-auth/AIPwW-4G5PKYNJPZ66W1Ofjzc8GILH0lks5t1W2DgaJpZM4UJc2H.

yallie commented 6 years ago

Looks like Stanford reference SRP-6 implementation doesn't use padding in H(N) ^ H(g):

// srp6_client.c, line 94
static SRP_RESULT
srp6_client_params(SRP * srp, const unsigned char * modulus, int modlen,
           const unsigned char * generator, int genlen,
           const unsigned char * salt, int saltlen)
{
  int i;
  unsigned char buf1[SHA_DIGESTSIZE], buf2[SHA_DIGESTSIZE];
  SHA1_CTX ctxt;

  /* Fields set by SRP_set_params */

  /* Update hash state */
  SHA1Init(&ctxt);
  SHA1Update(&ctxt, modulus, modlen);
  SHA1Final(buf1, &ctxt);   /* buf1 = H(modulus) */

  SHA1Init(&ctxt);
  SHA1Update(&ctxt, generator, genlen); /* <------------------ g is not padded */
  SHA1Final(buf2, &ctxt);   /* buf2 = H(generator) */

  for(i = 0; i < sizeof(buf1); ++i)
    buf1[i] ^= buf2[i];     /* buf1 = H(modulus) xor H(generator) */

  /* hash: H(N) xor H(g) */
  SHA1Update(&CLIENT_CTXP(srp)->hash, buf1, sizeof(buf1));

  SHA1Init(&ctxt);
  SHA1Update(&ctxt, srp->username->data, srp->username->length);
  SHA1Final(buf1, &ctxt);   /* buf1 = H(user) */

  /* hash: (H(N) xor H(g)) | H(U) */
  SHA1Update(&CLIENT_CTXP(srp)->hash, buf1, sizeof(buf1));

  /* hash: (H(N) xor H(g)) | H(U) | s */
  SHA1Update(&CLIENT_CTXP(srp)->hash, salt, saltlen);

  return SRP_SUCCESS;
}

and

// srp6_server.c, line 98
static SRP_RESULT
srp6_server_params(SRP * srp, const unsigned char * modulus, int modlen,
           const unsigned char * generator, int genlen,
           const unsigned char * salt, int saltlen)
{
  unsigned char buf1[SHA_DIGESTSIZE], buf2[SHA_DIGESTSIZE];
  SHA1_CTX ctxt;
  int i;

  /* Fields set by SRP_set_params */

  /* Update hash state */
  SHA1Init(&ctxt);
  SHA1Update(&ctxt, modulus, modlen);
  SHA1Final(buf1, &ctxt);   /* buf1 = H(modulus) */

  SHA1Init(&ctxt);
  SHA1Update(&ctxt, generator, genlen); /* <--------------- same here, g is not padded */
  SHA1Final(buf2, &ctxt);   /* buf2 = H(generator) */

  for(i = 0; i < sizeof(buf1); ++i)
    buf1[i] ^= buf2[i];     /* buf1 = H(modulus) XOR H(generator) */

  /* ckhash: H(N) xor H(g) */
  SHA1Update(&SERVER_CTXP(srp)->ckhash, buf1, sizeof(buf1));

  SHA1Init(&ctxt);
  SHA1Update(&ctxt, srp->username->data, srp->username->length);
  SHA1Final(buf1, &ctxt);   /* buf1 = H(user) */

  /* ckhash: (H(N) xor H(g)) | H(U) */
  SHA1Update(&SERVER_CTXP(srp)->ckhash, buf1, sizeof(buf1));

  /* ckhash: (H(N) xor H(g)) | H(U) | s */
  SHA1Update(&SERVER_CTXP(srp)->ckhash, salt, saltlen);

  return SRP_SUCCESS;
}
LinusU commented 6 years ago

Also, seems like it does pad g when computing k (if the flag SRP_FLAG_LEFT_PAD is set), so it's not that it doesn't support RFC5054 style padding at all.

static SRP_RESULT
srp6a_client_key(SRP * srp, cstr ** result,
         const unsigned char * pubkey, int pubkeylen)
{
  SRP_RESULT ret;
  BigInteger k;
  cstr * s;
  SHA1_CTX ctxt;
  unsigned char dig[SHA_DIGESTSIZE];

  SHA1Init(&ctxt);
  s = cstr_new();
  BigIntegerToCstr(srp->modulus, s);
  SHA1Update(&ctxt, s->data, s->length);
  if(srp->flags & SRP_FLAG_LEFT_PAD)
    BigIntegerToCstrEx(srp->generator, s, s->length);  /* <================= HERE */
  else
    BigIntegerToCstr(srp->generator, s);
  SHA1Update(&ctxt, s->data, s->length);
  SHA1Final(dig, &ctxt);
  cstr_free(s);

  k = BigIntegerFromBytes(dig, SHA_DIGESTSIZE);
  if(BigIntegerCmpInt(k, 0) == 0)
    ret = SRP_ERROR;
  else
    ret = srp6_client_key_ex(srp, result, pubkey, pubkeylen, k);
  BigIntegerClearFree(k);
  return ret;
}

This makes me even more confident in that we shouldn't pad it when doing H(N) ^ H(g), but should when doing k = H(N, g).

opencoff commented 6 years ago

After looking carefully at RFC5054 and the reference srp implementation (v2.1.2), I concur with Linus' interpretation below.

This is my implementation now: | ||    k = H(N, pad(g))|| ||||u = H(pad(A), pad(B))|

For storing the verifiers on the server, I think storing |H(I)| is a better option? In my implementation, I take the user provided |"I"| and turn it into |"H(I)"| before I use it anywhere.

The test vectors in RFC5054 are useless for me -- I don't use SHA-1 in my implementation; I use the newer Blake2b-256 algorithm. I have updated my code with the changes above.

Thanks all for catching this!

Sudhi

On 05/23/2018 05:21 PM, Linus Unnebäck wrote:

Also, seems like it /does/ pad |g| when computing |k| (if the flag |SRP_FLAG_LEFT_PAD| is set), so it's not that it doesn't support RFC5054 style padding at all.

static SRP_RESULT srp6a_client_key(SRP * srp, cstr * result, const unsigned char pubkey,int pubkeylen) { SRP_RESULT ret; BigInteger k; cstr * s; SHA1_CTX ctxt; unsigned char dig[SHA_DIGESTSIZE];

SHA1Init(&ctxt); s =cstr_new(); BigIntegerToCstr(srp->modulus, s); SHA1Update(&ctxt, s->data, s->length); if(srp->flags & SRP_FLAG_LEFT_PAD) BigIntegerToCstrEx(srp->generator, s, s->length);/ <================= HERE / else BigIntegerToCstr(srp->generator, s); SHA1Update(&ctxt, s->data, s->length); SHA1Final(dig, &ctxt); cstr_free(s);

k =BigIntegerFromBytes(dig, SHA_DIGESTSIZE); if(BigIntegerCmpInt(k,0) ==0) ret = SRP_ERROR; else ret =srp6_client_key_ex(srp, result, pubkey, pubkeylen, k); BigIntegerClearFree(k); return ret; }

This makes me even more confident in that we shouldn't pad it when doing |H(N) ^ H(g)|, but should when doing |k = H(N, g)|.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/LinusU/secure-remote-password/issues/12#issuecomment-391515453, or mute the thread https://github.com/notifications/unsubscribe-auth/AIPwW73OSKzqP0l66qoGyrMA8q706m2mks5t1eDUgaJpZM4UJc2H.

idlesign commented 6 years ago

@yallie

I'd say that g should be padded anywhere its value is hashed. If k uses padded g, then M should also use padded g.

The right thing for libs should be sticking to the RFC, as long as errata is not confirmed and listed in https://www.rfc-editor.org/errata_search.php?rfc=5054. Otherwise the implementation would be something different from srp, and libs won't play well together. Bear in mind, when in doubt, you can always contact the RFC authors.

Bouke commented 6 years ago

When implementing SRP in Swift for getting it to act as a Homekit device, I used srptools to verify my implementation. It is currently also used for integration tests, replacing pysrp because of incompatibilities. The implementation matches with Apple's implementation of SRP, as it can correctly setup sessions with iOS devices.

Note that there are a few additional implementations targeting Homekit compatibility:

Library k u M H(A, M, K)
go-pkg padded padded not not
fast-srp padded padded not not
Nimbus-SRP padded padded not not

Ideologically it would be very great to achieve compatibility between all SRP implementations, so great initiative going on here!

(table updated)

LinusU commented 6 years ago

@Bouke I think that fast-srp asserts that the length of A and B is the same as N, so for all intents it's padded...

https://github.com/zarmack/fast-srp/blob/3ca4cef4f2ee7a863550a208f35f2bf97be0ceb5/lib/srp.js#L64-L69

https://github.com/zarmack/fast-srp/blob/3ca4cef4f2ee7a863550a208f35f2bf97be0ceb5/lib/srp.js#L228-L235

The implementation matches with Apple's implementation of SRP, as it can correctly setup sessions with iOS devices.

That's great!

Ideologically it would be very great to achieve compatibility between all SRP implementations, so great initiative going on here!

Yeah, I think it would be awesome 🙌

yallie commented 6 years ago

Perhaps we could keep all SRP implementations in a dedicated github organization. So it'd be easier to pick a standard-compliant implementation for any given platform. I can contribute my C# implementation. It's compatible with @LinusU code and passes the RFC5054 test vectors.

slechta commented 6 years ago

@LinusU Pull request are welcome. I have also written an email to Tom Wu (one of the authors of SRP) with the link to this discussion.

cocagne commented 6 years ago

Organizing a group for compatible SRP implementations would be fantastic. I'm not sure about the other projects but when I started pysrp, I wasn't particularly concerned about inter-library compatibility given the wide latitude in the srp6a specification and lack of implementation guidance. Now that RFC5054 has emerged as the de-facto standard though it's a different story. My only reticence for pulling in patches is that pysrp is known to be compatible with a few other implementations due to patches received for them over the years. If a cluster SRP projects commit to formal interoperability though I expect everyone else would probably fall in line. I'll certainly jump on board that effort.

On Thu, May 24, 2018 at 5:02 AM, Pavel Slechta notifications@github.com wrote:

@LinusU https://github.com/LinusU Pull request are welcome. I have also written an email to Tom Wu (one of the authors of SRP) with the link to this discussion.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/LinusU/secure-remote-password/issues/12#issuecomment-391659819, or mute the thread https://github.com/notifications/unsubscribe-auth/ABrLfEUllCJ28_baQAGCI6M_DVHPShOVks5t1oVFgaJpZM4UJc2H .

yallie commented 6 years ago

Organizing a group for compatible SRP implementations would be fantastic.

I've created an organization for RFC5054-compliant implementations: secure-remote-password. Also, I've created a repository for test vectors in JSON format: test-vectors.

SHA1 test vectors are taken from the RFC5054 document. Additional test vectors are generated using srptools by @idlesign.

If anyone is interested in contributing a compatible SRP implementation, please let me know. Thanks!

idlesign commented 6 years ago

Hi,

I think it would be great if compatible repos are not transfered into organization alltogether but rather listed in some repository under org (say secure-remote-password/implementations), so that on the one hand maintainers could subscribe to issues, and end-users will see some kind of readme with a library listing table (maybe even with badges version, CI, etc.).

So that:

opencoff commented 6 years ago

Hello,

I am not sure implementing a fully RFC 5054 compliant SRP is a good idea:

1) There are no guidelines for how to store verifiers securely; for user authentication purposes, it almost makes sense to NOT use the standard moduli but, generate a new one for each user. 2) SHA1 is a poor hash function

The folks at ProtonMail have a good writeup on how their SRP implementation is deliberately different from the RFC: https://protonmail.com/blog/encrypted_email_authentication/

Best regards,

Sudhi

On 06/08/2018 01:10 AM, Igor Starikov wrote:

Hi,

I think it would be great if compatible repos are not transfered into organization alltogether but rather listed in some repository under org (say |secure-remote-password/implementations|), so that on the one hand maintainers could subscribe to issues, and end-users will see some kind of readme with a library listing table (maybe even with badges version, CI, etc.).

So that:

  • New libraries are added into table using pull requests.
  • Maintainers are added into organization.
  • Problems and similar would go into Issues.
  • Whenever there's a confirmed issue with a library, README table is updated accordingly (library line is marked as having problem).

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/LinusU/secure-remote-password/issues/12#issuecomment-395658137, or mute the thread https://github.com/notifications/unsubscribe-auth/AIPwW7brZpI-tDyGWxM4v9bQYjhOqkGbks5t6hVGgaJpZM4UJc2H.

yallie commented 6 years ago

@idlesign

I think it would be great if compatible repos are not transfered into organization alltogether but rather listed in some repository under org (say secure-remote-password/implementations)

I believe both options are just fine. My account is mostly used for personal projects, so I'd rather host my library in the org account and have all SRP-related issues/discussions in a single place.

@opencoff

Good point! But most libraries mentioned here can use custom parameters and/or hash functions. When set up using SHA1 and 1024-bit group, my library passes the RFC5054 test vectors, but the default parameters are different from those suggested by the RFC.

My goal is just to have a list of libraries that can connect to each other, not to enforce strict RFC5054 compliance by default.

idlesign commented 6 years ago

I've started https://github.com/secure-remote-password/implementations Contributions are welcome.

cocagne commented 6 years ago

+Simon Massey (thinbus-srp)

I can see the pros and cons of both approaches but I have no problem transferring my srp implementations over to a common organization. Doing so would add a measure of credibility to the organization and my projects, at least, have been almost entirely in the hands of the community for several years anyway, so it wouldn't be much of a change for me. Almost all of my effort these days is devoted to other projects but I think Alexey's initiative is a worthwhile effort that will benefit the OSS community so I'd like to support it. I'm not particularly opinionated on the details though so I'll go along with whatever direction you guys decide on.

On Fri, Jun 8, 2018 at 10:24 PM, Igor Starikov notifications@github.com wrote:

I've started https://github.com/secure-remote-password/implementations Contributions are welcome.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/LinusU/secure-remote-password/issues/12#issuecomment-395936171, or mute the thread https://github.com/notifications/unsubscribe-auth/ABrLfGPcvANsD7Z3d3is-PeMSFUFvGAnks5t6z_1gaJpZM4UJc2H .

LinusU commented 6 years ago

I'd be happy to move this implementation into the new org as well! As soon as we've figured out exactly how we all want to be compatible.

cocagne/pysrp#38 raised some interesting concerns about padding g when calculating M.

@Bouke it seems like your library doesn't pad g, and is using a BigInt for g and not raw bytes. That should mean that Apple doesn't pad g, right? 🤔

LinusU commented 4 years ago

Hey everyone 👋

Sorry for not moving forward with this in a very long time. I would really like to figure out if we should pad g before hashing it or not 🤔

If anyone has any information to chime in with I would be very happy to hear it!

zbarbuto commented 4 years ago

Copying my findings from #24:

I've tested this library on its own as per the docs and can see that it will correctly verify the client as expected. However, I've tried passing values between this and other SRP libraries and the values seem not to verify (while they would when passing between the other libraries alone).

This includes:

I've found that while sirp and jsrp will happily communicate and verify against each other, secure-remote-password will not verify client values from jsrp configured in 2048 mode and sirp on the server will not verify client values from secure-remote-password. I've yet to get secure-remote-password to successfully work with another library.

After much digging, the only thing I can find that might be causing the issue is that the k values being used are different. I compared all the hex values form both calculations of a B value (secure-remote-password's const B = k.multiply(v).add(g.modPow(b, N)).mod(N) and jsrp's this.k().multiply(v).add(this.params.g.modPow(b, this.params.N)).mod(this.params.N) and all hex values were identical expect the k value.

It's strange because the calculations seem to be the same:

secure-remote: exports.k = sha256(exports.N, exports.g)

vs

jsrp: createHash(this.params.hash).update(transform.pad.toN(this.params.N, this.params)).update(transform.pad.toN(this.params.g, this.params)).digest();

Both use the same values for N and g. The only difference seems to be that jsrp will pad the g value to the same length as the N value in the hash.

k value from jsrp:

5b9e8ef059c6b32ea59fc1d322d37f04aa30bae5aa9003b8321e21ddb04e300

k value from srp-js (a fork of node-srp by mozilla):

5b9e8ef059c6b32ea59fc1d322d37f04aa30bae5aa9003b8321e21ddb04e300

k value from secure-remote-password:

4cba3fb2923e01fb263ddbbb185a01c131c638f2561942e437727e02ca3c266d

space55 commented 3 years ago

Hey, just wanted to chime in. I'm looking to use this library against Python's srptools, which it is currently incompatible with. Is there any update on making everything work together? Maybe a configuration option which allows you to choose what to pad?

Thanks!

cocagne commented 3 years ago

Compatibility with other RFC5054 compliant SRP implementations can be enabled by calling "srp.rfc5054_enable()". I'm not sure if srptools supports RFC5054 padding though, it's the first I've heard of it.

On Fri, Apr 30, 2021 at 8:32 AM Eamonn Nugent @.***> wrote:

Hey, just wanted to chime in. I'm looking to use this library against Python's srptools, which it is currently incompatible with. Is there any update on making everything work together? Maybe a configuration option which allows you to choose what to pad?

Thanks!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/LinusU/secure-remote-password/issues/12#issuecomment-830096814, or unsubscribe https://github.com/notifications/unsubscribe-auth/AANMW7GQN636WYWEK2RTHUDTLKWN3ANCNFSM4FBFZWDQ .