1,433 reputation
412
bio website
location
age
visits member for 2 years, 8 months
seen yesterday

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


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
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
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.)
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
comment Should tweak be unique per message?
It depends on the algorithm. For encryption algorithms, such as OCB, tweak values are usually derived from the IV.
Dec
15
comment Game traffic encryption AES CTR + HMAC
Regarding GCM-AES tag length, 8 bytes may be enough here. See eprint.iacr.org/2012/438.pdf, theorem 2. Assuming the 70-byte upper limit to plaintext length mentioned by the OP can be assured even against adversarial players, then $\ell_A = 5$. So the probability of a successful forgery after q forgery attempts would be at most ~ 6q/2^{64}. Which is, I think, perfectly reasonable for a game.
Nov
25
comment Ciphers in CBC mode reveal place of change in plaintext
CBC-ESSIV does not solve the problem of IV-reuse leaking information about where a plaintext has changed; it's simply a fix on the even worse problem of IVs changing in predictable ways from sector to sector that affected earlier versions of dm-crypt (and still affects CBC-plain). While you're probably aware of this, I worry that your answer does not make it clear.
Sep
15
comment What is the ideal cipher model?
@pg1989 MD5 uses a Merkle–Damgård structure with a Davies-Meyer compression function. The compression function uses a block cipher. A natural question to ask is if we can prove MD5 is, e.g., collision resistant by starting with some assumption about the security of the block cipher. My point was that the PRP assumption won't help us out here, because the PRP definition assumes a random secret key, but the block cipher is being used in a mode of operation where the key bits are known to (in fact, chosen by) the attacker.
Sep
15
comment What is the ideal cipher model?
@RichieFrame It's true that if you use a Davies-Meyer compression function, the message bits get used as key bits in the block cipher. But the message bits certainly aren't secret when talking about collision resistance (and they aren't necessarily random, either).
Aug
24
comment Do ciphertexts leak information about their algorithmic creators?
Minar's point was that a good block cipher is computationally indistinguishable from a random permutation. That is, AES (with a random key) may not be a perfect random permutation, but in practice attackers cannot tell the two apart. This is a design goal for block ciphers that is expected to hold "out-in-the-field"; if someone were to demonstrate that AES lacks this indistinguishability property in practice, they would send cryptographers scrambling for a new block cipher. Most experts believe this is unlikely to happen any time soon.
Aug
5
comment Is AES-XTS considered safe to encrypt multiple files with the same keys?
How do you propose to derive the IV for XTS (sometimes called the tweak in this context)? When encrypting block devices, the sector ID is used. Are you hashing the filename or something?
Jul
25
comment Hash function based on pseudorandom functions and security
@Dingo13 Only a very small fraction of functions are multi-linear (i.e., can be described using matrices). Therefore there's a big difference between a random function and a random multi-linear function. By definition, each output of a random function is independent of not only the input, but also other (input, output) pairs. Therefore knowing the output doesn't help you guess the input (i.e., random functions are pre-image resistant). In contrast, the behavior of a random square matrix is not "random" in this same sense, since multilinear functions have strict algebraic properties.
Jun
17
comment Security of authenticated encryption modes gcm & ccm
It's my understanding that the different versions of OCB were motivated by desires to improve performance, simplify the proof, support associated data --- basically everything but security concerns. The "attack" you mention basically says that if you encrypt several gigabytes of data under the same key, an attacker can create a forgery with probability 2^-64; i.e., there is roughly a one-in-a-quintillion chance that the attacker will succeed. I doubt this is much of a concern for practioners.
Jun
8
comment Questions about the ideal cipher model
Your characterization of an ideal block cipher in the last paragraph is a bit off --- an ideal block cipher is a set of random permutations, one for each possible key. So the elf would have a set of tables.