Block cipher security - deterministic systems problem

From: John Eskie (cyberheg_at_l115.langkaer.dk)
Date: 10/06/03 

Date: Mon, 6 Oct 2003 15:58:51 +0200

I have a exercise which I'm having alot trouble with given my lack of
knowledge in university level math.
Hopefully someone here is kind enough to help me out or atleast point me
into the right direction.

We are given a note about pseudo random function families which is written
by my teacher. The exercise makes use of the knowledge given in section 4.
http://www.daimi.au.dk/~ivan/cryptosystems.ps

The exercise text is given as follows: 

---
This exercise is to study how the definition in section 4.1 of
pseudorandom function (or block cipher) security relates to
exhaustive key search. More precisely, we want to check that the
definition correctly captures the intuition that a block cipher
cannot be very secure if the adversary has enough computing time to
search through a large fraction of the possible keys. So consider a
block cipher with k bit keys and n bits blocks (and where of course
key generation just consists of choosing a random k-bit key). Let
time(m) be the computing time needed to do m encryption operations.
Consider the following adversary A:
A chooses at random T plaintext blocks M_1,..,M_T and submits them to
the encryption oracle. The oracle sends back blocks C_1,...,C_T.
A now chooses m different keys and computes for each key the encryptions
under this key of M_1,...,M_T. If a key is found where the encryption
results match C_1,...,C_T, then A outputs 1, else A outputs 0.
Clearly, A runs in time time(mT).
Show that the advantage of this adversary is at least m/2^k - m/2^(nT).
Draw a conclusion on the possible parameters (t,q,epsilon) for which
the block cipher can be (t,q,epsilon)-secure.
---
For the first question I understood that I must make use of the fact that:
ADV(A) = |p(A,0) - p(A,1)| which should give the result already given in the
text.
The question is about probabilities but I got no clue in which direction I
should think to come up with some formulas that can eventually be reduced to
the result given.
For the second part I still havn't understood how to calc the possible
parameters for (t,q,epsilon).
Lets say for DES you pick a part of the keyspace (2^56) 2^40 like done in
the note. If one DES encryption takes one cpu cycle (best case) the time t
will be 2^40. Then it says in the note that "Infact, if you ask q queries,
the probability of a collision in the ideal world will be aprox q^2 devided
by the number of blocks. So it will certainly not be more then 2^-20 in case
of DES for 2^20 quieries."
Can someone explain me those numbers?
The conclusion should be that for DES it's (2^40,2^20,2^-20) but I still
havn't found out how exactly to guess/calculate these numbers.
Another place in that section it says: "Even if we are optimistic on behalf
of the adversary, he will need atleast one CPU instruction per round of DES,
so in time 2^40, he can test at most 2^40/16=2^32 keys". 2^32 is probably
wrong but thats another case. 16 I assume is because of the number of rounds
of DES but I don't feel any smarter by learning this information. Can
someone explain me this?
Thanks in advance.
-- John

Relevant Pages

  • Re: DES decrpytion tools
    ... > I am looking for a shareware or freeware tool that uses standard DES ... You have to consider the mode of encryption too. ... DES is a block cipher ...
    (sci.crypt)
  • Block cipher and CBC based MAC using the same key / stream cipher based MAC
    ... what would be the security of the following scheme: ... -using the encryption block-cipher as block-cipher for the OMAC ... since I use the same block cipher for both tasks. ... to use the same block cipher for both encryption and integrity. ...
    (sci.crypt)
  • Re: Block cipher and CBC based MAC using the same key / stream cipher based MAC
    ... should use different keys for authentication and encryption. ... find this attack. ... encryption key and E_Kas your authentication key. ... provably secure, assuming that the block cipher is good, and if it isn't ...
    (sci.crypt)
  • Re: Random Ciphers
    ... general" block cipher. ... encryption function may be. ... The security can be transferred ...
    (sci.crypt)
  • Re: des iv
    ... However it (and any other block cipher) are ... normally used in one of the "modes" of encryption, CBC, CFB, OFB or CTR. ... All of these modes require an initialisation vector. ...
    (sci.crypt)