Reputation
21,829
Next tag badge:
98/100 score
23/20 answers
Badges
4 29 79
Impact
~463k people reached

May
10
comment Cryptographically secure keyed rolling hash function
Thanks, @RickyDemer, I've edited my answer accordingly. Universality is all that matters (all that matters is the probability that two inputs yield the same output.) I agree with both of your comments -- thank you for them.
May
10
comment Cryptographically secure keyed rolling hash function
Sorry, I'm still not clear on how Tarsnap works. When is the substitution done? Is it applied to the input data, or to the output? If it substitutes from bytes to 32-bit values, does it expand the size of the input by 4x before hashing (or expand the size of the output by 4x after hashing)?
May
10
comment Cryptographically secure keyed rolling hash function
@cyril42e, have you benchmarked it? The AES-NI instructions are surprisingly fast. So you might want to implement, benchmark, and see if it meets your performance requirements. If it doesn't, I suggest editing your question to describe your performance requirements and how close this scheme gets and what you tried, to improve performance. Selecting the fastest block cipher for your platform is beyond the scope of this question, but you can find lots of other questions here that talk about that, or you can ask a new question.
May
9
comment Cryptographically secure keyed rolling hash function
Thanks for the update. I'm still not clear on how Attic and Tarsnap work. Is the substitution applied to the input data, or to the output of the Rabin-Karp/cyclic hash? I don't know what you mean by "HMAC of indexes". Would you like to try expressing it in mathematics?
May
9
comment On modeling a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$
What do you mean by "model a random oracle hash function"? Also, do you require it to be a group homomorphism?
May
9
comment Cryptographically secure keyed rolling hash function
Also, if you want us to comment on the security of Tarsnap or Attic, please define more precisely what you mean by "random secret substitution".
Apr
29
comment Pseudocode for constant time modular exponentiation
You might have missed the "constant time" in the title (and also mentioned once more in the question). I don't blame you, because that wasn't emphasized in the question as it might have been, and the question didn't mention what prior research he'd done (a shortcoming of the question). But I don't think Alex Gaynor was looking for a generic description of the RSA algorithm; I think he was looking for a description of how to make a constant-time implementation of RSA. That said, I agree that the question could have been clearer.
Apr
29
comment Pseudocode for constant time modular exponentiation
@figlesquidge, I beg to differ. It does answer the question (just not in way the author had expected). This is an XY problem: the author wants a constant-time RSA implementation (that's the X) and thinks the right approach is to implement it himself even though he doesn't understand the math (Y). I'm telling him that Y is not the answer to X; that the right answer is Z (use well-vetted code, or hire a cryptographer). P.S. "Don't do it" is a perfectly acceptable answer if you explain why: meta.stackexchange.com/q/8891/160917
Apr
29
comment Pseudocode for constant time modular exponentiation
@CodesInChaos, The fact that GnuPG failed does not mean that it is a good idea for a beginner who lacks a strong math background to try to implement RSA on their own. If the OP cannot understand mathematical descriptions of solutions to the problem, the OP probably shouldn't be trying to implement this himself (maybe he needs to hire a qualified cryptographer). Would you hire a random person off the street to design a bridge, if they told you they couldn't understand some of the core elements of bridge engineering (finite elements, differential equations, structural modeling)?
Apr
28
comment Simplified Key Wrapping to Achieve Only Confidentiality?
Ignoring authenticity/integrity is a really bad idea. It has led to successful attacks on confidentiality in the past. I strongly recommend against this sort of thing; use authenticated encryption or an authenticated key wrap algorithm that does provide integrity + authenticity.
Apr
26
comment Tiger Tree Hash vs generic Merkle Tree
Would you care to edit your question to define TTH? Maybe spell out the acronym, give a link, etc.? Also, I encourage you to describe what research you've already done to try to answer the question on your own.
Apr
26
comment Timestamping using a hashed linked list and public known events
@jliendo, I've edited my answer accordingly. The bottom line remains the same.
Apr
26
comment Zero-knowledge proof of a product
This is an excellent start, but it proves that $xy \equiv z \pmod q$, rather than that $xy=z$. I think if you choose $q$ to be $>2k$ bits long, and combine it with a range proof of the size of $x,y,z$, though, this might work. Thank you!
Apr
26
comment Multiple-prime RSA; how many primes can I use, for a 2048-bit modulus?
@fgrieu, awesome, thank you for the detailed comments! Would you like to either create your own answer or to edit this answer into a form that addresses these issues? I'm not quite sure how to take into account the first issue you mention (about 1% chance of success), so would need help on that. Thank you again!
Apr
26
comment Can I prove set membership and uniqueness without revealing the element?
P.S. I see: the Wikipedia article on commitment schemes is a bit sucky, and it has led you astray. Wikipedia seems to imply that $C(x)=g^x$ is a commitment scheme, but in fact, that's not a good commitment scheme. The Wikipedia article does go to admit that such a scheme is not hiding, but it fails to connect the dots and realize this means that the scheme wasn't a (secure) commitment scheme after all, and thus does not make a good example of a commitment scheme. So, don't rely upon Wikipedia as your main source of information about commitment schemes.
Apr
26
comment Can I prove set membership and uniqueness without revealing the element?
@DrLecter, yeah, you definitely have a misconception about commitment schemes. $g^a$ is not a secure commitment to $a$. It is not hiding (neither computationally hiding nor information-theoretically hiding). As a result, it is not classified as a secure commitment scheme. A secure commitment scheme must be both binding and hiding. Therefore, what you are talking about is not a DL commitment -- it's not a commitment at all; it's just a broken thing that doesn't work. Of course, when I mention using a commitment scheme, I assume you use a secure commitment scheme, not something broken.
Apr
25
comment Can I prove set membership and uniqueness without revealing the element?
@DrLecter, I think you have a confusion/misconception about DL commitments. I'm not sure what specifically you have in mind when you mention "DL commitments", but any commitment scheme (whether information-theoretically hiding or computationally hiding) will conceal what was committed to -- nothing is leaked. It doesn't matter whether the value being committed to is low entropy or not; secure commitment schemes promise not to leak what was committed, even if the value has low entropy. If it's not hiding, it's not a secure commitment scheme. For instance, $C(x)=g^x$ isn't secure.
Apr
25
comment Nonlinearity of the J-K Flip Flop
@WilliamHird, I think you might have a misconception. It sounds like you want to design a secure stream cipher, and your approach is to try to find a function that in isolation has some combinatorial properties. This has two problems: (1) to design a secure stream cipher, you need to look holistically at the entire design; you can't just pick out one component/function used in the stream cipher and say that "since it has properties X,Y,Z, the cipher is secure"; (2) designing secure ciphers is very hard, and you're unlikely to do better than existing state-of-the-art schemes.
Apr
21
comment Stateless hash based public key cryptography?
@HenrickHellström, the blog post (the first URL) has some more details. We save only the first level -- that's generated during key generation and treated as part of the private key. We regenerate the subtrees on the fly as needed. How are they generated? They can be generated via a GGM construction from a seed (e.g., computed as a PRF of some master key that's part of the private key, plus an identifier that identifies which subtree we're looking at). There's no need to save the subtrees, since they can be generated deterministically on demand as needed. Does that answer your questions?
Apr
17
comment Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?
Can you explain what you mean by "compose the modulus of some other quadratic ring"? Do you mean that instead of multiplying two integers to get the modulus, we multiply two elements of some quadratic ring? Have you worked out what the corresponding version of Euler's lemma is? What is the order of the multiplicative group of such rings? What's the motivation for your question? Are you hoping to get a cryptosystem that will be faster than RSA, for a given security level?