Proof of work for determining whether a number is prime? I have an idea for a system that would be outsourcing some brute force calculations to many users in hopes of finding divisors of a number. However, there is a possibility that a given number would be prime, or that it would not have a divisor in a given range.

For example, a computer might be tasked to look for a divisor of a number 2^n-1 (which would be a very large number) and whether there is a divisor in range x*10^10 to (x+1)*10^10.

Proving that one has found a divisor is easy - they just need to submit that divisor and the number can be checked against it. However, how should the users go about proving that there is no divisor to be found in a given range? Obviously one couldn't just trust a user in their claims - this would open a possibility for malicious reports messing with the system.

So far I was pondering a few options - submitting overlapping regions to various users for checking and comparing their results, challenging the users to find the smallest / biggest remainder of a check they would be performing in the range and so forth. Are there any approaches to the presented problem that are more vetted in the crypto world than "an idea that sounds okay"?

First off: Divisibility testing is an atrociously bad way to check whether a number is prime or not.  It is horribly inefficient and ineffective.  You need to first read up on the literature on primality testing before you think about how to distribute it among untrusted clients.

Use any standard primality test.  Give each client a different iteration of the test, and have them send you the result.

For instance, you could use Miller-Rabin primality testing.  The idea of this primality test is that you choose a random value $a$, then do some computation based upon $a$ (e.g., you compute $a^d \bmod n$, and some other stuff that I'll ignore for simplicity); this might result in a proof that $n$ is not prime, or it might result in nothing.  If you do this 10 times with 10 different random values $a$, and none of them find a proof, then it's very likely that $n$ is prime.

Here's how you could distribute Miller-Rabin primality testing:

Choose a few dozen clients randomly.
For each client, pick the value $a$ randomly.  Give the client $a$.  Ask the client to compute $a^d \bmod n$ and send it back to you.
If any client claims to have found a proof that $n$ is not prime, send the same $a$ to 4 other randomly chosen clients.  If at least 3 out of those 5 clients give you the same value for $a^d \bmod n$, then probably all 3 of those were honest and probably $n$ is not actually prime.
If none of the clients found a proof of non-primality, then probably $n$ is prime.
If you ever want to confirm that a particular client did its work correctly, send the same value $a$ to a few other clients and see if they all return the same value for $a^d \bmod n$.

You can adjust the parameters (the number of clients selected, the number you require to agree before you accept the result is probably correct, the number of iterations of Miller-Rabin) based upon how much confidence you require and what fraction of your clients you think are honest.

I expect this framework ought to lead to an efficient way to test primality of even very large numbers.  If it doesn't suffice in your setting, then you should edit your question to provide more specifics of why it does not work and what you have tried.


Is CRC32C (any) better than CRC32(B)? Is CRC32C (any) better than CRC32(B)?

I read that CRC32C (alias Castagnoli) is better than CRC32 (sometimes referred as CRC32B) in detecting errors but what that exactly means and how to check it didn't mention. I know they use different polynomial but that alone doesn't explain that. So I started to search a bit more and found nothing really. Only one post on Intel's forum where the guy from Intel says it's been chosen because "this polynomial has nice mathematical properties". I immediately wanted to ask "Since when 'niceness' is a criterion to choose one algorithm (here - polynomial) over the other?". Anyway...

Inspired by this topic I created my own test and checked collisions in English dictionary (from here, note there are two repetitions: "OUTSOURCING", "OUTSOURCINGS"). I used my author's program that hashes all entries and compares these hashes with each other. I also used lowercased, capitalized and first-letter capitalized words. After optimization it gives (n*(n-1)/2) comparisons. The results I got are somewhat characteristic:
('_32a' means first 32 bits of hash ( memcpy(hash32, hash, 4); ), '_lo32b' means low 32 bits of hash ( (uint32_t)hash64; ); (polynomials taken from wikipedia)

| hash         | collisions | polynomial |
+--------------+------------+------------+
| crc32b       |     44     | 0x04C11DB7 |
| crc32c       |     62     | 0x1EDC6F41 |
| crc32k       |     36     | 0x741B8CD7 |
| crc32q       |     54     | 0x814141AB |
| fnv1a        |     51     |      -     |
| md5_32a      |     45     |      -     |
| sha1_32a     |     44     |      -     |
| wyhash_lo32b |     47     |      -     |
| xxh32        |     49     |      -     |
| xxh64        |      0     |      -     |
| xxh64_lo32b  |     51     |      -     |
+--------------+------------+------------+

As you can see - 32 bit hashes are prone to collisions, and good hashes have similar chance of collision in set of this size equal to ~45. All but CRC32C... Seems like CRC32C has 40%+ more collisions than CRC32B which is significant, comparing that other hashes, including cryptographic, have around 45 like CRC32B.
Is it better? Somehow I don't see that.

I also checked how they compare in smhasher as it's designed to test hashed and both CRC32B and CRC32C fail miserably on the same tests in the same fashion (collective set of those tests here).
Is it better? Somehow I don't see that.

I know this crude test is not the best way of testing but smhasher shown the same, and even more of it, so is CRC32C any better than CRC32(B)?

What does «CRC32C (alias Castagnoli) is better than CRC32B in detecting errors» exactly means?

Multiple metrics are used in the original article. One is: when we restrict to messages of equal length differing by at most some low number of bits (e.g. 4 bit), CRC32C gives certainty of error detection up to a larger message length than CRC32 does. This is confirmed independently. Variations consider the probability of error detection for messages slightly above the threshold of perfect detection on either the message length, or number of bits in error.

I'm not sure that the 66 vs 44 collisions found in the question is statistically significant, or the cause of that if it is significant.


What key is used to encrypt the certificate and certificate verify message in TLS1.3? Which key is used to encrypt certificate and certificate verify message in TLS1.3?

I could not figure out which one it is reading section 4.4.2 of RFC 8846 and I only saw a vague mention on page 11.

Due to the design of TLS 1.3 and different to earlier TLS versions the normal (EC)DHE key exchange is already finished once the server sends the certificate. They key server_handshake_traffic_secret used to encrypt the certificate and other handshake messages is based on the same key material as the keys which are used for the application data later. For the exact details on which separate keys exist and how they are derived from the common key material see RFC 8446 section 7.1 Key Schedule.


Implementing PKCS#7 Padding on a Stream of Unknown Length? I have a fairly simple Python program using PyCrypto to use AES+CBC to encrypt a stream of input. In order to adhere to the 16-byte input size multiple, I've implemented PKCS#7 by hand. (While I know implementing cryptographic methods by hand is generally a bad idea, padding 1-16 bytes of data isn't exactly the hardest thing in the world. Here is essentially what I'm doing:

while True:
    input_chunk = infile.read(1024)

    if len(input_chunk) == 0:
        # if we've reached the end of the file and it _is_ a
        # multiple of 16 in length, pad 16 bytes with the value '16'
        end_of_line = True
        input_chunk += struct.pack('{}B'.format(16), *(16 * [16]))
    elif len(input_chunk) % 16 > 0:
        # if we don't have an input_chunk which is divisible by 16,
        # pad it by the remainder with bytes with the value of the
        # remainder
        end_of_line = True
        input_chunk_remainder =  16 - (len(input_chunk) % 16)
        input_chunk += struct.pack('{}B'.format(input_chunk_remainder),
                *(input_chunk_remainder * [input_chunk_remainder]))

    outfile.write(encryption_cipher.encrypt(input_chunk))

    if end_of_line:
        break

The only problem I'm now having is trying to understand how I'll decrypt an input stream if I don't know its length in advance. The encryption I'll be implementing will actually be used to read a stream of bytes from a socket, decrypting each 'chunk' as it comes across.

How will I know when to trim the PKCS#7 padding? Can I assume that if the last n bytes in the stream are all the same value from 1-16 that I can trim the input after decrypting it? I would assume that this is dangerous and may trim data unnecessarily.

Is there a way to solve this problem?

Bit padding, PKCS#5 padding and PKCS#7 padding are always applied, and they are always applied to the end of the plaintext. The last block of ciphertext will always contain the padding. The padding is always 1 to [blocksize] bytes, which in case of AES is 1 to 16 bytes.

For PKCS#5 padding and PKCS#7 padding - which are basically identical - the value of the padding bytes is equal to the length of the padding. So you would get values 10, 0F, 0E to 01 (in hexadecimals) for ciphertext lengths Z*16 + 0, 1, 2 to 15 respectively.

To unpad quickly simply read the last byte of the decrypted ciphertext, and remove that number of bytes (not characters) from the end of the plain text.

Notes:

It is possible to verify the other padding bytes, as long as the padding bytes themselves are not used to verify the correctness of the data;
It is only possible to unpad at the end of the ciphertext but it is not possible to use the padding bytes to detect the end of the ciphertext (unless the padding is clearly distinct from the plain text);
Please know of and beware of padding oracle attacks.


How does the squeeze function in the NaCl Poly1305 implementation work? The NaCl ref implementation of the Poly1305 algorithm uses the following reduction function (which is called squeeze()):

static void squeeze(unsigned int h[17])
{
    unsigned int j;
    unsigned int u;
    u = 0;
    for (j = 0;j < 16;++j) { u += h[j]; h[j] = u & 255; u >>= 8; }
    u += h[16]; h[16] = u & 3;
    u = 5 * (u >> 2);
    for (j = 0;j < 16;++j) { u += h[j]; h[j] = u & 255; u >>= 8; }
    u += h[16]; h[16] = u;
}

I understand globally what is done in the first for loop, namely that each integer in h is reduced to 256 bits, with the carry being carried over to the next integer. I only don't grasp what happens from the h[16] = u & 3; on. Where does the u & 3; come from? and the u = 5 * (u >> 2);?

Also, if I would want to change the radix here, say from 2^8 bits to 2^16, would that require me to change the above mentioned fragments? I would need to change al the 8's to 16, and the 255's to 2^16-1, but would that be it?

Does anyone know how this squeeze function works, and provide an explanation, as well as an answer to my second question?

The implementation itself provides no documentation, and the answer on How does NaCl Poly1305 implementation do modular multiplication? does not delve into the squeeze function. See this stackexchange question for the full code.

There are two ideas going on here:

Radix 256 arithmetic with delayed carries.
Here we represent an integer $x$ by $x_0 + 2^8 x_1 + 2^{16} x_2 + \dots + 2^{128} x_{16}$.  In canonical form, the digits $x_i$ lie in $\{0,1,2,\dots,255\}$, but in the Poly1305 computation, we delay the propagation of carries as long as we reliably can in order to save computation, so the $x_i$ might be larger, giving multiple possible representations for each integer $x$ in this form.

Poly1305 reduction $2^{130} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 5 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p$.
We are working modulo $p = 2^{130} - 5$, which has $2^{130} - 5 \equiv 0 \pmod p$ and so $2^{130} \equiv 5 \pmod p$.  The idea is that if we have an integer $x$, we can take its 130 low bits $x_{\mathrm{lo}} = x \mathbin\& (2^{130} - 1)$, and the high bits $x_{\mathrm{hi}} = x \mathbin\gg 130$, so that $$x = (x_{\mathrm{hi}} \ll 130) \mathbin| x_{\mathrm{lo}} = 2^{130} x_{\mathrm{hi}} + x_{\mathrm{lo}},$$ and then do a reduction step by computing $$x \equiv 5x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p;$$ i.e., shift/multiply/add.

The two ideas are done simultaneously.  I recommend that you try to work through it yourself from those two ideas, but—spoiler alert!—here's the full gory details if you're still completely stuck:

static void squeeze(unsigned h[17])

On entry, $h$ represents an integer $x$ in radix 256, with digits that may exceed 255 because of delayed carries, as long as they have some bound $B$ so the carries aren't too excessive.
$x = h[0] + 2^8 h[1] + 2^{16} h[2] + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[16] < B$
First, we propagate all the delayed carries and bound each digit by the radix up to 128 bits:
u = 0;
for (j = 0; j < 16; j++)

Loop invariants:
$x = h[0] + 2^8 h[1] + \dots + 2^{8j} (h[j] + u) + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[j] < 256 \\
h[j + 1], \dots, h[16] < B$

    { u += h[j]; h[j] = u & 255; u >>= 8; }

Now $h[0], \dots, h[15]$ are reduced, leaving us with $h[16]$ and a 128-bit carry.  We'll go two bits further to get a 130-bit carry:
$x = h[0] + 2^8 h[1] + \dots + 2^{128} (h[16] + u) \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < B$
u += h[16]; h[16] = u & 3;

Now note that $2^{130} \equiv 5 \pmod p$.  So—after we shift $u \gg 2$ below—when we have
$x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] + 2^{130} u \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$
we can reduce $x = h[0] + \dots + 2^{130} u \equiv h[0] + \dots + 5 u \pmod p$.
u = 5 * (u >> 2);

Now we can add $5 u$ starting at the first digit, and propagate the carries:
$x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] + 5 u \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$
for (j = 0;j < 16;++j)

Loop invariants:
$x = h[0] + 2^8 h[1] + \dots + 2^{8j} (h[j] + u) + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$

    { u += h[j]; h[j] = u & 255; u >>= 8; }

Now we have a 128-bit carry again, but there's plenty of room because $h[16]$ is only two bits at this point, from the above h[16] = (u & 3).
$x = h[0] + 2^8 h[1] + \dots + 2^{128} (h[16] + u)
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$
u += h[16]; h[16] = u;

Finally, $h$ again represents an integer in radix 256, with digits that are bounded by the radix:
$x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[16] < 256$
However, it is not necessarily the least representative modulo $p$.  For that, we need to freeze; squeeze just propagates a batch of delayed carries and does a single reduction step so there's room for more arithmetic.
(Figuring out what $B$ is and setting corresponding bounds on the carry $u$ in each step left as an exercise for the reader.)

Also, if I would want to change the radix here, say from 2^8 bits to 2^16, would that require me to change the above mentioned fragments? I would need to change al the 8's to 16, and the 255's to 2^16-1, but would that be it?

The array $h$ represents the integer $x = h[0] + 2^8 h[1] + 2^{16} h[2] + \dots + 2^{128} h[16]$ on entry, and $x - (2^{130} - 5) k$ for some $k \geq 0$ on exit after the reduction step where we replace $2^{130} u$ by $5 u$.  (Casting out $2^{130} - 5$'s.)
If you want to change the radix, say from $2^8$ to $2^{17}$, then the array $h$ will instead represent $x = h[0] + 2^{17} h[1] + 2^{34} h[2] + \dots + 2^{119} h[7] + 2^{136} h[8]$.  The goal is to compute the same reduction, $x - (2^{130} - 5) k$ for some $k \geq 0$, but finding multiples of $2^{130}$ to replace by multiples of $5$ for the reduction step will happen at a different digit position, $h[i]$, and a different bit position within that digit or carry, $u \gg j$.
It is an easy exercise to find these positions.  For a simpler exercise, you could try writing arithmetic modulo $2^{31} - 1$ in radix $2^8$, in which you can easily exhaustively test a reduction step for correctness.  I recommend that you carry out this exercise rather than asking pseudonymous strangers on the internet to spoon-feed you answers!


As you know, RSA encryption works by raising a plaintext block $p$ to some power $e$ modulo some composite modulus $n$:

$$c = p^e \pmod n$$

Now suppose $p$ and $e$ are so small that $p^e < n$. This is a disaster for Alice, because Eve can retrieve the plaintext by simply calculating the $e$-th root of $c$:

$$p = \sqrt[e]{c} \quad (\text{if }p^e < n)$$

On the other hand, if $p^e \ge n$, then $c$ will not be an exact $e$-th power. In this case, you could try adding integer multiples of $n$ to $c$ until you end up with a number that does work; i.e.,

$$p = \sqrt[e]{c + kn} \quad (\text{for some }k \in \mathbb{Z})$$

Note that this works without knowing the factors of $n$. In practical situations, RSA uses a much larger value of $e$ (usually 65537) and a much larger value of $p$ (through the use of padding), making this sort of attack impossible.

A couple of examples:

Using the same modulus and exponent:

e = 3
n = c7d6bca5802235a56df4faf08d0fb4701e9e94b886a5c3d0c6441c92e3d3a0e6
    d7549720d814961b53385dc1fbd28237b028a93c10d08b2d47bf31c8bd6f7aa8
    062c6d7479a2e12734d17d851955de11382cf42137f1fc40839df2562b7a91dc
    3b6751f6060ceb3090837d760b748997a43a01919a0c8f2c6b1bfb72653de70a
    8ae197eb1c6780a75914cdacf9aca56af35059b728584e9bb284c4791e8cfed1
    73ec641e7cc5b278ff680086b934c0abb2ec1f431b1d2173eac97019ff5100b0
    b510fc87ff47a07e7c748f67c768d7dd739adfdd7d082e933d6038ca554f3282
    d7aa9072028f4353dbef515b8eb6ff5867c039e1bd1f807a0cbed4655862060f

see if you can decipher the following:

(a) A simple example where $p^e < n$ (making the value of $n$ irrelevant):

c = 000608a5a8b32e3b218b49f9f0c33d05f135eff53dabee5ac00ec13e72997ef7
    c4b478d6b95cecc01ebcf7cecf24785ba28b4b88f605ee93d6502f24635624cc
    f4772e0d7334d125e047853c4a42e21d4bc3412729b0d230c1f5d6a2f8272bb1
    8927313328c6e431bf1e38d5200a5ac32293f4d58c467636a20bc7393d7133c3
    65880f07a2a29ad63fb21ebd2011b02dcd298fbd97c70d72fbc5c433a223987d
    898da302aa100efd95f43e7d6698a7eeea05dd97870583f149beda3aa6334ba4
    641c224e8c8f2cd61156abd42e4e3d03070c453656ec072526618e2ad74c87e8
    9c54397de803b8e2347f7daf413695e1df816782758f26a2abfe947c82ce9e9d

(b) A slightly harder one where $p^e$ is larger than $n$. You'll have to test for multiple values of $k$ to crack this one:

c = 9478dff8ca00aa472291b24a2db6288c4a865cfb53bff7c6ecb304a2d506bbbd
    16c4d26584657c17693becbdbba5a9bb18d462d72d52ae10bfe3edf906120bc2
    b0bec55f529f8eb2a0ae6cd997db467c53c463d7ed44790c7917b76dc6992a4c
    db7362e93eb3f4f2bb433d7256793a5992891a86ce87edc4234ec81e83c7ecc7
    d7659fa3639a1e299745c8ef5bd632928cb4871f19a6bd63ec974e45ac132f04
    f53f1e5c0e4a12d008783e31650816d2c78d9ec84ecd828a5ed7d915bf7a9a08
    c23ebb85e69c9c2a3bef0d4a77b28a62db65f437e019062a74891ad17c3a9c58
    ba73644a3097de31dbd5a13349f7a3f031d2352cbba680525e4249147aa58053


Are coprocessors (Intel Phi) a threat for modern key stretching functions? Modern key stretching functions (password-based key derivation functions, also used for password hashing) are memory-hard to mitigate parallel attacks, and as far as I know this is working well. Last year there was the password hashing competition (PHC 2015) where new password hashing functions were presented, Argon2 is going to be the new recommended password hash.

In the last few years Intel introduced its Xeon Phi coprocessors, which are devices with a moderate numbers of cores and great memory. At first sight this seems to be the perfect weapon for a hardware-accelerated dictionary attack (or brute-force) on these memory-hard KDF.

Is it really feasible? How?

If yes, is there a way to emulate this architecture's behaviour on such tasks?

The key idea of memory-hard functions like scrypt and Argon2, as I understand them, is to analyze the cost to the attacker in terms of a time-area product.  Time is how much time the attacker spends.  Area is how much silicon they use for the attack.  The attacker is going to allocate a given area, but once that amount is fixed:

More cores means less memory dedicated to each core;
More memory dedicated to each core means fewer cores.

This sort of analysis should still apply to the coprocessors you bring up.  Since they offer lots of memory per core, this must inevitably come at the cost of fewer cores than could otherwise be put in the same area of silicon.  But if the functions' time-area product cost analysis is correct, the attacker should be unable to gain an advantage this way; the speed each core gains from its generous memory allocation should come at a corresponding loss in parallelism.

Note in passing that:

Memory complexity implies time complexity (using memory requires time).  So algorithms that use a lot of memory are by necessity going to be (at least) proportionately slow.
Argon2 supports tuning the memory and time cost more or less independently.  I.e., for a given amount of memory, we can always raise the time cost further to thwart a high-memory but low-parallelism attacker.


Is perfect forward secrecy (PFS) possible without public key cryptography I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public key) cryptography. Am I missing something? Can PFS be achieved with symmetric cryptography and preshared keys only.

Yes, perfect forward secrecy is possible using symmetric primitives alone.

Take for instance a set of one time pads:

Alice generates two identical stacks of one time pads and hands one of the stacks to Bob.
Alice encrypts a message with the first one time pad and then passes the ciphertext to Bob.
Bob decrypts the message with the first one time pad and then both Alice and Bob destroy the first one time pad. So long as all copies of the one time pad are destroyed the ciphertext is now undecipherable.
The next message is passed using the second one time pad and at the conclusion of that protocol round all copies of the second one time pad are destroyed. And so on.

This basic protocol achieves perfect forward secrecy.

Of course it's likely not a practical protocol for many applications as, for instance, it requires secure advance exchange of a set of one time pads and the message length is limited by the length of a one time pads which much be agreed in advance. Nevertheless you can start from this model and apply some basic cryptographic improvements such as:

replace each one time pad with a key and a stream cipher so now we just need to exchange a set of keys
replace the set of keys with a single key and a one way function to obtain the next key so now we just need one key (and of course you simply destroy the previous key each time you derive the next key).

It's not difficult obtain a relatively practical scheme assuming pre-shared keys. The security of this construction is not too difficult to bound (How secure is the stream cipher? How secure is the one way function?).


Is this DH variant a workable zero knowledge proof? I encountered the use the following protocol as a zero-knowledge proof (argument?) of knowledge of x given y=g^x for a typical DL group:

Verifier chooses c and sends g^c
Prover responds with g^(cx)

It is simpler and more efficient than Schnorr. Intuitively it seems satisfactory. It is zero-knowledge (can be simulated) and I cannot come up with a strategy for responding without knowing either x or c in advance.

That said, I cannot write an extractor for it (and if one did exist, it seems it would break DH key exchange). So it is not provably sound but let's pretend this fact isn't enough to scare me away. I am wondering if anyone can shed more light on why it might be problematic to do this in practice.

why it might be problematic to do this in practice.

One issue with it is that it potentially allows the attacker an Oracle to the cDH problem.

For example, suppose the Prover uses his $g^x$ value as his key share with a DH key exchange with Alice, who sends $g^a$, and both sides arrive at the $g^{ax}$ secret value.

Then, what your protocol would allow an evil Verifier to do is ask the Prover to prove that he knows $x$, and submits $g^a$ (or a blinded version) as his challenge; the Prover sends back $(g^a)^x$, and that gives away the secret value.


If the plaintext contains the key used to encrypt the ciphertext, is the ciphertext easier to decrypt? I have a symmetric key which can be used to encrypt plaintext and decrypt the resulting ciphertext.
I use it to encrypt a plaintext which is a copy of the aforementioned key.
My adversary gets a copy of the resulting ciphertext.

Assuming my adversary knows that the plaintext is a copy of the key,
is there a way they can guess my key more easily than if the plaintext wasn't the key?

Note: I am new to cryptography so if there is a flaw in my question I will be happy to clarify.

There aren't any known generic attacks against this setup to work on arbitrary ciphers. On the other hand, the standard notion of IND-CPA security does not imply security when encrypting your own key.

I don't know of any commonly used block or stream cipher which has trouble with this setup, but one could be created and might even exist.


Is there a reason to use multiple hashing algorithms in a single system? I came across an authentication system Here that uses multiple hashing algorithms to hash data in different stages of the authentication.
My question is what's the rationale behind this?
If a hashing algorithm is secure (or has been secure so far, like SHA-256) why use different ones?
For example: When someone/something is registered in the system, its registration token is generated using algorithm H0 and when it is doing some other actions in the system it uses another hashing algorithm like H1.

A protocol might rely on using some string $x$ as an index into a set of uniform random bit strings $H(x)$.  The security of the protocol may rely on the $H(x)$ being uniform random and independent for different $x$.

A complex protocol may rely on having multiple independent uniform random bit strings for any particular string $x$, used for different purposes in the protocol.  If you use the same $H(x)$ for both purposes, the security may evaporate.

Here's an example: A deduplicating encrypted storage scheme like Tahoe-LAFS needs to derive an encryption key for each file it stores, and needs to choose a storage index that depends only on the content.  Using a single hash function for both—$H(x)$ as the encryption key, and $H(x)$ as the storage index—is a fatal mistake: a malicious storage server can now decrypt every file you store on it.  But using two different hash functions prevents this: knowledge of the storage index $H_1(x)$ doesn't help to find the encryption key $H_0(x)$.

In practical terms, we implement $H_0$ and $H_1$ in terms of a single hash function with a specially formatted input for ‘domain separation’: $H_n(x) := H(n \mathbin\| x)$, where $n$ is some prefix-free encoding of an integer as a bit string—say the 32-bit little-endian encoding.


Best method to achieve authenticated encryption with openssl Problem

I want to send a plaintext document between from myself to someone else over an untrusted link. I want to firstly stop third parties from reading the document, I want the receiver to be able to authenticate that any message they receive comes from me. Finally I want the receiver to be able to read the document. I have the ability to give the receiver a key by a trusted channel.

Proposed solution

the document is encrypted with a symmetric cipher. The aes-key I was going to use for that could be turned into a signature. e.g.

openssl pkeyutl -sign -in "aes.key" -inkey privkey.pem -out sig.nature

This signature is not used for authentication (a separate signature based on the hash of the encrypted file is used for that), but it seems to hide the value of the key, which can then be extracted with the public key, e.g. openssl rsautl -verify -inkey pubkey.pem -in sig.nature -pubin >> aeskey.recov

The public key will not be made public, but will be given to the reciever via a trusted channel and secured. I understand however if the public key is ever compromised, then all my encrypted documents can be decrypted.

Is this valid (providing the public key remains private) or is there a better way to do this?

If as you say you

  have the ability to give the receiver a key by a trusted channel.

then there is no need to involve any public key cryptography here. Just generate a symmetric key and send that key to your friend over the trusted channel.

Later, once you are ready to send the file, simply encrypt the file using an authenticated encryption mode and send the encrypted file to your friend. They can then use they key to verify the ciphertext's authenticity and decrypt.

You're saying that you specifically want to know how to do that with the OpenSSL commandline tools. This is a bit off-topic here, but nevertheless here we go.

Disclaimer: Do not use anything I write below in any actual application, I make no claim whatsoever that the use of openssl described below is actually secure in practice.

Note, I'll be using bash syntax in the following, I have no idea if it works in other shells.

First thing we need to do is generate keys. We'll be using AES-128, so we will generate 16 random bytes and store them in a key file. (encoded as hex to make our life easier later on.)

openssl rand -hex 16 > enc.key

we will also generate a separate MAC key, I will explain why in a minute:

openssl rand -hex 16 > mac.key

These two files you will give to your friend.

The first idea -- since we want an authenticated encryption mode -- would be to use something like AES-GCM, sadly however, the commandline tool openssl enc will then tell us that

  AEAD ciphers not supported by the enc utility

Bummer! And the authors are unwilling to change that.
So we will have to do the authentication the hard way. For example with AES-CTR + HMAC. This is why we created a separate MAC key before.

And because the authors of OpenSSL really want you to shoot yourself in the foot: If you actually specify a key, then the openssl enc utility will not create an IV for us, so we will have to do that ourselves as well.
So let's get going. We generate an initialization vector

openssl rand -hex 16 > file.iv

and then encrypt our file file.txt using AES-CTR using the generated IV and the key we previously exchanged.

openssl enc -aes-128-ctr -in file.txt -out file.aes -K $(cat enc.key) -iv $(cat file.iv)

compute the HMAC over both the IV and the ciphertext

cat file.iv file.aes | openssl dgst -mac HMAC -macopt hexkey:$(cat mac.key) -out file.mac

and now you can send file.iv,file.aes,file.mac to your friend.

Then again, because the OpenSSL authors really, really want you to shoot yourself in the foot, the openssl dgst utility naturally does not support verification. Instead your friend will have to do verification by hand:

if [ "$(cat file.iv file.aes | openssl dgst -mac HMAC -macopt hexkey:$(cat mac.key))" == "$(cat file.mac)" ]; then
    echo "MAC verification succesful."
    openssl enc -d -aes-128-ctr -in file.aes -out file.txt -K $(cat enc.key) -iv $(cat file.iv);
else
    echo "MAC verification failed."
fi

And if everything went well they should now have the plaintext back.

By now I hope every reader has realized that there's way too much that could go wrong in all of this and has decided not to do encrypted file-transfer by hand.


How can mega store my login details and still be secure? I understand how Mega's encryption works. For a quick summary of all those in the future looking for an answer on this... here is how it works:

Upon first signing up for an account you make a username and password. It also generates a symmetric key which is used to encrypt your files and a RSA key pair to share secrets securely when files are sent to other peoples "inboxes". Once the client has both these, the symmetric key is encrypted with your password and uploaded to the server. This way only someone with your password can decrypt your symmetrical key and then decrypt your files. I'll leave it at this for now as thats all that is relevant to my question.

If my symmetric key is encrypted with my password, no matter how secure my key is would it not still be as weak as the hashing function they use to store my password on their server? This ties into my second question, do they even store a hash of my password? I'm thinking along the lines of no, as it would weaken the encryption hugely, but Mega still needs to be able to determine if your login details are correct. How can they do this without compromising their encryption?

This may be the wrong place for asking this, so please move it if appropriate.

Here are some hints on how it's done on Mega:

The password provided is passed through a KDF to derive a key, that is used to en-/decrypt the master key (later provided by the server through an API call).

To bring it down to the crucial bits: The KDF applies $2^{16}$ rounds of AES-128 with it. The details can be found in the function prepare_key() of the web client in file crypto.js.

The user supplied password itself is never sent over the wire. And the master key is only decrypted client side using this password-derived 128 bit AES key.

To log in against the Mega servers, which gives one a valid session that allows one to access the (encrypted) master key, a token is computed. This token is computed using the derived key (see above) by running it through an additional series of $2^{14}$ rounds of AES-128 (see the stringhash function in crypto.js) after "joining" the user's email address with the above mentioned derived key.

D.W. is right, that the procedures in place are unfortunately not properly documented, yet. This is a severe shortcoming that needs to be rectified over time. Having said that, newer cryptographic work by Mega is paired with documentation in the form of a white paper as it is implemented to allow for peer review. These white papers are currently not openly published, yet, but interested parties have received these easily as needed or as requested, as they're still somewhat in flux.

If anybody is interested in further information, please feel free to email crypto@mega.co.nz for this to get first hand answers. However, that should still hold nobody back from discussing here or elsewhere, though it seems not easy to get explicit answers from the Mega developers here without letting them know of a question raised here.

Update:

There's an independent study that has been conducted by a researcher team in Spain: English PDF. They have dug into the available JavaScript code and reasoned on it. Except for minor flaws, the information is pretty much correct.


Is using the same MAC twice insecure? I was thinking last night about whether or not a HMAC-Encrypt-HMAC would be secure if you used the same HMAC key.

Here is the full recipe:

Compute a HMAC on the data to encrypt, and append it to the data.
Encrypt the data with AES_CTR_256.
Compute another HMAC, this time on the encrypted message+HMAC combo, and append it the the ciphertext.

Would using the same key, eg. thisisareallyinsecurekey, on both the HMAC's be cryptographically secure? Or would I need to use different keys for each HMAC?

No, you can use the same HMAC key for any message, including an already HMAC'ed message (regardless if the HMAC value is encrypted or not).

The key in HMAC is protected by the one-way hash function used internally, so getting the key should be hard.

The collision resistance and other security properties will also prevent an attacker from generating a HMAC based on a previous HMAC value. The way that HMAC is preventing length extension attacks may be very important in that regard, because Merkle-Damgård based hashes do (generally) not protect against those. MD5, SHA-1 and SHA-2 (but not SHA-3) are all MD-hashes and vulnerable to length extension attacks.

It is much harder to proof that using the same key for AES is also secure. There may be a mathematical way of retrieving key data if the key is reused in any kind of algorithm. The chance that it is possible to use relations between the algorithms to get information on the key or plaintext message is rather small though. Still, most cryptographers would prefer to use a separate key for different algorithms unless any weakness has been ruled out (as in most AEAD schemes that use a single key, for instance).

Note that this answer is for the security of the HMAC construction itself rather than the security of the entire protocol. Attackers may still perform replay attacks where a previous message and authentication tag are resend to the receiver by the attacker. The protocol should prevent those (e.g. by including a unique message ID in the message).

As Yehuda has already hinted: it isn't apparent if this scheme would be beneficial in any way; you may perform an additional run of HMAC without security benefits. If this is the case or not depends on your use case (maybe you do want to store the decrypted plaintext message together with valid, pre-generated HMAC; that would be a strange use case, but we don't know).


AES number of Round calculation I wondering about the formula for calculating the number of AES rounds.

The formula is $R=(\text{Keysize}/32)+6$

I would like help understanding why we divided by $32$ and add $6$ in this formula.

i wanna help to understand why we divided by 32 and add 6 in this
  formula

AES is defined for three key-sizes: 128, 192 and 256 bit with 10, 12 and 14 rounds respectively. These round numbers have been tabulated originally (that is no continuous function was given) and why these were chosen is because they offered the optimal (or at least a very good) trade-off between security and performance.

Now if you want to turn these three points into a continuous function, you can do interpolation and this will return you the function you found: $$R=k/32+6$$

as clearly $10=128/32+6, 12=192/32+6$ and $14=256/32+6$.


Would data be secure if a cryptographically secure PRNG was used for encryption? For example, say you have a client and server. You use asymmetric encryption to securely deliver two seeds from server to client. Each user then seeds two PRNGs (one for incoming data, one for outgoing). Then when they send data over the network, they add a new randomly generated byte (from the outgoing PRNG) to each unencrypted byte. The receiver can decrypt using their incoming PRNG which has the same seed as the senders outgoing PRNG. An HMAC could also be used to verify integrity and authenticate messages.

I was just musing over this idea. I'm a total novice to cryptography, so I'm sure there's something flawed with this. I would just like to know what the flaw is?

(The PRNG I'm looking at is ISAAC which is also a stream cipher, but would this work with any PRNG, disregarding speed?)

EDIT: Also, if not secure by itself, would it be possible to do this on top of AES? Is there no point (AES is already secure enough)? Or would it actually hurt security?

A PRNG with a seed $S$ whose output is combined with the plaintext is called a stream cipher with the key $S$. So assuming that the details are filled in correctly, what you're describing is a stream cipher algorithm with two session keys, one used in each direction. Each seed/key must be unique, and the combination must ensure that each output bit has a $1/2$ probability of being flipped (xor is common, but addition of bytes would work too).

If you have an encrypted communication channel, then it's already using a stream cipher, which may be built on AES. (Note that AES is not a stream cipher — it's a family (128, 192, 256) of pairs (encrypt, decrypt) of algorithms that operate on blocks of exactly 128 bits. There are ciphers built on top of AES with a mode of operation, which result in a block cipher or stream cipher.) For example, AES-CTR is a popular stream cipher. AES-CTR is also a popular PRNG, for exactly the same reason.

Combining your scheme with another cipher would mean, in fact, chaining two ciphers. This is hardly ever useful, but is at least as strong as the weakest cipher if the ciphers are not correlated. (Possibly not as strong as the strongest cipher, because the weakest cipher may leak information.) Correlation can lead to catastrophic failures — for example, if you encrypt twice with the same stream cipher with the same key, you get the original stream.

A stream cipher only ensures confidentiality, not integrity or authenticity. For example, AES-CTR is trivial to modify: flipping a bit of ciphertext results in the same flipped bit in the plaintext (this applies to any stream cipher that uses xor as the combination function). HMAC or some other form of MAC can ensure integrity and authenticity. Alternatively, you may use a mode of operation that performs authenticated encryption, such as CCM or EAX which are CTR combined with CBC-MAC or CMAC.

Further reading: Is modern encryption needlessly complicated?

 I'm only rehashing what's been said in comments really, just so that this question is answered.


Key management for military GPS receivers I wonder what encryption scheme is used in high-precision encrypted GPS streams (the so-called “P(Y) code”). If there's a master key needed, then it has to be in every device. Yet the master key doesn't seem to have ever leaked (unlike like game consoles or Apple devices).

So what could explain why military-precision channel GPS receivers haven't been hacked yet? How does the protocol work?

Am I going to regret posting this? There seems to be enough non-classified information available about GPS to answer this question.

I see 3 reasons why P(Y) encryption is different and less likely to be hacked than game console encryption:

Hardware containing the GPS decryption key is more difficult to obtain than hardware containing the game console decryption key.
Now that selective availability is turned off, even civilian receivers have positioning accuracy about as good as military receivers -- eliminating the biggest benefit of obtaining the GPS decryption key.
(The other abilities that key gives a person -- receivers that are more resistant to spoofing, and spoofing transmitters that can cause even anti-spoofing military receivers to give bad location data -- are useless unless someone broadcasts spoofing transmissions, which for various reasons few people are willing to do).
From what I read on Wikipedia about the selective availability anti-spoofing module (SAASM) and the previous PPS-SM system,
there is apparently no master key.
Periodically a fresh new (and I suspect completely unguessably random) key is generated, distributed to all military units that require it, and then uploaded to the GPS satellites.
After that the old key is pretty much useless.
So even if one GPS decryption key did leak, it would only be useful for a short time.


How do the following new (2013) ECC curves compare in security or efficiency? I read about the following "safe" ECC curves and notably, secp256 and all the NIST curves are marked as "unsafe" when compared to more modern curves.

I need a curve for signing or encryption, (or both) but not sure how to choose from the following:

M-221
E-222
Curve1174
Curve25519
E-382
M-383
Curve383187
Curve41417
Ed448-Goldilocks
M-511
E-521

Questions:

Are there performance, size, or power efficiencies from one curve to another?
Perhaps more important, are there security improvements over a given curve?

Are there performance, size, or power efficiencies from one curve to another?

The larger the curve, the larger the keys and signatures, and likely the slower the computations. There are exceptions to the last one – curve parameters do affect how efficiently they can be implemented, so some curves with good parameters can be faster than slightly smaller curves.

  Perhaps more important, are there security improvements over a given curve?

All of them should be safe, but the larger curves have more security margin.

  If a new alt-coin (Bitcoin) were created today, which curve is ideal?

Since signatures and public keys appear in the blockchain, having them be small would be great. Having signature verifications take little time would also be good, since that's time wasted.

Curve25519 has 256-bit keys and 512-bit signatures, and is known to have a fast implementation (Ed25519 for signatures). Especially if it gets standardized, it would be a decent choice.

Unless there's some kind of a breakthrough, 256 bit curves with 128-bit security should be enough until/unless quantum computers break ECC. For a post-quantum altcoin, you could use e.g. hash signatures, but that would expand the blockchain quite a bit.


RSA - are we able to encrypt into any possible ciphertext in $Z_n$ given a specific key? Given a public key $(e,n)$, if we are free to choose the plaintext does that mean we are able to generate any possible ciphertext in $Z_n$ ?

Because if we were given $e$ we can say that the decryption key is $e^{-1} = k \mod n$ and then choose the ciphertext we wish to generate, say $c$,  perform $c^k$ and that shows that any ciphertext is "reachable" via encryption given a specific key and some plaintext?

Is that correct?

Edit: The question is theoretical so we assume we know both the public and the private key.

Given a public key $(e,n)$, if we are free to choose the plaintext does that mean we are able to generate any possible ciphertext in $Z_n$ ?

Yes

  Because if we were given $e$ we can say that the decryption key is $e^{-1} = k \mod n$

Not quite; the decryption key (which is traditionally named $d$; I'll leave it $k$ using your terminology) is related to the encryption key as $e \cdot k \equiv 1 \pmod{ \text{lcm}(p-1, q-1) }$, where $p, q$ are the prime factors of $n$, or in other words $e^{-1} = k \mod \text{lcm}(p-1, q-1)$.  Other than that detail, you're correct.

  and then choose the ciphertext we wish to generate, say $c$, perform $c^k \bmod n$ and that shows that any ciphertext is "reachable" via encryption given a specific key and some plaintext?

That is correct...


The question is referring to Nigel P. Smart's The Discrete Logarithm Problem on Elliptic Curves of Trace One, in Journal of Cryptology (1999) (earlier version). Quoting the intro:

(…) we describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice, the method described means that when choosing elliptic curves to use in cryptography one has to eliminate all curves whose group orders are equal to the order of the finite field.

Trace of an Elliptic Curve: For an elliptic curve $E$ defined over $F_q$ with $\#E(F_q) = q+1−t$. The $t$ is called the trace of $E$.
In the specification of secp256k1 it is apparent that $n$ (the curve's order¹,²) is not equal to $p$ (the order¹,³ of the base field). In other words, the trace $t=p-n+1$ is not $1$.
Thus Smart's attack can't apply to secp256k1.

Off-topic note: assertions are there to stop execution before code does a silly thing. Removing an assertion without other code change working around the asserted limitation is seldom a good idea.

¹ The order of a finite group or finite field is how many elements it has.
² That order is the number $\#E(F_q)$ of points on the elliptic curve including the neutral "point at infinity".
³ That order is $p=q$, the prime modulus. The finite field considered is integers modulo $p$, noted $(\Bbb Z_p,+,\cdot)$, equivalently $F_q$.


Why does a nonce prevent a replay attack? I have a question about a cryptographic nonce. I understand the use of a nonce, however there is one particular part that I don't understand. Please consider the picture below.

I don't really understand why a replay attack is impossible, if the nonce is not encrypted. Because, if it isn't encrypted and I (as an attacker) know the nonce, then I can predict the next number (N + 1) and send that to Bob. Obviously I can't generate a MAC by myself (well, I can but Bob won't trust it) - I don't have the corresponding key; but I can send the MAC, who is previously generated by Alice, again with a "new" nonce (N + 1)..?

Could someone explain why this won't work?

Thanks in advance.

Given no knowledge of the MAC key and that M1 != M2, it is not possible to compute MAC(K, M2) from MAC(K, M1).

More generally, it isn't possible to determine the MAC of any message you haven't already seen. (Again, without the key.) The definition of a nonce is a number which is only used once with a given key.

Bob ensures that nonces are only used once by rejecting requests unless the nonce value Alice submits is strictly increasing.

There are other problems with this protocol. I assume it's meant to be used to authenticate users. No information is transmitted besides what is basically just proof that Alice knows K.

The protocol functions a lot like a one time password scheme and has the same limitations. It doesn't prevent MITM attacks, session hijacking, or server impersonation. It is not a full communication protocol.

Sometimes people comes up with schemes like this to control locks or appliances. It is unsafe to use such a protocol with "toggle" signals. An authentication request could be blocked, leaving a user's device in the state opposite from the state they believe it is in.

It is also possible to combine blocking Alice's requests with a replay attack. One could block Alice's request to engage a lock, trespass, then play back Alice's message to make it look like the lock was engaged the whole time.

Delayed playback can be solved by Alice instead sending MACK(NA || timestamp). (As long as Alice and Bob have trusted synchronized clocks.) An acknowledgment message could allow Bob to tell Alice that the command was received. The ack would needs its own authentication tag, otherwise it could be spoofed.


Are rainbow tables still useful? With unsalted passwords becoming rare, and stream ciphers having a significantly large state, are there currently any widely deployed systems still vulnerable to such time-memory-data trade-off attacks?

If I were to show a small generic improvement to rainbow tables, what would be a good problem to demonstrate on?

If you just want to provide a generic improvement I'd just target password hashing. If you think that directly running passwords through a cryptographic hash is history then I can show you plenty of StackOverflow questions where it is still being performed.

For a generic attack you don't need a new problem; just focus on your improvement and let your solution be interesting on its own merit.


Stuck on an affine cipher exercise I'm tired and can't seem to get the right answer for the following exercise:

  Alice sends a message to Bob, but he doesn't know the key. He knows only that the first two plaintext letters are C and R.

  The ciphertext is turgifsfsferbi.
  The plaintext is cryptananalyst.

The first two plaintext letters are ${\rm C} = 2$ and ${\rm R} = 17$, while the corresponding ciphertext letters are ${\rm T} = 19$ and ${\rm U} = 20$.  The encryption formula is $f(x) = ax+b$, so we have:

\begin{aligned}
19 &= \phantom{0}2a+b \\
20 &= 17a+b,
\end{aligned}

which I solved to get $-1=-15a \implies a=15$
and $b=3$.

For decryption, we use the formula $f(c)=a^{-1}(c-b) \bmod 26$.  The inverse of $a=15$ modulo $26$ is $a^{-1} = 7$, so for the first ciphertext letter I get:

$$7 \times (19-3) \bmod 26 = 7 \times 16 \bmod 26 = 8 = {\rm I} \ne {\rm C}.$$

So where is my mistake?

If I'm reading your question right, you've made two simple math mistakes:

The solution to $-1 \equiv -15a \pmod{26}$ isn't $a = 15$; it's $a \equiv 15^{-1} \pmod{26}$, or $a = 7$.
I'm not sure where you got $b = 3$, but it's not correct, either.  The right solution, using the correct value of $a = 7$, is $b = 19 - 2a = 19 - 14 = 5$.

(FWIW, using the incorrect value $a = 15$ should've given you either $b = 15$ or $b = 25$, depending on which of the two original congruences you plugged the wrong $a$ into.)

With the correct values of $a$ and $b$, your decryption formula works just fine: $a^{-1} = 7^{-1} \equiv 15 \pmod{26}$, so:

\begin{aligned}
15 \times (19 - 5) &\equiv \phantom{0}2 \pmod{26} \\
15 \times (20 - 5) &\equiv 17 \pmod{26}.
\end{aligned}

Both of your mistakes seem like simple lapses of concentration.  Maybe you just need to take a break from your homework and go get some sleep first.


How to measure Cycles per Byte of an Algorithm? I am trying to measure the cycles per byte for $\mathop{SHA-3}$ reference implementation. I am using recommendations from Microsoft querying the performance counter. As you can see in the first snippet, cycles are measured before converting into microseconds. My code looks like the following:

QueryPerformanceCounter(&StartingTime);
SHA3_256(K_OUT, K_IN, length);
QueryPerformanceCounter(&EndingTime);

ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
printf("Elapsed ticks: %.20f \n", ElapsedMicroseconds.QuadPart / (float)(length));

But the results are definitively wrong. It is mostly something smaller than $0.9$. I would guess a value around $30$ Cycles per Byte. What am I doing wrong?

To perform a good check, please use a large number of iterations (i.e. a for loop) of calls to the cryptographic primitive with your specific data size. Then average these out.

To avoid compiler optimizations, be sure to print out the result after the clock has been stopped. For instance, you could XOR all the outputs together and print that out. Otherwise the compiler may determine that your call has no side effects and simply remove the entire call to SHA-3.

Note that internal operations are usually performed on 64-bit or larger registers, i.e. 8 bytes at a time. It is perfectly possible to have sub-one scores - although I admit that for SHA-3 the value of 0.9 cycle/byte does not seem likely.


What are the implications of quantum collision search algorithms like Ambainis for collision-resistant hash functions? I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet):

Post-quantum security of the sponge construction
Quantum Collision-Finding in Non-Uniform Random Functions
An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography

From the latter:

  From similar techniques [to Grover's], quantum collision search is known to attain
  $O(2^{n/3})$ query complexity, compared to the classical $O(2^{n/2})$. ... Our algorithm is the first to propose a time complexity that improves upon $O(2^{n/2})$, in a simple setting with a single processor.

My questions: can someone who's been following this research discuss:

Implications of this for security practitioners ... will we need to triple hash lengths instead of doubling them?
Is this family of quantum collision-finding attacks only effective against the sponge construction and SHA-3, or does it apply to hash functions more broadly?

Related questions that were asked and answered prior to these 2017 papers:

[2014] Space complexity of quantum collision search?
[2011] What security do Cryptographic Sponges offer against generic quantum attacks?

The query complexity, i.e. the number of times the machine evaluates the function as a black box, may be $O(2^{n/3})$, but that's not the only cost of an algorithm: the size of the machine and how long you have to run it figure in too.

So far, there are no implications of quantum algorithms for security parameters of collision-resistant hash functions.  Classical algorithms are still the cheapest algorithms for generic collision-finding, and would remain so even if Grover-capable quantum computers had the decency to merely exist.

The original Brassard–Høyer–Tapp algorithm[1] precomputes $H(x_1), H(x_2), \dots, H(x_{2^{n/3}})$ and stores them in a table $C$; then it applies Grover to find a preimage of 1 under the function $f(y) = [H(y) \in C]$, which reveals a collision in $H$.

Even if the communication costs for table lookup were zero (which seems unrealistic), this costs $O(2^{n/3})$ space, and the algorithm is expected to take $O(2^{n/3})$ oracle evaluations before finding a preimage under $f$ of 1, for a total of $O(2^{n/3})$ evaluations of $H$, and a total area*time cost of $O(2^{2n/3})$—far greater than the $O(2^{n/2})$ area*time cost of standard classical algorithms like the van Oorschot and Wiener collision search algorithm based on parallel $\rho$[2].

Variants of the algorithm have been proposed, but so far none of them has beaten the $O(2^{n/2})$ cost of the best classical algorithms in any plausible cost model even if qubit operations are no more expensive than bit operations—and most of them are much more expensive in any plausible cost model[3].  See here for an overview of some of the proposed algorithms and of problems in the cost models, and for broader context.

The Ambainis algorithm[4] takes a slightly different approach of a quantum random walk to find a repetition if there is one among a sequence of $M$ elements in $O(M^{2/3})$ time, which can be converted to an algorithm for finding a collision in an $m$-bit-to-$n$-bit function in $O(2^{m/3})$ queries.  But it also requires maintaining a data structure holding all $O(M^{2/3})$ queries throughout the algorithm.  So the area*time cost for a collision search based on it is $O(2^{2m/3})$, which remains far beyond the $O(2^{n/2})$ cost of classical collision search for any input size $m$ that gives a collision in $n$-bit outputs with nonnegligible probability.  What Czajkowski et al. describe[5] is a generic way to apply it to a sponge with $c$-bit capacity producing an $n$-bit output costing $O(\min\{2^{2c/3}, 2^{2n/3}\})$, which is essentially what you would expect.

And since the query complexity of a generic quantum collision search has a lower bound[6] of $\Omega((2^n/r)^{1/3})$ if $r$ is an upper bound on the number of colliding preimages, unless there are dramatic breakthroughs in storage costs it seems unlikely that this situation will change any time soon.


Will Fernet’s key function at any timeframe? I’m very new to cryptography and I need to use a symmetric cryptography approach.
My simple question is, will the key always at any time be able to decrypt the encrypted text?
The encrypted text may be years old, and key will be saved years before as well.
Is there any time factor applied that may make the decryption fail?

No, there is generally no time factor when it comes to decryption.
However, you should remember that even a single changed bit can cause decryption to fail. This is especially the case if that bit is part of the IV, authentication tag or nonce. So I'd rather worry about storage of keys and data. Disks may get stuck, flash may degrade or loose voltage differential.


Are pairings still the most efficient implementation for identity and attribute-based encryption? I read on Wikipedia:

  [...] pairings have also been used to construct many cryptographic systems for which no other efficient implementation is known, such as identity based encryption or attribute based encryption schemes.

Is this still the truth? I cannot find any newer sources for this. Is someone up-to-date on this?

I am just going to answer regarding identity-based encryption (IBE): I don't know much about the situation for attribute-based encryption.

Also, I am just answering based on today's situation: recent IBE constructions may prove to be very efficient (or not) in the future, and if you want to consider only post-quantum schemes you will have to discard IBEs based on pairings, Diffie-Hellman and factoring.

Pairings

So first, pairing-based IBE is arguably the most studied and mature kind of IBE. The wireless sensor networks (WSN) community has shown great interest in using IBE (there even is a book on it), and there exist many implementations of IBE targeted for WSN: you can for example google TinyTate, TinyPBC or TinyPairing. Dan Boneh's company, Voltage (which has been bought by HP), also proposes pairing-based IBE.

Lattices

There exist a few IBE constructions, but as far as i know, only one public implementation
 (full disclosure: I am a co-author of this paper). It is faster (by an order of magnitude) but less efficient space-wise (secret keys and ciphertexts are about 4 KB).

Also, the encryption and decryption operations can be efficiently implemented on embedded devices (as they are based on Ring-LWE, they have been implemented, just not under the "IBE" tag). For key extraction, I know of no public implementation.

Other technologies

As far as I know, IBEs based on other technologies are less efficient than either pairing-based or lattice-based IBE (depending on the metric of efficiency you choose). This seems clear for IBEs based on quadratic residuosity. Very recently, IBEs have been introduced based on codes or the Diffie-Hellman assumption. There is no implementation proposed yet, so it is hard to give an educated opinion on their efficiency.

Conclusion

If your metric of efficiency is space, the most efficient solutions are pairing-based, but depending on what you consider "efficient" there exist alternatives.
If your metric is speed, it is not true that no other efficient implementation exist (lattice-based ones are faster).
If your metric is "the implementation must be on an embedded device", that leaves just pairings (and lattices if and only if you only need encryption and decryption to be on an embedded device).


Breaking ciphertext using a quantum computer when the public key is not available As we know about Shor's algorithm on quantum computers it is possible to crack RSA / ECC easily if we have enough qubits.

Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Does it matter if we have many ciphertexts and corresponding plaintext for some of them that are generated using the same public key?

You asked:

  Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Typically not, with a few exceptions; here are the exceptions:

RSA signatures with deterministic padding (eg. PKCS #1.5) and a small to moderate $e$ (e.g. $e = 65537) - with two signatures (and corresponding message), we can recover the public key with a conventional computer (and then use our quantum computer to break it).
ECDSA signatures - with one signature (and corresponding message), we can recover the public key (with a few "false hits") with a conventional computer; we can then use our quantum computer to break it.

Things that likely look immune:

RSA encryption (which always uses random padding), or randomized RSA signatures (e.g. PSS); the relationships between the plaintexts would appear to be too subtle for the attacker to use them.
EdDSA signatures - because of how the public key is stirred in, the key recovery method we used with ECDSA doesn't work (and without the public key, the attacker can't compute $H(R, A, M)$, which you need to know to have a copy of generating a forgery)
ECIES - the ciphertext consists of $rG$ (for some random $r$) and a symmetric ciphertext that is keyed based of $rP$; the attacker could recover the value $r$ with his handy quantum computer, however without knowing $P$, there's not much else he can do (and having multiple ciphertexts wouldn't appear to help).


LFSR and Markov chain question This may seem an elementary question about LFSRs, and their link to Markov chains. LFSRs show Markov chain behaviour in that there can be a transition matrix defined over the LFSR, this follows from the very definition of the LFSR. Is there any formal formulation for the LFSR as a Markov chain?

In a standard linear feedback shift register (LFSR), the succession of states
(generally taken to mean the shift register contents) is
predetermined; there is nothing random about the state transitions. Given
any state and the feedback polynomial, the next state can be readily computed.
Indeed, the states recur in periodic cycles.

In contrast, in a Markov chain, the next state cannot be determined from
knowledge of the current state; all we know are the (conditional)
probabilities that the next state is $S_j$ given that the current state is
$S_i$.  Think of it this way: the transition matrix of a $N$-state Markov
chain is a $N\times N$ matrix of transition probabilities. In contrast,
an LFSR with $N$ bits/symbols has $2^N$ (more generally, $q^N$) different
states, but its transition matrix is only an $N\times N$ matrix.  If you
were to write down the transition matrix in Markov-chain style, it would
be a $2^N\times 2^N$ matrix and all the transition probabilities (entries
in the matrix) would be either $0$ or $1$ and there would be exactly
one $1$ in each row and in each column, that is, it would be a permutation
matrix.


Pseudorandom Permutation equals to PRF? I stuck on the same problem in a cryptography, as stated in this question

I found following statement in famous textbook by J. Katz (main wiki PRP article refers to this textbook)

  PROPOSITION 3.27 If F is a pseudorandom permutation and additionally
  L-input(n) >= n, then F is also a pseudorandom function.

So the question is extremely simple, but I spent hours trying to find an answer.
If Fk(x) - is a PRP which takes n-length input, uniform n-length key k, and x - as an input n-bit string. How it can be a pseudorandom function?!

Permutation means F(00000) = 00000 ? So the function just reorder given input bits in pseudorandom manner determined by key K?  If not, can someone explain what actually does a PRP? And what is the difference with PRF? Except invertibility.

A psuedorandom permutation is a permutation in the "arrangements" sense if you examine all possible n-length blocks. It is not a shuffling of the block that you input to the function. The function takes the whole block and replaces it with another, completely different block.

To see this, picture encrypting a counter using a blockcipher with a given key. It would spit out one random block after another. Encrypt the same counter sequence using a different key, and it will spit out different random blocks. If you were to encrypt all possible values of the counter under the two different keys and examine the two resulting sets of ciphertexts, you would see two different arrangements of all n-length blocks. This is the "permutation" part of psuedorandom permutation.

The prototypical permutation producing algorithm is the Fisher-Yates shuffle. You could view a psuedorandom permutation like applying a Fisher-Yates shuffle to the sequence of counter blocks, where each entry is one possible n-length block.

As for the difference between a prp and a prf, I'm pretty sure we have an answer to that on the site already.


How does sending compressed points in ECC can limit the attacker's capabilities? While sending an EC point we mainly have two options, send it compressed or uncompressed. The uncompressed has prefix 04 and compressed has 02 or 03 which indicates which $y$ to choose. Actually, it is costly, first find the $y$ and $-y$ from the curve equation;
$$E(K): y^2=x^3+ax+b$$ a cube and a square root is required. If the base field is prime then select according to the last bit of $y$ or $-y$. Select the one with 0 if 02 is encoded and select the one with 1 if 03 is encoded.
For 32-byte coordinates, this can save 31-byte of message size ( one byte increased, we send 65 for uncompressed due to prefix). If we consider the cost, it increases the computation, and sending 64-bye instead of 33-byte is not really a huge issue.
Now, Bernstein in their slides mentions that

Never send uncompressed $(x; y)$. Design protocols to compress one coordinate down to $1$ bit, or $0$ bits! Drastically limits possibilities for attacker to choose points.

How does sending compressed points in ECC can limit the attacker's capabilities?

If the implementation is using uncompressed point exchange, The attacker gets an opportunity to supply points to Bob that are not in the Curve which was selected by Alice and Bob. The attacker will supply points to Bob that are in curves of a lower order which makes it possible to estimate Bobs secret.
Therefore if the implementation ensures that Bob has to calculate the point then he will come to know that the point being provided is not on the curve selected by Alice and Bob in the first place and will result in coming to know about the attack or the corruption.
Two basic constructs in ECC are the standard curves and Implementation by programmers. The argument is should use of compression be specified in the standard or should be left to the implementation. Since compression is so important for ensuring security it should be made part of the standard( As per the presenters ) to prevent implementation errors.


Does length-prepending stop length-extension attacks? Does length-prepending stop length-extension attacks on Merkle-Damgård hash functions, assuming that the length is checked?

Yes, if the length is formatted in a constant-size value (e.g. 64-bit field) or in an otherwise uniquely decodable manner.

With such a length field, no hash input can be the the prefix of another valid input. Thus there is no length-extension attack.

(Assumptions include that you reveal no intermediate values, of course.)


Which encryption algorithm is used for password protecting a file I am using a library to password protect my files into a zip file. The implementation has been taken from this piece of code.
I want to understand which algorithm(if any) has been used here to password protect the files.
The code is minimal and easily readable.
Any leads on this would be helpful.

This is Traditional PKWARE Encryption as documented in the PKWARE ZIP specification (see Section 6.0). It's an old stream cipher which suffers from a known-plaintext attack (see Biham and Stay publications) and has been replaced with AES in newer ZIP archive utilities.

See a lengthy answer here regarding the possibility of ZIP file password recovery when this cipher is in use.

Various people have implemented the known-plaintext attack and code is available (pkcrack and bkcrack).


When is factoring semi-primes thought to be hard? In Lattice Cryptography, problems like LWE or SIS have relatively easy to specify distributions that are thought to be average case hard.
I'm curious what specific distributions on semi-primes $(p,q)$ such that $N = pq$ is a certain bit-length are thought to be average case hard.

Essentially, there are many different special-case factoring algorithms for when $(p,q)$ have some special structure (I've found Pollard's $p-1$ algorithm, William's $p+1$ algorithm fairly easily, things like Coppersmiths seems to apply if some number of the bits of $p$ or $q$ leak.

What I'm curious about is which of these attacks on semi-primes with special structure are devastating enough such that proper generation of $(p,q)$ should explicitly check that they don't have that structure.

In a certain sense this question is asking for current "best practices" for RSA modulus generation, but with the intent of getting pointers to why best practices are what they are (as in which attacks they avoid).

There are many different special-case factoring algorithms for when $(p,q)$ have some special structure.
  Which of these attacks on semi-primes with special structure are devastating enough such that proper generation of $(p,q)$ should explicitly check that they don't have that structure?

TLDR: None in modern practice. Except when there's a regulatory requirement for such explicit precautions.

There is now a large consensus that for semi-primes of cryptographic interest (say at least 512 or is it 1024 bits), we need to consider no special-case factoring algorithm when we care about the expected cost of factoring (using classical computers/hardware) one particular semi-prime generated per a process where both factors $p$ and $q$ are primes each picked independently and roughly uniformly at random in the same interval $[a,b]$, when $a>b^{0.9}$ and $a<0.99\,b$. A common choice is $a=2^{(n-1)/2}$ and $b=2^{n/2}$, which is guaranteed to give an exactly $n$-bit semi-prime.

There's a lot of headroom in both fudge factors $0.9$ and $0.99$, which are out of my head. The condition  $a>b^{0.9}$ ensures that the bit size of $p$ and $q$ is never too far apart, which optimizes resistance to ECM. $a<0.99\,b$ ensures that the interval is not overly restricted.

It is often added further range restrictions, and that's OK especially for large $n$. For example it can be added that $p$ and $q$ are $n/2$-bit primes with their respective top 4 bits set to 1110 and 1100, which gives absolute (rather than statistical) certainty that FIPS 186-4's requirement $\lvert p-q\rvert\;>\;2^{n/2-100}$ and required ranges are met for endorsed $n$, and complies to ETSI TS 102 176-1's suggestion $0.1<\lvert\log_2p-\log_2q\rvert<30$.
Note: The fudge factor 0.1 in ETSI's suggestion used to be 0.5, which was incompatible with FIPS 186. The whole suggestion seems obsolete.

The same selection rules is usually fine when we care about small (but still palatable) residual odds that the semi-prime is factored for a given effort. This is a significantly different metric though, and it can matter. E.g., it might be considered unacceptable that an adversary has 0.1% chance to succeed with \$1M cost in electricity, even though certain success for \$500M is acceptable. ECM's probability of success grows linearly with the computational effort, when that of GNFS remains essentially at zero until the necessary effort is spent. GNFS might thus be less a concern when considering residual odds.

The argument for the above choice of interval $[a,b]$ is that at the size $n$ considered, all known factorization algorithms worth consideration have their expected cost larger (and their residual odds of success for limited work lower) than GNFS or ECM:

we know how to improve resistance to ECM, and did that by random choice in an interval $[a,b]$ with $a>b^{0.9}$
we don't know how to improve resistance to GNFS for a given size $n$, other than by avoiding semi-primes amenable to SNFS, which is kept to negligible probability thanks to random choice in an interval with $a<0.99\,b$
MPQS, variations (PPMPQS, PPSIQS..) and ancestors (QS, CFRAC..), as well a the rational sieve, require more work than GNFS, and the gap increases when $n$ grows
Pollard's p−1 and William's p+1 have larger expected work than ECM for sizable fixed probability of success, given the order of magnitude of the factors and the fact they are randomly seeded.
Note: that does not quite hold for extremely small probability of success (more on that later).
Pollard's rho is outclassed by ECM on all counts, given the order of magnitude of the factors.
Whatever improvement of Fermat's method or trial division requires knowledge of the order of magnitude of one of the factor, and random choice in an interval $[a,b]$ with $a<0.99\,b$ give a wide margin against that.

Things are more muddy when we care about factoring $k$ semi-primes of size $n$, for large $k$ and $n$ not too large, especially any one among those semi-primes (rather than all). The later consideration matters to a system designer who wants assurance that no semi-prime among $k$ used will be factored (perhaps because there is no way to detect rogue use of a factored semi-prime, or no revocation list, which is common in Smart Card applications; or just because the excuse "that's only for one in 100 million devices issued" would be untenable from a public relations perspective, even if it makes perfect sense economically).

This "batch factorization" problem is much less studied, especially in the "any one among" variant. Daniel J. Bernstein and Tanja Lange's Batch NFS, in proceedings of SAC 2014, conclude that increasing $k$ allows asymptotic savings on the expected cost per factorization. However, that does not require a different method of choosing $p$ and $q$; and it tells nothing useful about the "any one among" variant.

We can't state with confidence that increasing $k$ leaves the expected effort for factoring any one among $k$ semi-primes unchanged, even if we additionally discount attacks with an overall negligible probability of success (which makes sense). We even have a hint of the contrary: when $k$ increases, the expected effort using Pollard's p-1 lowers; and there's a threshold when it beats ECM with random curves, which expected effort is independent of $k$.
Pollard's p-1 can be viewed as ECM on a special curve amenable to lots of optimizations. In practice, the strategy maximizing probability to factor a semi-prime (with randomly selected factors of about equal size) using the popular GMP-ECM program and some maximum amount of CPU time involves spending some sizable fraction of the effort with its built-in Pollard's p-1. The lower the CPU allowance (and the probability of success), the larger that fraction is. When we switch to factoring any one among $k$ such semi-primes for the same maximum amount of CPU time, the optimal proportion spent on Pollard's p-1 grows markedly with $k$. That's because we can afford to use less random curves. At some point ECM on general curves is not used at all.

In order to reach a situation where Pollard's p-1 is worth considerations, we would need to

somewhat discount NFS and QS algorithms so that ECM and friend are back into competition (perhaps because moduli have more than two factors as in multi-prime RSA, or/and one of the factor is small as in unbalanced RSA, or we are trying to lower residual odds of success for adversaries that will not manage to reach the work threshold or RAM requirement necessary for NFS),
and consider that an adversary is content factoring any one among many moduli.

Under such hypothesis, adding precautions in the generation of the semi-primes that block Pollard's p-1 could be beneficial to some degree (I wish I could make that quantitative). The same applies, to a lesser degree, for William's p+1. This may be why such precautions remain mandated by FIPS 186-4 section B.3 for 1024-bit semi-primes.

Notice that for Pollard's p−1 and William's p+1, such precautions are not implemented as checks (that would be too computationally intensive), but rather are built into the method by which the prime factors are derived.


Concatenation of two strong hashes may have striking weakness For any hash functions $H_0$ and $H_1$, it is easily proved that their concatenation $H_0\|H_1$, defined by $(H_0\|H_1)(X)=H_0(X)\|H_1(X)$, is at least as resistant as the strongest of $H_0$ and $H_1$ with respect to collision-resistance, first preimage resistance, and second-preimage-resistance. Here we study another commonly assumed notion of preimage resistance, possessed by common hash functions, that (I believe) could be totally lost by concatenation for uncommon hash functions.

For a hash function $H$, define $m$-bit preimage resistance as: given $m$ and $h=H(M)$ for a random unknown $m$-bit message $M$, it is computationally hard to find a message $X$ with $H(X)=h$. For an ideal $n$-bit hash (random oracle), breaking $m$-bit preimage resistance requires about $2^{\min(m-1,n)}$ hashes (queries to the oracle). Common hashes are expected to reach that security level. $m$-bit preimage resistance is desirable e.g. when hashing an $m$-bit password (+salt).

From an $n$-bit hash $H$ secure in the Random Oracle Model, can we construct two $n$-bit hashes $H_0$ and $H_1$ such that:

$H_0$ and $H_1$ each are secure in the ROM, to near the theoretical optimum;
for any $m\le n$, $H_0\|H_1$ has no $m$-bit preimage resistance (there's a fast algorithm to solve the problem defining $m$-bit preimage resistance)?

My guess is yes. A simpler construction than what I had in mind shows just that.

What's the best level of $m$-bit preimage resistance that we can demonstrate for $H_0\|H_1$?

If we use $H_1(X) = H_0(X) \oplus firstnbits(X)$, this would seem to be trivial.

EDIT: As Cédric Van Rompay pointed out, this is only a counterexample if $H_1$ winds up being preimage-resistant. This may not be a necessary consequence of $H_0$ being preimage-resistant, but I really only need one case where it is.


Implementing OpenSSL padding I'm conducting an experiment dealing with differences in padding across different aes operations for my Intro to Crypto class, and the question says OpenSSL uses PKCS5 padding, and that I need to prove this. All we've been taught up to this point was how to encrypt something by doing this:

openssl enc -aes-128-cbc -e -in example.txt -out example.bin -K 1001001 -iv 0100110

Now my question, really, is: Where do you implement the padding into this shell command, or is the padding automatically added, and if it is auto added, why can I not see in it my hex editor?

You can decrypt with the -nopad option and check the HEX output.

Example piped command :

$ echo "hi"
| openssl enc -aes-128-cbc -e -K 1001001 -iv 0100110
| openssl enc -aes-128-cbc -d -nopad -K 1001001 -iv 0100110
| hd

And  output :

00000000  68 69 0a 0d 0d 0d 0d 0d  0d 0d 0d 0d 0d 0d 0d 0d  |hi..............|
00000010


Output of a Linear Shift Register given Plaintext and intial state Given an initial state $S_0 = (0101)$ and plaintext $P = 1010101011$ I need to find the ciphertext.

The method to solve this was not taught in my coursework, and the information I have found online does not seem to apply to this.

Can anyone explain the steps needed to solve this?

Read the drawing assuming:

each of the four (about) square boxes $a_j$ initially (at $t=0$) holds one of the four  bits of $S_0$ (in reading order, unless otherwise stated);
information follows arrows (almost) instantly, except when getting into a square box where that is delayed until $t$ has grown by $1$ (in time unit or clock period); notice this implies that the content of the left square box is also (with negligible delay) on the arrowhead going straight down and the one going right-down;
there are three implicit short arrows between the four square boxes, oriented as the rightmost arrowhead;
each $\oplus$ symbol performs the exclusive-OR of all the ingoing arrows, and outputs that result to outgoing arrow, with no significant delay;
the plaintext bits are made available one by one (starting at $t=0$, and in reading order, unless otherwise stated) on the input side of the arrow marked "plaintext";
the ciphertext bits are what's at the arrowhead marked "Cipher-text" (with the same convention as for plaintext).

You can now manually compute what there is in each of the boxes, arrowheads, "plaintext", "Cipher-text", at any integer value of $t\ge0$ (or, more precisely, shortly after). Assuming increasing time matches reading order, you might want to format this as a table with $t$ increasing from left to right, so that the lines with "plaintext" and "Cipher-text" will contain the plaintext and ciphertext in reading order.


How does a preimage attack on MD5 break the security of HMAC-MD5? It was mentioned in an answer to a different question that

  it's possible that, any day now, someone might figure out a way to
  turn those into a preimage attack, which would compromise the security
  of HMAC-MD5.

Reminder: $\text{HMAC-MD5}_K(x) = \text{MD5}(K \oplus opad \mathbin\| \text{MD5}(K \oplus ipad \mathbin\| x))$

Given that the input to the MD5 calls in HMAC includes the keys I don't immediately see how this turns into an attack. Could somebody clarify?

I fail to see how an hypothetical black box doing a (first) preimage attack on MD5 could be turned into an attack on HMAC-MD5, even if that box was able to effortlessly find the admissible combinations of prescribed unknown bits in an otherwise known message, given the hash; for example, if that box returned the (likely: very few, like less than 3) possible first 128 bits of message, given rest of message and hash.

And I'm at least convinced that a key-recovery attack on HMAC-MD5 requires more than a few preimage attacks on either MD5 or its round function.

Updated rationale: a successful attack on HMAC-MD5 can't be made by guessing a key $K$ of $k$ bits using a preimage attack on either of the two MD5 composing HMAC, taken in isolation.

The output of the outer MD5 (the one with opad) is known, but one not knowing $K$ is facing the situation where the first $k$ bits of the hashed message are unknown, as well as the 128 bits produced by the other MD5 (that involves the unknown $K$ thru at least two rounds, thus is essentially random). A preimage attack on the outer MD5 is thus expected to return about $2^k$ solutions (each yielding a combination of $K$ on $k$ bits, and the result of the inner hash on 128 bits). We have to weed out which is the right $K$, which requires about $2^{k-1}$ tests involving the inner MD5 and the $K$ tested, to check if that matches the last 128 bits of the preimage. We have hardly reduced the effort compared to a brute force attack. The alternate strategy of computing the full HMAC-MD5 for each $K$ suggested by the preimage black box is no better, under the reasonable assumption that these $K$ are random-like, thus have moderate overlap.
The output of the inner MD5 is not known, thus a defining hypothesis of a preimage attack is not met.

If we break HMAC-MD5 into individual rounds, we similarly conclude that a preimage attack on any round taken in isolation can't break HMAC, because the attack is no better than brute force, or/and because the round's output is unknown.

However, if a preimage attack on MD5 (or/and its round function) was possible, the security argument we have on HMAC-MD5 would vanish, and the prudent thing would be to act as if HMAC-MD5 was broken.


Different ways/algorithms for implementing AES I have seen a couple software implementations of the Advanced Encryption Standard. They are pretty much straight forward, i.e. they are implemented exactly the same way as the AES is described. This makes an implementation of AES very easy to achieve. Nevertheless I was wondering if there are other ways of implementing it? Other algorithms for achieving a faster or more secure implementation?

For example, with ECC I know that there are different algorithms for implementing the point multiplication (double-and-add, double-and-add-always, Montgomery Algorithm).

So, are there different algorithms for implementing AES?

To my knowledge there are at least 4 ways to implement AES.

I. lookup tables

For simple blocs, lookup tables are fast but they are sensible to timings
attacks.

Here is an example of lookup table implementation:

b0 = T0[ a0 >> 24 ] ^ T1[(a1 >> 16) & 0xff] ^ T2[(a2 >>  8) & 0xff] ^ T3[ a3 & 0xff] ^ rk[4];
b1 = T0[ a1 >> 24 ] ^ T1[(a2 >> 16) & 0xff] ^ T2[(a3 >>  8) & 0xff] ^ T3[ a0 & 0xff] ^ rk[5];
b2 = T0[ a2 >> 24 ] ^ T1[(a3 >> 16) & 0xff] ^ T2[(a0 >>  8) & 0xff] ^ T3[ a1 & 0xff] ^ rk[6];
b3 = T0[ a3 >> 24 ] ^ T1[(a0 >> 16) & 0xff] ^ T2[(a1 >>  8) & 0xff] ^ T3[ a2 & 0xff] ^ rk[7];

II. With Inversion in $GF(2)[X]$

One can represent a polynomial of degree 7 in $GF(2)[X]$ by a number in $GF(2^8)$. (2.1.4 Polynomials over a Field, p. 13, The Design of Rinjdael) or in other word a byte.

By going back to the initial definition, one can implement subBytes is such way and have it potentially protected against timing attacks.

III. Bit sliced

Wait! This is slow as hell!

In order to gain speed, we can have a look at a bit sliced version. Bit slicing is basically writing an hardware implementation in software, considering that each bit is a different input and operations as gates applied at the same time.

In 2007 Matsui and Nakajima propose a bit-sliced implementation of AES-CTR, about 30% faster than the table lookup version. It uses 128 bits vector registers and computes 128 blocs of AES at the same time.
The only draw back is that you need 2kB of data to encrypt to benefit from the speed up. But that is still useful in the case of HDD encryption ...

Two years later P. Schwabe and E. Käsper implement another version 20% faster and that does not have this 2kB requirement.

IV. But I need more SPEED !

In 2010, Intel provides a hardware AES instruction.

aesenc xmm1, xmm3   % xmm1 - data, xmm3 - key

Which leads to:

# Encrypt the block.
pxor       %xmm5,  %xmm0
aesenc     %xmm6,  %xmm0
aesenc     %xmm7,  %xmm0
aesenc     %xmm8,  %xmm0
aesenc     %xmm9,  %xmm0
aesenc     %xmm10, %xmm0
aesenc     %xmm11, %xmm0
aesenc     %xmm12, %xmm0
aesenc     %xmm13, %xmm0
aesenc     %xmm14, %xmm0
aesenclast %xmm15, %xmm0

source

V. More readings:

Implementing AES 2000-2010: performance and security challenges by Emilia Käsper

How can bit slicing be constant time, when Mix Columns is in the cipher


What is the role of the round counter in the key schedule of PRESENT? Currently I am working on PRESENT block cipher implementation (Hardware) and I am unable to understand the role of round counter in key scheduling part of cipher.

Can some share some insight on round counter and its working?

to prevent self-similarity of key scheduling

The importance of constant addition (not only present cipher) appears in preventing key schedule-based attacks  such as slide attack ,related key attacks and other structural attacks such as: invariant subspace attack , and nonlinear invariant subspace attacks.

paragraph  5.4 Key schedule attacks in original Present Block cipher
answers your questions.


Zero Knowledge Example using discrete log I've been exploring Zero Knowledge Proofs and while the classic cave example by Jean-Jacques Quisquater makes sense, I find the discrete log example problematic.

Since the Verifier is given p, g and y, where p is a large prime, g the generator and y = g x mod p. The value x is secret. My problem is that that there is leakage of information since y depends directly on the secret x.

Alternatively, the security is that of the discrete algorithm problem. Is this a poor example or do all realizable ZKP leak information?

A zero-knowledge proof is a protocol by which the Prover demonstrate to the Verifier that he knows the solution to a given problem, without giving to the Verifier any additional information about the solution -- that is, no information that the Verifier could not already obtain alone. In the case of the discrete logarithm, the y value is not part of what the Prover sends; it is a given. The base problem consists in (p,g,y) and what the Prover tries to demonstrate is that he knows the corresponding x -- but without helping the Verifier find out x.

The Verifier can always try to solve the problem by himself. This is in fact unavoidable: since a ZK proof is about proving knowledge of a solution to a given problem, anybody can, conceptually, try to solve the problem upfront, if only by exhaustive search of all possible bit patterns for a solution.

This does not count as a leak because it is not information obtained from the Prover. It is part of the context. It is information that everybody already has. The whole of ZK is about demonstrating knowledge of some value without yielding extra information that was not already public knowledge.

(Honestly I never understood why the cave example was all the rage. It is an analogy and it breaks down when looked at too closely. For instance, Victor could say to Peggy: enter the left corridor, and exit from the right one. This would demonstrate that Peggy knows how to open the door, and would be vastly simpler than the pseudo-ZK concocted for that example.)


Secure Remote Protocol - Are these 2 equations equivalent? I'm implementing the Secure Remote Protocol that is specified to have this equation for the parameter S, the premaster secret.

 S = (B - (k * g^x)) ^ (a + (u * x)) % N

But the implementation I'm referring to, has done it this way. Is this equivalent to the author's description? Its too complex for me to understand. Can you please check it and/or explain?

 S = ((B + (N - ((k * (g^x % N)) % N))) ^ (a + u * x) %  N);

Some questions:

Why the 3 mod's instead of just 1 at the end?
Why B+ and N- instead of B-?
Can it be optimized in any way?

Well, the bottom line is that it is equivalent.

The intermediate mod's do not modify the value of the expression; this is because all the arithmetic done by the expression (except for the calculation of the exponent (a + u * x)) is done modulo N; it is always safe to do intermediate reductions.

And, in this case, it's actually necessary; g^x is quite a huge number, and you really have to compute it modulo N, the actual value is just too big.

As for why B+ and N- instead of B-, well, it is likely that the modular exponentiation primitive that the programmer used wasn't able to handle negative bases.  By reducing the value of k * g^x modulo N (which is safe, as above), that value is always less than N; and so N - (k * g^x % N) is always positive, and so is B + (N - (k * g^x % N)).  Also note that this modification is also safe, because for all $A$, $B$, $N$, we have:

$A - B = A + N - B = A + (N - B) \mod N$

I would note that there are some further reductions that could have been done:

The exponent could have been computed modulo (N-1), as in (a + u*x) % (N-1).  This is a safe reduction because N is prime (and Fermat's Little Theorem); this would speed up the second modular exponentiation operation by giving it a smaller exponent.  Note that the modular exponentiation primitive cannot do it (it couldn't assume N is prime).
When computing (B + (N - ((k * (g^x % N)) % N)), they could have done a final % N to it; this might speed up the second modular exponentiation operation (by giving it a smaller base).  However, unlike the above operation, the code that computes the modular exponentiation might do that already (because that is always safe, whether or not N is prime).