[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[minion-cvs] Increase packet key length to 2048 bits, and describe t...



Update of /home/minion/cvsroot/doc
In directory moria.mit.edu:/tmp/cvs-serv27742/doc

Modified Files:
	minion-spec.tex 
Log Message:
Increase packet key length to 2048 bits, and describe the revised ("compact")
header encoding rules.  George -- are these right?

Also, drop mention of BEAR -- next to 2048-bit RSA, LIONESS is plenty fast.


Index: minion-spec.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-spec.tex,v
retrieving revision 1.87
retrieving revision 1.88
diff -u -d -r1.87 -r1.88
--- minion-spec.tex	13 Apr 2003 15:56:23 -0000	1.87
+++ minion-spec.tex	16 Apr 2003 15:29:40 -0000	1.88
@@ -148,14 +148,25 @@
 - Len(M) (2 bytes) is the length of message M (* bytes).
 - x|y (Len(x)+Len(y) bytes) denotes x concatenated with y.
 
+- Symbolic constants:
+
+   OAEP_OVERHEAD=42.   The number of bytes added by OAEP padding,
+   using SHA-1 as the digest primititive.
+
+   RSA_LEN=256.   We require that all RSA keys be 256 bytes long
+   (2048 bits).
+
+   MAX_RSA=RSA_LEN - OAEP_OVERHEAD = 214.
+
 - PAD(M,L)=M|Z(L-Len(M)) (L bytes) pads the message M (Len(M) <= L)
   to length L using zeroes.
 - HASH(M) (20 bytes) is the SHA-1 hash of M (* bytes).
-- PK_Encrypt(K,M) (128 bytes) The RSA-encryption of a header M 
+- PK_Encrypt(K,M) (RSA_LEN bytes) The RSA-encryption of a header M 
   using the public key K.  M is padded using RSA-OAEP, and encoded
   with PKCS1.
-- PK_Decrypt(K,M) (up to 86 bytes) Gives the decryption of the
-  message M (128 bytes) under the private key corresponding to K.
+- PK_Decrypt(K,M) (up to RSA_LEN-OAEP_OVERHEAD=MAX_RSA=214 bytes) 
+  Gives the decryption of the message M (256 bytes) under the private
+  key corresponding to K.
 - Encrypt(K,M) (Len(M) bytes) Rijndael encryption (in Counter mode,
   with 128-bit blocksize) of message M using key K.  (All Rijndael
   operations use 128-bit blocks.)  The Initial Vector (IV) is Z(16).
@@ -169,11 +180,6 @@
   as described in XXXXCITE, with ENCRYPT(K,m) as our stream cipher,
   and the keyed-SHA1 construction specified in the LIONESS paper.
 
-  [XXXX I think we can get away with BEAR instead.  See my email of
-    September 6. -NM I agree -GD]
-  [XXXX Okay.  Whose approval were we waiting for to get final
-    verification of this?  Was it David Hopwood? -NM]
-
   K1 through K4 are 160 bits long.
 
   Thus, SPRP_ENCRYPT(K1,K2,K3,K4,M) is computed as follows:
@@ -216,8 +222,8 @@
 
 A subheader contains all the information that a mix needs to check the
 integrity of a message and route it through the Internet. The subheader
-is encrypted using RSA after having been padded using OAEP, using a 1024
-bit key. This results in an encrypted block of 128 bytes.
+is encrypted using RSA after having been padded using OAEP, using a 2048
+bit key. 
 
 A subheader contains the following fields:
 
@@ -231,6 +237,9 @@
 RT  Routing Type:    2 bytes [total 42 bytes]
 RI  Routing Info:    [Routing Size] bytes
 
+   (We use the symbolic constant MIN_SH=42 below to indicate the
+   length of the invariant part of a subheader.)   
+
 * The Version is used to manage concurrent versions of the
 protocol. If a packet is received with a version that is not supported
 it must be discarded. Nodes must advertise in their status blocks what
@@ -240,9 +249,12 @@
 other keys for the operations the node performs on the packet. It must be
 kept secret and discarded as soon as the packet has been processed. 
 
-* The Digest contains an integrity check of the remainder of the current
-header (128*15 bytes in total). The digest does not cover the current
-subheader: modifications to it are detected because of the OAEP padding.
+We will formally refer to the subheader structure as:
+SHS(V, SK, D, RS, RT, RI)     [MIN_SH+Len(RI)) bytes] 
+
+* The Digest contains an integrity check of the remainder of the
+  current header. The digest does not cover the current subheader:
+  modifications to it are detected because of the OAEP padding.
 
 * The Routing Type defines how the mix should deliver or relay the
   message. If a mix receives a routing type it does not recognize,
@@ -251,30 +263,35 @@
   Most routing methods require additional addressing information.
   The Routing Size field indicates the total size of the Routing
   Information. If the information is too long to fit in a single
-  subheader (more than 86-42=44 bytes), then one or more additional
-  Routing Extension blocks have to be added. These additional blocks
-  must be 128 bytes each and should have the following structure:
- 
-  Routing Extension:
-
-    Address Data:     Variable
-    Padding:          Variable
+  subheader (more than RSA_LEN - OAEP_OVERHEAD - MIN_SH = 172 bytes), 
+  then additional data is added after the subheader.
 
 * The address data length is specified by the "Routing Size" field
   contained in the subheader.
-* The final Routing Extension block is padded with zeroes so it is
-  exactly 128 bytes.
 
-The Routing Extension(s) corresponding to a particular subheader are
-appended to the subheader, and encrypted along with the rest of the
-subheaders.
+Thus, when adding a new subheader SH to a partial header H, there are
+two possibilities:
 
-We will formally refer to the subheader structure as:
-SHS(V, SK, D, RS, RT, RI)     [MIN(86, 42+Len(RI)) bytes] 
-And to the RSA-OAEP encrypted portions of the subheader structure as:
-ESHS(PK, V, SK, D, RS, RT, RI)   [128 bytes]
-And to the extension blocks for a given subheader as:
-EXT(RI)                       [Ceil((Len(RI)-44)/128) * 128 bytes]
+   1. If the subheader is less than MAX_RSA bytes long, it fits into a
+      single RSA encryption, and we include some of the data from the
+      rest of the header:
+   
+     Before: (S is the new subheader, H is the existing header material)
+      SSSSSSSSSS   HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH.....
+
+     After: 
+      (Encrypted with RSA)   (Encrypted with AES)
+      SSSSSSSSSSHHHHHHHHHH   HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH.....
+
+   2.  Otherwise, the subheader won't fit into a single RSA
+       encryption, so we spill some of it over:
+
+     Before:
+      SSSSSSSSSSSSSSSSSSSSSSSSS   HHHHHHHHHHHHHHHHHHHHHHHHHHH.....
+
+     After:
+      (Encrypted with RSA)   (Encrypted with AES)
+      SSSSSSSSSSSSSSSSSSSS   SSSSSHHHHHHHHHHHHHHHHHHHHHHHHHHH.....
 
 \subsection{Routing information}
 
@@ -320,12 +337,13 @@
 Each type III message has two headers with identical structure. These
 headers are swapped at the crossover point.
 
-A header is 16*128 bytes long and contains up to 16
+A header is HEADER_LEN=2048 bytes long and contains up to
+2048/(OAEP_OVERHEAD+MIN_SH)=24.
 subheaders. Starting with N subheaders SH_0..SH_N containing secrets
 SK_0..SK_N (and placing routing extension blocks directly after their
 respective subheaders), the header is constructed by appending 
 random padding to achieve a total size
-of 128*16 bytes. Then, each subheader key is used to create a key
+of 2048 bytes. Then, each subheader key is used to create a key
 Hash(SharedSecret | "HEADER SECRET KEY") with which the part of the
 header after the subheader (but including its routing extension) is
 encrypted using counter-mode AES.
@@ -335,6 +353,75 @@
 
 PROCEDURE: Create a single header.
 
+Inputs: RI_1..RI_n, RT_1..RT_N (addresses of intermediate nodes), 
+        PK_1 .. PK_N (Public keys of intermediate nodes),
+        SK_1 .. SK_N (Secret keys to be shared with intermediate nodes),
+        R Routing type and information of last header (FWD, DROP, SWAP, etc.)
+Output: H (The header)
+
+Process: 
+  // Calculate the sizes of the subheaders.
+  for i = 1 .. N
+        // OAEP Padding plus invariant parts plus routing info.
+        SIZE_i = MIN_SH + OAEP_OVERHEAD + Len(RI_i)
+        JUNK_KEY_i = HASH(SK_i | "RANDOM JUNK")[0:16]
+        K_i = HASH(SK_i | "HEADER SECRET KEY")[0:16]
+  end
+
+  PADDING_LEN = 2048-SUM(SIZE_1 ... Size_N)
+
+  // Calculate the Junk that will be appended during processing.
+  // J_i is the junk that node i will append, and node i+1 will see.
+  J_0 = "";
+  for i = 1 .. N
+        J_i = J_(i-1) | PRNG(JUNK_KEY_i, SIZE_i)
+        Stream_i = PRNG(K_i, 2048 + SIZE_i);
+        // Before we encrypt the junk, we encrypt all the data, and all
+        // the initial padding, but not the RSA-encrypted part.
+        //    OFFSET = PADDING_LEN + SUM(SIZE_1 ... SIZE_i) - 256
+        //           = 2048-256 + SUM(SIZE_1 ... Size_i)
+        //                      - SUM(SIZE_1 ... Size_N)
+        //           = PADDING_LEN + Len(J_i) - 256
+        OFFSET = PADDING_LEN + Len(J_i) - 256
+        J_i = J_i XOR Stream_i[OFFSET:Len(J_i)];
+  end
+
+  // Create the Header, starting with the padding.
+  H_(N+1) = Rand(PADDING_LEN)
+
+  for i = N .. 1
+        IF i = N (set appropriate routing type and A_i)
+
+        // Decide whether to spill RI out of the RSA-encrypted chunk
+        // (unlikely), or to include some of the rest of the header
+        // in the RSA-encrypted chunk (likely).
+        if Len(RI_(i+1)) > MAX_RSA-MIN_SH then
+             RI_SPILL_LEN = Len(RI) - MAX_RSA + MIN_SH
+             H_INCL_LEN = 0
+        else
+             RI_SPILL_LEN = 0
+             H_INCL_LEN = MAX_RSA - MIN_SH - Len(RI_(i+1))
+        endif
+
+        REST = RI_(i+1)[Len(RI_(i+1)) - RI_SPILL_LEN : RI_SPILL_LEN]
+               | H_(i+1)[H_INCL_LEN : Len(H_(i+1))-H_INCL_LEN]
+
+        EREST = Encrypt(K, REST)
+        DIGEST = HASH(EREST | J_i-1)
+
+        SH = SHS(V, SK_i, DIGEST, len(RI_(i+1)), RT_(i+1), RI(i+1))
+        ESH = PK_ENCRYPT(PK_i, 
+                         SH[0:Len(SH)-RI_SPILL_LEN] |
+                         H[0:H_INCL_LEN]) 
+        H_i = ESH | EREST
+  end
+
+return H_1;
+
+============================================================
+[XXXXXX THIS IS THE OLD ONE.
+PROCEDURE: Create a single header.
+
 Inputs: A_1 .. A_N (addresses of intermediate nodes), 
         PK_1 .. PK_N (Public keys of intermediate nodes),
         SK_1 .. SK_N (Secret keys to be shared with intermediate nodes),
@@ -371,6 +458,8 @@
 
 return H_1;
 
+XXXXXXXXXXXXXXXXXXXX END OLD HEADER GENERATION. ]
+
 \subsection{The Payload of messages}
 
 The payload of a Mixminion message has a fixed length of 32 kb
@@ -423,6 +512,36 @@
 PK receiving message M = (H1, H2, P) performs the following operations:
 
 PROCEDURE: Process a message M
+        PK_PART = PK_Decrypt(PK,H1[0:256]);
+        If there is any problem with the OAEP padding discard the message.
+
+        If Len(PK_PART) != MAX_RSA, discard the message.
+
+        SHS(V, SK, D, RS, RT, ..) = <extract from PK_PART[0:MIN_SH]>
+        Check that D = HASH(H1[256:2048-256]), and discard if not.
+
+        If RS > MAX_RSA-MIN_SH then 
+            // RI is incomplete.
+            RI = PK_PART[MIN_SH:MAX_RSA-MIN_SH]
+            MISSING_RI_LEN = RS - (MAX_RSA-MIN_SH)
+            EXTRA_H = ""
+        else
+            RI = PK_PART[MIN_SH:RS]
+            MISSING_RI_LEN = 0
+            EXTRA_H = PK_PART[MIN_SH+RS:Len(PK_PART)-MIN_SH-RS]
+        endif
+
+        JUNK_KEY = HASH(SK | "RANDOM JUNK")[0:16]
+        H1 = H1[RSA_LEN : 2048-RSA_LEN] | 
+             PRNG(JUNK_KEY, OAEP_OVERHEAD + MIN_SH +RS)
+        HEADER_KEY = HASH(SK | "HEADER SECRET KEY")[0:16]
+        H1 = H1 XOR PRNG(HEADER_KEY, Len(H1))
+        RI = RI | H[0:MISSING_RI_LEN]
+        H1 = EXTRA_H | H1[MISSING_RI_LEN:2048-MISSING_RI_LEN]
+        H2 = SPRP_DEC(SK, "HEADER ENCRYPT",H2);
+        P = SPRP_DEC(SK, "PAYLOAD ENCRYPT",P);
+
+ [XXXXXXXXX OLD!!!!!!
         SHS(V, SK, D, RS, RT, RI) = PK_Decrypt(PK,H1[0:128]);
         If there is any problem with the OAEP padding discard the message.
         Check that D = HASH(H1[128:15*128]), and discard if not.
@@ -435,6 +554,7 @@
         H1 = H1[128*n_extra:128*16]
         H2 = SPRP_DEC(SK, "HEADER ENCRYPT",H2);
         P = SPRP_DEC(SK, "PAYLOAD ENCRYPT",P);
+  XXXXXXXXXXX END OLD]
 
         if routing type is DROP:
                 End.