Reputation
26,609
Next tag badge:
419/400 score
79/80 answers
Badges
2 37 113
Newest
 Nice Answer
Impact
~412k people reached

Jun
15
comment How to quickly detect incorrect password in encrypted file without compromising security?
I think that is valid only if " long, random passwords" is really long and random enough to be a key not needing stretching; e.g. has 22 letters randomly chosen among 0…9A…Za…z, giving next to 131 bits of entropy. I fear this solution (perhaps any) seriously cuts corners on security for anything a human can be expected to memorize, or routinely key-in.
Jun
15
comment Is there a scheme that allows to use RSA based challenge response protocol limited to signing only 8 bytes to create a secure signature of any data?
@Ricky Demer: if $K$ is predictable, the schemes becomes brittle, especially if $P$ is not purposely slow. In particular the adversary can (with effort about $2^{62}$ evaluations of $P$) find $m$ such that $P(K,m)$ for the predicted next $K$ has an $x_i$ of the adversary's choice, and make an existential forgery with about $2^{64}$ evaluations of $P$ and 4 queries to the broken signer with predictable $K$.
Jun
11
comment How are primes generated for RSA?
@mikeaso: I doubt that the bias that I describe can lead to any security problem. That could be a certification issue, however; knowing a moderate number of RSA private keys, this bias is computationally detectable from the distribution of the number of consecutive composites below the primes forming the factors of the moduli.
Jun
11
comment How to prove the hardness of Rabin's function?
Hint: choose a random $r$ with $0<r<n$, apply the hypothetic square root finding method to $r^2\bmod n$
Jun
11
comment Can a combination of encryption algorithms weaken the overall encryption?
@Nova: here's an counterexample: the first algorithm is GPG with the common option of plaintext compression before encryption, and the second is AES-CTR with random IV; the ciphertext for a 1MB text document will be recognizable from the ciphertext for a 1MB mp3 file (the former will be much smaller than the later), which is at least a theoretical weakness; when the second algorithm alone does not exhibit this leak. Other counterexamples are possible if we consider timing or side-channel attacks on the first algorithm.
Jun
11
comment How are primes generated for RSA?
The algorithm (as it stands now) generates primes with significantly biased distribution: primes with a long gap of composites just below them are significantly more likely than other primes. It is common to first choose a moderately large random secret $s$ and replace $p=p+2$ in step 3 by $p=p+2s$. It is enough that $s\approx\log_2(p)$ to mostly avoid that bias. In practice, $s$ is often the product of two much larger secret auxiliary prime $p_1$ and $p_2$ chosen such that we'll end with $p\equiv1\pmod{p_1}$ and $p\equiv-1\pmod{p_2}$.
Jun
11
comment Rationale for use of right-shift (rather than rotate) in SHA-2?
@Richie Frame: Indeed, the message schedule of SHA-1 is linear:$$W_t=\operatorname{ROTR}^{31}(W_{t-3}\boxplus W_{t-8}\boxplus W_{t-14}\boxplus W_{t-16})\;\text{ for }16\le t\le79$$and further a rotation in input translates to a corresponding rotation of output. Neither weakness holds for the message schedule of SHA-2, including modified to use only $\operatorname{ROTR}$. Still, reducing odds of the second property might be the motivation I'm asking for. $\;$ I guess that should be turned into an answer.
Jun
10
comment Rationale for use of right-shift (rather than rotate) in SHA-2?
@LightBit: that applies to a linear transformation. In SHA-2, the key schedule is not linear, thanks to the alternation of ⊕ in the σ functions, and ⊞ in the message schedule. Thus I do not think that the reasoning applies, at least to a comparable degree. Something on that tune would indeed apply if we changed ⊞ to ⊕, so perhaps the desire to better guard against an approximation of ⊞ by ⊕ may have been in the mind of the designers. $\;$ Thanks for the contribution!
Jun
10
comment Residue requirements of Rabin-Williams primes?
In " minimum requirements " and " I'm not sure it's forbidden ", the crucial point is: required/forbidden BY WHAT? A standard? A particular implementation (or definition) of RW? The feasibility of a working implementation (or definition) of RW using $p\;q$ as the public modulus?
Jun
5
comment What's the inverse function of this decryption function?
For the very reason outlined in the question, it is not possible to make en encryption function accepting any arbitrary input (in particular with bytes in the 0x54 to 0x5B range, that is TUVWXYZ[ in ASCII) and such that the supplied decryption function will output the original plaintext.
Jun
5
comment Is the one-time-pad a secure system according to modern definitions?
@Bardi Hardborow: chacha20 as used e.g. in Chrome is a stream cipher (which keystream generator is generated by a CSPRNG, which is a PRF applied to a counter and a key); it is not an OTP, which keystream is true random, rather than derived from a key.
Jun
5
comment How do we know a cryptographic primitive won't fail suddenly?
" There is only a single cryptographic algorithm that is mathematically proven secure: the one-time pad. " requires an unusual definition of one-time pad to become true: it is easy to define a mathematically proven secure algorithm, as long as it require at least as much key material as the plaintext length. We can use a variety of substitute to XOR. It is even possible to make one where some of the key material is reused (e.g: XOR plaintext with pad used in previous session, then XOR with fresh pad of current session)
Jun
2
comment Advantages/Disadvantages of Bcrypt vs. hash/salt
Yes. In a nutshell, SHA3-512 has not work factor parameter, which is of paramount importance for password storage; and uses little RAM, which in this application is a drawback.
May
29
comment Fast PKI for embedded device
@Ricky Demer: the premise of Quick Verification of RSA Signatures is that quotient estimation is costly (so that handing it with the signature saves significant time). While that's true in some implementations, it does not have to be. In good RSA/Rabin signature verification code, quotient estimation has marginal contribution to execution time, including all precomputation for arbitrary $N$. Efficient quotient estimation in mulmod (or efficient mulmod) would make an interesting separate question.
May
29
comment Fast PKI for embedded device
@Ricky Demer: $\overline\pi$ is just a nothing-up-my-sleeves number for a (relatively well-known) trick to compress the public modulus. DJB is throwing that, and the simple but effective primality test, as additions to his fast signature scheme, which AFAIK has security reducible to factorization independent of these extras. $\;$ I wish the paper had an exposition of the cryptosystem reduced to the main point; perhaps it is best explained in the original disclosure now linked in the answer.
May
28
comment Fast PKI for embedded device
@Ricky Demer: any hint on the tradeoffs in the quoted paper, in particular leak in the proof that ability to break the signature system implies ability to factor $N$ or breaking whatever hash is used?
May
27
comment Why is public key cryptography not widely used in governments?
A QR code is easily copied. Putting a digital signature on a QR code on each ID won't prevent making a copy of a valid ID. It won't even prevent changing the photo on the copy, unless the photo is available from an online database (and if we have this, we hardly need the signature in the QR code).
May
27
comment What is the difference between H(M) and H3(M, s, IDA)?
@Nubila: $H3(M,S,I)=\operatorname{SHA1}(\;M\;\|\;S\;\|\;I\;)$ with all parameters of fixed length will be fine for all but a very powerful adversary: the best known attacks require work of $2^{63\pm9}$ hashes, and so far have not been performed publicly. Same with a single parameter of variable length if you do no not care for the length-extension attack (which breaks security in the ROM, mentioned in version 1 of the question). For output in $\mathbb Z_p$ (as originally asked), see note in answer, and change 512 to 160 for SHA1.
May
27
comment What is the difference between H(M) and H3(M, s, IDA)?
@Nubila: I gave three examples of suitable functions $E$ (sorry I changed notation from $e$ to $E$). If this is for an actual implementation: If any two of $M$, $S$, $I$ are of fixed size, then $H3(M,S,I)=H(\;M\;\|\;S\;\|\;I\;)$ is just fine. Or perhaps $M$ and $S$ are restricted to bytestrings (not bitstrings) and of known maximum length; in which case $E(M)$ can simply be $M$ prefixed with the length of $M$ over a fixed number of bytes suitable for expressing the maximum length.
May
26
comment RSA public key exponent generation confusion
@Robert NACIRI: All hard-coded values of $e$ that I have ever met in practice are prime, I guess for the reasons exposed by Poncho.