2,038 reputation
820
bio website
location
age
visits member for 3 years, 2 months
seen Oct 15 at 6:01

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


Oct
14
comment Key management protocol for end-to-end security on Advanced Metering Infrastructure
This is a bit of a tangent, but if you're interested in learning about what some more sophisticated crypto can do in the specific context of smart meters, you might want to read up on work by George Danezis et al., e.g., www0.cs.ucl.ac.uk/staff/G.Danezis/papers/DFKZSEGS13.pdf.
Oct
3
comment Has there been any cryptanalysis of AES under a non-uniformly distributed key?
@owlstead This is not my area, but it seems to me that key scheduling attacks would be well in-scope here. For example, consider generating an AES-256 key by appending 178 zeros (or whatever) to a uniformly random 80-bit string. The result would (arguably) have enough entropy to be border-line secure against brute-force attacks, but it's my understanding that the key scheduler wasn't designed to handle this level of abuse.
Oct
3
comment Has there been any cryptanalysis of AES under a non-uniformly distributed key?
@TravisMayberry I was using the term "uniform distribution" in the technical sense, i.e., all keys are equally likely. The standard PRP security definition assumes this property of the blockcipher key, and I was wondering if anyone had looked at the question of what happens when this assumption is violated (aside from related key attacks).
Sep
30
comment Bridging the gap between security proofs and “real-world” security
I think that in its current form, this question might be too broad and subjective. This rabbit hole is deep. The range of possible issues includes appropriateness of the attack model (most models assume no timing side-channels exist), the interpretation of what "secure" means (when is it safe to leak plaintext length? Are even the strongest possible order-preserving encryption security definitions "secure enough"?), the assumptions (AES? Good. LWE? Hmm... ROM? Uh...). To say nothing of concrete vs. asymptotic security, a can of worms on its own! Not to mention implementation issues.
Sep
19
comment Authenticating Very Short (Sub-Block) Data
Addendum: I should probably also note that this approach won't protect you against replay attacks. While this is true of authenticated encryption in general, it's a harder problem to solve if messages are too short to include a monotonically increasing counter or some other protocol-level countermeasure. Without knowing more context, it's hard to know what threats you should be concerned with.
Sep
19
comment Authenticating Very Short (Sub-Block) Data
Length-preserving schemes are by definition FPE. But if bandwidth is an issue, you can get very short authenticated ciphertexts by using encode-then-encipher (seclab.cs.ucdavis.edu/papers/Rogaway/encode.pdf). If you pad your 64-bit payload with 0s until it's 128 bits long and encrypt using AES (in ECB mode, no IV), then you can check authenticity by verifying that the padding is all 0s when you decrypt. Some warnings: (1) an attacker will be able to learn if a message is repeated (2) this only works if messages are significantly shorter than the AES block length (128 bits).
Aug
23
comment Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?
I'm not sure what you're arguing. For concreteness, let's use the example I gave earlier, and suppose that, say, n = 63, both x1 and x2 are at least 2^63, x2 = DES_K(x1), and suppose that y = DES_K(x2) < 2^63. My understanding of your proposal is that both x1 and x2 would map to y because this is the first value in [0, 2^63) we reach by repeated application of DES_K, regardless of whether we start from x1 or from x2. If this is incorrect, could you please clarify how the mapping is computed?
Aug
23
comment Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?
The "cycle-walking" method wouldn't work here because your target space is not your source space. For example, you could have two inputs X1 and X2 in your source space such that AES_K(X1) = X2 (it would make slightly more sense to use DES here, but same thing would happen). In this case, X1 and X2 would then map to the same point in your target space, unless X2 was already in it.
Aug
5
comment How many degrees of freedom up my sleeve?
You might find the (satirical but still substantive) paper "How to manipulate curve standards: a white paper for the black hat" interesting; it addresses this question in the context of ECC parameters. PDF: eprint.iacr.org/2014/571.pdf
Jul
21
comment Lowest number challenge scheme
This is Yao's Millionaires' Problem: en.wikipedia.org/wiki/Yao's_Millionaires'_Problem
May
28
comment AES/CBC fixed Initial vector use-case
Using a fixed IV will also leak the information about the length of any shared prefixes. Also note that CBC won't stop someone from tampering with the cookie so that it decrypts to something that you don't expect, and if an attacker can guess at some of the cookie's contents, he will have a degree of control over what this is.
May
22
comment Can you determine an unknown value when it is combined with a known value and you are given the resulting hash?
If this is motivated by a homework question asking about the security of H(K|M) as a MAC (for hash function H, key K, and message M), you should consider the possibility that an attacker may not need to learn K in order to produce a forgery. Think about how SHA256 works internally.
May
22
comment Simple way to extend AES to 256-bit block size
possible duplicate of Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$?
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!
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.