Ossasepia

November 30, 2018

SMG Comms Chapter 10: Actions and RSA Keys

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

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

Eulora's communication protocol uses RSA keys only for new players who don't yet have a set of Serpent keys agreed on for communication with the server. The main reason for not using RSA for all client-server communications is simply that RSA is essentially too expensive for that. As it happens, it turns out that republican RSA with its fixed-size 256 octets (2048 bits) public exponent is anyway too expensive even for this reduced role - communicating all those octets to the server inside a RSA package takes quite a lot of space. As a result, Eulora will use a smaller e, on only 8 octets (64 bits) that fit neatly into the message structure for requesting a new account in the game (5.1 RSA key set). This means of course that I'll also have to patch EuCrypt to allow arbitrary size of the public exponent in order to have a way to actually generate such RSA key pairs but this will have to be the next step and another post on its own. For now, at the level of read/write from/to SMG Comms messages, there's no direct concern with the crypto lib itself: the e will simply be 8 octets long at its specified place in the message and that is that.

Since the RSA Key Set message includes also some client information (protocol version and subversion, client hash, preferred padding), I've first defined a new data structure (in data_structs.ads) to hold all this in one place:

  type Player_RSA is
    record
      -- communication protocol Version number
      Proto_V    : Interfaces.Unsigned_8;

      -- communication protocol Subversion number
      Proto_Subv : Interfaces.Unsigned_16;

      -- Keccak hash of client binary
      Client_Hash: Raw_Types.Octets_8;

      -- public exponent (e) of RSA key (64 bits precisely)
      -- nb: this is protocol-specific e, aka shorter than TMSR e...
      e          : Raw_Types.Octets_8;

      -- public modulus (n) of RSA key (490 bits precisely)
      n          : Raw_Types.RSA_len;

      -- preferred padding; magic value 0x13370000 means random padding
      Padding    : Raw_Types.Octets_8;

    end record;

The choice to have the new structure shown above comes mainly from the fact that all the information in there is on one hand related (as it belongs to and describes one specific player at any given time) and on the other hand of no direct concern to this part of code. In other words, this part of the code reads and writes that information together but it has no idea regarding its use (nor should it have). It's for this same reason also that I preferred to keep e and n simply as members like any others of the Player_RSA record rather than having them stored already inside a RSA_pkey structure. For one thing there's no need for the read/write part to even know about the RSA_pkey structure (which is defined in rsa_oaep.ads where it belongs). And for another thing, having e and n as members of the record just like any others keeps the code both clear and easy to change in principle at a later time. Basically the read/write do as little as they can get away with - there is even no attempt to interpret e for instance as a number although its reduced size makes that possible here. Note that the protocol version and subversion are however interpreted as integers but in their case there's no point to keep them as raw octets. On the other hand, the choice of padding is kept as raw octets precisely because this is how it will be needed and used anyway.

Choosing the correct place for storing the padding option also gave me a bit to think about because it's not fully clear to me at this stage exactly where the padding belongs. Strictly speaking, padding is entirely the job of this level so there shouldn't normally be any leaking outside/upwards of anything to do with it. However, having the ability to choose types of padding means that the protocol itself effectively pushes this particular aspect upwards since it's the user ultimately who makes this choice. As a result, I decided to keep the mechanics of padding local (i.e. actual padding of messages + the magic value for requesting random padding + the interpretation of a padding parameter) while providing this Padding value in the Player_RSA record and otherwise refactoring all the Write procedures to require a Padding parameter indicating the desired choice of padding for that write. Moreover, to have this padding stuff in one single place, I also extracted the writing of counter+padding into its own procedure and then refactored all the Write procedures to call this one (since ALL messages always have at the end precisely a counter + padding). The main benefit to this is that it reduces the chances of making an error in one of the multiple places where otherwise one has to write the counter and then check the requested padding and then pad (if needed) accordingly. Other than this benefit, there isn't necessarily a big reduction in number of code lines nor really much an increase in clarity of the code since there is another procedure call to follow in there. Nevertheless, the alternative is worse: having copy-pasted same stuff in every write procedure and having to change all of it if anything changes. So here's the new Write_End procedure which is private to the Messages package since this is just a helper for all the other Write procedures:

  -- Writes Counter and padding (rng or otherwise) into Msg starting from Pos.
  procedure Write_End( Msg     : in out Raw_Types.Octets;
                       Pos     : in out Natural;
                       Counter : in Interfaces.Unsigned_16;
                       Padding : in Raw_Types.Octets_8) is
  begin
    -- check that there is space for Counter at the very least
    if Pos > Msg'Last - 1 then
      raise Invalid_Msg;
    end if;

    -- write counter
    Write_U16( Msg, Pos, Counter );

    -- pad to the end of the message
    if Pos <= Msg'Last then
      if Padding = RNG_PAD then
        RNG.Get_Octets( Msg( Pos..Msg'Last ) );
      else
        -- repeat the Padding value itself
        for I in Pos..Msg'Last loop
          Msg(I) := Padding( Padding'First + (I - Pos) mod Padding'Length );
        end loop;
      end if;
      -- either rng or fixed, update Pos though
      Pos := Msg'Last + 1;
    end if;
  end Write_End;

After the above changes, the read/write procedures for RSA key set from/to RSA messages are quite straightforward to write:

  procedure Write_RKeys_RMsg( K       : in Player_RSA;
                              Counter : in Interfaces.Unsigned_16;
                              Pad     : in Raw_Types.Octets_8;
                              Msg     : out Raw_Types.RSA_Msg) is
    Pos : Natural := Msg'First + 1;
  begin
    -- write correct message type
    Msg( Msg'First ) := RKeys_R_Type;

    -- write protocol version and subversion
    Msg( Pos ) := K.Proto_V;
    Pos := Pos + 1;
    Write_U16( Msg, Pos, K.Proto_Subv );

    -- write keccak hash of client binary
    Msg( Pos..Pos + K.Client_Hash'Length-1 ) := K.Client_Hash;
    Pos := Pos + K.Client_Hash'Length;

    -- write e of RSA key
    Msg( Pos..Pos + K.e'Length - 1 ) := K.e;
    Pos := Pos + K.e'Length;

    -- write n of RSA key
    Msg( Pos..Pos + K.n'Length - 1 ) := K.n;
    Pos := Pos + K.n'Length;

    -- write preferred padding
    Msg( Pos..Pos + K.Padding'Length - 1 ) := K.Padding;
    Pos := Pos + K.Padding'Length;

    -- write counter + padding
    Write_End( Msg, Pos, Counter, Pad );

  end Write_RKeys_RMsg;

  -- Reads a RSA Keyset (Player_RSA structures) from the given RSA Message.
  -- Opposite of Write_RKeys_RMsg above
  procedure Read_RKeys_RMsg( Msg      : in Raw_Types.RSA_Msg;
                             Counter  : out Interfaces.Unsigned_16;
                             K        : out Player_RSA) is
    Pos : Natural := Msg'First + 1;
  begin
    -- check type id and raise exception if incorrect
    if Msg(Msg'First) /= RKeys_R_Type then
      raise Invalid_Msg;
    end if;

    -- read protocol version and subversion
    K.Proto_V := Msg( Pos );
    Pos := Pos + 1;
    Read_U16( Msg, Pos, K.Proto_Subv );

    -- read Keccak hash of client binary
    K.Client_Hash := Msg( Pos..Pos+K.Client_Hash'Length - 1 );
    Pos := Pos + K.Client_Hash'Length;

    -- read e
    K.e := Msg( Pos .. Pos + K.e'Length - 1 );
    Pos := Pos + K.e'Length;

    -- read n
    K.n := Msg( Pos .. Pos + K.n'Length - 1 );
    Pos := Pos + K.n'Length;

    -- read choice of padding
    K.Padding := Msg( Pos .. Pos+K.Padding'Length - 1 );
    Pos := Pos + K.Padding'Length;

    -- read message counter
    Read_U16( Msg, Pos, Counter );

    -- the rest is message padding, so ignore it

  end Read_RKeys_RMsg;

As usual, I also wrote the tests for all the new procedures, including the private Write_End. However, the testing package as it was could not directly call this private procedure from Messages. My solution to this is to change the declaration of the testing package so that it is effectively derived from Messages - at the end of the day it makes sense that the tester simply needs to get to all the private bits and pieces. This change makes however for a lot of noise in the .vpatch but that's how it is. The new test procedure for the counter+padding is - quite as usual - longer than the code it tests1 :

  procedure Test_Padding is
    Msg     : Raw_Types.Serpent_Msg := (others => 12);
    Old     : Raw_Types.Serpent_Msg := Msg;
    Pos     : Natural := 16;
    NewPos  : Natural := Pos;
    Counter : Interfaces.Unsigned_16;
    U16     : Interfaces.Unsigned_16;
    O2      : Raw_Types.Octets_2;
    Pad     : Raw_Types.Octets_8;
    Pass    : Boolean;
  begin
    -- get random counter
    RNG.Get_Octets( O2 );
    Counter := Raw_Types.Cast( O2 );

    -- test with random padding
    Pad := RNG_PAD;
    Write_End( Msg, NewPos, Counter, Pad );
    -- check NewPos and counter
    Pass := True;
    if NewPos /= Msg'Last + 1 then
      Put_Line("FAIL: incorrect Pos value after Write_End with rng.");
      Pass := False;
    end if;
    Read_U16(Msg, Pos, U16);
    if U16 /= Counter then
      Put_Line("FAIL: incorrect Counter by Write_End with rng.");
      Pass := False;
    end if;
    -- check that the padding is at least different...
    if Msg(Pos..Msg'Last) = Old(Pos..Old'Last) or
       Msg(Pos..Pos+Pad'Length-1) = Pad then
      Put_Line("FAIL: no padding written by Write_End with rng.");
      Pass := False;
    end if;
    if Pass then
      Put_Line("PASS: Write_End with rng.");
    end if;

    -- prepare for the next test
    Pass   := True;
    Pos    := Pos - 2;
    NewPos := Pos;
    Msg    := Old;

    -- get random padding
    RNG.Get_Octets( Pad );

    -- write with fixed padding and check
    Write_End( Msg, NewPos, Counter, Pad );
    Pass := True;

    if NewPos = Msg'Last + 1 then
      -- check counter + padding
      Read_U16( Msg, Pos, U16 );
      if U16 /= Counter then
        Put_Line("FAIL: Counter was not written by Write_End.");
        Pass := False;
      end if;
      for I in Pos..Msg'Last loop
        if Msg( I ) /= Pad( Pad'First + (I - Pos) mod Pad'Length ) then
          Put_Line("FAIL: Msg(" & Natural'Image(I) & ")=" &
                    Unsigned_8'Image(Msg(I)) & " /= Pad(" &
                    Natural'Image(Pad'First+(I-Pos) mod Pad'Length) &
                    ") which is " &
                    Unsigned_8'Image(Pad(Pad'First+(I-Pos) mod Pad'Length)));
          Pass := False;
        end if;
      end loop;
    else
      Put_Line("FAIL: Pos is wrong after call to Write_End.");
      Pass := False;
    end if;
    if Pass then
      Put_Line("PASS: test for Write_End with fixed padding.");
    end if;
  end Test_Padding;

With the above read/write of a RSA key set, all the RSA messages specified in the protocol are provided. Of the Serpent messages, those not implemented are the Client Action, World Bulletin, Object Request and Object Info. All of those still require some details to be filled in but for the moment I went ahead and implemented read/write for Client Action based on a text representation of the action itself (i.e. precisely as specified in the protocol for 4.5 although the action can be/is in principle a fully specified structure by itself as described in section 7 of the specification). At this stage I'm not yet sure whether to provide another layer of read/write for that action text or whether to attempt to read/write directly the Action structures. So this will have to wait and as details are becoming clearer, the code will get changed /added to, no big deal. Anyway, the Write_Action and Read_Action for now:

  -- writes the action (octets+length) into the specified Serpent message
  procedure Write_Action( A       : in Raw_Types.Text_Octets;
                          Counter : in Interfaces.Unsigned_16;
                          Pad     : in Raw_Types.Octets_8;
                          Msg     : out Raw_Types.Serpent_Msg) is
    Pos    : Natural := Msg'First + 1;
    MaxPos : Natural := Msg'Last - 1; --2 octets reserved for counter at end
    U16    : Interfaces.Unsigned_16;
  begin
    -- check whether given action FITS into a Serpent message
    if Pos + 2 + A.Len > MaxPos then
      raise Invalid_Msg;
    end if;

    -- write correct type ID
    Msg( Msg'First ) := Client_Action_S_Type;

    -- write action's TOTAL length
    U16 := Interfaces.Unsigned_16(A.Len + 2);
    Write_U16( Msg, Pos, U16 );

    -- write the action itself
    Msg( Pos..Pos+A.Len-1 ) := A.Content;
    Pos := Pos + A.Len;

    -- write counter + padding
    Write_End( Msg, Pos, Counter, Pad );

  end Write_Action;

  -- reads a client action as octets+length from the given Serpent message
  procedure Read_Action( Msg      : in Raw_Types.Serpent_Msg;
                         Counter  : out Interfaces.Unsigned_16;
                         A        : out Raw_Types.Text_Octets) is
    Pos : Natural := Msg'First + 1;
    U16 : Interfaces.Unsigned_16;
  begin
    -- read and check message type ID
    if Msg( Msg'First ) /= Client_Action_S_Type then
      raise Invalid_Msg;
    end if;

    -- read size of action (content+ 2 octets the size itself)
    Read_U16( Msg, Pos, U16 );

    -- check size
    if U16 < 3 or Pos + Natural(U16) - 2 > Msg'Last - 1 then
      raise Invalid_Msg;
    else
      U16 := U16 - 2;  --size of content only
    end if;

    -- create action, read it from message + assign to output variable
    declare
      Act : Raw_Types.Text_Octets( Raw_Types.Text_Len( U16 ) );
    begin
      Act.Content := Msg( Pos..Pos+Act.Len-1 );
      Pos := Pos + Act.Len;
      A := Act;
    end;

    -- read counter
    Read_U16( Msg, Pos, Counter );

  end Read_Action;

As previously with the components of a RSA key, I chose to keep the "action" as raw octets rather than "text" aka String. This can be easily changed later if needed but for now I fail to see any concrete benefit in doing the conversion to and from String. The new Text_Octets type is defined in Raw_Types and I moved there the definition of Text_Len (previously in Messages) as well since it's a better place for it2:

  -- length of a text field (i.e. 16 bits, strictly > 0)
  subtype Text_Len is Positive range 1..2**16-1;

  -- "text" type has a 2-byte header with total length
  -- Len here is length of actual content ONLY (i.e. it needs + 2 for total)
  type Text_Octets( Len: Text_Len := 1 ) is
    record
      -- actual octets making up the "text"
      Content: Octets( 1..Len ) := (others => 0);
    end record;

There is of course new testing code for the read/write action procedures as well:

  procedure Serialize_Action is
    O2 : Raw_Types.Octets_2;
    U16: Interfaces.Unsigned_16;
    Len: Raw_Types.Text_Len;
    Counter: Interfaces.Unsigned_16;
  begin
    Put_Line("Generating a random action for testing.");
    -- generate random counter
    RNG.Get_Octets( O2 );
    Counter := Raw_Types.Cast( O2 );

    -- generate action length
    RNG.Get_Octets( O2 );
    U16 := Raw_Types.Cast( O2 );
    if U16 < 1 then
      U16 := 1;
    else
      if U16 + 5 > Raw_Types.Serpent_Msg'Length then
        U16 := Raw_Types.Serpent_Msg'Length - 5;
      end if;
    end if;
    Len := Raw_Types.Text_Len( U16 );

    declare
      A: Raw_Types.Text_Octets( Len );
      B: Raw_Types.Text_Octets;
      Msg: Raw_Types.Serpent_Msg;
      ReadC : Interfaces.Unsigned_16;
    begin
      RNG.Get_Octets( A.Content );
      begin
        Write_Action( A, Counter, RNG_PAD, Msg );
        Read_Action( Msg, ReadC, B );
        if B /= A then
          Put_Line("FAIL: read/write of Action.");
        else
          Put_Line("PASS: read/write of Action.");
        end if;
      exception
        when Invalid_Msg =>
          if Len + 5 > Raw_Types.Serpent_Msg'Length then
            Put_Line("PASS: exception correctly raised for Action too long");
          else
            Put_Line("FAIL: exception INCORRECTLY raised at action r/w!");
          end if;
      end;
    end;
  end Serialize_Action;

The (rather lengthy) .vpatch for all the above and my signature for it can be found on my Reference Code Shelf as usual or through those links:

The next step now is to patch the rsa/oaep part of SMG Comms to use the 8-octets public exponent and then to get back to EuCrypt and patch it to allow arbitrary size public exponent - so much for fixed size. In other words, it's a very good opportunity to re-read and review EuCrypt!


  1. It is also true that I spend waaaay less time on the tests than on the main code. In writing code like in any other writing, the result of less time spent on it is... longer writing rather than shorter, who'd have thought it, right? I mean who other than Samuel Clemens and pretty much everyone else who actually thought at all. 

  2. This is even more refactoring and therefore noise in the .vpatch, yes! It does say work in progress on the whole thing and in every post on this, right at the top. What did you think that meant? 

1 Comment »

  1. [...] 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 [...]

    Pingback by SMG Comms Chapter 11: Arbitrary Size of Public Exponent « Ossasepia — December 6, 2018 @ 11:01 a.m.

RSS feed for comments on this post. TrackBack URL

Leave a comment

Theme and content by Diana Coman