21,915 reputation
12991
bio website
location Paris, France
age
visits member for 3 years, 4 months
seen 10 hours ago

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


Nov
14
comment How can CBC-MAC be secure when message length is fixed?
The title of the question looks wrong to me; nearest logical substitute: How can CBC-MAC be secure only when message length is fixed?
Nov
13
comment Strange MAC algorithm
Somewhat related to this question. $\;$ Independently: knowing MD5(k||m) allows computing MD5(k||m||m'||m") for m' a certain known function of m and the length of k (with m' at least 9 bytes or 65 bits), and freely chosen m".
Nov
13
comment AES with weak keys
Yes. An easy statistical calculation shows that if for $j$ increasing from $0$ to $13$ we try the $128!/(128-j)!/j!$ keys with $j$ zero bits and $128-j$ one bits (using encryption of some known plaintext), we'll find a key with odds about $59.6\%$, and less than $2^{57.8}$ AES encryptions. With $j$ up to $8$, our chances to find a key are still a fair $9.7\%$, with effort less than $2^{40.5}$ encryptions. With $j$ up to $5$, $0.93\%$, with effort less than $2^{28.1}$.
Nov
12
comment Permutation parity after cycle-walking
@poncho: You are absolutely right! I misinterpreted the argument given in that answer into the (incorrect): any reversible transformation leaving at least 1 bit of the state unchanged is even. What's correct is: any transformation leaving at least 1 bit of the state unchanged and without influence on the other bits is even.
Nov
12
comment Permutation parity after cycle-walking
@poncho: I think you mean addition of a key as wide as the state, which does give balanced parity. Replacing XOR with modular addition in the combination of the round function output and half state does not.
Nov
11
comment How to perform frequency analysis of a substitution cipher using a Base64 alphabet
[Revised] Hint: How many letters, when present as first (resp. third, fourth, sixth) position of the plaintext generate a U (resp. O R S) in first (resp. fourth, fifth, eighth) position of the Base64? How does the expected frequency of letters in plaintext translate to expect frequency in first, fourth.. (resp third, sixth..) letter of the Base64? What about digrams in third and fourth, sixth and seventh.. position in plaintext and relation to digrams in fourth and fiveth, eighth and nineth.. position in the Base64?
Nov
11
comment How to perform frequency analysis of a substitution cipher using a Base64 alphabet
Note: UlVORk9SWU9VUkxJRkU= can't lead to k9U9VUJx=RWUOSkVUklR by character substitution. For example, the four U in the original are substituted with the different k, R, Oand l.
Nov
11
comment How big an RSA key is considered secure today?
@j.p. My article is about academic factorization records, and predates the article that you quote, which AFAIK did not lead to actual and public implementations. But yes, I will mention it.
Nov
11
comment How big an RSA key is considered secure today?
@Lembik: the curve would grow faster than linear (but, at least in the 2000 region, slower than what I show).
Nov
10
comment Are modified implementations of cryptographic algorithms a good idea?
Example: an apparently harmless modification of RC4 (that reportedly was used by a US government agency, most likely unknowingly), turns out to have a serious weakness that's not in the original.
Nov
7
comment Which attacks are possible against raw/textbook RSA?
Vast subject! Do you plan to answer your own question, or do you want others to dive in?
Nov
7
comment Franklin-Reiter related message attack m2 = a(m1)+b
Hint: if $v\in\mathbb Z$ with $\gcd(v,N)=1$, then $\exists w\in\mathbb Z, v\cdot w\equiv1\pmod N$. Such a $w$ can be efficiently found using (a slight variant of) the Extended Euclidian algorithm. That allows proper definition of $1/v$, then $u/v$, in $\mathbb Z_N$.
Nov
6
comment What is the most computationally efficient way of generating pseudo-random permutations?
@user44353: I concur with this comment, that 6 rounds of Feistel each one round of AES (implementable using AES-NI) in the round function, can be next to cryptographically secure (except for parity) for $18\le n\le 32$ as in the original question (but the devil lies in the details). Lower $n$ requires more rounds, (will think about how many). I don't know when cryptographic insecurity becomes a problem in your application, or what $n$ you need with your current round function (fair, but significantly lesser than an AES round).
Nov
6
comment What is the most computationally efficient way of generating pseudo-random permutations?
@user44353: I was only pointing the trivial: you must avoid that (((char)n_cipher)&0x7f)^key_aux[1] gets out of the range where the SBox entries are defined. That's either by filling all 256 entries or by limiting key_aux[1] to 7-bit. Which method is used is immaterial to the quality of each permutation, but the first option (your current one) widens the number of possible permutations (which is desirable) compared to 7-bit key_aux[1].
Nov
6
comment What is the most computationally efficient way of generating pseudo-random permutations?
@user44353: So currently $n=13=6+7$, and in effect the S-boxes have 7-bit of data-dependent input, and 6-bit output. Provided implementation details are correct (all 256 S-box entries are populated or key_aux[1] is 7-bit; unused high 2 bits in S-box outputs are zero..), to me it looks like this implements a permutation, and would be a fine asymmetric Feistel Cipher IF there was significantly more rounds. With 4 rounds, unless I err, the lowest bit of input gets only one chance to change, at the third round, which is a serious cryptographic gap (but may be quite bearable in the context).
Nov
6
comment What is the most computationally efficient way of generating pseudo-random permutations?
Given the maximum number of iterations and the (unspecified) distribution of the K entries queried at each iteration, what is a rough proportion of entries of each permutation that will be queried at least once? That matters to the quality of the technique you need to use. $\;$ Are you after speed to the point that you would consider use of AES-NI instructions or intrinsics?
Nov
6
comment Brute Force AES Calculations
Efficient implementations of AES on modern CPUs increasingly use hardware extensions such as AES NI, available on many Intel and AMD CPUs. A typical performance quote would be bulk encryption at 1.3 cycle/byte, per core (0.6G AES/s on a 3.2GHz 4-core CPU). That's for very repetitive use of a fixed key, which does not match brute force key search so well, but I have no better number or source in mind.
Nov
5
comment AES mix column stage
Code Golf style, the C formula for $2\otimes x$ can be shortened to x<<1^283&-(x>>7); adding decoration, that is (x<<1) ^ (0x11b & (0x200-(x>>7))). It has the real benefit of being constant-time, when the ? operator is often not
Nov
5
comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$
Common wisdom (see this) seems to be that all known factoring algorithms are no more efficient than GNFS at factoring a 2048-bit $pq$ with $p$ and $q$ mostly random primes with a 680-bit difference in size; we would be conservative with 512. AFAIK, among subexponential algorithms, only Lenstra's ECM really takes advantage of the imbalance, but if it is not, and can't be, made faster by the special form implied by $\gcd(pq, (p-1)(q-1))\ne 1$, we seem to be safe from ECM.
Nov
5
comment Is a die implemented in a physics engine truly random?
Dices are truly random in the real world, but are not fair, and that's a fact accessible to experience (with patience or a simple robot + computer vision). It is not hopeless to show that the holes traditionally made in an otherwise symmetrical dice to mark the values create an imbalance with a practical effect, IMHO making 1 slightly more likely than 6 (a physics engine could help show that, turning the question around).