Skip to content
Snippets Groups Projects
  1. Feb 28, 2020
    • Simon Tatham's avatar
      New query function ecc_montgomery_is_identity. · c9a8fa63
      Simon Tatham authored
      To begin with, this allows me to add a regression test for the change
      in the previous commit.
      c9a8fa63
    • Simon Tatham's avatar
      Preserve zero denominators in ECC point normalisation. · 141b75a7
      Simon Tatham authored
      ecc_montgomery_normalise takes a point with X and Z coordinates, and
      normalises it to Z=1 by means of multiplying X by the inverse of Z and
      then setting Z=1.
      
      If you pass in a point with Z=0, representing the curve identity, then
      it would be nice to still get the identity back out again afterwards.
      We haven't really needed that property until now, but I'm about to
      want it.
      
      Currently, what happens is that we try to invert Z mod p; fail, but
      don't notice we've failed, and come out with some nonsense value as
      the inverse; multiply X by that; and then _set Z to 1_. So the output
      value no longer has Z=0.
      
      This commit changes things so that we multiply Z by the inverse we
      computed. That way, if Z started off 0, it stays 0.
      
      Also made the same change in the other two curve types, on general
      principles, though I don't yet have a use for that.
      141b75a7
  2. Sep 08, 2019
    • Simon Tatham's avatar
      Whitespace rationalisation of entire code base. · 5d718ef6
      Simon Tatham authored
      The number of people has been steadily increasing who read our source
      code with an editor that thinks tab stops are 4 spaces apart, as
      opposed to the traditional tty-derived 8 that the PuTTY code expects.
      
      So I've been wondering for ages about just fixing it, and switching to
      a spaces-only policy throughout the code. And I recently found out
      about 'git blame -w', which should make this change not too disruptive
      for the purposes of source-control archaeology; so perhaps now is the
      time.
      
      While I'm at it, I've also taken the opportunity to remove all the
      trailing spaces from source lines (on the basis that git dislikes
      them, and is the only thing that seems to have a strong opinion one
      way or the other).
          
      Apologies to anyone downstream of this code who has complicated patch
      sets to rebase past this change. I don't intend it to be needed again.
      5d718ef6
  3. Feb 09, 2019
  4. Jan 03, 2019
    • Simon Tatham's avatar
      Fix non-generality bug in ecc_weierstrass_point_valid. · 4eb1dedb
      Simon Tatham authored
      It was computing the RHS of the curve equation affinely, without
      taking account of the point's Z coordinate. In other words, it would
      work OK for a point you'd _only just_ imported into ecc.c which was
      still represented with a denominator of 1, but it would give the wrong
      answer for points coming out of computation after that.
      
      I've moved the simple version into ecc_weierstrass_point_new_from_x,
      since the only reason it was in a separate function at all was so it
      could be reused by point_valid, which I now realise it can't.
      4eb1dedb
  5. Dec 31, 2018
    • Simon Tatham's avatar
      Complete rewrite of PuTTY's bignum library. · 25b034ee
      Simon Tatham authored
      The old 'Bignum' data type is gone completely, and so is sshbn.c. In
      its place is a new thing called 'mp_int', handled by an entirely new
      library module mpint.c, with API differences both large and small.
      
      The main aim of this change is that the new library should be free of
      timing- and cache-related side channels. I've written the code so that
      it _should_ - assuming I haven't made any mistakes - do all of its
      work without either control flow or memory addressing depending on the
      data words of the input numbers. (Though, being an _arbitrary_
      precision library, it does have to at least depend on the sizes of the
      numbers - but there's a 'formal' size that can vary separately from
      the actual magnitude of the represented integer, so if you want to
      keep it secret that your number is actually small, it should work fine
      to have a very long mp_int and just happen to store 23 in it.) So I've
      done all my conditionalisation by means of computing both answers and
      doing bit-masking to swap the right one into place, and all loops over
      the words of an mp_int go up to the formal size rather than the actual
      size.
      
      I haven't actually tested the constant-time property in any rigorous
      way yet (I'm still considering the best way to do it). But this code
      is surely at the very least a big improvement on the old version, even
      if I later find a few more things to fix.
      
      I've also completely rewritten the low-level elliptic curve arithmetic
      from sshecc.c; the new ecc.c is closer to being an adjunct of mpint.c
      than it is to the SSH end of the code. The new elliptic curve code
      keeps all coordinates in Montgomery-multiplication transformed form to
      speed up all the multiplications mod the same prime, and only converts
      them back when you ask for the affine coordinates. Also, I adopted
      extended coordinates for the Edwards curve implementation.
      
      sshecc.c has also had a near-total rewrite in the course of switching
      it over to the new system. While I was there, I've separated ECDSA and
      EdDSA more completely - they now have separate vtables, instead of a
      single vtable in which nearly every function had a big if statement in
      it - and also made the externally exposed types for an ECDSA key and
      an ECDH context different.
      
      A minor new feature: since the new arithmetic code includes a modular
      square root function, we can now support the compressed point
      representation for the NIST curves. We seem to have been getting along
      fine without that so far, but it seemed a shame not to put it in,
      since it was suddenly easy.
      
      In sshrsa.c, one major change is that I've removed the RSA blinding
      step in rsa_privkey_op, in which we randomise the ciphertext before
      doing the decryption. The purpose of that was to avoid timing leaks
      giving away the plaintext - but the new arithmetic code should take
      that in its stride in the course of also being careful enough to avoid
      leaking the _private key_, which RSA blinding had no way to do
      anything about in any case.
      
      Apart from those specific points, most of the rest of the changes are
      more or less mechanical, just changing type names and translating code
      into the new API.
      25b034ee
Loading