9,686 reputation
12347
bio website github.com/CodesInChaos
location Frankfurt, Germany
age
visits member for 3 years, 1 month
seen 5 mins ago

Jul
6
comment Convergent encryption has dictionary attack, but why hash function doesn't?
Sending the hash of the plaintext suffers from the same problems as convergent encryption. The best writeup of the security properties of CE I've seen so far is zooko's Drew Perttula and Attacks on Convergent Encryption
Jul
4
comment Use ElGamal to solve Diffie-Hellman problem
AFAIK ElGamal only reduces to the decisional DH problem, not the the computational DH problem. So this proof shouldn't exist
Jul
1
comment Types of cryptography
You should read Structure vs. Combinatorics in Computational Complexity
Jul
1
comment Types of cryptography
The underlying problem is called AES. Typical symmetrical schemes don't reduce to an elegant mathematical problem. They rely on the complexity emerging out of the interaction of many simple operations. In a way RSA/DH etc. are structured whereas AES is unstructured.
Jun
30
comment Combining Random Hashes - avoiding collisions and ensuring randomness
@Navonod SipHash has been designed with a uniformly random key in mind, so you're not using it as intended. But since your requirements are much weaker than what it's designed to offer, that might still be okay for you.
Jun
30
comment Does collision resistance imply (or not) second-preimage resistance?
If you have a two block message you can run a meet-in-the-middle attack since the primitive function is invertible. This should break (second) preimage resistance with cost $2^{c/2}$ where $c$ is the capacity. (I didn't look into the memory requirements, they might be unrealistically large) This is the reason why SHA-3 uses $c=2 n$.
Jun
28
comment Does collision resistance imply (or not) second-preimage resistance?
A sponge with capacity $n$ is another example. This one is important since NIST considered having SHA-3 with only $2^{n/2}$ preimage resistance.
Jun
28
comment Does collision resistance imply (or not) second-preimage resistance?
The only thing I can think of is that we usually expect $2^n$ second pre-image resistance, whereas collision resistance is limited to $2^{n/2}$. So from collision resistance we can only prove $2^{n/2}$ second preimage resistance, not the stronger bound we'd like.
Jun
28
comment Does collision resistance imply (or not) second-preimage resistance?
Please provide a link to the claim that there are collision resistant but not second-preimage resistant hashes.
Jun
26
comment Combining Random Hashes - avoiding collisions and ensuring randomness
You should write a bit more about the problem you want to solve. What your inputs are, what the outputs should be. What you want to guarantee etc. Your answer is mostly about the problems you encountered with your approach. I suspect that the best solution throws most of that approach away, replacing it by a single standard crypto function.
Jun
26
comment Combining Random Hashes - avoiding collisions and ensuring randomness
4) You say the hash should be very fast. Can you give any numbers? 5) All your inputs have exactly 64 bits. Did I understand that correctly? 6) Do you actually need a hash? Perhaps a keyed permutation (i.e. a 64 bit block cipher) is more appropriate? Permutations have no collisions by definition.
Jun
26
comment Combining Random Hashes - avoiding collisions and ensuring randomness
1) It's almost always better to choose a single good hash rather than combining multiple hashes. 2) Use a modern crypto hash. 3) With 64 bit hashes, you only get 32 bits of collision resistance. So in the cryptographic sense, you don't get any practical collision resistance. Even pre-image resistance is rather low at 64 bits.
Jun
25
comment What is the quantum-resistant signature scheme with the smallest signature + pubkey?
Isn't the security level of 128 bit hashes just 64 bits since the Grover reduces the pre-image resitance?
Jun
24
comment Minimum length of PKI key for signature
1) If you care about key size, don't use RSA or DSA. ECC has much smaller keys. 2) Key size by itself is meaningless since it can be trivially reduced, increasing the signature size by the same amount. Do you actually care about the sum of the size of key and signature?
Jun
24
comment Minimum length of PKI key for signature
Your question says RSA, the tags say DSA.
Jun
24
comment What is the quantum-resistant signature scheme with the smallest signature + pubkey?
@RickyDemer eBACs lists a fast Ed25519 implementation at 170k CPU cycles. Most implementations are closer to a million CPU cycles. So 600 calls to a compression function should be in the right ballpark, probably even faster than ECC if you choose a fast hash function.
Jun
24
comment What is the quantum-resistant signature scheme with the smallest signature + pubkey?
@RickyDemer ECDSA sigs use 4x the security level and public keys 2x the security level. So total of public key and signature is around 100 bytes.
Jun
23
comment Fastest random number generator
Why do you care? It's not like you need more than 256 bits of true random data to seed a great PRNG, which can exceed 10 Gbit/s on a modern CPU.
Jun
20
comment How big an RSA key is considered secure today?
The "do not cost significant performance penalty" depends very much on context. For email that may be true since you usually don't receive several emails per second. For many other contexts, such as SSL, several hundred milliseconds of decryption time for a single handshake are not acceptable. The other big problem is that many RSA implementations do not support such large keys.
Jun
19
comment Is a 1024-bit DSA key considered safe?
AFAIK a DSA cracker requires a few hundred times the RAM of an RSA cracker, so I'd assume that cracking a DSA key is a few hundred times more expensive than cracking an RSA key of the same size. Further evidence towards DSA being stronger is that the largest solved discrete logarithms over prime fields are smaller than the largest factored semi-primes.