Ossasepia

November 4, 2018

SMG Comms Chapter 6: Packing and Unpacking RSA

Filed under: Coding, SMG_Comms — Diana Coman @ 1:38 p.m.

~ This is a work in progress towards an Ada implementation of Eulora's communication protocol. Start with Chapter 1.~

Building on the new convenient way to simply call rsa+oaep encrypt/decrypt from Ada, this chapter provides the Pack/Unpack functions that convert between SMG Comms RSA packets (each of them 1470 octets long, effectively several RSA-encrypted chunks glued together) and SMG Comms messages aka the actual content of the packet from the game's point of view. To do this, the Pack/Unpack functions simply chop the input into fixed-size parts, apply rsa+oaep encrypt/decrypt as suitable and then glue back the results in order, providing the whole thing as final output. Note that from the point of view of Pack/Unpack, both packets and messages have fixed lengths, as specified! In other words: the padding that might be added to data structures to get the whole thing to the specified length of a RSA message is preserved - that is no concern at this layer at all1. In a nutshell: Unpack removes any padding that Pack added but preserves any other padding that was added *before* calling Pack. In turn, Pack expects as input a fixed-size array of octets aka a RSA message as defined in Raw_Types - and the size of this is simply a multiple of the maximum size that one single RSA-encrypted operation can handle.

While the above fixed-size helps considerably to keep the whole thing quite easy to follow and clear, things are still a bit more gnarly than with Serpent, there's no escaping that. In particular, the RSA Decrypt operation CAN fail visibly - when the decoded "length" of the actual content turns out to be larger than maximum/provided space. For this reason, the Unpack function has a "Success" flag that gets set to false when output is essentially undefined. Note that the Unpack will fail in this way as soon as one of the chunks fails the RSA+OAEP decrypt in any way - there is no point in even attempting to recover some "partial" thing. Even more importantly: a True value for the Success flag does NOT indicate in any way that the result obtained is valid - all it says is that the RSA+OAEP decrypt operations completed successfully and the result is the one returned but whether that's a valid data structure or not is not a concern at this point (nor could it be since Unpack can't check such a thing in any way).

The .vpatch for this chapter includes the following main changes/additions:

  • A new note is added next to the offending Keccak line, describing the proposed way2 to preserve the No_Implicit_Conditionals restriction if desired. As mentioned in the forum, I do not quite see the need for this change at this moment but perhaps it will be needed at a later time, so there it is, right where it'll come in handy.
  • There's a correction of the value for the constant RSA_MSG_OCTETS. The new, correct value matches the fact that this is meant to be the fixed-size length of a SMG Comms RSA message rather than (as it was before) the max length that can be encrypted with RSA in one operation. So the RSA_MSG_OCTETS is calculated based on other specification-defined constants and it is a multiple of the max length that can be encrypted with RSA in one operation.
  • As part of doing the above correction of RSA_MSG_OCTETS, I also moved the initialization of some of the OAEP constants into Raw_Types (from OAEP packet where they were before). More precisely, the OAEP packet still uses its own internal constants (e.g. the "reserved" octets spelling "TMSR-RSA") but it initialises those (at elaboration time) with the values that it reads from Raw_Types. This reflects the fact that the OAEP packet in this project is the one using the Raw_Types that the protocol defines, not the other way around (in other words: OAEP does not define/impose those values - it's SMG Comms that does!).
  • The Packing package lost its "Pure" status (i.e. the compiler can't rely on it having no internal state and can't therefore cache calls to its method). The reason for this is at root the need for random padding for RSA since yes, can't cache the call to a method that has to use different, random padding at every call. In any case, for anyone interested, the specific route to follow this is that the Pack method for RSA calls OAEP+RSA which in turn use the non-pure Sequential_IO (via the RNG package) to read random octets from a Fuckgoats.
  • The new Pack and Unpack methods for RSA messages <-> packets conversions are in packing.ads/adb.
  • Corresponding tests for the Pack/Unpack methods are added to test_packing.ads/adb and called from testall.adb.

The signatures of the new Pack/Unpack methods in packing.ads are the following:

  -- Packing a RSA message into RSA packet, using the given key
  function Pack( Msg : in Raw_Types.RSA_Msg;
                 K   : in RSA_OAEP.RSA_pkey)
                return Raw_Types.RSA_Pkt;

  -- Unpacking a RSA packet into contained message, using the given key
  function Unpack( Pkt     : in Raw_Types.RSA_Pkt;
                   K       : in RSA_OAEP.RSA_skey;
                   Success : out Boolean)
                  return Raw_Types.RSA_Msg;

And the corresponding code for the new Pack/Unpack in packing.adb:

  -- Packing a RSA message into RSA packet, using the given key
  function Pack( Msg : in Raw_Types.RSA_Msg;
                 K   : in RSA_OAEP.RSA_pkey)
                return Raw_Types.RSA_Pkt is

  -- a chunk that can be processed via rsa+oaep at any given time
    Chunk: Raw_Types.Octets(1..Raw_Types.OAEP_MAX_LEN) := (others => 0);

  -- number of chunks in the message to process
  -- NO incomplete chunks will be processed!
  -- NB: values are set so that there are no incomplete blocks here
    N   : constant Natural := Msg'Length / Chunk'Length;

  -- intermediate result, as obtained from rsa_oaep
    Encr: Raw_Types.RSA_len := (others => 0);

  -- final resulting RSA Packet
    Pkt : Raw_Types.RSA_Pkt := (others => 0);
  begin
    -- there should ALWAYS be precisely N chunks in Msg to feed to rsa_oaep
    -- process chunks of Msg one at a time
    for I in 1..N loop
      -- get current chunk
      Chunk := Msg(Msg'First + (I-1) * Chunk'Length ..
                   Msg'First + I * Chunk'Length - 1 );
      -- call rsa oaep encrypt on current chunk
      RSA_OAEP.Encrypt( Chunk, K, Encr );
      -- copy result to its place in final packet
      Pkt( Pkt'First + (I-1) * Encr'Length ..
           Pkt'First + I * Encr'Length - 1 ) := Encr;
    end loop;
    -- return final result
    return Pkt;
  end Pack;

  -- Unpacking a RSA packet into contained message, using the given key
  function Unpack( Pkt     : in Raw_Types.RSA_Pkt;
                   K       : in RSA_OAEP.RSA_skey;
                   Success : out Boolean)
                  return Raw_Types.RSA_Msg is
    -- a chunk - basically input for RSA_OAEP.Decrypt
    Chunk : Raw_Types.RSA_len := (others => 0);

    -- intermediate result of rsa_oaep decrypt
    Decr  : Raw_Types.Octets( 1..Raw_Types.OAEP_MAX_LEN ) := (others => 0);
    Len   : Natural;
    Flag  : Boolean;

    -- number of chunks in the packet
    -- NB: there should be only FULL chunks! otherwise -> fail
    N   : constant Natural := Pkt'Length / Chunk'Length;

    -- final resulting message content of the given RSA packet
    Msg : Raw_Types.RSA_Msg := (others => 0);
  begin
    -- initialize Success flag
    Success := True;

    -- process given packet, chunk by chunk
    for I in 1..N loop
      -- get current chunk
      Chunk := Pkt( Pkt'First + (I-1) * Chunk'Length ..
                    Pkt'First + I * Chunk'Length - 1 );
      -- decrypt it via rsa+oaep
      RSA_OAEP.Decrypt( Chunk, K, Decr, Len, Flag );
      -- check result and if ok then copy it to final result at its place
      -- NB: if returned length is EVER less than OAEP_MAX_LEN then -> fail!
      -- the reason for above: there will be undefined bits in the output!
      if Len /= Raw_Types.OAEP_MAX_LEN or (not Flag) then
        Success := False;
        return Msg;
      else
        Msg( Msg'First + (I-1) * Decr'Length ..
             Msg'First + I * Decr'Length - 1 ) := Decr;
      end if;
    end loop;

    -- return obtained message
    return Msg;
  end Unpack;

The new tests for the above, in test_packing.adb:

  procedure Test_Pack_Unpack_RSA is
    Msg       : RSA_Msg;
    Decr_Msg  : RSA_Msg;
    PKey      : RSA_pkey;
    SKey      : RSA_skey;
    Success   : Boolean;
    Pkt       : RSA_Pkt;
    n: String := "C6579F8646180EED0DC1F02E0DDD2B43EABB3F702D79D9928E2CDA5E1D42DF5D9ED7773F80B1F8D9B0DB7D4D00F55647640D70768F63D3CED56A39C681D08D6191F318BB79DC969B470A7364D53335C8318EF35E39D5DF706AB6F2393C6DD2128C142DBAB1806EB35E26C908F0A48419313D2D0F33DD430655DBFEC722899EC21C238E8DB7003430BBC39BAD990F9887F6B03E1344F537EC97389B78DBC656718ACD7B0FDC13DD24534F417BC7A18F077A0C4227354CEA19670331B6CAA3DFC17BBA7E70C14510D9EB3B63F3014994EC87BD23E868C0AE6E9EC55027577F62C0280B2D7DD1135001844923E5455C4566E066B3FDE968C6BC4DC672F229FCE366440403D7A4F4A8BFBA5679B7D0844BA1231277D13A77C9E2B5A1CB138C1B7AB5B4D4832448723A3DE70ED2E86D5FC5174F949A02DE8E404304BEB95F9BF40F3AA3CA15622D2776294BE7E19233406FF563CB8C25A1CB5AADBC1899DA3F2AE38533931FE032EE3232C2CD4F219FADF95B91635C0762A476A4DE5013F4384093F0FB715028D97F93B2E6F057B99EE344D83ADF2686FD5C9C793928BEF3182E568C4339C36C744C8E9CA7D4B9A16AA039CBF6F38CC97B12D87644E94C9DBD6BC93A93A03ED61ECC5874586E3A310E958F858735E30019D345C62E5127B80652C8A970A14B31F03B3A157CD5";
    e: String := "F74D78E382FC19B064411C6C20E0FDB2985F843007A54C7D8400BB459468624126E7D175F397E55C57AF25858EAE2D2952FB7998C119A6103606733EB5E1D27FCA1FACF14ADE94101D383D1B25DA511805569BC344EAD384EDBF3F3A541B34887FE199D99D7F62E6E9D516F88D6F5AD3E020DF04D402A02CC628A0064362FE8516CF7CD6040E9521407AB90EE6B5AFFF9EA9EBB16A7D3407CE81FD3844F519880556AB94AB349C1F3BBB6FDB4C4B377FE4C091EBDC2C3A1BD3AA56382D8D80E7742B5C751008FD6ECDD2EC3B2E3B6C566F698ED672000B403766DD63C3ACBDE16A14FB02E83A2EB6AA018BFC0020401E790DEE24E9";
    d: String := "698DA05DA25B230211EEF0CBA12083A1457B749A11937AC9993859F69A3BF38D575E5166AF2EC88D77F1DF04E68AEA358EACF7659FD4722A4F5A1C8BA7676DA97A9FBA75451152F8F68887D3451A9CCFFFE9EB80979786E37495B17687A6212F77FA616E4C0CD8A8EB7AEB88EA6CCABB7F3E854FB94B35394A09F95F0D6F997947E865CC0606F437C30FE8C48D96FBF5E2F52807BC9E9ED7BBEB23D5C45EDDCD16FE2BF410A9A1E5EF879E71C0D41FAE270C0C5D442860103F8C3944E802F33DB38432F11F763A7AF593656108E4A98A44A8549913CE5DCEC1A6500F280E3190991B2B938561CFACD8BC5183AAC9A4914BFE52C3BE39BB83688E1DE52479107EF8E087DCDB409432FC954C6349407E81DDFB11AE92BABB32A31868597958C9C76E0B4156F380955F0E09C1F3B98BB4CDD59E1B5C7D8CC2AA7491B0D319D219CF459A527CE1AA2729DEC53269653BF0ED3E0253F4451168437E3B069E48350CA4C3EC82134E87135624C768D1330B0D70C6E447FD9945BF06FCB91AA334C0FD8EEF1ADBC15928B3DB62077B537F7E9F468CC95CD5AAFEAE1F760A863B48D07B163F670E2E5B550BB3E960230BA9FDAED9903AE2E669A7F3C4D1F1E25B8E8EDB8CC6E6FD2164E66F4E64ED77BEF1EC9E6CEA5624FD84C0680248746DC1C8187145F3CD2411659DAEAD11D";
    p: String := "CDD6F7673A501FB24C44D56CA1D434F6CB3334E193E02F8E906241906BCB7412DD2159825B24C22002F373E647C2DA62A854F3841C00FD5985D03227CA9B54A69380BA9D63BE738BDF9E65C247E43E1220EEDD9281DCA78B32A4E1B786B7697ED0C3195D5AF2990881B11D6FC9EC9F940067B2DEA2A516FAA5F269C98F0B67628A6D2708515A4A58041AA17A93E4C4DD95C85BC38351DDA1DCF3DFD91C505B22383132649CF9F9233852C7207075BCF43C71038F043F1EC53E9787FB051B7927D020903233C16897B993C8089D8464451F086E756CF20E46CE6ED4A6AC5C327A0AAFBECBAAFD177969E7C952C76A4F4E7C85BF7F63";
    q: String := "F6ACF0790A250802C8D45DAC549CDBEF7806D5877A5DF0069136A458FAC4F0B0858060A873DA6355A965A064A0BC1BBB874872CD7ED89674AD407533041E74BCA317EC73597D335115523F61A05071E5ED81EE2A05331F65D4DC7A25AD7938B124CF03F49154B6693FB0B598B33ABDEF85C599A57A9B7347EAFF82638E1CBC28FCDFFF1FF04A18C2DBF3938395C2F8D1782B43D3A25EF7633B5DDAC89EFD3BAA64D976425A0891E00B876E9DE9FE4B6492B0EA8DFC7C8DEEC61721356EC816295B1BD9CD9DA3E30D2D90DC9CB3987F4BE042104900E036F3044A016749EF910CCFB9F377A90849B4CCCF4471A74E67EF6C814C9467";
    u: String := "854B89ED10F52258D00D6B3FA7F1FD22752804668F51FF7806DB82E22CB8B3AA8448D9B8E9DB14D31A36AEC2BCFA89E341B7334D494E97ED8051244136192233332C4612D963E7B6AF2535FDB7FE97E28DDFEBDFB3E1AFC29D05DBDF37106A817D3AB1864C7F7F247982897EDA6A92BED47D9C68305CD170C7301ACEB05F8A6382E73CC7614B2D8D758669B3A99AB64114809254B0BE21F40341A5B48B9B032603B14875B87EB5E16603FD16552E146A0FC6964958DFC25AA9FFCCD1ED1F4DEAF9FBAA0D7357F5FF0803FEB9BA78E74AC6B3070F417CEC6CFC7A3CF1E305FC7B76B7ED71893999AF797B2EBDE41FE90F076CCEDBFB";
  begin
    -- initialize RSA key with values previously obtained from EuCrypt
    Hex2Octets( n, SKey.n );
    Hex2Octets( e, SKey.e );
    Hex2Octets( d, SKey.d );
    Hex2Octets( p, SKey.p );
    Hex2Octets( q, SKey.q );
    Hex2Octets( u, SKey.u );
    -- copy n and e for public key
    PKey.n := SKey.n;
    PKey.e := SKey.e;
    -- get random data for "message"
    RNG.Get_Octets(Msg);

    -- pack the message into corresponding packet
    Pkt := Packing.Pack( Msg, PKey );
    -- unpack and check the result
    Decr_Msg := Packing.Unpack( Pkt, SKey, Success );
    if (not Success) or (Decr_Msg /= Msg) then
      Put_Line("FAIL: pack/unpack with RSA.");
    else
      Put_Line("PASS: pack/unpack with RSA.");
    end if;

    -- try to unpack a mangled package
    Pkt(Pkt'First + 3) := Pkt(Pkt'First + 3) and 16#AB#;
    Decr_Msg := (others => 0);
    Decr_Msg := Packing.Unpack( Pkt, SKey, Success );
    if Success then
      Put_Line("FAIL: pack/unpack with RSA on mangled package.");
    else
      Put_Line("PASS: pack/unpack with RSA on mangled package.");
    end if;

  end Test_Pack_Unpack_RSA;

The .vpatch with all the above is on my Reference Code Shelf and linked below for your convenience:

UPDATE (5 November 2018): I've changed the tests so that they read the RSA keypair from a file rather than using a hard-coded key; as discussed in the logs, this is the only way I can see to keep all lines in code files under 80 columns while also keeping RSA components as they are i.e. well longer than 80 characters in any sane format. The added procedure simply reads key components in a rather blunt way, character by character and demanding *exactly* as many characters as needed to fill the length of key it expects. This is NOT a generic "key reading" but simply a quick switch of input for the basic tests:

  procedure ReadRSAKey( Filename: in String; Key: out RSA_OAEP.RSA_skey ) is
    package Char_IO is new Ada.Sequential_IO(Character);
    use Char_IO;
    Full : String(1..RSA_len'Length*2) := (others => '0');
    Half : String(1..RSA_half'Length*2) := (others => '0');
    F    : Char_IO.File_Type;
    C    : Character;
  begin
    Open( File => F, Mode => In_File, Name => Filename );

    -- read n
    for I in Full'Range loop
      Read(F, Full(I));
    end loop;
    -- read new line character and convert to hex
    Read(F, C);
    Hex2Octets(Full, Key.n);

    -- read e
    for I in Half'Range loop
      Read(F, Half(I));
    end loop;
    -- read new line character and convert to hex
    Read(F, C);
    Hex2Octets(Half, Key.e);

    -- read d
    for I in Full'Range loop
      Read(F, Full(I));
    end loop;
    -- read new line character and convert to hex
    Read(F, C);
    Hex2Octets(Full, Key.d);

    -- read p
    for I in Half'Range loop
      Read(F, Half(I));
    end loop;
    -- read new line character and convert to hex
    Read(F, C);
    Hex2Octets(Half, Key.p);

    -- read q
    for I in Half'Range loop
      Read(F, Half(I));
    end loop;
    -- read new line character and convert to hex
    Read(F, C);
    Hex2Octets(Half, Key.q);

    -- read u
    for I in Half'Range loop
      Read(F, Half(I));
    end loop;
    Hex2Octets(Half, Key.u);

    -- Close file
    Close( F );

    exception
      when Char_IO.End_Error =>
        Put_Line("ReadRSAKey ERROR: Unexpected end of file in " & Filename);
      when others =>
        Put_Line("ReadRSAKey ERROR: can not open file " & Filename);

  end ReadRSAKey;

Since this change of inputs for tests has nothing to do with either protocol code per se or with advancing the protocol implementation, I'm considering it more of a fix of sorts to this chapter's code and so it'll be a .vpatch by itself, to be found both on the Reference Code Shelf and linked from here:

UPDATE (12 November 2018): I've refactored the tests to extract the reading of a RSA key in a package of its own and thus use it afterwards from everywhere it's needed (i.e. not only in testing oaep_rsa but also in testing the packing for instance). Since this happened after I published Chapter 7, it's a new .vpatch on top:


  1. It will be handled at a higher level, where data structures are populated. 

  2. Thank you, asciilifeform! 

3 Comments »

  1. Bag de seamă că sărbătorești prin muncă :-)

    Comment by Cristian — November 4, 2018 @ 10:18 p.m.

  2. Si, si.

    Comment by Diana Coman — November 5, 2018 @ 10:18 a.m.

  3. And update no. 2 that finally truly gets rid of lines > 80cols *everywhere*: the reading of a RSA key is now extracted separately so that all tests that need that can call it from its own package.

    Comment by Diana Coman — November 12, 2018 @ 12:00 p.m.

RSS feed for comments on this post. TrackBack URL

Leave a comment

Theme and content by Diana Coman