Re: End to end mixminion rationalized, with compression and K-of-N

[Roger Dingledine <arma@mit.edu>]

On Fri, Oct 11, 2002 at 02:33:52AM -0400, Nick Mathewson wrote:
> Tag: A 20 byte sequence contained in the final subheader of every
>    packet.  Every routing-info field associated with an exit
>    routing-type has a Tag subfield.
> Tagged Payload:The 28K contents of a packet, plus the Tag from the
>    packet's header.

Since we already say 'tag' in the context of a tagging attack, can we use
an alternate name for this? id? mid (mixminion id)? something better? :)

> Stateful SURB: A mode of SURB generation in which the SURB generator
>     remembers an independent set of decryption keys for each generated
>     SURB.
> Stateless SURB: A mode of SURB generation in which the SURB generator
>     only needs to remember a single medium-to-long-term secret to
>     decrypt packets sent to any number of SURBs.

I can see why these are named like this, but on first glance they
seem backwards. A stateful surb is one that carries its own state; a
stateless surb is one that doesn't need to carry any state. The above
notions are instead with-respect-to-the-SURB-generator. State-keeping
surb? State-carrying surb? We may be able to decide a better name here
once we've renamed 'tag' above.

>     PROCEDURE: Divide a message into packets.  [DIVIDE(M,PS,EXF)]
>     ARGUMENTS
>         M: the message to send
>         PS: payload sized (fixed)
>         EXF: expansion factor (fixed: everyone must use the same EXF,
>                               see below.)
> 
>     Let M_SIZE = CEIL(LEN(M) / PS)
>     Let K = Min(16, 2**CEIL(Log2(M_SIZE)))
>     Let NUM_CHUNKS = CEIL(M_SIZE / K)
> 
>     Let M = M | PRNG(Len(M) - NUM_CHUNKS*PS*K)

Is the arg to PRNG going to be negative here?

>     For i from 0 to NUM_CHUNKS - 1:
>        Let CHUNK_i = M[i*PS*K : (i+1)*PS*K]

If we're using the same notation as before, this should be M[i*PS*K :
PS*K], yes?  I think I argued a while ago we might want to change to
your above notation. Should we?

>     End
> 
>     Let N = Ceil(EXF*K)
> 
>     For i from 0 to NUM_CHUNKS-1:
>       For j from 0 to N-1:
>         FRAGMENTS[i*N+j] = FRAGMENT(CHUNK_i, K, N, j)
>       End loop
>     End loop
> 
>     Return FRAGMENTS.
> 
> Note that a message will rely intact if and only if at least K

'rely'? You mean 'arrive'? 'remain'?

> Third, consider a different failure model. It's far more likely that
> packets are lost due to entire paths failing.  In this case, it makes
> sense to "stripe" each chunk over a set of paths, such that Packet 1
> from Chunk 1 goes along the same path as Packet 1 from Chunk 2, Packet
> 1 from Chunk 3, and so on.  Thus, if we choose N different paths, we

(more precisely, 'different' means disjoint)

> can reconstruct the message so long as at least K paths are
> functioning.  If we choose Q paths for Q<N, at least K*Q/N paths must
...
> THE DESIGN ITSELF

Bedtime for me. I'll read the meat of this tomorrow. :)

--Roger