1,463 reputation
412
bio website
location
age
visits member for 2 years, 8 months
seen 14 mins ago

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


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
Feb
11
comment Should tweak be unique per message?
@sashank: Yes, FPE, like full-fisk encryption, is another example of when the tweak is exposed to the programmer (hence "almost" never). I think we might be using slightly differently terminology here, though. When you say IV in the context of "block cipher + IV", do you mean using the tweak as a nonce (i.e., never repeating it)? That is, are you asking if FPE is more secure if you don't repeat tweaks? The answer to that question is: a little. If you repeat a tweak, an attacker can only learn if the corresponding plaintexts are equal. Unique tweaks prevent even this.
Feb
11
comment Should tweak be unique per message?
@RichieFrame Yes, and this was precisely my point: that tweaks belong to tweakable blockciphers and IVs belong to modes of operation. I've edited the part of my answer that talks about OCB to hopefully make this more clear.
Feb
11
revised Should tweak be unique per message?
deleted 139 characters in body