Re: Interop lsh and SSH-2.0-GitLab-SSHD

>> So it's not just modulus size, but I'm wondering if the gitlab code
>> is stupid enough to consider any exponent over 65537 as an error or
>> some such.
> My guess is it considers any exponent larger than a machine word
> (which makes ops with it quite efficient) as irrational and therefore
> rejects it.

nisse@'s original message said that

	The only unusual thing with the key, as far as I can tell, is
	that the "e" value is a randomly selected 32-bit number, not
	just 17 or 65537.

I would be surprised if that were larger than a machine word on the
machines gitlab is using.

> My code does this too - there's no sane reason for having an exponent
> like that apart from opening yourself up to DoS attacks.

I guess we won't interoperate, then; I'm sorry to hear it.

moussh uses an exponent chosen by taking 0x8000000000000001 and, twice,
setting a randomly-selected bit (so in most cases four bits set),
retrying generation until it finds a value which is suitable, one which
is coprime to (p-1)(q-1).  As my explanatory comment puts it,

/*
 * We want e to be large enough to make the low encryption exponent
 *  attack hopeless right out of the gate; but we also want it to have
 *  relatively few bits set, so as to speed up operation.  So we set e
 *  equal to 0x8000000000000001 plus up to two other bits in random
 *  positions, trying different random values until we get an e that's
 *  relatively prime to t=(p-1)(q-1).  (The code always sets two bits;
 *  I say "up to" two other bits because the code may hit the bits
 *  already set, or may pick the same bit for each of the two.)
 *
 * This way, it's unlikely that two different keys will have the same
 *  value of e, but even if they do, it is impossible to mount the
 *  attack, because it requires at least e different messages, and e is
 *  very large when considered as a count of things.
 */

The relevant exponentiation thus means 64-to-66 (if I've counted right)
multiplications.  I didn't - and don't - consider that unreasonable.
Neither do most implementations; I have heard of only one or two (yours
and maybe gitlab's) that disagree.

I considered doing the 32-bit version instead, but collecting
two-to-four billion example messages, to mount the low encryption
exponent attack, was just a little bit too close to plausible for
comfort.  (I wouldn't even consider 17, nor even 65537, because of that
attack.)  And a random 32-bit value, re-chosen until it's
mathematically suitable, will require a mean of about 48
multiplications, only three-quarters what my exponents require.  On a
32-bit machine, exponents over 32 bits long are a little more
expensive to use, but that cost is so dwarfed by the modular
multiplications that I don't consider it even worth thinking about
until e's size approaches n's.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email protected]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B