Niggling differential probability question.

From: Matt (cipher_q2000@yahoo.co.uk)
Date: 02/13/03 

From: cipher_q2000@yahoo.co.uk (Matt)
Date: 13 Feb 2003 03:30:47 -0800

Apologies for this somewhat trivial question...

In an early DC paper[1], Biham and Shamir give a formula for the
probability of a certain (xor) difference after modulo addition: let
the two inputs be X and Y, yielding Z = X + Y mod 256. Given two
differences in the inputs, X' and Y', and the output difference Z',
the probability that X' and Y' may cause Z' = X' xor Y' is "about":

 1 / (2 ** N(X' or Y')), where N(B) is the number of bits set to "1"
in the lower seven bits of B, "or" is bitwise or, and ** is
exponentiation.

This seems straightforward, but I don't understand why the word
"about" was used -- it seems that it should be "exactly", but I know
it's easy to overlook stuff in probability calculations. The paper
elaborates:

"This happens because each bit which is different in the pairs (X and
X*, Y and Y*) gives rise to a different carry with probability close
to 1/2",

Again, I don't know why it's "close to"; can someone put me out of my
misery?

Matt

[1] E. Biham and A. Shamir, "Differential Cryptanalysis of Feal and
N-Hash",
http://www.cs.technion.ac.il/~biham/Reports/Weizmann/cs91-17.ps.gz

Relevant Pages

  • Re: Niggling differential probability question.
    ... > Apologies for this somewhat trivial question... ... > In an early DC paper, Biham and Shamir give a formula for the ... > it's easy to overlook stuff in probability calculations. ...
    (sci.crypt)
  • Re: Pseudorandom Hashing
    ... to significantly reduce the probability of ... IIRC you XOR and feed back on the input, and just XOR on the output. ... Wescott Design Services ...
    (sci.electronics.design)
  • Re: Another Conditional Probability Question
    ... The first test correctly identifies blood ... type with probability .7, and the second test with probability .8. ... Normally, the statement "at least one of E, F" means exactly {E union ... Pr(E XOR F)? ...
    (sci.math)
  • Re: Another Conditional Probability Question
    ... The first test correctly identifies blood ... type with probability .7, and the second test with probability .8. ... Normally, the statement "at least one of E, F" means exactly {E union ... Pr(E XOR F)? ...
    (sci.math)
  • Re: Pls. help to count probabilities
    ... That mean that probability of their XOR to be equal to a chosen number ... How these probabilities change if A and B will be two distinct 32 ... be zero, from 1 in 2^32 to zero. ...
    (sci.math)
Quantcast