Reputation
36,265
Next tag badge:
99/100 score
20/20 answers
Badges
2 55 151
Impact
~630k people reached

Mar
3
comment Why does 0x00 make bcrypt weaker?
I've heard of a system with a worse problem: reportedly, the bcrypt hash was stored in binary, and truncated at the first zero in that binary. Thus one in about 256 accounts was accessible with about one in 256 random passwords.
Mar
3
comment How to show that this modification of CBC-MAC is insecure?
Hint: show how to obtain a valid MAC for a 1-block(-after padding) message by submitting a 2-blocks(-after padding) message.
Mar
3
comment Is it OK to reseed a Deterministic Random Bit Generator from itself?
The simple, logical, tried and tested way to generate lots of randomness for simulation purposes is: for each simulation, use a fast CSPRNG with a seed unique to this simulation, that you keep track of (allowing a repeat). That seed can be random; incremental; the date/time..; or derived from one of the later two and a key. If the CSPRNG is the computational bottleneck of a simulation, typically either 1) the CSPRNG is way overkill; 2) it's poorly coded (e.g. in an interpreted language); 3) or/and the simulation could be replaced by an ounce of math from a good course on stats.
Mar
2
comment Constant time multiplicative inverse within a word
@Myria: the code you commented works at least on a platform with 64-bit int using 2-complement that does not raise exception on integer underflow. But indeed the suffix ushall be used here. I originally posted 0x2in hope that was more recognizable than than 2u in my code, but I incorrectly remembered the rules governing signedness of hex constants without suffix (contrary to decimal ones, they can be unsigned for some intervals of value, where I wrongly remembered they allways are unsigned). Thanks for correcting me.
Mar
1
comment Constant time multiplicative inverse within a word
@poncho: the algorithm I point to is the one to implement exponentiation (by right-to-left exponent scanning); so it is constant time (if modular multiplication and reduction is), and combined with your technique yields constant-time modular inverse. Designating this "Knuth's algorithm" was meant as an illustration of your note.
Mar
1
comment Constant time multiplicative inverse within a word
@Yosef: simple, use Knuth's algorithm! TAOCP Volume 2, 4.6.3, Algorithm A (it's over 3400 years old), reducing modulo $p$ at each step. Or any of the following ones.
Mar
1
comment Is a random circuit likely to compute a one-way function?
This is mathematically correct; but from an applied cryptography standpoint, there are one-way functions.
Mar
1
comment Is a random circuit likely to compute a one-way function?
It depends on how you define random circuit. If you use $n$ block inputs, $m$ NAND gates each with 2 inputs and one output, with the block's outputs these $m$ gate outputs, and randomly connect each of the $2m$ gate inputs to one of the $n+m$ block inputs and gate outputs, you often end up with something that is not a function (two NAND gates can make an RS latch). If you add some rules preventing this, that's a function but not a one-way function. You need to hide many of the outputs to hope for that. I know no quantitative result (hence this is not an answer) [fixed]
Feb
28
comment Trying to calculate the strength of a Bitcoin brain wallet created with a custom diceware password
Also: the entropy is the base-2 log of the number of (assumed equiprobable) passwords, thus $\log_2(46656)\cdot5$, not $2^{\log_2(46656)\cdot5}$. You do not account for key stretching, which can help a lot in many contexts, perhaps this one. Using long words has no discernible advantage, if they are public, which the computation assumes.
Feb
28
comment Simple digital signature example with number
The choice of $p=7$, $q=13$, $e=5$ is not ideal as an RSA example: the numbers are such that $e$ is both the public exponent and a working private exponent (using $d=29$ or $d=5$ as private exponent always give the exact same result). Also, it is questionable to even illustrate any use of RSA (except enciphering or signing a random number) without padding.
Feb
27
comment Applicability of birthday attack to AES brute force
@Mok-Kong Shen: I fully agree with that part of Thomas Byrd's answer starting after the first comma. For the rest I can't read minds.
Feb
27
comment Can a list of hashes with property $X_{n+1} = \operatorname{SHA-256}(X_n)$ loop?
Hint: we can approximate SHA-256 restricted to 256-bit input to a random mapping. Then, the classical results of Philippe Flajolet, Andrew M. Odlyzko Random mapping statistics apply, and allow to answer quantitatively (under such approximation). You can also experiment with a computer simulation, e.g. by studying SHA-256 restricted to its lowers 32 or 40 bits.
Feb
27
comment Applicability of birthday attack to AES brute force
@Mok-Kong Shen: I hope to have addressed your first 3 comments in the expanded second paragraph of the answer (noting that in this, one can replace 1.774 by any fixed small constant, including 1.2 for a better estimate of the birthday bound, or twice that in order to be almost certain that the number of distinct keys is above the birthday bound).
Feb
26
comment How to attack RSA-CRT with large public exponent?
Do you have an idea of how small are $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$ ?
Feb
26
comment Rabin-Williams, blinding and size of Integer r?
@bayo15: assuming $(e\cdot d\bmod\varphi(n))=1$ or equivalently $e\cdot d\equiv1\pmod{\varphi(n)}\;$, the equality $(r^{e\cdot d}\bmod n)=r$ holds for integers $r$ with $0\le r<n$, while the congruence $r^{e\cdot d}\equiv r\pmod n$ holds for all integers $r$. I can't think of another interpretation of mathematically correct.
Feb
26
comment What is the fastest modular reduction algorithm available?
@abejoe: you have not defined if you want support for arbitrary modulus. In the context of ECC over base field $\mathbb F_p$, the fastest modular reduction algorithm depends a lot on the choice of the prime $p$. Often, that choice is made for efficient modular reduction. For example, for the extremely common Curve P-256, $p=2^{256}-2^{224}+2^{192}+2^{96}-1$ and that allows very efficient modular reduction.
Feb
26
comment What is the fastest modular reduction algorithm available?
Define fastest. At least, define if you want support for arbitrary modulus (needed for at least the private-key computation of RSA, but not all ECC in $\mathbb F_p$), for how many reductions the thing is optimized, and how much memory can be devoted to temporary results. If the definition involves actual implementation on some hardware, define how you make sure the same care was used in implementations compared, the number of registers used, the speed of memory accesses and how the access pattern influences that.
Feb
25
comment DES_cblock and Key Recovery
Hint: the meat of the crypto part of the problem is insrand(seed); which gathers (too little) entropy, and the 4 lines that follows which make use of that. One way to tackle the problem is to find and analyses the simple (in comparison to DES) relation between that initial entropy and something that you know from the message, deduce key[], then decipher the message without breaking DES, which is still way too compute-intensive to ask in an assignment.
Feb
24
comment How is a per round key generated in DES algorithm?
Related question.
Feb
24
comment Difficulty to find any preimages $a$ and $b$ for given $V$ so that $H(a) \oplus H(b) = V$?
@user13741: your statement requires an about to become correct. In order to reach odds of success $1/2$, over $1/6$ more than $2^{112}$ evaluations of $H$ are required, even if the adversary had arbitrarily large and fast memory; and since that's not, and such huge search (much larger than all bitcoin mining done to that day) needs to be distributed, significantly more hashing is required.