21,905 reputation
12991
bio website
location Paris, France
age
visits member for 3 years, 4 months
seen 2 mins ago

I'm an engineer with experience in applied cryptography, in particular in Smart Card systems.


Feb
27
comment Example of second preimage attack
The new GOST paper claims a " complexity of about $2^{225}$ evaluations of the compression function "; I suggest you ponder what that number means in term of time for the hardware you have. The MD4 paper allows a concrete implementation of a program that accepts any file matching some simple constraint on how it starts, and quickly spits a different file with the same MD4 hash, as verifiable with a reference MD4 implementation. With the first implementation strategy that I suggested, the program is dead simple. A file editor like HxD can even be used to perform the attack without coding.
Feb
27
comment Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known
@Ricky Demer: A solution for $p^5\bmod N=3$, $q^5\bmod N=3$, $N=6$ is $p=9$, $q=3$, leading to $m=27$. In this particular case, $m=9+18\cdot k$ for $k\in\mathbb Z$. Sorry for so many iterations of this comment before I finally remove much incorrect stuff about the general case, and fix that simple one.
Feb
26
comment Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known
I find this puzzle incredibly rich: some theoretical aspects of it are hard; and by changing the numerical values, we can vary the techniques required to solve it, and the difficulty. If the source of the puzzle is published, I want to read it!
Feb
26
comment RSA with small exponents?
That's very dangerous advice. Hastad's broadcast attack only applies when there is no random padding, and many other things can go wrong regardless of $e$ when no random padding (or worse no padding at all) is used in RSA encyption. On the contrary, in any application of RSA, if there is something (other than conformance to the diktat of some authority) to worry about with $e=3$, that's a strong indication that something other then $e$ needs to be seriously improved.
Feb
26
comment PRP, PRF and modular arithmetic
I do not understand " $2^{\ell}$ is a polynoimal of the security parameter", and that has nothing to do with the minor typo. The answer is still great.
Feb
26
comment PRP, PRF and modular arithmetic
Are you asking for an arithmetic function $(k,x)\mapsto F(k,x)$ such that, for some random unknown $k$, $x\mapsto F(k,x)$ would be computationally indistinguishable from a random permutation or function? That seems to be a good question with some useful characterization of arithmetic, which is missing. Ultimately, AES or SHA-1 can be written as a long composition of arithmetic functions, if you consider $(a,b)\mapsto a\bmod b$ to be arithmetic. Any interesting definitions of arithmetic that I can think of uses a threshold; like, at most some number of operators.
Feb
26
comment RSA public key security issue
Yes, every $d$ such as $e⋅d=k⋅φ(N)+1$ will be good private exponent. And there typically are others. If $N=p⋅q$ with $p$ and $q$ large distinct primes, one can use $\operatorname{lcm}(p-1,q-1)$ which is also $\lambda(N)$, and is smaller than $φ(N)$. That's what the de-facto-standard definition of RSA does. It allows smaller $d$, that often are slightly more efficient.
Feb
26
comment RSA public key security issue
No research effort whatsoever was made. Proper tagging is not enough!
Feb
26
comment RSA public key security issue
Writing nice formulas is easy: $d=e^{-1}\bmod\varphi(N)$ is just $d=e^{-1}\bmod\varphi(N)$; an important point is that this $d$ will be a working private exponent; however it is not guaranteed to be the private exponent; there are several equally fine private exponents.
Feb
25
comment Detecting steganography in the stream of short messages
If you control the PRNG assumed to be used by the third party, you seem to have a way to test if stego is used. The simplest: make the PRNG output all-zero, and any non-zero message that you then see can't be the output of that, thus was transformed in some way. It is even better to let the PRNG run normally, and check if the messages exactly match the PRNG. If not, that tells you there is a transformation. Now getting back at what the transformation is and what it conveys can't be done from the info we have.
Feb
25
comment Example of second preimage attack
The paper is a second-preimage attack with a restriction: it works for a fraction ($1/2^{56}$) of messages. If your are content with similar restriction to $1/2^{511}$ of messages, you can just use the example in table 2: for any $X$, a second-preimage of $M||X$ (resp. $M'||X$) is $M'||X$ (resp. $M||X$). For the full attack, you choose you own first block $\widehat{M_0}$, follow what the paper prescribes to get $\widehat M$ and $\widehat{M'}$, then proceed as I explained before. Tell us what part of what the paper prescribes you have issue with, that might help re-open the question.
Feb
25
comment Detecting steganography in the stream of short messages
@Moonwalker: there is a chance that the basis of your "There is a probability that PRNG of the carrier is not cryptographically secure" could help us propose a way to break the PRNG, potentially making your goal feasible. Lacking that basis (and as much info as feasible even remotely linked to that), no progress is possible.
Feb
25
comment What RC4 key value will completely invert $S$ after initial permutation?
I'll only give hints on this apparent homework. A) If you could achieve your goal with a key of k bytes, with what other key lengths and keys could you achieve the same goal? Now choose a k that you won't regret. B) Each round swaps S[i] and S[j]; what latitude do you have on deciding indexes i and j? C) Pick and place according to your target S[], whatever that is.
Feb
25
comment How to generate initial vectors during DPA attack on stream cipher in real life?
One possibility would be to obtain some legitimate devices with known test keys (or known test master keys used to set device keys), by social engineering on the tune of that will open a huge market in (remote location).
Feb
25
comment Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known
Something could emerge from the values. In particular, if we can factor $N$; or if $(p^5\bmod N)+a\cdot N$ and $(q^5\bmod N)+b\cdot N$ are fifth powers for some guessable $a$ and $b$. Also: either there is no solution, or there an infinity, for $m+i\cdot p\cdot N+j\cdot q\cdot N$ is also a solution when $m$ is; so, at least implicitly, we want the smallest nonnegative $m$, which perhaps the context suggests.
Feb
25
comment Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known
Do we happen to know anything else? Like, $0\le m<N$? Or some numerical values? Or/and perhaps $m^e\bmod N$ for some known $e$, that is the naked-RSA encryption of $m$ under public key $(N,e)$?
Feb
24
comment Get permutations from password
This way of going from password to key is suboptimal, in particular makes it easier than necessary to deduce the whole permutation from part of it by enumerating likely passwords. A better solution uses key stretching.
Feb
24
comment Get permutations from password
I find the new algorithm easier to grasp and prove: we start from one of the $(i-1)!$ permutations of $i-1$ elements $j\mapsto F(j)$ for $0\le j<i-1$; and a $t$ with $0\le t<i$. Then make a new function of $i$ elements defined by: $G(j)=F(j)$ for $0\le j<i-1$ with $j\ne t$; $G(t)=i-1$; $G(i-1)=t$. Each $(F,t)$ yields a distinct permutation $G$. Proof that we reach each of the $n!$ permutations of $n$ elements when $0\le x<n!$ follows by induction. You made a good point by noticing that a slow PBKDF only slows precomputation, unless there's a previously unknown salt.
Feb
24
comment Get permutations from password
What about replacing the first three loops (including one nested) with for i := 1 to n do begin t := x mod i; x := x div i; y[i-1] = i-1; y[i-1] = y[t]; y[t] = i-1; end; ? Also: a slow PBKDF is a must to make it hard to find the whole permutation from the image of a few elements (like half as much as there are letters in the password, for a typical choice of password).
Feb
24
comment How has the “power” of cryptography evolved from its beginnings till today?
Remove times earlier than the 1980s (or earlier if you include non-public state-of-the-art) and the question is no longer arguably too broad; and answer is: so far ahead that it became immaterial. The designers of DES knew what it takes to make a practically unbreakable block cipher (DES's key and even block size is only a compromise, with authorities and performance). I like the observation that side-channel attacks include rubber-hose cryptanalysis.