fgrieu

10,722 reputation

1339

bio	website
	location	Paris, France
	age
visits	member for	1 year, 10 months
	seen	2 mins ago
stats	profile views	96

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

	10,722 reputation	bio	website		visits	member for	1 year, 10 months
1339 badges		location	Paris, France		seen	2 mins ago

summary answers questions tags badges favorites bounties reputation activity

674 Comments

suggestions reviews revisions comments badges posts accepts all

May 29	comment	How robust is discrete logarithm in $GF(2^n)$? There has been recent results that seem relevant to the question, including Göloğlu, Granger, McGuire, and Zumbrägel's Solving a $6120$-bit DLP on a Desktop Computer
May 28	comment	What security authorities and standards reject $e=3$ in RSA, when, and with what rationale? @Gilles: the question linked in your comment is less focused. It is also (and the answers are mainly) about RSA with small *private* exponent. This, in summary, is unsafe when used to a degree such that it offers a worthwhile speed advantage.
May 28	comment	What security authorities and standards reject $e=3$ in RSA, when, and with what rationale? On using $e=2$: I love Rabin schemes for their performance. But there's a very real practical issue: current lack of support in commercial security-evaluated devices (Smart Cards, HSMs) of even standardized schemes (ISO/IEC 9796-2 with $e=2$). Also the common description of this is one mistake/fault/weakness away from total disaster (messing up the Jacobi evaluation reveals the secret key, so does an attack on padding); and Jacobi evaluation (required for semantic security of encryption AFAIK, and also a concern when signing secret material) has its channel leakage hardly explored.
May 28	comment	What security authorities and standards reject $e=3$ in RSA, when, and with what rationale? Nice to see this voiced in no uncertain terms! That makes me even more willing to trust "full domain" padding schemes with $e=3$ (despite my current lack of understanding of the debate on theoretical hardness of the RSA problem for $e=3$ vs random $e$). But there's also the issue of implementations attacks. Perhaps $e=3$ makes side channel leakage in encryption more of a concern?
May 27	comment	What security authorities and standards reject $e=3$ in RSA, when, and with what rationale? @ratchet freak: your observation is correct, and can be extended to $e=3\implies p\equiv q\equiv 2\pmod 3$ for any good RSA key. That makes the key space slightly smaller. But there is no indication that it seriously weakens the key. One out of four RSA keys for $e=2^{16}+1$ have this property anyway.
May 27	comment	Why is verification using DSA slower than verification with RSA? For DSA, the order of magnitude seems right to me. But for RSA and $e=65537=2^{16}+1$, that's 16 squares and 1 multiplication $\bmod n$; not 4 squares and 2 multiplications.
May 27	comment	What security authorities and standards reject $e=3$ in RSA, when, and with what rationale? @Reid: I'll think about making the second part a separate answer/community wiki. But it is not a satisfactory answer, at least yet. I am afraid that I do not have a complete list of relevant attacks, and more generally reasons to avoid very low public exponents. In particular I did not touch hardness of the RSA problem for random argument w.r.t. low public exponent; and implementation attacks. And there are other standards and official recommendations.
May 25	comment	sir,please suggest me an algorithm or method how can i improve the prediction based encryption method using randomization? @pg1989: If homework from an English-speaking teacher mentions "prediction based encryption", run away.
May 22	comment	Increased CRC collision probability when adding bits to input message @jmbeck: I'm proposing to trade a little usable space in the V2 format against improved error-detection capability. E.g. if V1 messages are 12-bytes payload + 1-byte CRC, V2 could be 10-bytes payload + 2-byte CRC/EDC + (K xor (1-byte CRC of the 12 previous bytes)), for some non-zero byte K to be decided from the polynomial (K=0xFF is rarely disastrous). The receiver computes the 1-byte V1 CRC of the first 12 bytes and uses that to reject the message or determine its type as V1 or V2, and (for V2) further checks the additional 2-bytes EDC/CRC. The undetected error rate is almost as good as V1.
May 22	comment	Is the likelihood of a birthday collision linear (evenly distributed) for all ciphers? When are they not? Also: see this about principal versus principle.
May 22	comment	Is the likelihood of a birthday collision linear (evenly distributed) for all ciphers? When are they not? You need to improve the question. Ask yourself: Does bias in the distribution of birthdays make collisions more or less likely? Is "all PRFs evenly distributed in set E" a proposition? Is AES a PRF, a block cipher, or modelisable as a PRP? Is the output of a permutation biased, for random input?
May 21	comment	Do I need to keep a 64-bit version number secret? The proposal $Version_n \oplus Hash(iv_n)$ (notice the fix) is security by obscurity: security lies in the method, not a key. Hiding the key version, as well as including it in the HMAC, looks pointless to me. If its desirable for some reason to hide the key version, what about replacing $Version_n$ by $Version_n \oplus HMAC(HMAC(version \| iv \| ciphertext \| ..., key_{version_n}), longtermkey)$?
May 21	comment	Is Wikipedia's table about SHA-2 collisions correct? @Paŭlo Ebermann: What about a separate column for the best reduced-round attacks?
May 21	comment	Increased CRC collision probability when adding bits to input message @jmbeck: The summary would be: use the SAME polynomial, for defining the 1-byte field used as CRC for V1 and V2 (or multiple versions), with (in V2) a final XOR by an appropriate constant (or appropriate constants for more version), determined from the polynomial. Optionally, format the V2 (and up) messages as having an additional EDC (e.g. another CRC), inserted before the 1-byte CRC is computed.
May 18	comment	Alternatives to HMAC + CBC? @Luke: If the attacker does not have "direct access to the database" or an equivalent mean, why do you want to encipher each record, and protect their integrity with a keyed scheme? You may need authenticated and enciphered access to the database, and this is NOT the same as authenticating and enciphering each record.
May 18	comment	Alternatives to HMAC + CBC? Also, in the database context: while the confidentiality of each record is protected, the location of updated records is not. And the atomicity of the updates of multiple related records (e.g. update of accounts in a manner preserving the overall balance) is not protected.
May 18	comment	Alternatives to HMAC + CBC? Indeed, the scheme is solid at the record level. I second @Reid's comment: each record's integrity is protected, but the database's integrity is not. Adding an identifier of the record's location in the HMAC helps, by preventing moving records, but it still allows rolling back each record of the database to an earlier state. Even if we link the update of records in some way, the database as a whole can still be rolled back.
May 17	comment	What are the potential security impacts of using CRAM-MD5 for Emails, when not using an SSL connection? The summary of CRAM-MD5 protocol weaknesses on wikipedia is not bad.
May 17	comment	Help me describe/identify this challenge-response protocol/algorithm? @Cybergibbons: in a secure MAC with $k$ possible keys small enough that all keys are enumerable, and $o$ possible outputs, little more than $\lceil k/o\rceil$ examples are necessary to find the key. Here $k=256$ (after vector becomes public), $o=100000$, thus little more than one example is enough. In fairness, an adversary was not supposed to get the program that you reverse-engineered to extract vector; but even considering this, the algorithm is ridiculously weak, see 3a'
May 17	comment	Now that quantum computers have been out for a while, has RSA been cracked? I want to point as worthwhile this opinion and report on the recent events surrounding the D-Wave computer. Especially that part: "Matthias Troyer’s group spent a few months carefully studying the D-Wave problem—after which, they were able to write optimized simulated annealing code that solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine itself solves the D-Wave problem! "