Re: [Cfrg] AES-based PRF - comment please

[David Hopwood <david.hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

David Wagner wrote:
> Uri Blumenthal  wrote:
> >Ran Canetti wrote:
> >> If the key is either not secret or not random then all bets are
> >> off - no security whatsoever is guaranteed.
> >
> >I thought that the "degree" of non-randomness - i.e. fixing only
> >a certain part of the key - reduced the workload of adversary,
> >i.e. lowered the security guarantees ("resistance"), but didn't
> >invalidate the whole thing?
> 
> No.  Ran is right.
> 
> If you fix a few bits of the key to a PRP, all bets are off
> (unless you make extra assumptions beyond just that it's a PRP).

In general, if you fix k bits then the bound on the success probability of
an attack is degraded by a factor of 2^k. (This is not the same as reducing
the workload.)

The intuition behind this is that there is a 2^-k probability of an
attacker who assumes that the k bits are fixed, having that assumption
satisfied by chance for the unmodified PRP. Therefore the success probability
cannot be multiplied by more than 2^k. Actually the same argument applies for
any keyed algorithm.

Of course for sufficiently large k, this is effectively the same thing as
"all bets are off". For k < 8, say, it is probably harmless. Anyway, this
argument does not in any way justify using non-secret or non-random keys,
unless you know that they are only "slightly" non-random.

- -- 
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPn7g7jkCAxeYt5gVAQGqZgf9ElXjonj0y6hg1bNDEHb2umymUZXc8yub
PCTXglr0TjZC6GvgCzalwnOLtZ0wTEC5mtYkAiXpj/GMHnOkkaV7z7WlIiiG2JDc
jVHT1/MHZMBXf9mojJzri+ujNMpm1o3lz/S/Vxd+VWPHbqM3K8Wuhw00QtDdS8Q4
KNjTElXcdINKbJGeGqvaLqc1fr0rzXkQEK0R/FtZQK81Q4RLO+0Otc64LzCEshmI
6sAHdro6V3wc/gx8mRia8vKSnTxF+0abJ8QS0Hs5TMVYdTeZLe7Qz6e1wkvVG3aH
Hq9LkKw6pYDLy3oxk9TSj9q3sQil+bRFPw21YdfeRYq51cv1Q1MiXA==
=Yzfn
-----END PGP SIGNATURE-----
_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg