How is block cipher padding verified for consistancy? Under what circumstances is a decryption routine able to tell that the padding of a message is invalid?  If a cipher text block where to be randomly modified,  what is the probability that the padding would be correct?  How does the type of padding influence the detectability of cipher text that has been tampered with?

Let's say we are using PKCS#7 padding, and we'll stick to a single block message for simplicity. Modifying the ciphertext should result in an completely random decryption. To get proper padding, the resulting decryption would have to look something like this (RANDOM DATA)01 or (RANDOM DATA)0202, and so on.

Since the result is random, the probability that you would get (RANDOM DATA)01 is $1/256\approx 0.004$, the probability that you would get (RANDOM DATA)0202 is $(1/256)^2$, and so on. The sum of these is the probability $\displaystyle\sum_{n=1}^{16} (1/256)^n\approx 0.004$ (notice that all cases except padding of 01 are of negligible probability).

Looking at this padding method, it is easy to see how one would detect a modified ciphertext by simply looking at the padding. If the resulting plaintext is something like (RANDOM DATA)(SOMETHING OTHER THAN 02)02, the padding is not correct. Using this as a message authentication attack and reporting the result to the user (either directly or indirectly) would result in a padding oracle attack, which would be very devastating.

Other padding methods, for example, will have different probabilities. For example, ISO 10126 uses random padding with the last byte used to tell how much padding was used. If the block size is 16 bytes, a last byte of 01 through 0f would be valid. Thus the probability would be $16/256=0.0625$.


For CBC, if the initialization vector is corrupted, can we still decrypt the message? Actually, I think IV (initialization vector) is random number which is same size as the other block of plaintext. But if the IV is corrupted, message cannot be decrypted because original IV used to encrypt doesn't exist so it actually cannot recover the message from ciphertext.

Is it right?

If the IV is send with the ciphertext rather than derived (this seems assumed, otherwise the IV is unlikely to get corrupted) and is indeed fully unpredictable the those bits that are affected cannot be decrypted (presuming that the bits are changed with a 50% chance). This is because decryption of the first block of CBC depends on a XOR with the IV to derive the plaintext. If the value of any of the IV bits is unknown, then the value of the plaintext is unknown as well, similar to the way a one-time-pad works.

However, the decryption of the other, unaffected bits is still fully possible. And any block after that only relies on the ciphertext block before it, rather than the IV. So most of the message would still be recoverable, regardless of what happens to the IV.

So basically, the answer is no this is not correct other than for the bits in the first block of the ciphertext / plaintext that are affected by the changes in the IV.


Sum vector elements homorphically I'm looking for the homomorphic version of the following (I'm using Python here):

$ a = [1,2,3]
$ s = sum(a)
$ print(s)
6

Is there an open source fully homomorphic library which is able to do $sum(vector)$? So far I just found libraries allowing operations with input-output either only vectorial or only integer. Here I'm asking for a vector to integer operation.

Of course there is another way, namely encrypting every integer element of $a$ individually, summing in the encrypted domain, and then decrypt the result. Since I would like to take advantage of the speed of vector batching, I'm not considering this as a good solution.

As far as I know, there are many libraries that use lattices and LWE schemes to implement fully homomorphic Encryptions.

This is a set, Most of them is in C++ and Only one by MSFT is C#, But in all cases you can port the code to python aftor compiling:

HElib in C++
SEAL By MicroSoft C++/C#
Palisade C++
FHEW C/C++
TFHE C++
NFLib C++

Note: The set in no particular order.


Do data-dependent rotations have any advantage over fixed rotations? There are many ARX ciphers, however most use fixed rotations.

I know data-dependent compared to fixed rotations are:

patented (expired)
harder to implement constant time
more expensive in hardware
harder to analyse
attacker can control rotation to some degree

Do data-dependent rotations have any advantage over fixed rotations?

Compared to fixed rotations, data-dependent rotations improve resistance to differential and linear cryptanalysis. A fixed rotation has no effect (beyond helping with diffusion) in the probability of a (xor-)differential characteristic, whereas a data-dependent rotation also introduces differences in the rotation amounts, which brings probabilities down. There's a 2000 paper by Scott Contini that quantifies this advantage.

Successful attacks against ciphers using data-dependent rotation have focused on trying to avoid differences in the rotation amounts, or to fix them to some value; this was the case for RC5. Later designs like RC6 and MARS made this harder by using more complex functions as the input to the rotations. This is an interesting paper studying the effect of varying that complex function in RC6, and how it affects the overall security of the cipher.

That said, the disadvantages you listed outweigh the potential advantages, and data-dependent rotations are generally not employed in new designs.


Shamir's secret sharing for vectors How would we go about building a scheme for Shamir secret sharing for vectors?
I have already tried to use a vector of secrets and random distribution of the secrets to $n$ parties and then use $t$ of them to get the data, where $t<n$.

To share a vector using Shamir's secret sharing, you can just share each element of the vector independently.  It really is that simple.

To save some space, you can assign all the shareholders a distinct fixed non-zero $x$ coordinate and reuse those same $x$ coordinates for all elements of the vector being shared.  The $x$ coordinates only need to be distinct; they don't have to be random or secret in any way.

(If your shareholders already have some unique ID that can be encoded as an element of the field you're using for Shamir's scheme, you could just use those as the $x$ coordinates.  Or, if you're working in a sufficiently large field to make collisions unlikely — say, ${\rm GF}(2^{128})$ or larger — you could even derive the $x$ coordinate of each participant by hashing some arbitrary pre-existing public ID, like, say, an e-mail address.  Just make sure not to allow $x = 0$ in any case, since that directly leaks the secret.)

In fact, the only reason we don't just interpret all secrets as vectors of bits and run Shamir's scheme over ${\rm GF}(2)$ is the fact that the field size limits the number of shareholders (and, in particular, a two-element field allows only one shareholder, which is kind of useless).  However, it is quite common to e.g. interpret arbitrary strings as vectors of 8-bit bytes, and share them with Shamir's scheme over ${\rm GF}(2^8)$, which works for up to 255 shareholders.


Which hash algorithms are suitable for use with Elliptic-curve cryptography I try to use Elliptic-curve cryptography system first time really, so i confused about it.
this is the scenario:
First i want to hash a message then, sign it. i use javascript so i try to follow this code.

The reason of my confused is why this code use 'sha256' algorithm to hash a message? is there any reason for that?

Also is there any hash algorithm customized or preferred to use with ECC?

To be more clear, is ECC using to sign and generate keys but does not have a special algorithm to hash a message?

thanks.

You really have two questions, and so I'll try to address both of them; it appears that your question really is the second one, but the answer to the first one will illuminate the second one:

  The reason of my confused is why this code use [a hash function] to hash a message? is there any reason for that?

Well, we use some public key transform to transform 'the message' and the 'private key' into 'a signature'; however this transform takes input of fixed size.  That is, it cannot handle a message longer than expected (and this is pretty much true for all signature algorithms: Elliptic Curve signature algorithms, RSA, postquantum signature algorithms).

Now, we may want to sign documents considerably larger than the maximum that the raw public key operation can handle.  The internal parts of ECDSA with P256 can handle only 256 bits at a time, quite often, we want to sign something that's larger than 32 bytes.  To handle this, what we do is send the actual message through a 'hash function', that is, a transform that converts our long message into a fixed length (which the raw public key operation can handle).  We hash the message, and then hand that hash to the ECDSA internal logic.  Then, to verify a signature, the verifier hands the message it has to the same hashing logic, computes the hash, and then hands that hash to the ECDSA verification logic.

By the above description, there are a couple of things which are apparent:

The hashing logic must be public; after all, the verifier (which we can assume has the public key, but no secret knowledge) must be able to compute it.
The hash must be 'collision resistant'; that is, it should be infeasible (that is, no one can do it) to find two different messages that hash to the same value.  After all, if someone could find two messages $\text{Good Message}$ and $\text{Evil Message}$ that hash to the same value, he could take $\text{Good Message}$, convince the signer to generate a signature for it (which he might, as the message is benign), and then that signature would also be a valid signature for $\text{Evil Message}$ (because the signature only depends on the hash, and those two messages hash to the same value).

  is why this code use 'sha256' algorithm?  is there any hash algorithm customized or preferred to use with ECC?

No, there is no specialized hash algorithm for ECC.  If you look through the criteria I gave for hash functions, there's nothing specific to the public key method.  A hash function that is good for RSA will also be good for ECC.

We have a number of functions that appear to be good hash functions; SHA256 is one of them, and that happens to be want they picked.


Why is proof-by-reduction needed (for Elgamal proof of security, for example)? The textbook proof for Elgamal encryption basically reduces to the Decisional Diffie-Hellman assumption (DDH).

Elgamal:
$Gen(.): x \xleftarrow{R} \mathbb{Z}_p$; $Enc(m,g^x): r \xleftarrow{R} \mathbb{Z}_p, U= m.(g^x)^r, V = g^r$; $Dec(U,V,x): m = U/V^x$.

Suppose I prove the secure of Elgamal (in the CPA security model) as follows:

  Since $r$ is uniformly random, $(g^x)^r$ is also uniformly random. Thus, $m.(g^x)^r$ follows a uniform distribution. Given two message $m_0, m_1$ during the Challenge phase, the corresponding ciphertext $c_0$ and $c_1$ follow the same uniform distribution. Therefore, the advantage of the adversary is the same as distinguishing two identical distributions, which is 0.

Can someone tell me what is amiss in the proof above? Why is it (or isn't it) sufficient to show that the ciphertexts following a uniform distribution, i.e. indistinguishable from a truly random value?

Why is proof-by-reduction needed?

In general, reduction proofs are a very common thing in computer science. Specifically in cryptography, the reasoning goes something like this:

  The general cryptographic community believes that problem $X$ is very difficult to solve. I have designed a new cipher $Y$ and want to convince the community that it would be hard to break. So, I assume that someone could efficiently break $Y$, then I show that using an efficient break of $Y$, someone could also solve problem $X$. Therefore, we can conclude that breaking $Y$ is at least as hard as solving $X$. Since general consensus is that $X$ is really hard to solve, $Y$ must be a secure cipher.

That is not the only way to prove security of a cipher. If I remember correctly, the proof of security for the one-time-pad does not follow this paradigm. It has, over time, however, proven to be a very good way to prove security of a cipher and has worked well in practice.

  Can someone tell me what is amiss in the proof above? Why is it (or isn't it) sufficient to show that the ciphertexts following a uniform distribution, i.e. indistinguishable from a truly random value?

See Maeher's comment.


Quantum computing vs AES s-box equation Do quantum computers  have any affect on the ability to solve the non-linear AES s-box algebraic expression, or does solving it still fall under search algorithms (Grover's)? If quantum computer do help solve it, what affect does this have on AES given that finding the key is still a brute-force search?

Take a look at this chapter (Introduction to post-quantum cryptography by Daniel J. Bernstein). It gives an excellent overview of what is known. (Bottom line, Grover's is the best known today and so this can be thwarted by taking 256 bit keys.)


Reverse Java random seed using 81 calls to nextInt with a bound of 4? I'm trying to reverse the Java random seed using 81 calls to nextInt(bound) with a bound of 4. I am wondering if it is at all possible to reverse the random seed.

In this situation Java's random number generator is called 81 times, and for each call I know if the returned value is either 0 or not 0. Looking at the int nextInt(int bound) method, here is the relevant code:

int r = next(31);
if ((bound & (bound-1)) == 0)  // i.e., bound is a power of 2
    r = (int)((bound * (long)r) >> 31);

where r is the returned value, and next(31) is the next pseudo-random value using 31 bits. Here is that next method:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

where the multiplier is a constant 0x5DEECE66DL, addend is 0xBL, mask is (1L << 48) - 1. Here, 0x indicates a hexadecimal value, and the L is there to make the literal value a Java long (64-bit).

In Java, int is always 32 bits in size. Furthermore AtomicLong is a multi-threading related construct that simply represents a 64 bit long in this code. The mask makes sure that the value never exceeds 48 bits. The loop construct and !compareAndSet can be entirely replaced by a simple seed = nextSeed.

Basically then, the seed $s$ is updated using:

$$s \gets (\mathtt{5DEECE66D}_{16} \cdot s + \mathtt{B}_{16}) \bmod {2^{48}}$$

after which the two most significant bits of the 48 bit value $s$ are returned.

I don't know if this is possible, since so many bits are dropped, but I have seen this done with calls to nextInt(10).

Sorry if there is anything I left out or if this is too vague, this is my first cryptography post.

The $48$-bit state $s_i$ evolves per a Linear Congruential Random Number Generator, with modulus $n=2^{48}$, multiplier $a=\mathtt{5DEECE66D}_{16}$, and additive constant $b=\mathtt B_{16}$; that is $s_i=(a\cdot s_{i-1}+b)\bmod2^{48}$. We are given the OR $r_i$ of its two upper bits for $i\in[1,81]$, or equivalently the $81$ booleans $s_i\ge2^{46}$. Our goal is to find $s_0$: if the Java default generator was explicitly seeded, $s_0\oplus a$ is the low-order 48 bits of the given long seed.

The $81$ givens yield about $-81\left(\frac14\log_2(\frac14)+\frac34\log_2(\frac34)\right)\approx65.7$ bit of information, which should be typically ample to pinpoint a single $48$-bit seed.

A most brute force solution to the problem enumerates all the $s_0$ in $[0,2^{48})$, and for increasing $i$ computes the $s_i$ and eliminates a candidate $s_0$ as soon as there's a mismatch between a bit $r_i$ and the condition $s_i\ge2^{46}$. That's feasible, and particularly easy to distribute on multiple threads/CPUs/GPUs/FPGAs. The rest of this answer illustrates the NSA saying (popularized by Bruce Schneier): Attacks always get better; they never get worse.

Notice that we can compute for $z\in[-81,81]$ the $48$-bit constants $a_z$ and $b_z$ such that $s_{i+z}=(a_z\cdot s_i+b_z)\bmod2^{48}$. We have
$$\begin {align}
a_0&=1&b_0&=0\\
a_{z+1}&=a\cdot a_z\bmod2^{48}&b_{z+1}&=(a\cdot b_z+b)\bmod2^{48}\\
a_{-1}&=a^{-1}\bmod2^{48}=\mathtt{DFE05BCB1365}_{16}&b_{-1}&=a_{-1}\cdot (-b)\bmod2^{48}\\
a_{z-1}&=a_{-1}\cdot a_z\bmod2^{48}&b_{z-1}&=a_{-1}\cdot (b_z-b)\bmod2^{48}
\end{align}$$
This allows computing directly any $s_j$ from any $s_i$, by taking $z=j-i$. That's put to use in the following optimizations:

Pick an $i$ with $r_i=0$ and reorganize the search by walking $s_i$ in the interval to $[0,2^{46})$, then compute $s_0$ from $s_i$. That's a welcome gain by a factor of $4$.
We most likely¹ can pick the above $i$ such that $r_i=r_{i+1}=0$. The condition $s_{i+1}<2^{46}$ (which must hold) changes rarely when incrementing $s_i$: it holds true for about $2^{46}/a\approx2791$ consecutive values, then is false for an interval about three times longer, that we can skip, giving a speedup by a factor next to $4$.

At that stage of optimization, we explore $2^{44}$ values of $s_i$. I guesstimate² we can run faster than $2^6$ cycles/value tested on a core of a modern x64 desktop CPU. With a single $2^2$-core CPU at $2^{31}$ Hz, that would be $2^{17}$ seconds (1.5 day for the full exploration), and half that on average.

We can do better, but be warned that premature optimization is the root of all evils (Donald Knuth). We most often are able to make good use of the fact that $a_{-67}$ is small: when we can find $i,z$ with $r_i=r_{i+1}+r_{i-67}=0$, that allows getting down to $2^{42}$ values searched at cost of a further sub-division of the search sub-intervals for $s_i$ into sub-sub-intervals of width $2^{46}/a_{-67}\approx394$.

We often are able to further subdivide at least once or even twice, each time gaining another reduction by a factor of $4$ of the number of $a_i$ to test. We want to explore the usefulness of such subdivision for each $s_{i+z}$ with $r_{i+z}=0$. The better choices have the highest width $\approx2^{46}/\min(a_z,2^{48}-a_z)$ for the interval of $a_i$ with $s_{i+z}<2^{46}$. In particular, we might be able to use that $2^{46}/a_{19}\approx60$ or $2^{46}/(2^{48}-a_{-12})\approx60$. But we'll quickly get hit by the law of diminishing returns.

Update: There must be better methods. Something at least quite close was studied by Alan M. Frieze, Johan Hastad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing Truncated Integer Variables Satisfying Linear Congruences, in SIAM Journal on Computing, 1988.

¹ In the very unlikely case (I'm not even sure it is possible) that there's no $i$ with $r_i=r_{i+1}=0$, the simplest of several possible fallbacks is to pick $i$ and $z$ with $r_i=r_{i+z}=0$ and the smallest $a_z$ possible; that will often be $z=-67$ or $z=19$. The reduction in number of $s_i$ scanned is the same, but we'll more often change sub-intervals.

² When $s_i$ increases in a sub-interval, we want to quickly update at least one $s_j$ that we'll always test. An update of $s_j$ cost one addition of $a_{j-i}$ and a mask³. We'll pick $j$ with $r_j=0$, which will leave only one out of $4$ values of $s_i$ needing more scrutiny. For these, we sequentially compute and test the many other $s_{i+z}$ that we could still have wrong, of course stopping at the first mismatch and first testing $z$ with $r_{i+z}=0$. Each additional $z$ requires a multiplication by $a_z$. If that's too costly, we'll want to maintain one or a few more $s_k$ by addition.

³ A simple micro-optimization maintains $2^{16}s_i$ over a $64$-bit variable, saving the masking. The comparison becomes against $2^{62}$, also implementable as a $62$-bit right shift and a test for zero.


How is formal analysis of the strength of a round achieved? I've been trying to understand how the number of rounds are picked for ciphers.  There seems to be a minimum number of rounds that is analyzed for "strength" and then some security margin is added.

M. Luby and C. Rackoff showed that you need only three rounds for a Feistel network if you have sufficiently random keys; however, this is not practical in reality, which is why we have key expansions.  This leads me to my questions:

How is the strength of a key schedule formally analyzed?

We have suites for random numbers, such as diehard, but I've not found a reference how key schedule strength is formalized.  One could look at series of rounds through diehard, but the keys will obviously be related.  Furthermore, in literature, generally it seems that the key schedule is the most ridiculed part of every cipher.  I dug into Ph.D. dissertations but I didn't find anything.  Any suggestions would be greatly appreciated.

diehard is not the answer you're looking for. diehard is a randomness testing tool. It looks at a sample of ~10MB and checks if that sample is  independent and uniformly distributed (IID).  It uses simple statistics not implicit cryptographic experience.  The output is essentially a binary output in that if some p values = 0.00000 or 1.00000 then the sample is not sufficiently IID.  The sequence of p's that you'd get for a sample unequivocally known to be IID is  somewhat a matter of interpretation, feelings and guesswork.   dieharder, it's successor makes this binary choice much more explicit in outputting PASS, WEAK or FAILs.

You could easily produce a 10MB sample from the first round of a Feistel network such as DES. It would probably fail with a series of 0's after the decimal point.  As the round count increases, the p values would start to look reasonable, but not increase any further.  You would learn little of security from this exercise other than that the output is IID. So is 10MB of RC4 when analysed with diehard.

Don't be surprised that key expansion inside some of these primitives is weak.  AES is weakish.  Key expansion is only a part of the entire primitive and their security comes from a sum of the parts.

PS. Colourful language is great, but in this particular instance categorising key expansion algorithms as ridiculous skews the question somewhat.  I think that analysts call them weak, rather than ridiculous.  "Ridiculous" would transfer all the security responsibilities to the main part of the primitive, and imply that any old expansion like ROT13 could be used.


Is there any way to track if a ciphertext has been decypted? Just like the case of a box that has been sealed. We can detect if the box has been opened or not by looking at the seal. Is there any way in cryptography or any encryption scheme that allows this to happen? If we have a ciphertext, I wonder if there is a mechanism that can detect if someone has decrypted it?

Digital data can always be copied. So it is easy to see that such a seal would not work in general: you could just leave the original ciphertext where it is and decrypt the copy.

There are ways around this, but they need some other trusted party or device. For instance you could use a simple secret sharing technique where (information from) a trusted third party is needed to reconstruct the decryption key. Or the trusted third party could do the decryption themselves, but in that case they may learn the plaintext. There are also plenty of techniques where the trusted third party never knows the plaintext.

Obviously you don't know the other party actually learns the plaintext. It could perform the digital equivalent of looking away. You can just learn if they received the plaintext and had the opportunity to see it. It would be easy to require the other party to sign the plaintext to verify that information was received.

You can of course generate the digital variant of a sealed box in hardware. This lets you get around the fact that the ciphertext can be easily copied.


Using RSA encryption with OpenSSL library: secure? I'm working on a small program (in C) that writes encrypted log files, but there are a lot of articles out there that say you should avoid RSA whenever possible. However, most of these articles also seem to refer specifically to home-cooked algorithms involving RSA, because in such cases inexperienced crypto-devs tend to pick insecure parameters.

In my case I'm simply using the OpenSSL library and its RSA_public_encrypt() function, along with OAEP padding. The plaintext is received over the network and never fed directly to the program, any error messages will be reported only to people having local access to the machine it's running on. The private key can be either 2048 or 4096 bits long and will be stored offline and far away from the public key. The key pair is generated outside of the application, but also through OpenSSL:

openssl genpkey -aes-256-cbc -algorithm RSA -out foo.key -pkeyopt rsa_keygen_bits:4096
openssl rsa -pubout -in foo.key -out bar.pub

Is this setup:

Considered cryptographically secure? I know you could still attach a debugger and just read the plaintext strings from memory, but in that case you have bigger problems anyways so it's not really relevant for this question.
Future-proof (i.e. do I need to migrate it over to something else sooner rather than later)?

New systems should not use RSA unless interoperability requires it. See for example this twitter thread for current zeitgeist: https://twitter.com/veorq/status/1148258833896263680

With RSA, the recommendation is to not even have a mode where data is encrypted using RSA directly, even if it fits. Always use hybrid encryption to not have two code paths. The symmetric encryption part should use a modern AEAD, and unless the performance difference between AESGCM (up to 5GB/s) and ChaPoly (up to 2GB/s) is important, use the ChaPoly since a random implementation of ChaPoly is more likely to be secure than a random implementation of AESGCM.

Instead of RSA-OAEP, I would use Curve25519 ECDH in ephemeral-static mode. Meaning you create a Curve25519 keypair, store the private safely offline and copy the public to the system that will encrypt.

Every time it needs to encrypt a file it generates a new Curve25519 keypair, writes the public into the beginning of the encrypted file, does ECDH between the private and the destination's public to get a shared secret, forgets the newly generated Curve25519 keypair, uses KDF over the DH shared secret, and uses the result of the KDF to generate key and nonces for the AEAD. If the cleartext is long, use chunks.

To decrypt, use the private key stored offline to do the ECDH with the ephemeral public, KDF, AEAD.

Oh wait, I'm describing libsodium. Use libsodium. It is the embodiment of 20 years of lessons learned in cryptography and misuse resistant crypto API design, it is production quality, it is portable, it is fast, etc.

If large quantum computers ever happen, both Curve25519 and RSA would be broken. Details about the future quantum computer are not available to judge whether using larger RSA would give you more safety margin (unless you use post quantum RSA, which is a joke).


Storing Salt in Ciphertext? I found the cryptomator encryption documentation online, because I was looking for something to learn about x). I altered the process a bit to fit "my need" / so that I would not have a vault, but a single file encryption. I did a chart for you:

cryptomator stores salt/ parameters in a config file, but as I want to encrypt and decrypt single files, they have to be stored with the file.
It should as safe as the boxcryptor encryption when I store the salts for the key derivation (for MAC & content) in the ciphertext, is it?

Another question is: Do I really need two salts & keys? According to this thread there's no known interaction between SHA-256 and AES, but on the other hand, it seems just sloppy to me to use one key for both and also there are possible unknown interactions. I'm really interested in what you think about that.

Have a nice day and thanks :)

It should as safe as the boxcryptor encryption when I store the salts for the key derivation (for MAC & content) in the ciphertext, is it?

Yes, that's the definition of a salt, a salt is public (otherwise it is commonly called a pepper). E.g. the various text encodings of bcrypt store the salt next to the hash (which has the same security consequences as storing it next to the ciphertext).

  Do I really need two salts & keys?

And using two salts implies deriving the key multiple times. That's bad, especially if that is done by using a password derivation twice. This looks like the case for your scheme. Performing PBKDF2 twice or for more output than the hash delivers will double the amount of work you have to do while an attacker has to perform the 50K operations only once (per try).

Using HKDF or any other KDF over the output of PBKDF2 is sufficient and much more efficient. You can just use two different labels (identifiers) for the two keys - if two keys are needed. This is also present in the answer of Codes that you linked to.

Another trick is to extract 256 bits of output from PBKDF2 and then split that into two 128 bit keys (or two 256 bit keys for PBKDF2 with HMAC/SHA-512). You probably don't need to extract an IV if the salt is always different (because the derived keys would then also always be different). Or you can generate a separate IV: your choice.

No, you don't need two keys either. You could use a mode of authenticated encryption such as AES-GCM. Then you'd only need just one key. If you use HMAC with a single key then you probably cannot prove that it is secure. But the chance that you run into practical security issues is minimal.

Don't change the MAC to CBC-MAC or another MAC based on AES if you use a single key, because that could make your scheme vulnerable to attack. The protocol using a single key and separate cipher and MAC is more brittle: it could break catastrophically if you implement it incorrectly.


Can a self-signed certificate's signature algorithm be changed? I've a large number of self-signed certificates that are currently being used by multiple clients which were signed with the SHA1 ('SHA1WITHRSA' as it appears in the cert) algorithm at the time they were created.

My boss has asked me to look into 're-signing' these with SHA2 (256) instead rather than re-generate a new key that would then be self-signed with SHA2 as this would be a logistical nightmare. We used to be our own CA, which would've made this possible if all keys were signed by us, but we ceased doing that and just started giving out self-signed certs.

I'm not sure if this is possible.  We can easily get access to the private key(s) on the client sites that were used to generate the original (self) signature, however, since I'm not a crypto expert, I don't know if, once a (public) key is self-signed, whether it is possible to somehow 1) detach that signature and 2) replace it with a newly generated one from the same private key which we have just as it was done the first time the key was generated and signed.

Can someone more versed in crypto shed some light on this?

Yes, you can do this, but you would need to change the OID for the signature generation algorithm as well. This may require some more advanced ASN.1 decoding and re-encoding. This is very likely more problematic than the calculation of the signature.

Obviously the fingerprint of the certificate will change as well (as that is just over the binary encoding of the certificate). So beware of this if the certificate is placed in a trust store.


True asymmetric ciphers beside RSA Is there any TRUE public key cipher beside RSA? Most people would answer Elgamal or ECC, but for what is my understanding (and I know cryptography only superficially), those are not true asymmetric ciphers (because both parties can encrypt and decrypy).

EDIT:

I realized that my question needed better explaining.

The following quote is from the Handbook of Applied Cryptography:

  Definition 1.50: Consider an encryption scheme consisting of the sets of encryption and decryption transformations $\{E_e : e ∈ K\}$ and $\{D_d : d ∈ K\}$, respectively. The encryption method is said to be a public-key encryption scheme if for each associated encryption/decryption
  pair $(e, d)$, one key $e$ (the public key) is made publicly available, while the other $d$ (the private key) is kept secret. For the scheme to be secure, it must be computationally infeasible to compute $d$ from $e$.

Now take for instance Elgamal encryption. Bob chooses the parameters, then sends the public key to Alice, Alice computes the mask $K_M$ (the session key) and the ephemeral key $K_E$, encrypts the message $M$ with $K_M$ obtaining $C$, and sends ($C$,$K_E$) to Bob. Bob can compute $K_M$ using $K_E$ and his private key. The quoted definition is not satisfied. Alice and Bob, in the end, both have $K_M$ which is used for encryption and decryption.

EDIT2:

The reply I got from fgrieu was very satisfying, I was mistaking a shared secret key for a public key. However this made me reflect on another difference between an Elgamal scheme and an RSA scheme. I'm going start with another quote from HAC (Basic Terminology, p.12):

  An encryption scheme consists of a set ${E_e : e ∈ K}$ of encryption transformations and a corresponding set ${D_d : d ∈ K}$ of decryption transformations with the property that for each $e ∈ K$ there is a unique key $d ∈ K$ such that $D_d = E_e^{−1}$; that is, $D_d(E_e(m)) = m$ for all $m ∈ M$. An encryption scheme is sometimes referred to as a cipher.

With this, Elgamal randomized E is not acceptable, because a randomized function can't be the left inverse of another function. Se we can heve $D_d(E_e(m)) = m$ for all $m ∈ M$, but we can't have $D_d = E_e^{−1}$. This is also the reason (I think) why Elgamal cipher can't be usued for digital signatures (Elgamal DS is different from the cipher).

Now my question: is the second quoted definition correct? Or $D_d = E_e^{−1}$ should be "$D_d$ is a left inverse of $E_e$"? Also unicity of $d$ is really necessary?

Yes, there are true asymmetric (public-key) ciphers beside RSA. Elgamal encryption is an example, and matches the question's definition when we allows that definition's encryption transformation $E_e$ to be randomized (as we must: otherwise, anyone could use the public $E_e$ to verify a guess of the message, which would be a disaster in many practical applications, e.g. enciphering the name of some guy on the class roll).

Using the notation in Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984),

Parameters are a large prime $p$ with $p-1$ having at least one large prime factor, and a generator $\alpha$ (e.g. with $q=(p-1)/2$ prime, and $\alpha\in[1,p)$ with $\alpha^q\bmod p\ne 1$ ). Parameters are public, or part of individual public keys.
The definition's encryption/decryption pair $(e,d)$ is the combination of parameters and long-term public-private key pair $(y_B,x_B)$ used by recipient Bob. More precisely, $e$ is $(p,\alpha,y_B)$ and $d$ is $(p,\alpha,x_B)$, with $x_B$ a random secret and $y_B=\alpha^{x_B}\bmod p$.
The definition's encryption transformation $E_e$ accepts as input a message $m$ in $[0,p)$. As part of each invocation of $E_e$, the sender (Alice) draws ephemeral random $k$, computes $K={y_B}^k\bmod p$, $c_1=\alpha^k\bmod p$, $c_2=Km\bmod p$. The ciphertext is $(c_1,c_2)$.
The definition's decryption $D_d$ accepts as input a ciphertext $(c_1,c_2)$ in $[0,p)^2$. The receiver (Bob) computes $K={c_1}^{x_B}\bmod p$, and $m=K^{-1}c_2\bmod p$.

Note: In the version described here and in the original paper, ElGamal encryption is not CPA secure. For a start, $m=0\iff c_2=0$. And even if we exclude message $m=0$, the Legendre symbol $\displaystyle\biggl(\frac m p\biggr)$ can be found from $(p,\alpha,y_B,c_1,c_2)$, and that leaks one bit of information about $m$.

Regarding EDIT2 (about as it stands less a few typos):

  we can have $D_d(E_e(m))=m$ for all $m\in M$, but we can't have $D_d = E_e^{−1}$.

To my eyes, the two statements are equivalent by any sensible definition of $E_e^{−1}$, which must be a transformation taking the output of $E_e$ and returning what was the input. And the Elgamal cipher matches that. The second quoted definition looks correct to me.

I would agree with "we can't have $E_e= D_d^{−1}$", because multiple inputs of $D_d$ have the same output, making $D_d$ impossible to invert for the classical definition of that. And yes, this is a reason why Elgamal cipher can't be used for digital signatures using the techniques allowing RSA signature.

RSA is not quite the only public-key cipher internally using a trapdoor permutation, usable for both encryption and signature scheme (which turns out to be the meat of the question's introductory phrase). There is at least the Rabin cryptosystem, which can be thought as RSA with even public exponent. I fail to name another which got sizable traction.

Note: RSA as in the original paper and PKCS#1 does not match the "unique key $d$" requirement. For this to hold, we need to reduce $d$ modulo $\lambda(N)$ (where $\lambda$ is the Carmichael function), as in FIPS 186-4.


Why does the server in S/KEY authentication only store a single password? I've been reading about the S/KEY One-Time Password system on wikipedia here and was wondering why the server only stores a single password and not the list of one-time passwords like the client does.  In other words, why is the implementation not a simply a password-to-password compare but instead a cryptographic hash function is run on the password and then the result of that hash function is compared to the previous One-Time-Password the client sent to the server?

Applying the hash function assures that only the next password in sequence will be valid.  There is no reason to store the previous state, or the client's original secret.  Once a valid key is used, the server stores the hash of it (which is the same algorithm used to generate the list of hashes in the first place.)  This puts the burden of storage on the client, meaning the server doesn't need a 1000 rows in the database for each user.

Of course, this algorithm was developed in the days before hardware boxes capable of testing 1.5 trillion hashes per second were commercially available.


Does SIV mode work for asymmetric encryption? In ECIES and similar asymmetric schemes, is it possible to use a hash of the plaintext as the IV?

Taking the hash of the message as IV would not be secure, since, like Ricky Demer mentioned in comments, it would make the hash public and allow guessing. However, that is not what SIV mode does – it uses a MAC as IV.

Doing that with ECIES would be possible, but probably not a good idea:

Normal ECIES has single-use symmetric keys, so it requires no IVs.
For the same reason ECIES+SIV would not be deterministic, if that is the objective.

Unless SIV happens to be the best kind of encryption available for other reasons, there is no advantage over other forms of authenticated encryption, and probably downsides like speed (since it requires two passes over the data).

With other asymmetric systems it may be another matter. E.g. Curve25519 uses static Diffie–Hellman keys for both the receiver and sender, so using SIV would avoid total breakage on nonce reuse.


Encryption of a number with RSA bigger than $n$ I'm having trouble understanding why encrypting a number $m$, which is larger than $n=p\cdot q$. I've looked into the following threads:
Why RSA can't handle numbers above 76?
Why does plain RSA not work with big messages ($m>n$)?

Can somebody point me to a simpler source, that explains this?

I'm assuming that you mean "encrypt with a single encryption operation" (and not to split it up into consecutive blocks such that each fits into $Z_n$).

RSA with modulus $n$ works in the ring $Z_n$, i.e., the set of integers $\{0,\ldots,n-1\}$. So you are limited to working with messages in this set. If you want to encrypt a message $m\geq n$, you are essentially encrypting a message $m'$ in the set $\{0,\ldots,n-1\}$ such that  $m'\equiv m\pmod n$, i.e, the message $m$ is "implicitly" mapped to another message $m'$ in the set $\{0,\ldots,n-1\}$ which is the remainder of $m$ when divided by $n$ (the two messages $m$ and $m'$ can be considered identical when working modulo $n$ , i.e., in the residue class ring $Z_n$).

Now, the problem is that after encryption of $m\geq n$ with RSA and decryption thereof you get back $m'$ and you cannot figure out what your initial message $m$ was, since $m'$ is in the set $\{0,\ldots,n-1\}$ and every message that has the same remainder modulo $n$ as $m'$ will be a potential candidate for $m$ (and that are infinitely many ones). So you would be lost. Consequently, to make encryption and decryption of a message $m$ unambiguously, you need to limit the messages you encrypt to the set $\{0,\ldots,n-1\}$.

You may also look at this question and its answers for a more detailed discussion (on the residue class ring $Z_n$).


What does MULx operation in SNOW 3G correspond to? According to the spec, MULx operation is defined as  -

MULx maps 16 bits to 8 bits. Let V and c be 8-bit input values. Then MULx is defined:
If the leftmost (i.e. the most significant) bit of V equals 1, then
 MULx(V, c) = (V <<8 1) ⊕ c,
else
 MULx(V, c) = V <<8 1.
Example:
MULx(0x69,0x1B) = 0xC2
MULx(0x96,0x1B) = 0x2C ⊕ 0x1B = 0x37.

What does it really do ?

It essentially is the value $02 \times V$ in the field $GF(2^8)$, and so MulxPOW(V, I, c) is essentially $02^i \times V$ in the field $GF(2^8)$, where $c$ specifies the representation used.

What is a representation: there are a lot of ways to map between 8 bit values and the members of the abstract $GF(2^8)$ field, and a number of those mappings are plausible (unless $GF(p)$, which has an obvious mapping between integers in the range $[0, p-1]$ and members of that field - so obvious that we typically ignore it).

What Snow does is use several different mappings (representations) for the various SBoxes, by specifying different $c$ values for the different sboxes.


Signature and Timestamp for Long Term Document Archival Question I have a PDF document intended for long-term (many years, maybe decades) archival which I would like to digitally sign with my personal certificate to ensure its integrity.

As far as I understand, I need to timestamp the signature in order to ensure it remains valid even after certificate expiration.

Let's say I use a trustworthy TSA. From what I understand they sign the timestamp with they own signature.

Now, let's suppose the original TSA bankrupts or is compromised and its certificates revoked. Will my document remain readable without warnings?

Time stamps are also signatures; see for instance RFC 3161 which is the most commonly used time stamp format. In particular, such time stamps also rely on certificates (the TSA certificate), and thus also expire.

So you need regular time stamping; whenever the latest time stamp is about to expire (but before expiration), you need to obtain a new time stamp computed over the previous time stamp. Such chaining is described in several standards, including PAdES (which supports embedding signatures and time stamps within the PDF file itself); a somewhat clearer description of time stamp chaining is Evidence Record Syntax.

To survive unexpected loss of a TSA before the time stamp expiration date (e.g. due to a compromise), you can use several TSA and interleave them in the chain: you get a time stamp from TSA A, and immediately after another time stamp from TSA B (computer over the time stamp from A). Whenever either time stamp is about to expire, expand the chain with two extra time stamps, again from A then from B. With interleaving, you can survive the loss of either TSA (but, of course, not of both).


Discrete log accumulator without pairings? Here $g$ is some fixed generator of a discrete log group. I don't want the group to be bilinear for efficiency and BDH-skepticism reasons.

Is anyone aware of a discrete log accumulator? What I mean specifically is some function $f(x, A)\mapsto A'$ (that is, $A$ is the accumulator value; $f$ adds $x$ to the accumulator, changing its value to $A'$) such that given $(g^x, A')$ anyone can check whether $x$ was placed in the accumulator.

So I'm roughly asking for an accumulator with the property that an accumulated element $x$ has $g^x$ as a witness.

Sure.  Use the strong RSA assumption.  The accumulator of $x_1,\dots,x_k$ is $A = g^{x_1 x_2 \cdots x_k} \bmod n$, where $n$ is a RSA modulus and $g$ is a fixed base.  To prove that the accumulator $A$ contains $x$, exhibit a value $h$ such that $h^x=A \pmod n$.  This is secure under the strong RSA assumption, and has a discrete log "feel" to it.


RSA square and multiply If an RSA encryption uses a modulus $n$ of 15000 bits and $e = 3$ or $e = 2^{16} + 1$, how many squarings and multiplications will we need for encryption, and for decryption? Could you please explain the concept of square and multiply as well?

I'm thinking the number of squarings is going to be equal to the number of $e$, and that the number of multiplications will be roughly half of the number of $e$, but how does the number of $n$ bits factor into that?

Also, why is it different for encryption and decryption? I thought encryption is $m^e \bmod n$, and decryption is $m^d \bmod n$, so what does the length of $e$ have to do with decryption?

After reading the comments on your original post, I thought I'd give you an example for exponentiating by $e$. Take for example the case $e=2^{16}+1$. Then, to calculate $x^e$ we use $16$ squaring operations and one multiply. This is because
$$x^{2^{16}+1}=x \cdot x^{2^{16}} = x\cdot x^{\underbrace{2\cdot 2 \cdots 2}} =x\cdot ((x^2)^2)\cdots)^ 2$$
(where the brace contains sixteen $2$'s).

So, we use repeated squaring to calculate $x^{2^{16}}$, then having done so can simply multiply by $x$ once to find $x^e$.

If we think about the binary expansion of $e$, this techinque can be generalised to give [relatively] efficient exponentiation to any power. For example, how to we take an element to the power $e=41$? Well, first writing $e$ in terms of powers of two (ie in binary), we see that $e=32+8+1=2^5+2^3+2^0$ and thus $e=101001$. So, to evaluate this we simply initialise our answer as $1$ and set $y=x$ ($y$ will store $x^{2^i}$ as $i$ increases), then work from right to left along the binary expansion of $e$. If the digit is $1$, then we multiply by $y$. Then, we square $y$ and move on to the next digit.

The reason $e$ is chosen to be a value like $2^{16}+1$ or $3=2^1+1$ are that they each only require one multiplication. Looking back at my rather poor explanation above, we see that we have to square $x$ for each 'place' in the binary expansion of $e$, and we have to multiply our running value once for each $1$ in the binary expansion of $e$. So, if $e$ is $n$ bits long (ie $n=\lfloor\log_2(e)\rfloor+1$) we require $n-1$ squaring oparations and at most $n$ multiplications (or $n-1$ if we start our multiplication with the first value power of $x$ encountered rather than initialising with $1$ as in my example).

As mentioned by other comments, it is hard to know how many multiplications/squarings will be required to decrypt, since to do so requires knowing the binary expansion of $d$. That said, we can be pretty confident that $d$ is very unlikely to have anywhere near as nicer expansion as $e$ did with these choices, suggesting decrypting will require rather more work than encryption.


Why does this RSA example break when: 1) setting p or q as non-prime, or 2) setting p and q as the same number? This answer talks about how non-prime numbers would make the algorithm easier to break, not that the algorithm doesn't work full-stop:
Why does RSA need p and q to be prime numbers?

Question 1:
this implementation uses the number 57, which is not prime as it divides by 3.

Choose p = 13, q = 57, e = 5 and message 'm' = 4
Therefore n = pq = 741 and (p - 1)(q - 1) = 672
encrypt message m as m^e mod n = 4^5 mod 741 = 283
calculate decryption key d as e^-1 mod (p–1)(q–1) = 5^-1 mod 812 = 269
decrypt '283' by 283^d mod n = 283^269 mod 741 = 199 ≠ 4

How does using a non-prime number cause the result to be wrong?
I suspect the answer has something to do with the way that an inverse mod calculation looks for prime factors using the Euclidean algorithm, and if n is not the product of two prime numbers then it will give a different answer. But how is (p-1)(n-1) affected by p or q not being prime?

Question 2: p and q are the same prime number:

Choose p = 11, q = 11, e = 3 and message 'm' = 2
Therefore n = pq = 121 and (p - 1)(q - 1) = 100
encrypt message m as m^e mod n = 2^2 mod 121 = 8
calculate decryption key d as e^-1 mod (p–1)(q–1) = 5^-1 mod 100 = 67
decrypt '8' by 8^d mod n = 8^67 mod 121 = 24 ≠ 4

How does using two (prime) identical numbers cause the result to be wrong? For this one I don't know where to start.

A first step is to use the correct value for
the totient function
$\phi(n),$ which is $432$ and $110$ in your examples.

Even better use the
Carmichael function $\lambda(n)$ as described in RSA key generation, which is
$36$ and $110.$

With either of these numbers, your encrypted messages are decrypted correctly.


How can I solve the discrete logarithm modulo 2q+1 if I can solve it in the subgroup of order q? As part of my cryptography course I came across an exercise that neither me or my friends could figure out.

The problem statement is as follows:

  Let $p$ be a large prime of the form $p = 2q + 1$ with $q$ also prime. Let $g$ be a
  generator of $\mathbb Z^∗_p$ and consider the discrete logarithm problem: given $h = g^x$,
  find $x$.

  Let $G_q$ denote the subgroup of order $q$ and assume you have access
  to an oracle $O : G_q ×G_q \to \{0, 1\}$ that on input two elements $s, t \in G_q$ with
  $t = s^y$ returns the least significant bit of $y$. Design an algorithm (using the
  oracle) to solve the DLP in $G_q$ and an algorithm (again using the oracle) to
  solve the DLP in $\mathbb Z^∗_p$.

The first part of the question is fairly easy (solve DLP in $G_q$ with the oracle). However, we cannot figure out the second part.

I have solved the first part as follows:

  Run the oracle on $t$. On output 0 you know that the LSB of $y$ is 0, hence $y$ is even. $s^y$ can therefor be written as $s^{2*y'}$, which is still equal to $t$. By taking the square root of $t$, $\sqrt(t) = s^{y'}$ I no longer now the LSB of $y'$, but I know it's 1 bit smaller than $y$.

  Similarly if the LSB of $y$ is 1 I know I can write $t = s^{y} = s^{y'+1} = s^{y}s$, hence dividing $t$ by $s$ gives me a new pair $s',t'$ on which I can unleash the oracle.

  If I repeat the steps above $log_2(q)$ times and store all the LSB's I have found $y$.

Any hints/clues/advice will be most appreciated :).

Ok, lets try again from scratch.  First, some group theory definitions:

A group is a set of elements and an operation $\times$ which satisfies a specific set of properties (closure, associativity, an identity element, inverses)
A subgroup is a subset of elements of a group which, along with the group operation from the main group, satisfies those same set of properties (closure, associativity, an identity element, inverses).  Note that the subgroup uses the exact same group operation $\times$, except that it restricts the operands to the subset.

For a finite group $G$, a subset of elements $H$ is a subgroup iff the subgroup is closed; that is, if you take any two elements $h_1, h_2$, then $h_1 \times h_2$ is also an element of $H$.

Now, $\mathbb Z^∗_p$ is a group with $p-1$ elements; the operation $a \times b$ is defined to be $ab \bmod p$; this satisfies all the group properties.

Now, consider only those elements $x$ of $\mathbb Z^∗_p$ that can be represented as $x = y^2 \mod p$ for some value of $y$ (or, in other words, that quadratic equation has at least one solution for $y$).  This turns out to be closed; that is, if we have two such elements $a = c^2$ and $b = d^2$, then $a \times b = ab = c^2d^2 = (cd)^2$ is also within this subset, and so these elements make up a subgroup.  It turns out that this subgroup has $(p-1)/2 = q$ elements (and is the only subgroup of that size), and hence is the "subgroup of order q" of the question.

With that background in place, the question under discussion is: suppose we had an oracle that could, given values $s$ and $t$ that were point a part of this subgroup (that is, there are some values $u$ and $v$ such that $s = u^2$, $t = v^2$) it could give us the value $x$ such that $t = s^x \bmod p$ (note: this is $\bmod p$, not $\bmod q$, because the subgroup shares the same operator with the main group).  Now, with such an oracle, how can we solve the DLP in the full group, that is, given $u$ and $v$, either of which may or may not be a member of the subgroup, how can we solve $v = u^x \bmod p$?

The first thing to note is if we define $s = u^2$ and $t = v^2$, both $s$ and $t$ are members of this subgroup.  Hence, we can use the oracle to find $y$ with $t = s^y \bmod p$.  Replacing the definitions for $s$ and $t$, we get $v^2 = u^{2y} \bmod p$.  Now, if there is a solution $v = u^x \bmod p$, we know that $v^2 = u^{2x \mod p-1}$ (Fermat's Little Theorem), we know that either $2y = 2x \bmod p-1$, and since $p-1$ is even, either $y = x$ or $y + (p-1)/2 = x$


Why is padding used for RSA encryption given that it is not a block cipher? In AES we use some padded bytes at end of message to fit 128/256
byte blocks.  But as RSA is not a block cipher why is padding used?
Can the message size be any byte length (is the encrypting agent
free to choose) or must it be a certain byte length to use RSA
encryption?

RSA without padding is also called Textbook RSA.
The question why RSA without padding is insecure has already been answered
in this question.

We can fix a few issues by introducing padding.

Malleability: If we have a strict format for messages, i.e. that the first or last bytes contain a specific value, simply multiplying both message and ciphertext will decrease the probability of creating a valid (in terms of padding) message.
Semantical Security: Add randomness such that RSA is not deterministic anymore (a deterministic encryption scheme yields always the same $x$  for each instance of  $x = enc_{pubkey}(m)$ for constant $m$ and $pubkey$). See OAEP as an example on how to achieve this.

Edit: To answer the second question, RSA plain text are (unlike AES plain texts) limited by an upper bound. Messages must not be longer than the $N$ of the public key. It is also noteworthy, that common cipher schemes don't handle or pad blocks of RSA ciphertexts at all. Usually, the message is encrypted using a symmetric cipher (like AES) and only the key to this seperate cipher text is encrypted using an asymmetric cipher (like RSA). This is also called hybrid encryption.


Why is the GHASH output in GCM mode encrypted to calculate the tag? To calculate the authentication tag in the Galois/Counter mode (GCM), first a MAC is calculated using GHASH over the cipher text and the additional data. After that, this MAC is encrypted using GCTR (using the first counter).

My question is: Why is this last encryption step neccesary? What would the security problem be, if I just used the output of GHASH directly as the authentication tag?

What would the security problem be, if I just used the output of GHASH directly as the authentication tag?

Then someone listening into encrypted messages could recover $H$, one of which is correct.

The output of GHASH is a public polynomial (based on the ciphertext and the AAD), evaluated at a secret value $H$.  It turns out that, given such a polynomial, $H$ can be efficiently recovered, either by rewriting the polynomial as $\mathrm{GHASH}(H) + \mathrm{Tag} = 0$, and recovering the roots of that (which can be done in a finite field), or even easier, getting two such ciphertexts, rewriting both of them, and use an Extended Euclidean value to recover their common root.

Given $H$, an attacker can trivially make arbitrary modifications to encrypted messages; yes, that's bad.


Self-synchronizing cipher recovery from dropped bits This cryptography book says:

  There are also asynchronous or self-synchronizing stream ciphers,
  where the previously produced ciphertext bits are used to produce the
  current keystream bit. This has the interesting consequence that a
  receiver can eventually recover if some ciphertext bits are dropped.

CFB is an example of a self-synchronizing cipher. What does this mean that it can "eventually recover if some ciphertext bits are dropped"?

This is the equation for CFB:

$$
C_i = E_K (C_{i-1}) \oplus P_i
$$

There are 4 variables. I don't see how you eliminate more than two such that the receiver knows all but one and deduce the only unknown variable.

The receiver knows $k$. The receiver knows $C_i$ or $C_{i-1}$, but not both since the situation we're considering is "some ciphertext bits are dropped". The receiver does not know $P_i$ since it's the receiver and it's trying to decipher.

What am I misunderstanding?

First, when the textbook talks about 'dropped bits', they are not referring to bits that are received incorrectly; instead they are talking about transmission errors where certain bits are deleted.

One example of this would be if the sender sent the pattern:

$$0123456789$$

and the receiver received:

$$012456789$$

That is, the byte containing the value 3 has disappeared, and the 4 immediately follows the 2.

Furthermore, the textbook is referring to a rather older understanding of CFB.

  This is the equation for CFB:
  $$ C_i = E_K (C_{i-1}) \oplus P_i $$

Actually, in the original design of CFB, it was a bit more complex; it was:

$$ C_i = \text{Trunc}_k(E_K (C_{i-1} || C_{i-2} || … || C_{i-n/k})) \oplus P_i $$

where:

$k$ is a value selected by the designer
$\text{Trunc}_k$ is a function that returns only the first $k$ bits of its argument
$P_i, C_i$ are $k$ bit values (rather than the full block size of $n$)

This is equivalent to the modern understanding of CFB if $k=n$; however we can also consider smaller values of $k$.

Now, why would we do that (especially considering that CFB becomes less efficient with smaller $k$; we perform one block encryption for every $k$ bits)?

The answer is because of error recovery; suppose that we have a communication channel that could, by accident, add or delete blocks of $k$ bits (as explained above).  If we look at, for example, CBC mode, if we had a long encrypted stream, and deleted 8 bits from the ciphertext, the blocks that the decryptor used to decrypt would not line up with the blocks that the encryptor used, and so the decryptor would get gibberish; and they would never sync up (until a multiple of block size bits were deleted).

In contrast, if we used CFB mode with $k=8$, then deleting 8 bits from the ciphertext is not a major issue; the next 8 bytes (assuming a 64 bit block size; given the historic context we're talking about, this is appropriate) will be gibberish, but after that, things would sync up, and (assuming that the communication channel didn't get more errors) everything would decrypt correctly.

This is what the textbook was referring to; that even after add/delete errors, CFB mode (with an appropriate $k$) will resync.

And, yes, back in those days, we had communication channels that could add or delete blocks of bits as a common error; RS-232 could delete or (more rarely) add bytes (and so $k=8$ would be appropriate in that case); I believe that bisync could add or delete individual bits (and so $k=1$ would work there).

Now, all that is historic; in the modern error, we are rather more sensitive to the issues an attacker could do if he could modify the text.  Hence, we are less interested in self-synchronization properties of CFB, and are considerably more concerned about detecting when any error has occurred (either by accident or by maliciousness).


Proving that a scheme is $\epsilon$-perfectly secret I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell:
Let $\epsilon > 0$ be a constant. Say an encryption scheme is $\epsilon$-perfectly secret if for every adversary $A$ it holds that $Pr[PrivK^{eav}_{A,\Pi}] \leq 1/2 + \epsilon$.
Consider a variant of the one-time pad where $M = \{0, 1\}^l$ and the key is chosen uniformly from an arbitrary set $K \subseteq \{0, 1\}^l$ with $|K| = (1-\epsilon) \cdot 2^l$. Encryption and decryption are otherwise the same.
Prove that this scheme is $\epsilon$-perfectly secret.
I've tried the following:
$Pr[PrivK^{eav}_{A, \Pi} = 1]$ = $1/2 \cdot Pr[PrivK^{eav}_{A,\Pi} | b = 0]$ + $1/2 \cdot Pr[PrivK^{eav}_{A,\Pi} | b = 1]$
Assuming that the adversary is deterministic we can fix $m_0$ and $m_1$ generated by $A$. In addition, let $C_{m}$ be the set of possible ciphertexts derived from any given $m \in M$.
Then
$Pr[PrivK^{eav}_{A,\Pi} | b = 0]$ = $\sum_{c \in C_{m_0}} Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] \cdot Pr[C = c]$
= $1/|K| \cdot \sum_{c \in C_{m_0}} Pr[Priv^{eav}_{A, \Pi} = 1 | C = c]$
For any $c \in C_{m_0}$, let $M(c)$ be the set of messages that can be encrypted to $c$. Therefore
$Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] = 1 \cdot Pr[m_1 \notin M(c)] + 1/2 \cdot Pr[m_1 \in M(c)]$
Because if $m_1$ is not in $M(c)$, $A$ knows for sure that $m_0$ was encrypted. Otherwise, $A$ can only give a random guess.
Now, what is $Pr[m_1 \notin M(c)]$? In the best case, $A$ selects $m_0, m_1$ such that $|C_{m_0} \setminus C_{m_1}| = |C_{m_1} \setminus C_{m_0}| = 2^l - |K|$
As a consequence, $Pr[m_1 \notin M(c)] = Pr[c \in C_{m_0} \setminus C_{m_1}] \leq \frac{2^l - |K|}{|C_{m_0}|} = \frac{\epsilon}{1 - \epsilon}$
Thus, $Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] = 1/2 + 1/2 \cdot Pr[m_1 \notin M(c)] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$
This implies that $Pr[PrivK^{eav}_{A,\Pi} | b = 0] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$.
Since the same holds for $Pr[PrivK^{eav}_{A,\Pi} | b = 1]$, $Pr[PrivK^{eav}_{A,\Pi}] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$
Can someone point me out where my mistake in this reasoning is?
Thanks in advance.

There is no mistake.
Just prefix your work with the observation that any scheme is secure for $\epsilon\ge 1/2$ because all probabilities are less than or equal to 1.
Then consider the case $0<\epsilon<1/2$. Repeat your argument, then note that $2(1-\epsilon)>1$ and so $\epsilon/2(1-\epsilon)<\epsilon$.


Decryption possible only within a period of time Time-locked encryption and time-released encryption seem to be security systems focused on making sure that the decryption of certain message cannot take place before a certain time has passed.

However, I was wondering if there's in cryptography something aiming at the opposite of the above, so I would like to make the decryption possible ONLY during a certain period of time but NOT after that time has passed.

Would it be possible? If so, which mechanism do you know achieving this?

This is possible, but only if you introduce one or more parties in addition to the sender and receiver. Also, the receiver must be online when decrypting.

Typically, the security requirements would be that (a) if the recipient tries to decrypt inside the time window, he should be able to decrypt, even if the sender is not cooperating; (b) if the recipient did not decrypt the message inside the time window, he should not be able to learn anything about the contents of the ciphertext; and (c) any additional parties should not learn anything about the ciphertext.

From such requirements, it should be fairly straight-forward to come up with reasonable schemes. Some variant of threshold decryption should do the trick.


How HMAC.Update function works? I know how standard HMAC(key,msg) function works, and I want to write a Delphi port of HMAC class that implements Update function. The problem is that I don't understand how this Update function works (for example of Update function, see SSL definition here: https://www.openssl.org/docs/crypto/hmac.html).

If I understand this correctly, these two pieces of pseudocode should return the same HMAC (e.g. Result1 = Result2):

Code 1:
HMAC.Init;
HMAC.Update('key','abc');
HMAC.Update('key','def');
Result1 = HMAC.Digest;

Code 2:
HMAC.Init;
HMAC.Update('key','abcdef');
Result2 = HMAC.Digest;

I have found Python implementation here: https://hg.python.org/cpython/file/2.7/Lib/hmac.py but I have no knowledge of Python (I am Delphi programmer) and I don't undesrtand it. Could somebody explain it to me, or, possible provide an example of pseudocode/Delphi?

EDIT:
Probably I should have given some more details about the  reason I have asked this question. Basically, I need to calculate HMAC(key,msg) where msg is a content of a stream/file, which can be big - and therefore its contents can't be passed to HMAC function at once. Therefore I need to read blocks of the stream and continuously update the HMAC message, so that after whole stream/file was processed, HMAC digest contains HMAC of the whole stream.

Let's shortly recall, how HMAC looks like:

$HMAC_K(M):=H((K\oplus opad) || H((K \oplus ipad) || M))$

As you may observe here, the calculation of the outer hash is fully independant of the message.

So the standard approach into implenting "update" functionality is to store the key and go as follows:

Init(Key):
Store the Key in K
Init two Hash-function instances H1 and H2
Feed (K XOR IPAD) into H1
Feed (K XOR OPAD) into H2

Update(Message):
Feed the Message into H1

Final:
Get the digest of H1 and feed it into H2
Output the digest of H2


Number of words to be outputted from PBKDF2 based on HMAC-SHA512? I'm using PBKDF2 to generate a 512 bit key. My question is language agnostic, but for the sake of demonstration, I'm using CryptoJS, which defaults to using SHA1, but can be overridden like so:

var hasher = CryptoJS.algo.SHA512;
var output = CryptoJS.PBKDF2(input, salt, { keySize: 512/32, hasher: hasher });

The output string I get for input = "hello" and salt = "world" is

  d75f41243491533cc1ecc178d4bae14e7c3384dd2d94067c333594ebf3aa4cce4cd6670e4a3233af4237425617b3b21ec7d586a9478c0749cc40a778500821c8

However, upon inspection of the output object, it tells me that the output has:

64 sigbytes
16 words

If I run the function without specifying a hasher, which means I would be demanding a 512 bit output from SHA1, like so:

var output = CryptoJS.PBKDF2(input, salt, { keySize: 512/32 });

Then I get 64 sigbytes and 20 words, and a result of:

  798ef2617367d80daeacf8b457af7903eebf6d1f384c9fed762b14186036e912b37026c14ae315da0a9782aa773bdafcd9cd259e95381ac9ab26d026fe6a3375

My question is, what is the right number of words for a 512 bit function? Why does the second one result in more words?

PBKDF2's output is defined by the underlying functions which produce 160 bits (20 bytes) at a time. Let me explain using RFC 2898 which defines PBKDF2.
OK, so lets start with the output of PBKDF2 and work backwards:

Concatenate the blocks and extract the first dkLen octets to produce a derived key DK:
DK = T_1 || T_2 ||  ...  || T_l<0..r-1>

Now the values of T_x are defined as output of function F:

F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c

and U_i is again the output of the PRF. The PRF is the HMAC value and the HMAC output size is the same size as the underlying hash function.
OK, so the output size of the of the T_x values is consists of 4 blocks of length hLen (4 times 160 bits for SHA-1, making 640 bits or 80 bytes), the hash length. If there were 3 blocks then the output would be 60 bytes and you'd have 4 bytes too few.
Each hash consists of five 32 bit (4 byte) words, to make 160 bits. The size of a word in this case is determined by SHA-1 which is defined using 32 bit calculations. The same 32 bit word is used for the other calculations such as XOR. So in total the number of words in the output is 80 / 4 = 20.
So what you have there is the value of the output before the leftmost 64 bytes are taken. In general cryptographic functions should convert the output to bytes/octets of the correct size. But that has clearly not happened yet.

There is no problem for PBKDF2 with SHA-512 for the simple reason that you ask for exactly 512 bits, the output size of SHA-512 (i.e. four 64 bit words, as SHA-512 is defined using 64 bit operations).
Note that it could still return eight 32-bit words if the implementation uses 32 bit words instead of 64.


How does a "Tiger Tree Hash" handle data whose size isn't a power of two? Constructing a hash tree is simple enough if the data fits into a number of blocks that is a power of two.

root = H(H(A+B)+H(C+D))
         /            \
   H(A+B)             H(C+D)
   /    \              /   \
  A      B            C     D

In other cases, there is some flexibility. The missing blocks could be replaced with zeroes...

root = H(H(A+B)+H(C+0))
         /            \
   H(A+B)             H(C+0)
   /    \              /   \
  A      B            C     0

...passed up the tree...

root = H(H(A+B)+C)
         /      |
   H(A+B)       |
   /    \       |
  A      B      C

...hashed up the tree...

root = H(H(A+B)+H(C))
         /       |
   H(A+B)       H(C)
   /     \       |
  A       B      C

...or something different...

root = H(H(A)+H(B+C))
         /       |
      H(A)     H(B+C)
      /        /    \
     A        B      C

...and I'm just assuming that they do anything else like padding incomplete blocks before hashing.

The term "Tiger Tree Hash" seems to be used to refer to the root of a specific type of Tiger-based hash tree, but I haven't been able to find the details documented anywhere. How are such hashes constructed?

The Tree Hash EXchange format (THEX) spec (which seems to have dropped off the web, but is still available on archive.org) says, in section 2:

  2.1 Hash Functions

  The strength of the hash tree construct is only as strong as the
  underlying hash algorithm. Thus, it is RECOMMENDED that a secure hash
  algorithm such as SHA-1 be used as the basis of the hash tree.

  In order to protect against collisions between leaf hashes and
  internal hashes, different hash constructs are used to hash the leaf
  nodes and the internal nodes. The same hash algorithm is used as the
  basis of each construct, but a single '1' byte in network byte order,
  or 0x01 is prepended to the input of the internal node hashes, and a
  single '0' byte, or 0x00 is prepended to the input of the leaf node
  hashes.

  Let H() be the secure hash algorithm, for example SHA-1.

internal hash function = IH(X) = H(0x01, X)

leaf hash function = LH(X) = H(0x00, X)

  2.2 Unbalanced Trees

  For trees that are unbalanced -- that is, they have a number of leaves which is not a power of 2 -- interim hash values which do not have a sibling value to which they may be concatenated are promoted, unchanged, up the tree until a sibling is found.

  For example, consider a file made up of 5 segments, S1, S2, S3, S4, and S5.

                     ROOT=IH(H+E)
                      /        \
                     /          \
              H=IH(F+G)          E
              /       \           \
             /         \           \
      F=IH(A+B)       G=IH(C+D)     E
      /     \           /     \      \
     /       \         /       \      \
A=LH(S1)  B=LH(S2) C=LH(S3)  D=LH(S4) E=LH(S5)

  In the above example, E does not have any immediate siblings with which to be combined to calculate the next generation. So, E is promoted up the tree, without being rehashed, until it can be paired with value H. The values H and E are then concatenated, and hashed, to produce the ROOT hash.


Can one detect if two pairs of elements in Zp have the same exponential relation? Suppose that $p$ is a safe prime of 2048 bits ($p = 2q + 1$, and $q$ is prime).
Suppose that one is given two pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that:

$y_1 = x_1^{r_1} \pmod p$

$y_2 = x_2^{r_2} \pmod p$

Where $r_1$ and $r_2$ are unknowns.

Is it easy or hard to check if $r_1 = r_2$ without further knowledge? Does this problem have a name?

Is there a relation $f$ of $r$ and $x$, $y_1 = f(r,x_1)$, such that it is difficult to extract $r$ from it but it's easy to detect if the same $r$ is used in another pair $y_2=f(r,x_2)$ without leaking $r$?

This is another way of expressing the decisional Diffie-Hellman problem.  This problem is more typically written as 'given $g,\  g^a, g^b, g^c$, does $g^{ab} = g^c$?'.

As for the difficulty of this problem, it is believed to be difficult as long as you stay within a large prime subgroup; in this case (because you specify a strong prime), you means that you want to make sure that both $x1$ and $x2$ are quadratic residues.

Here's what can go wrong if you don't; an attacker can determine which subgroup any particular element belongs to; if he (for example) determines that $x1$, $x2$ and $y1$ are quadratic nonresidues, and that $y2$ is a quadratic residue, he knows that $r1 \neq r2$.  Staying within a prime subgroup prevents this possible information leakage.


How can companies authenticate messages sent between different security components in the company? How can companies authenticate messages sent between different security components in the company? (say SIEM for monitoring and IDS for intrusion detection)?

What protocols do they use in order to protect their authentication against an adversary who impersonate  to other security component in the company?

Usually point-to-point transport security is used for this. The most well known protocol is of course TLS, but there is also SSH, IPsec etc. etc. TLS works directly between two computers (although intermediate machines may of course route the IP packets from one to the other, without decrypting).

For communication between computer systems you would generally need client and server authentication. A public key infrastructure based on certificates (PKIX) makes most sense for the entity authentication part.

In addition end-to-end application level security may be used. This is simply wrapping up each message in a container such as a CMS container or XML signing and encryption. This way the message may be protected from the intended sender to the intended receiver, regardless of the protocols and hubs in between. It also has the advantage that a message can be protected before being send or being received.

There are too many protocols to name here otherwise. You'll have to look them up yourself. There is - to my knowledge - no generally accepted protocol for communicating between a SIEM and IDS.


Is OTP useful in modern electronic communication? I have seen from time to time questions about various OTP schemes and "OTP" (i.e. stream cipher) schemes. The most common OTP troubles appear to be:

How to extend size of previously generated key or how to generate key.
How to get key material securely to the recipient.

In electronic communication or storage encryption OTP appears scheme that is impossible to make work and if it works benefits are not clear. Requirement that the key needs to be the same size than input seems to be unbearable for many of modern use cases for encryption.

Is there any practice where OTP is useful in modern cryptography except:

As a component used on some proofs.
As a example ideal of encryption algorithm.

I.e.: Is it possible to base on OTP and provide the "information theoretic" strength to hashing (apparently not), authentication, etc.

The OTP is more a theoretical construction than a real world construction. The OTP suffers from three core problems:

Key Generation.
Key Distribution.
Key Destruction.

Let's deal with each one in turn.

Key Generation

Key generation is surprisingly difficult. In order to get the full security proof for the OTP, you need to each bit to be independent of every other bit and for there to be no bias whatsoever in the output.

Now practically every hardware RNG you're going to get does not fufil this in practice. They almost always run the bits through a hash function or some sort of entropy extraction routine. However, these routines do not carry a security proof that they preserve the underlying independent non-bias nature of the bits passed to them.

It's quite possible that if you the entropy extraction routine over enough bits, that a very small bias would be observed. However, any such bias, no matter how small would destroy the OTP security proof.

So you need to design your own RNG using only de-biasing techniques that maintain the security proof. Worse, you need to build an RNG with no detectable bias whatsoever over gigabits of output.

Key Distribution

Key distribution is a pain because the key has to be as long as the message. This immediately raises the question of why bother with encryption if you already have a secure channel of transmitting the key. Even with this massive key you haven't authenticated the cipher-text! You need provisions for that too.

This limits the OTP to scenarios where you want to time-shift a secure channel. It works okay in scenarios like the following. If Alice lives in Hong Kong and Bob lives in New York, they can meet twice a year and exchange a gigabyte or two of pad and be on their way.

Even if you're using QKD you've just moved the problem elsewhere. The problem now moves from a key distribution problem to an engineering problem. You've got to make a QKD device that is 100% reliable, doesn't have any side channel attacks, and is not susceptible to induced errors. Such as slightly overpowering/underpowering device to get duplicate photons, shinning a laser at the device to subtly break it or some other error inducing attack.

You've got many of the same problems of hardware quality as you had with the PRG. Good luck with that!

Key Destruction

Once you've used the key you have to make sure it is properly destroyed in both places. This is again more tricky than it seems at first.

If you don't do this properly and you use the key-stream twice, you have no security at all. If the program that manages the pad for you suffers some sort of error and fails to delete the used portion of the pad then re-use becomes quite likely.

Worse, because the pad is the same length as the message there's quite a lot of key stream to leak. This can leak in a number of ways. Parts of the key stream might have been paged to disk, for example, during encryption/decryption process.

An attacker could then decipher parts of your ciphertext by simply XORing bytes from your recovered hard-drive against the ciphertext.

Conclusion

The reason that the OTP isn't really fielded is that despite its strong security proof, the practical considerations around it actually render it insecure.

This is actually quite common in cryptography. Things with strong security proofs tend to be unworkable.

For every section of my reply, there is a documented case where precisely the problem I've raised has led to OTP messages being compromised.

OTPs are really hard to use properly and are typically less secure overall than a conventional scheme.

Small secrets, by virtue of them being small, are less likely to be leaked, easier to generate, easier to destroy and easier to transmit. All of these properties make them more secure.


Rijndael vs. Serpent vs. Twofish: General comparison Can anyone explain (or give a link to document about) why Rijndaal won the AES, especially comparing it to other finalists (Serpent and Twofish)? What criteria were used to make decision?

Or is there detailed comparison of these algorithms including cryptographic strength, performance tests on different CPUs and maybe FPGA implementations (AFAIK i.e. Serpent's round can be fully parallelized in dataflow architectures) and also point if there are some general issues with these algorithms (i.e. attacks on AES-256 that makes it less strong than AE-S128)?

The final report is here http://csrc.nist.gov/archive/aes/index.html. All five finalists had at least adequate security on all accounts studied during the process, but Rijndael had better performance characteristics in both software and firmware on other hardware than 32 bit processors, compared to the other finalists.


Difference between UF-CMA and UF-CMVA security I didn't understand the difference between this two definitions, and why UFCMA is weaker than UF-CMVA. Given a $MAC=(Gen,Tag,Vrfy)$ we define

$G_{\pi,\mathcal{A}} (\lambda):$

1) $k \leftarrow \$ \{0,1\}^{\lambda}$

2) $(m^*,\phi^*) \leftarrow \mathcal{A}(1^\lambda)$

3) Output $1$ if and only if $Tag_k (m^*)=\phi^*$ and $m^*$ is fresh (never queried from $\mathcal{A})$.
We are assuming that $\mathcal{A}$ can make $Q$ queries to $Tag_k()$.

$G^{UF-CMVA}_{\pi,\mathcal{A}} (\lambda):$

1) $k \leftarrow \$ \{0,1\}^{\lambda}$

2) $(m^*,\phi^*) \leftarrow \mathcal{A}^{Tag_k(),Vrfy_k()}(1^\lambda)$

3) Output $1$ if and only if $Vrfy_k (m^*,\phi^*)=Accepted$ and $m^*$ is fresh (never queried from $\mathcal{A})$.
We are assuming that $\mathcal{A}$ can make $Q_T$ queries to $Tag_k()$ and $Q_v$ queries to $Vrfy_k()$.

In pratice this new game is identical to the precedent game but here $\mathcal{A}$ has also access to the oracle $Vrfy$. But I can't understand why they are different and why if the tag $\phi$ is unique (that's for every key $k$, there exist a $\phi$ for every message i.e the algorithm $Tag$ is deterministic) the two Games are identical.

Why if the tag $\varphi$ is unique the two Games are identical?

If your Tag algorithm is deterministic, then verifying a tag-message-pair is actually just re-computing the tag for the message and checking if the provided and the re-computed tags match. So in this case $\operatorname{Vrfy}_k(m,\tau):=\operatorname{Tag}_k(m)\stackrel?=\tau$. So I hope now you see how step 3 is identitical in both games if $\operatorname{Tag}$ is deterministic.

  But I can't understand why they are different?

Because there are MAC algorithms for which $\operatorname{Tag}$ works non-deterministically, that is with large probability two tags for the same message will differ. Now you can no longer check whether a tag-message-pair is valid as above, you need a more complex verification algorithm.

As a contrived example consider the scheme $M$ which is HMAC with the following modification for the tag-generation: First you generate a random 128-bit string and prepend it to the message, then you run the modified message through the HMAC and return the concatenation of the random string and the HMAC-tag. Verification now works by taking the prepended random string and prepending it to the message before feeding it into the HMAC oracle.


What is the difference between data compression and compression in cryptographic algorithms? What is the differences between data compression as used in e.g. the ZIP protocol and compression as performed in cryptographic hashes? Are there common properties as well, apart from creating a smaller representation of the data?

In data lossless compression we want the data recoverable from the compressed form. This is usually helpful if the entropy is low like text files, so-called zipping.
In data lossy compression like JPEG, we still want to get the image (data) but we don't care about the full quality of the image. This can be considered as the original data can be recovered approximately.
The compression function of hash functions (one-way compression function) takes two inputs and produces one output - the compression ratio doesn't need to be 2:1. The transformation is required to be

one way: i.e. given an output finding the input value should be difficult.
and, have avalanche property: each output bit must depend on all input bits.

Being one way is not a desired property for lossless compression, however, lossy compression is not totally one way but some information is lost. JPEG or similar compression is not a good compression for hash functions.

Avalance property doesn't suit the data compression since that causes a random behavior on the compression. In avalanche property, we want each output bit to have a 50% chance of flip for a bit flip of an input bit.

In short, a single word "compression" should not be used to identify those. Use the "data lossless compression" or "data lossy compression" for data compression and "compression function" for hash functions.


Question about Cipher Block Chaining(CBC) I'm studying at the moment the CBC Encryption method,and I was asked in an excercise how many bits would be wrong after decryption if during the transmission 2 bits are interchanged.
My guess is that the whole bits are wrong due to how CBC works, am I correct?

It depends on the position of the two interchanged bits. Assume they have different values, i.e. one is $0$ and the other is $1$. Indeed, if they had the same value, interchanging would not affect plaintext decryption.

Let's say $n$ is the length of every block.

In CBC, every ciphertext block is involved in two plaintext blocks decryption: its own and subsequent one, therefore if one CT is corrupted only two PT will be so.

To move back to your question:

If $b_0$ and $b_1$ fall in the same block

2 plaintext blocks will be corrupted, $n+2$ bits will be corrupted.

If $b_0$ and $b_1$ fall in two adjacent blocks

3 plaintext blocks will be corrupted, $2n+1$ bits affected.

If $b_0$ and $b_1$ fall in two separate blocks

4 plaintext blocks will be corrupted, $2n+2$ bits affected.


Extending AES-GCM initialization vector We all know that applications of crypto primitives like to not think about the management of nonces, and initialization vectors and often prefer to just set them to random values. This sometimes leads to problems, when then IV is too short.
For example, in AES-GCM, the variable part of the IV is only 64 bits. If for each message we choose the IV randomly, we will start getting collisions after a $2^{32}$ messages; which is very insecure depending on the protocol.

Now a hacky way to roll our own crypto would be the following:
AES-GCM with extended-IV
First of all, we will stop using the normal IV part of the AES-GCM construction. Instead, for each message, we will mangle the key like this:
$$
K' = \text{KDF}(K || \text{nonce})
$$
where $K$ is the original key, $K'$ is the new key, and $\text{nonce}$ is a nonce that is long (say 256 bits) and randomly generated for each encryption; $\text{KDF}$ is assumed to be a properly domain-separated PRF that returns a new 256-bit value.
Now we encrypt our message using AES256-GCM with the new key. As mentioned, we set the IV to some kind of constant value. We transmit $\text{nonce}$ along with the ciphertext.

I would expect that, because collisions are possible in $K'$, this construction has only $\text{len}(K') = 128$ bits of security. However, I find it hard to reason about its security. The main question:
Could this scheme be used as an alternative for AES128-GCM, but with randomized nonces (similar to XSalsa20Poly1305)?

I mean hypothetically! I would not actually such a construction like that. I don't think that would make any sense.

Edit: As Poncho shows, this scheme is obviously not nonce-misuse resistant. I badly worded the question. I updated it.

Well, supposing everything is properly domain separated, nonces are always generated randomly for encryption queries, and your KDF behaves like a perfectly random function, the first step is to bound the probability of a nonce repeat. A birthday bound tells us that this happens with probability at most
$$
q^2/2^{256}\,,
$$
where $q$ is the number of encryption/decryption queries. So let's rule this case out, and move to the case where this never happens.
Next is the event of key collisions. Again, a simple birthday bound gives us a probability of at most
$$
q^2/2^{256}
$$
that there are repeated derived keys.
Now what we have here is, in fact, an instance of multi-user GCM where the same nonce is always used. That is, you have up to $q$ independent instances of GCM, and to break the scheme it suffices to break any one of these instances. (Strictly speaking, the multi-user setting gives you more freedom in choosing how many queries per user you can use, whereas here you're limited to 1 (encryption) query per user.)
The multi-user security of GCM was conveniently analyzed by Hoang, Tessaro, and Thiruvengadam in the ideal cipher model, which tells us in Theorem 3.1
$$
\begin{align*}
\mathbf{Adv}_{\mathtt{CAU}[H,E]}^{\text{mu-ae}} \le &\frac{d(p+q) + n(q + \sigma + p)}{2^k} + \frac{\sigma(2B + cn + 3)}{2^n} \\& + \frac{2q+1}{2^{2n}} + \frac{\sigma(\sigma + ncd) + 2pq}{2^{k+n}}\,.
\end{align*}
$$
Here we can set $n = 128$, $k = 256$, $d = q$ ($d$ is the number of nonce repetitions across users; since the nonce is fixed, this is equal to the number of queries), $c$ is a bound on the differential probability of $H$ (for GHASH, it can be set to $B/2^n$), $B$ is the maximum message size in blocks, $\sigma$ is the total number of blocks across queries (which can be bounded by $qB$), and $p \le 2^{n-2}$ is the number of offline AES evaluations (i.e., bruteforce of the key).
So, roughly speaking, as long as your messages are sufficiently short (to keep the $O\left(\frac{qB^2}{2^{128}}\right)$ term down), and the total number of queries remains well below $2^{128}$ (to keep the terms $2q^2/2^{256}$ and $O\left(\frac{q^2 + pq}{2^{256}}\right)$ down), as you suggested, this scheme should remain secure.


Why do these Python XTEA implementations require different deltas? I once needed to an XTEA snippet to from C++ to Python and it did not work properly. I then found a function on ActiveState.com and noticed that it looks almost exactly like mine, with one exception - for some reason, its "delta" variable was changed. Here's the test code:
import struct

def XTEA_encrypt(buf, k):
    ret = bytearray()
    for offset in range(int(len(buf)/8)):
        v0 = struct.unpack("<I", bytes(buf[offset*8:offset*8+4]))[0]
        v1 = struct.unpack("<I", bytes(buf[offset*8+4:offset*8+8]))[0]
        delta = 0x9E3779B9
        sum_ = 0

        for _ in range(32):

            v0 = (v0 + ((v1<<4 ^ v1>>5) + v1) ^ (sum_ + k[sum_ & 3])) & 0xFFFFFFFF

            sum_ = (sum_ + delta) & 0xFFFFFFFF

            v1 = (v1 + ((v0<<4 ^ v0>>5) + v0) ^ (sum_ + k[sum_>>11 & 3])) & 0xFFFFFFFF

        ret += struct.pack("<I", v0) + struct.pack("<I", v1)
    return ret

print(repr(XTEA_encrypt('\xfc\xd9\xd8A\x0b\xc4~\x82',
    [4060739823, 3225438839, 2808461571, 1241583342])))

With the new delta = 0x9E3779B9, the code prints \xec\xe8\xeaZ!\xec7\xde, as expected. On the other hand, the original C++ implementation (https://github.com/otland/forgottenserver/blob/788198e1afd96a0b83ddeb025a9f3910e72626d5/src/protocol.cpp#L87) had delta = 0x61C88647, which results in \x87Z\xed})\t:\xbe being printed. Why do the implementations differ?

If you take a close look at line 105 of the C++ implementation, you see that it subtracts delta from the sum instead of adding it:

103            for (int32_t i = 32; --i >= 0;) {
104                    v0 += ((v1 << 4 ^ v1 >> 5) + v1) ^ (sum + k[sum & 3]);
105                    sum -= delta;
106                    v1 += ((v0 << 4 ^ v0 >> 5) + v0) ^ (sum + k[sum >> 11 & 3]);
107            }

Since $\textrm{0x61C88647+0x9E3779B9}=2^{32}$, this is equivalent to adding the "normal" delta.

A rather odd design choice, if you ask me, but it works.


Is lattice-based cryptography relevant in symmetric cryptography? I've seen that lattice-based cryptography works well with public key cryptography as well as cryptographic hashing algorithms, but does it apply to symmetric key cryptography?

No, it is not, assuming you are talking about symmetric ciphers, pseudorandom generators, and hash algorithms.* Symmetric cryptography does not need to use any mathematical hardness problem to be secure, and there is no need to have a security reduction to one. It is technically possible to design a symmetric algorithm out of a core construct that is normally used for asymmetric cryptography, as in the very slow Blum Blum Shub or the backdoored Dual_EC_DRBG pseudorandom generators, but that's rare. Such constructions have no real advantages over typical symmetric ones.

Note that you do not need dedicated post-quantum cryptography to protect your symmetric encryption keys. The quantum Grover's algorithm does not hit symmetric cryptography nearly as hard as Shor's algorithm hits asymmetric cryptography. Even with extremely high-speed and low-latency quantum computers, it would suffice to double your key length from 128 to 256 to remain safe.

* If you consider homomorphic encryption to be symmetric, then the answer might very well be yes.


Why the output of elliptic curve based cryptosystems is smaller than the ordinary public key cryptosystems? I am trying to understand how much the output of elliptic curve based cryptosystems (for example elliptic curve ElGamal) is smaller than the ordinary public key cryptosystems.

I know that the security of a EC key size from a moduli of 160 bits is about the security of an RSA cryptosystem with a 1024 bits moduli. But my problem is that we usually have long messages, so we have to partition it into several blocks and then encrypt it. Therefore, when we have a 2048 bits long messages we make around 12 blocks and then encrypt them. Since the output is in the form of pairs, the out put will have a length of 2*13*150= 3900 bits.
Now we consider this example with RSA. in order to use RSA for such a message, since its moduli can accept up to 1024 bits messages, we need only 2 blocks as the input(each one 1024 bits long). RSA output is not in the form of pairs, so the final output will have 2048 bits long.

In conclusion: The output of RSA has the same length as input, while the output of EC base cryptosystems length is as twice as the input.

What's the problem? How EC is said to be smaller?

Based on what I wrote, I think it is smaller only for messages that their whole length is smaller than the moduli!

(Please see Table 5 of this as an example of EC's smaller outputs)

But my problem is that we usually have long messages, so we have to partition it into several blocks and then encrypt it. Therefore, when we have a 2048 bits long messages we make around 12 blocks and then encrypt them.

No, that's not what we do in practice.  Instead, when we need to public key encrypt a large message, we pick a random symmetric key, encrypt that key with the public key algorithm (RSA or ECC), and encrypt the large message with the symmetric key (e.g. with AES-GCM or ChaCha20-Poly1305).  We then send the two ciphertexts as a joint message.

That has the advantage of being computationally far cheaper (as we need to perform one public key encryption/decryption operation, no matter how long the message is).

In any case:

  Now we consider this example with RSA. in order to use RSA for such a message, since its moduli can accept up to 1024 bits messages, we need only 2 blocks as the input(each one 1024 bits long).

Even if we were to use RSA in such a multi-block mode, we wouldn't want to divide the message into blocks, and use RSA in the straight-forward manner.  If we did, then

If the adversary had a guess to the plaintext, he could encrypt the plaintext with the public key, and see if he gets the ciphertext
If we happened to encrypt related messages (for example, the two 2 block messages $M_0 || M_1$ and $M_0 || M_2$), the fact that there are related would be obvious.

Because of these reasons, we have to add randomness whenever we RSA encrypt a message (or key).


A modification of the Blum-Micalli construction Consider the following modification of the Blum-Micalli construction (denoted by BM):

$G_l(x) = f^l(x) || BM^l(x)$

I am asked the following questions about it:

Show it is a PRG of fixed stretch for every fixed $l$ polynomial in n.
Discuss the advantages/disadvantages of outputting also $f^l(x)$.
In particular, consider the case when a trap door permutation is used for $f$ and the resulting PRG is used within the pseudo random one time pad.

As an advantage I would say that this PRG gives $n$ more bits than plain Blum-Micali construction. However, I'm not sure how to handle the rest of the questions. Could you provide any hints?

Notation

$BM^j(x) = hc(f^{j-1}(x))\| \ldots \| hc(f(x)) \| hc(x)$

where $f: \{0,1\}^* \to \{0,1\}^*$ is a permutation on $\{0,1\}^n$ for every $n$ with hard-core predicate $hc$ and where $f^j$ denotes the composition of $f$ with itself $j$ times.

Solution

In this document you may find an answer as discussed in my class. I will still appreciate the effort to create a publicly available and pedagogic solution to this problem. Once it is here, I will remove the link.

One question that I still have is if the concatenation of unpredicatable functions is unpredictable.

Discuss the advantages/disadvantages of outputting also $f^l(x)$.

Knowledge of the trapdoor secret would allow the receiver of a message encrypted with the  pseudo random one time pad to recover the seed $x$ if one block of the generator output would be xored with a fixed value known to both the sender and receiver.

This would allow to encrypt more than one message by using a random seed for each message. If the seed could not be recovered from the ciphertext then sender and receiver had to securely exchange random seed values for each message in order to avoid using the same pseudo random one time pad twice.


Can anyone give an example where (asymmetric) crypto can go wrong due to selection of wrong groups? Basically the title says it all. It would be great if someone could tell give an example using provable security. More information about groups can be found at:

https://en.wikipedia.org/wiki/Group_(mathematics)

https://en.wikipedia.org/wiki/Group-based_cryptography

Basically, every time you choose a group where the required hard problem is not hard, then you will run into a problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography.

Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a generator. Then the discrete logarithm problem in this group is given $g$, $y$ you have to find the discrete logarithm $x=\log_g(y)$, i.e., compute $x$ such that $y\equiv xg \pmod n$. However, you can efficiently solve this linear congruence by using Euclid.

Consequently, the discrete logarithm problem in the group $(Z_n,+)$ is easy and thus every discrete logarithm based cryptosystem will be insecure in this setting.