Reputation
24,178
Next tag badge:
106/100 score
19/20 answers
Badges
2 32 102
Newest
 Nice Answer
Impact
~350k people reached

Mar
21
comment Which algorithm can be performed by humans?
I added the pen-and-paper tag, explore that !
Mar
21
comment Are factorization algorithms parallelizable?
Yes in (MP)QS, and as far as I understand GNFS, the more time spent sieving with a given criteria to keep what's found, the more data there is for the later steps (grouping relations involving the same large factors to find better ones, then for matrix reduction step); and past some threshold, extra data does not help much. $\;$ But I'm talking of changing the sieving criteria (lowering the size of the factor base and large factor bounds), so that sieving becomes much harder (there are fewer reports), but there is less input to the matrix reduction step and it gets easier.
Mar
21
comment Are factorization algorithms parallelizable?
If one spends more time in the sieving step, one can significantly reduce the matrix reduction step (I do not know how far this can go). Also, there is work toward running the matrix reduction step in a partially distributed way, search parallel block Lanczos.
Mar
21
comment Coding of unsigned int to prevent guessing next ID
Indeed. Or any block cipher with a small block, as common in Format-Preserving Encryption. I have re-tagged the question accordingly. Following that tag will lead to many related questions with good answers.
Mar
20
comment Information-theoretic bound on leakage by timing measurement
@Maarten Bodewes: following your comment I added a rationale.
Mar
19
comment Do asymmetric signatures require constant-time verification?
@SylarMorgan: you are very right to mention the secrecy of the message! The first version of my answer had forgotten about that, shame on me, time to go to bed!
Mar
19
comment Deterministically generate a RSA public/private key pair from a passphrase (with sufficient entropy)?
@Maarten Bodewes: I agree wholeheartedly, and thinking more about it find this very drawback has serious consequences.
Mar
19
comment What happens when a RC4 stream gets corrupted?
If RC4 was secure in a related-key setup, you could "append the blocknumber to the key", run a separate RC4 for each block, and that would be safe as long as a block is not modified (which amounts to keystream reuse). Problem is, RC4 key scheduling is insecure when used in this way. $\;$ We are wandering far away from the original question when we deal with security issues in unspecified variants of RC4, and with your performance issue; you should ask a separate question. Be careful to state your requirements/constraints, including if you have to use RC4 (or just consider this).
Mar
19
comment What happens when a RC4 stream gets corrupted?
In any case, you MUST NOT "reset the keystate" to the same state for every block, which would be the equivalent of re-using a pad in the One Time Pad. $\;$ If the file is read and written sequentially, it is best to use RC4 as designed, that is without resetting it. If you must access the blocks in random order, you need a carefully thought RC4 variant, perhaps where the key and block number are somewhat combined to "reset the keystate".
Mar
19
comment Can we reverse a hash when we know part of the input?
Discussing collisions only blurs the picture. In the situation considered in the question, even for MD5, they do not occur, thus do not matter. $\;$ As stated, the best known attack method (for practically used hashes) is trying every possible input, computing the hash and then comparing with the output. Thus having half of the message is of tremendous help; for a 20-digits message, the expected effort goes from $10^{20}/2$ hashes (hopeless with a few PCs) to $10^{10}/2$ hashes (10 billion times easier, feasible with a single PC unless the hash is purposely slow).
Mar
18
comment Creating a small number from a random octet string
@Neil Slater: Arithmetic coding indeed can reach optimality, or use O(1) memory and be practical. However, unless I err, arithmetic coding with O(1) memory can run into cases where it requires more bits than optimal arithmetic coding.
Mar
18
comment Concatenation of two strong hashes may have striking weakness
@Cédric Van Rompay. I too fail to prove that (and have some doubt about if) preimage-resistance of $H_0$ implies preimage-resistance of $H_1$. However if we assume $H_0=H$ is secure in the Random Oracle Model (as in the question's statement), then it can be proven that $H_1$ is secure in the ROM, which implies whatever preimage resistance. As often is, security in the ROM is the most powerful and useful model for a good hash.
Mar
18
comment Concatenation of two strong hashes may have striking weakness
Yes, that's simplest (thus better) than what I had in mind! $\;$ Can the last part of the question be so conclusively answered?
Mar
18
comment Concatenation of two strong hashes may have striking weakness
The definition of the HAC is: "preimage resistance — for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output". There is no notion of finding the original message, or that it is short. The given is a random element among possible hashes (or is it the hash of a random thus presumably huge message). If we concatenate good independent hashes (like SHA-256 and SHA-512 truncated to 256 bits), we obtain one that is much more resistant to that than the originals.
Mar
18
comment Concatenation of two strong hashes may have striking weakness
@Nova: My first statement was indeed wrong. However I'm not sure that I agree with your proof. I've been making the same proposition, and have since prudently backed out. Exactly what definition of first-preimage resistance are you taking? Find preimage for a random element of the destination set, or find preimage for the hash of a random unknown element of the source set? Or is it a random unknown element of some subset of the source set?
Mar
17
comment What practical uses can random hash collisions be put to?
Congratulation: you have built a machine to give a random solution to the first preimage problem, which can trivialy be turned into one generating collisions. Here is a variant of your machine: it can tell that the number you typed is also the SHA-256 of the ASCII string Password
Mar
17
comment Resynchronizing brute-force attack against stream ciphers
Searching the first 32-bit or 64-bit segment of known keystream into the candidate keystream while it is generated can be done at very little cost, if that's engineered into the software (or hardware) generating the candidate keystream; the rest of the search is more costly, but rare, thus has little impact on performance.
Mar
17
comment Resynchronizing brute-force attack against stream ciphers
Ah, so that attacker knows synchronized ciphertext-plaintext pairs, thus some of the true keystream. Is there anything problematic with just searching the chronologically first such known keystream segment in each candidate keystream corresponding to candidate keys, and in those few where it appears soon enough, computing more candidate keystream and search the other known keystream segments, in order to confirm the candidate key?
Mar
17
comment Resynchronizing brute-force attack against stream ciphers
Can we liberally interpret "know the general structure of the underlying plaintext" into all plaintext bytes have high bit clear? If yes, hint: that's choosen-enough plaintext. $\;$ If no, please clarify what the quote allows.
Mar
17
comment Resynchronizing brute-force attack against stream ciphers
Is the stream cipher in the question strictly exclusive-OR of plaintext with a single large keystream (or is it a more complex protocol)? $\;$ Also: can the attacker mount a chosen-plaintext attack? If yes, hint: do this with a plaintext that does not require re-synchronization.