1,863 reputation
615
bio website
location
age
visits member for 2 years, 11 months
seen 18 hours ago

I am a math/computer nerd. Nothing to see here, move along.


May
4
comment How do I produce a stream of secure random numbers from AES-Counter mode?
Updating the nonce won't let you beat the birthday bound. Additionally, the 2^64 bound is when the provable security of CTR becomes worthless; if you want the security to remain strong (say, by limiting an adversary's advantage to 2^{-40}), then you'd need to stop at 2^{44} bits. Not that this is usually a problem!
May
4
answered How do I produce a stream of secure random numbers from AES-Counter mode?
May
2
reviewed Approve suggested edit on How to argue to a paranoid that RSA is safe?
Apr
18
answered How vulnerable is the C rand() in public cryptography protocols?
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
I think there may be a (minor) error in the reduction to f, which is queried twice as often as F. Set n = 2, and consider the function family index by keys $(a_1, a_2, a_3) \in (\lbrace 0, 1 \rbrace^n)^3$, where $f = f_{(a_1, a_2, a_3)}$ is defined by $f(i) = a_i$ (for i = 1, 2, 3) and $f(4) = a_2 - a_1 + a_3$. Then because - and + are group operators, any three values of f are statistically independent over the choice of key. So f is $(\infty, 3, 0)$-secure PRF. However, for every key, $F(4) = F(2) = a_2 - a_1$. Therefore $F$ is not $(\infty, 2, 0)$ secure.
Mar
11
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
I managed to convince myself late last night that this proof was incorrect, "fixed" it, and then realized today that there's a reason one should never do math while tired. I apologize for the numerous edits. Hopefully everything is fine now. I made one of the arguments more explicit to reduce the probability that I made another mistake.
Mar
11
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
added 328 characters in body, reverted early, incorrect "fix" to the proof
Mar
11
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
added 328 characters in body
Mar
11
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
added 136 characters in body
Mar
11
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
added 61 characters in body
Mar
11
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
added 1682 characters in body
Mar
11
answered Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
Mar
6
comment Unpredictability vs randomness
It apparently converges to something that passes a Chi Square test. Is every distribution that passes that test a uniform distribution? I doubt it. For example, consider the distribution created by choosing a random K and outputting K|AES(K, 0)|AES(K, 1), where | is concatenation. It's trivial to distinguish these outputs for random (since you're given K), but highly unlikely that a standard statistical test, such as Chi Square, will be able to do so. See the second paragraph of my answer.
Mar
6
comment Authenticated encryption without padding
My answer to this question may be relevant: crypto.stackexchange.com/a/6434/519 (The question is just about confidentiality, but the answer touches on integrity).
Mar
6
comment Unpredictability vs randomness
@izaera Regarding Von Neumann vs hashing. Those who advocate the "easy way out" are willing to model the hash function as a random oracle; basically, you model each output is being sampled uniformly at random. This is a much stronger property than being non-invertible. Von Neumann would work if all the harvested bits were independent (not just pairwise independent, but independent of all other bits). I suspect that this assumption isn't valid. Of course, in my judgement, neither is the random oracle model.
Mar
6
comment Unpredictability vs randomness
(cntd). So if you harvest, say, a 256-bit string from a distribution that has 160 bits of min entropy, a good randomness extractor will be able to turn it into a 128-bit string that is (close to) uniformly distributed, and therefore suitable for use with AES-128. In contrast, using the original 256 bit string in AES-256 may actually be less secure, because the bits may have biases and/or not all be independent of the other 255 bits. The drop in security isn't against brute-force attacks, it's against attacks that leverage the fact that AES was designed with uniform keys in mind.
Mar
6
comment Unpredictability vs randomness
@izaera Any (deterministic) extractor algorithm can be attacked by a brute-force adversary. The only ways around this are to either gather more entropy or, as Ricky suggests, using a PBKDF to slow down a brute-force attack. The goal of the extractor isn't to resist brute-force attacks, the goal is to generate outputs that are (statistically close to) uniformly random from outputs that are merely unpredictable (have high min-entropy). AES was designed to be used with a uniformly random key; using a key that's merely unpredictable puts you on shaky ground.
Mar
6
revised Unpredictability vs randomness
added 53 characters in body
Mar
6
comment Unpredictability vs randomness
Since this is a crypto board, I answered the question from a crypto perspective. But from a practical security standpoint, I suspect your time might be better spent trying to find richer sources of entropy. (Also, and I suspect you are aware of this but just want to make sure, Van Neumann unbiasing only unbiases bits that are independent --- unlikely to be the case here.)
Mar
6
answered Unpredictability vs randomness