21,585 reputation
12990
bio website
location Paris, France
age
visits member for 3 years, 3 months
seen 10 hours ago

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


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 RSA-Like encryption for embedded systems
The formulas for decryption in phase 1 DO work [contrary to my initial incorrect assessment]; they are like usual RSA-CRT in an unusual and less efficient (but nicely symmetric) way, given without justification. $\;$ In phase 2, it is used $p$ and $q$ for encryption, which does not make sense (hint: in about any use case where it makes sense, symmetric crypto can be used). Worse, Section 3 does not hint at that! $\;$ Also, I see no discernible reason for the note in the left bubble.
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).
Nov
5
comment NIST implementation of the Lucas primality test
On these things FIPS 186-4 is inspired by ANSI X9.31. Therefore, I hope that Carl Pomerance, J.L. Selfridge and Samuel S. Wagstaff, Jr.'s The Pseudoprimes to $25\cdot10^9$ (in Mathematics of Computation, Volume 35, Number 151, July 1980, pages 1003-1026); and Robert Baillie and Samuel S. Wagstaff, Jr.'s Lucas Pseudoprimes (in Mathematics of Computation, Volume 35, Number 152, October 1980, pages 1391-1417) can help; they describe and give the list of pseudoprimes of the test ANSI X9.31 wanted.
Nov
5
comment RC4 encryption/ decryption with hashing
the attack rebuilds RC4's keystream generator output over the length of M+H, then process M'+H' where H' is the hash of M'. Truly truncating M'is thus feasible. Your idea of building a compressed M' with uncompressed meaning bigger than that of M is the best option in the other direction.
Nov
4
comment Why to try get key out of white box crypto? How can one protect WBC itself?
Yes. One possible motivation for WBC was to make different White Boxes embedding an identifier, behaving the same for many inputs, otherwise leaking the identifier (when input or output has a key and/or identifier-dependent characteristic). If such a White Box is cloned, and it is possible to interrogate clones, it is possible to determine which White Box was cloned. For pay TV, the White Box could be a Smart Card, and the manufacturer of the Smart Card reasonably held liable for the huge damage to the TV networks. Rather, Smart Cards became excellent Black Boxes.
Nov
4
comment RC4 encryption/ decryption with hashing
not aligned with best practices is an understatement! H is apparently here in an attempt to authenticate the message; but it does not if M is predictable by the attacker (known plaintext): it is trivial to forge a cryptogram deciphering to any apparently authentic message M' an attacker may wish, with the restriction that M' is no longer than M.
Nov
4
comment Timing Attack on OpenSSL by Brumley
Welcome to Crypto.se! Notice how easy it is to use $\TeX$ for formulas (just edit your question to see how it is done).
Nov
3
comment Showing that $2^{N-1}\equiv1\pmod N$ when $N=2^p-1$ for prime $p$
We are left wondering why the statement restricts to odd $p$, since this fine proof applies to $p=2$ just as well. $\;$ I'm raised on writing $(2^p)^k\equiv 1^k\equiv 1\pmod N$ using \pmod, or $(2^p)^k\bmod N=1$ using \bmod.
Nov
3
comment Is XCBC where k2 and k3 might be the identical, secure?
I guess the referenced paper is John Black and Phillip Rogaway's CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions (in proceedings of Crypto 2000, or 2003 version). $\;$ If we draw key randomly, the system is secure, because keys 2 and 3 are identical with infinitesimal odds. I think a more practically interesting question is: Is the system secure if we derive two keys K1 and K2 randomly, and set K3=K2.
Nov
3
comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$
Ah yes I now see the idea. So we need an even $k$ with a large prime factor. And we are left wondering if that's good enough.
Nov
3
comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$
Thinking about it again, $q-1$ is bound to have a high prime factor (that's $p$); is not that sufficient to guard against Pollard's $p−1$ algorithm on the $q$ side, even if $k$ is smooth?