~ This is a work in progress towards an Ada implementation of Eulora's communication protocol. Start with Chapter 1.~
The change from fixed-size to arbitrary size of the public exponent "e" of RSA keys1 turned out to be of course more than just introducing a parameter for e's size - all I can say about it is that I was rather ready for this development by now, given the known mess that is the MPI lib. So the only surprise here was the exact way in which MPI fails rather than the fact that it does fail. Let's take it slowly and in detail since it is - like everything else related to encryption - rather important to have it as clear as one can make it.
On the SMG Comms side, a shorter "e" is really no trouble at all: basically there is no such thing as "shorter" since it can perfectly be the same size as it always was, only starting with whatever number of 0s it needs to make up to the expected length, big deal. And this is in fact already handled and handled well in the wrappers I wrote previously for the RSA and MPI C code, since it was already clear that yes, any set of octets might start at any time with 0s but that doesn't make them fewer octets or anything of the sort. So at first look, there really isn't any need to change anything, since the "change" required is neatly and natively handled as what it is - just a specific case of the more general operation that is implemented. Still, for clarity and further use downstream, I decided to add a constant and a new subtype to Raw_Types simply for the purpose of providing an explicit way of using the exactly-8-octets-long e (neither the new constant nor the new subtype are put to use so far by any of the message pack/unpack or read/write methods):
-- RSA public exponent (e) size in octets
-- NB: this should normally match the E_LENGTH_OCTETS in smg_rsa.h
-- NOT imported here for the same reason given at RSA_KEY_OCTETS above
E_LENGTH_OCTETS : constant Positive := 8;
subtype RSA_e is Octets( 1 .. E_LENGTH_OCTETS);
On the RSA side, the same constant "length of e in octets" goes into include/smg_rsa.h since it is not exactly a knob of the whole thing but rather a parameter for RSA key generation:
/** * This is the length of the public exponent e, given in octets. * TMSR standard e has KEY_LENGTH_OCTETS / 2 octets. * Eulora's communication protocol uses however e with 8 octets length. * New keypairs generated will have e precisely this length. * Change this to your preferred size of e for generating new keys with that size of e. * NB: this impacts key generation ONLY! (i.e. NOT encrypt/decrypt). */ static const int E_LENGTH_OCTETS = 8;
As the comments above stress, the "length of e" should normally be a concern in the code only when generating a new key pair; at all other times (encrypt/decrypt), the e that is provided will be used, whatever length it might be. Looking at the key generation code, the change to make is minimal since the code is sane - simply replace a local variable that specified the length of the required prime with the new global constant that now specifies the user's choice of length for e (in rsa/rsa.c, function gen_keypair):
/* choose random prime e, public exponent, with 3 < e < phi */
/* because e is prime, gcd(e, phi) is always 1 so no need to check it */
do {
gen_random_prime( E_LENGTH_OCTETS, sk->e);
} while ( (mpi_cmp_ui(sk->e, 3) < 0) || (mpi_cmp(sk->e, phi) > 0));
Following the changes above, a re-read of all my rsa and smg_comms code confirmed that no, there is nothing else to change - it is after all just a matter of exposing a constant to the user, not any change of the underlying algorithm, so that's surely all, right? Well, no, of course it's not, because at the lower level, all those 0-led smaller "e" go into the MPI lib of gnarly entrails. And as it turns out, a quick test whipped out to see the whole thing in action got...stuck, going on for ever somewhere in the MPI code. Where? Well, the stack trace goes 8 levels deep into the MPI code and it looks (at times, as it rather depends on where one stops the neverending run...) like this:
#0 0x000000000040b492 in mpihelp_addmul_1 () #1 0x0000000000407cd4 in mpih_sqr_n_basecase () #2 0x0000000000407e68 in mpih_sqr_n () #3 0x0000000000408098 in mpih_sqr_n () #4 0x0000000000407d6b in mpih_sqr_n () #5 0x0000000000408098 in mpih_sqr_n () #6 0x0000000000407d6b in mpih_sqr_n () #7 0x0000000000405693 in mpi_powm ()
Claiming that one fully knows what goes on in 8 piled levels of MPI calls is rather disingenous at best so I won't even go there. However, a closer look at all that code, starting with mpi_powm and following the code seems to suggest that the issue at hand is that MPI simply can't handle correctly 0-led numbers. To which one should add of course "in some cases" so that one can't just say fine, wtf is it doing permitting any 0-led numbers then?? No, that would be too easy so the reality is that it permits and it probably even *requires* in places 0-led numbers but *in other places* it gets stuck2 on them. Aren't you happy to have followed this mess so far to such amazing conclusion? At any rate, going through the MPI code yields some more fun of course, such as this fragment in mpi-pow.c:
/* Normalize MOD (i.e. make its most significant bit set) as required by
* mpn_divrem. This will make the intermediate values in the calculation
* slightly larger, but the correct result is obtained after a final
* reduction using the original MOD value. */
mp = mp_marker = mpi_alloc_limb_space(msize, msec);
count_leading_zeros( mod_shift_cnt, mod->d[msize-1] );
if( mod_shift_cnt )
mpihelp_lshift( mp, mod->d, msize, mod_shift_cnt );
else
MPN_COPY( mp, mod->d, msize );
The obvious clue there is that at least one culprit of "can't handle 0-led numbers" is that divrem function that is indeed called as part of the exponentiation. But the added joke that's for insiders only is that the normalization there is done ad-hoc although there exists a function precisely for...normalizing aka trimming the leading 0s from an mpi! Eh, so what if it exists - by the time something gets as big and tangled as MPI, chances are nobody remembers everything there is but that's not a problem at all, right? But wait, just ~10 lines further down, there is another normalization and at *that* place, the author somehow remembered that there is even a macro defined for this purpose! And oh, another ~10 lines further, there is yet another way in which normalization is done on the spot (shifting the bits directly!). So what is it already that makes one write code like this, some misplaced purple-prose inclination, let's not repeat the same expression or what exactly? Frankly the only logical answer is that it's done on purpose - anything and everything to increase the number of lines of code. Increase productivity3 !!
Moving further, it turns out that this very same function actually *does* trim the leading 0s off the exponent at some point! Which of course begs now the question of just how and why is then a problem to give it a 0-led exponent? Essentially it trims it but too late/not fully/not for everything and not everywhere that it should do it, that's the best I can say about it. And overall, the fact of the matter is simply that MPI just doesn't correctly handle 0-led MPI values4, end of story. To quote from MPI code and comments themselves, the author's explanation:
/**************** * Sometimes we have MSL (most significant limbs) which are 0; * this is for some reasons not good, so this function removes them. */
So it is "for some reasons not good", mmkay? It reminds me of the other display of great expertise in "reasons". Without wasting even more time on the MPI code of wonders5, the solution for SMG Comms is essentially a work around: the C wrappers get another job, namely to ensure that the values passed on to MPI are normalized. Note that the symmetrical opposite of this, namely adding missing leading 0s is already implemmented where needed (in the Ada code that actually deals perfectly fine with 0-led values since they are not oh-so-special, really). Thankfully, this is a very simple thing to do: instead of using directly the mpi_set_buffer method to set the value of an mpi number, define an mpi_set_normalized method that calls mpi_set_buffer + mpi_normalize:
void mpi_set_normalized(MPI m, const char *buffer,
unsigned int noctets, int sign) {
mpi_set_buffer( m, buffer, noctets, sign );
mpi_normalize( m );
}
Using the above code, all the mpi_set_buffer calls in c_wrappers are replaced by mpi_set_normalized calls and so there are no more 0-led mpi values passed on to the C code when calling rsa from Ada (since this is the purpose of those c_wrappers: to provide a sane interface for Ada to work with the insanity of C for RSA needs). Obviously, if you insist on calling the C rsa encrypt/decrypt methods directly, it's up to you to make sure you don't pass them 0-led values. While I could change the encrypt/decrypt methods themselves to normalize all the keys' components before doing anything, I think that's a very ugly and ultimately incorrect thing to do: the encrypt/decrypt should use precisely what they are given, not go about tampering with the inputs, regardless of "reasons". Yes, it is ugly and incorrect that MPI forces this normalization nonsense but that's not a justification for messing the encrypt/decrypt functions to cover up for it.
Note also that I specifically chose NOT to include the normalization in the existing method mpi_set_buffer because on one hand it's not the job of mpi_set_buffer to trim its inputs and on the other hand there is a need for mpi_set_buffer precisely as it is: there is code in there relying on being able to set the buffer of an mpi to anything, including 0-led vectors (even if at times, that doesn't remain 0-led for long). So no, modifying mpi_set_buffer is not a good option, even without considering the fact that MPI is better thrown away6 than changed.
The rest of the .vpatch for this chapter of SMG Comms contains simply the 2 additional tests (and changes needed for them in the test environment) that I wrote: one for the RSA c code, to flag the issue and one for the Ada code to ensure that there is at least one test with an exponent of 8 octets. I've used first the rsa code with the length of e set to 8 to generate a pair of RSA keys that are used then for the new test. So there is now a new file, "8_keys.txt" containing this new set of keys and the Ada test is simply another call with different parameters to read its input from this file as opposed to another.
Given that the arbitrary size of e touches essentially EuCrypt code, I also packed those minimal changes to smg_rsa.h and to key generation, together with the new test using a shorter e, into a .vpatch for EuCrypt. I've also added in there stern warnings at the encrypt/decrypt regarding the 0-led issue since it is the responsibility of the caller to either make sure they don't provide 0-led values or otherwise deal with a potentially-blocking call. Both .vpatch files and their corresponding signatures are on my Reference Code Shelf as well as linked here for your convenience:
In practice this is more like 8-octets size for Eulora and otherwise 256 octets for TMSR rather than all sorts of sizes. Nevertheless, the big change is from one single size to ~anything more than one size since that means that the size can't be relied on to be anything specific at any given time. ↩
Or as good as stuck: I did not have the patience to wait on it for more than 3 minutes, given that the operation in question should have barely taken a couple of seconds at maximum. ↩
And probably surpass the 5-years plan too, since it's hardly distinguishable already. ↩
Or, apparently, only values with "too many" 0 at the front aka at least one limb. ↩
Yes, I did actually dig even deeper into the MPI code following this because I don't really have a choice not to as long as MPI remains part of SMG Comms and EuCrypt. The conclusion however is still the same, so I'm jumping here to the conclusion and you are free to tell me in detail in the comments section the results of your investigation on this. ↩
Hopefully there will soon be a replacement for it and so it WILL be thrown away, I can't wait for that! ↩
Comments feed: RSS 2.0