### Re: the meaning of linearity, was Re: picking a hash function to be encrypted

```
On 5/17/06, Kuehn, Ulrich [EMAIL PROTECTED] wrote:

Given known plaintext and corresponding ciphertext, there should not be too
many keys that map the plaintext to the ciphertext. I don't have the
probability at hand how many such 'collisions' you would expect from 256 random
permutations, but intuitively I would not expect too many. However, I could be
wrong here and would like to be corrected in this case.

I'm a little rusty but I'll give it a shot.

Well we have a byte x and a mapping f_k(x) = y, with f selected at
random (for now I'll assume with replacement since 256  256!) from
the set of all permutations, x and y from 0..255.  The questions is
what fraction of permutations have f_k(x) = y, I think the answer is
1/256.  There's 255 other permutations, so the chance that there is
at least one k' such that f_k'(x)=y is 255/256 = 99.6%.  The chance
that there is exactly one such k' is sampling with replacement and if
I am not mistaken P(|K|=1) = (255/256)^255 = 0.36.  Along those same
lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks
like the expected number of equivocating keys is very small.

I suspect that's why Terry Ritter's Dynamic Substitution algorithms,
which are meant to replace XOR combiner in stream ciphers, maintain
state.
--
Curiousity killed the cat, but for a while I was a suspect -- Steven Wright
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: the meaning of linearity, was Re: picking a hash function to be encrypted

```
On 5/18/06, Travis H. [EMAIL PROTECTED] wrote:

... There's 255 other permutations, so the chance that there is
at least one k' such that f_k'(x)=y is 255/256 = 99.6%.  The chance
that there is exactly one such k' is sampling with replacement and if
I am not mistaken P(|K|=1) = (255/256)^255 = 0.36.  Along those same
lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks
like the expected number of equivocating keys is very small.

Oops, I left off a term in the recurrence.
P(|K|=2) = (255/256)^253 * ((254*255)/2)/(256^2) = 0.18

So the expected number of equivocating keys, given one byte of known
plaintext, is a bit under two.
--
Curiousity killed the cat, but for a while I was a suspect -- Steven Wright
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```Travis H. [EMAIL PROTECTED] writes:

On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote:
Security is fragile. Deviating from well understood primitives may be
good research, but is not good engineering. Especially fragile are:

Point taken.  This is not for a production system, it's a research thing.

TLS (available via OpenSSL) provides integrity and authentication, any
reason to re-invent the wheel? It took multiple iterations of design
improvements to get TLS right, even though it was designed by experts.

IIUC, protocol design _should_ be easy, you just perform some
finite-state analysis and verify that, assuming your primitives are
ideal, no protocol-level operations break it.  The 7th Usenix Security
Symposium has a paper where the authors built up SSL 3.0 to find out
what attack each datum was meant to prevent.  They used mur-phi, which
has been used for VLSI verification (i.e. large numbers of states).
ATT published some code to do it too (called SPIN).  It's effective
if the set of attacks you're protecting against is finite and
enumerable (for protocol design, I think it should be; reflection,
replay, reorder, suppress, inject, etc.).  I wouldn't consider
fielding a protocol design without sanity-checking it using such a
tool.  Was there an attack against TLS which got past FSA, or did the

There have been a number of attacks on TLS since Mitchell et al's
paper was published in 1998. The most well known are the attacks
on CBC mode described in http://www.openssl.org/~bodo/tls-cbc.txt.

-Ekr

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### RE: the meaning of linearity, was Re: picking a hash function to be encrypted

```
-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]

The thing I've always wondered about stream ciphers is why we only
talk about linear ones.  A stream cipher is fundamentally constructed
of two things:  A stream of bits (alleged to be unpredictable) as
long as the plaintext; and a combining function that takes one
plaintext bit and one stream bit and produces a ciphertext bit.
The combining function has to conserve information.  If you only
combine single bits, there are only two possible functions:  XOR
and the complement of XOR.  But consider RC4:  It actually generates
a byte at a time.  We just choose to use that byte as a vector of
8 bits.  For plaintexts that are multiples of 8 bits long - just
about everything these days - there are many possible combining
functions.  Most aren't even close to linear.

I am not sure this will add to the security of the whole thing. My reasoning
behind that is:

The combining function needs to be invertible (we want to recover the
plaintext, don't we?), so we have an 8-bit block cipher with an 8-bit key
(supplied by the key stream generator).

Given known plaintext and corresponding ciphertext, there should not be too
many keys that map the plaintext to the ciphertext. I don't have the
probability at hand how many such 'collisions' you would expect from 256 random
permutations, but intuitively I would not expect too many. However, I could be
wrong here and would like to be corrected in this case.

Regards,
Ulrich

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```* Travis H.:

IIUC, protocol design _should_ be easy, you just perform some
finite-state analysis and verify that, assuming your primitives are
ideal, no protocol-level operations break it.

Is this still true if you don't know your actual requirements?

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: the meaning of linearity, was Re: picking a hash function to be encrypted

```|  - Stream ciphers (additive)
|
| This reminds me, when people talk about linearity with regard to a
| function, for example CRCs, exactly what sense of the word do they
| mean?  I can understand f(x) = ax + b being linear, but how exactly
| does XOR get involved, and are there +-linear functions and xor-linear
| functions?  Are they disjoint?  etc.
XOR is the same as addition mod 2.  The integers mod 2 form a field
with XOR as the addition operation and integer multiplication (mod 2,
though that has no effect in this case) as the multiplication.

If you think of a stream of n bits as a member of the vector space
of dimension n over the integers mod 2 treated as a field, then
adding two of these - the fundamental linear operation - is XOR'ing
them bit by bit.

The thing I've always wondered about stream ciphers is why we only
talk about linear ones.  A stream cipher is fundamentally constructed
of two things:  A stream of bits (alleged to be unpredictable) as
long as the plaintext; and a combining function that takes one
plaintext bit and one stream bit and produces a ciphertext bit.
The combining function has to conserve information.  If you only
combine single bits, there are only two possible functions:  XOR
and the complement of XOR.  But consider RC4:  It actually generates
a byte at a time.  We just choose to use that byte as a vector of
8 bits.  For plaintexts that are multiples of 8 bits long - just
about everything these days - there are many possible combining
functions.  Most aren't even close to linear.

Other than post by a guy - Terry someone or another - on sci.crypt
a number of years ago - I've never seen any work in this direction.
Is there stuff I'm not aware of?
-- Jerry

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: the meaning of linearity, was Re: picking a hash function to be encrypted

```
On 5/15/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:

Other than post by a guy - Terry someone or another - on sci.crypt
a number of years ago - I've never seen any work in this direction.
Is there stuff I'm not aware of?

That would probably be Terry Ritter, www.ciphersbyritter.com.

He calls this function Dynamic Substitution:
http://www.ciphersbyritter.com/#DynSubTech

You could also probably use a Latin square:
http://www.ciphersbyritter.com/#BBMTech
--
Curiousity killed the cat, but for a while I was a suspect -- Steven Wright
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```Travis H. writes:
Excellent point.  When I wrote that I had strongly universal hashes in
mind, like UMAC, where the hash is chosen from a family of functions
based on some secret data shared by sender and recipient.  I
mistakenly conflated them with ordinary hashes (which they are, once
you pick one).  Thanks for catching that.

A point of terminology, strong universal hash functions are different
than what you are probably thinking of.

UMAC is a MAC, not a SU hash function.  It uses an almost-SU hash function
in its construction, but that's different.

Universal hashes and their variants (see
http://www.cacr.math.uwaterloo.ca/~dstinson/universalhashingdefinitions.html
for a bibliography) are actually *weaker* than conventional hashes.
They can, in fact, be completely linear.  While you are right that the
hash is typically part of a parameterized family, once you pick one you
do not get an ordinary hash.  You are more likely to get an ordinary
polynomial that will not serve at all well as a crypto hash.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: the meaning of linearity, was Re: picking a hash function to be encrypted

```
Travis H. wrote:

This reminds me, when people talk about linearity with regard to a
function, for example CRCs, exactly what sense of the word do they
mean?  I can understand f(x) = ax + b being linear, but how exactly
does XOR get involved, and are there +-linear functions and xor-linear
functions?  Are they disjoint?  etc.

If you have a linear algebra book handy, look up linear transformation.

Briefly, a function T from a vector space V to another vector space W
(where V and W are defined over the same field) is called a

linear transformation if it satisfies

i) T(u +_V v) = T(u) +_W T(v)
ii) T(c *_V u) = c *_V T(u)
iii) T(0_V) = 0_W

CRC is a linear transformation because

CRC(u + v) = CRC(u)+CRC(v).

-James

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```On Sun, May 14, 2006 at 03:04:41AM -0500, Travis H. wrote:

Suppose I want a function to provide integrity and authentication, and
that is to be combined with a stream cipher (as is the plaintext).  I
believe that authentication is free once I have integrity given the
fact that the hash value is superencrypted using the stream cipher,
whose key is shared by only the sender and recipient.  I believe what
I'm looking for is a strongly universal hash.  I don't need much;
everything I've seen is simultaneously too much and too little, often
calling upon a block cipher, which seems redundant.

What I was thinking of doing was using Poly1305, and using the stream
cipher instead of AES.  I think in this case that I can leave the MAC
exposed, since it's a MAC and not a hash.  Is there an analogous, hash
function that does not use encryption internally?

Security is fragile. Deviating from well understood primitives may be
good research, but is not good engineering. Especially fragile are:

- Non-mainstream ciphers (often broken once someone good bothers to try)
- RC4 (poor key schedule)
- RSA (multiplicative)

The first is to be avoided entirely, the second and third should be
used only under duress, when block ciphers are a very poor fit for the
application. RSA needs to be used only in very specific ways (PKCS 2.1,
for example) that avoid the common pitfalls.

TLS (available via OpenSSL) provides integrity and authentication, any
reason to re-invent the wheel? It took multiple iterations of design
improvements to get TLS right, even though it was designed by experts.

--

/\ ASCII RIBBON  NOTICE: If received in error,
\ / CAMPAIGN Victor Duchovni  please destroy and notify
X AGAINST   IT Security, sender. Sender does not waive
/ \ HTML MAILMorgan Stanley   confidentiality or privilege,
and use is prohibited.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```
On 5/14/06, Eric Rescorla [EMAIL PROTECTED] wrote:

Consider the case where you're transmitting message M. The
hash is H(M). You then encrypt (M || H(M)), generating
K XOR (M || H(M)). If the attacker knows M and H, he can
compute (M || H(M)) and compute K. Then he can re-encrypt
a message M' of his choice.

Excellent point.  When I wrote that I had strongly universal hashes in
mind, like UMAC, where the hash is chosen from a family of functions
based on some secret data shared by sender and recipient.  I
mistakenly conflated them with ordinary hashes (which they are, once
you pick one).  Thanks for catching that.

IMHO encrypting MACs is a good defensive measure, because you can then
use a smaller hash value, so you end up encrypting as little as 4
bytes instead of transmitting 20 en clair, and now you also know the
opponent hasn't learned anything.

Does anyone know if MAC-then-encrypt(plaintext) versus
encrypt(plaintext)-then-MAC makes a difference if the MAC itself is to
be encrypted?  I can't think of why it would.
--
Curiousity killed the cat, but for a while I was a suspect -- Steven Wright
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```
On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote:

Security is fragile. Deviating from well understood primitives may be
good research, but is not good engineering. Especially fragile are:

Point taken.  This is not for a production system, it's a research thing.

TLS (available via OpenSSL) provides integrity and authentication, any
reason to re-invent the wheel? It took multiple iterations of design
improvements to get TLS right, even though it was designed by experts.

IIUC, protocol design _should_ be easy, you just perform some
finite-state analysis and verify that, assuming your primitives are
ideal, no protocol-level operations break it.  The 7th Usenix Security
Symposium has a paper where the authors built up SSL 3.0 to find out
what attack each datum was meant to prevent.  They used mur-phi, which
has been used for VLSI verification (i.e. large numbers of states).
ATT published some code to do it too (called SPIN).  It's effective
if the set of attacks you're protecting against is finite and
enumerable (for protocol design, I think it should be; reflection,
replay, reorder, suppress, inject, etc.).  I wouldn't consider
fielding a protocol design without sanity-checking it using such a
tool.  Was there an attack against TLS which got past FSA, or did the
--
Curiousity killed the cat, but for a while I was a suspect -- Steven Wright
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### the meaning of linearity, was Re: picking a hash function to be encrypted

```

This reminds me, when people talk about linearity with regard to a
function, for example CRCs, exactly what sense of the word do they
mean?  I can understand f(x) = ax + b being linear, but how exactly
does XOR get involved, and are there +-linear functions and xor-linear
functions?  Are they disjoint?  etc.
--
Curiousity killed the cat, but for a while I was a suspect -- Steven Wright
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: picking a hash function to be encrypted

```On Sun, May 14, 2006 at 07:56:17PM -0500, Travis H. wrote:

On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote:
Security is fragile. Deviating from well understood primitives may be
good research, but is not good engineering. Especially fragile are:

Point taken.  This is not for a production system, it's a research thing.

TLS (available via OpenSSL) provides integrity and authentication, any
reason to re-invent the wheel? It took multiple iterations of design
improvements to get TLS right, even though it was designed by experts.

IIUC, protocol design _should_ be easy

Once upon a time, everyone agreed that cipher design was hard.  Later
people discovered that protocol design is hard too.  More recently
people are discovering that given solid ciphers and protocols, secure
implementations are still hard... I could be wrong, but it does not
seem that the trend is towards increasingly easy security, in the
sense that anyone who learns a programming language reasonably well can
develop security toolkits. :-(

--

/\ ASCII RIBBON  NOTICE: If received in error,
\ / CAMPAIGN Victor Duchovni  please destroy and notify
X AGAINST   IT Security, sender. Sender does not waive
/ \ HTML MAILMorgan Stanley   confidentiality or privilege,
and use is prohibited.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```