When using AES-CBC-128, what attacks become feasible as you decrease the entropy of the IV? 16 bytes is the recommended entropy for the IV, AFAICT. Is 12 bytes of randomness with 4 fixed (across invocations of this encrypt function) bytes at the end, significantly worse? How so? What about 8 random bytes followed by 8 fixed bytes?

Decreasing entropy of IV doesn't just allow any attack. You can have IV entropy of 0 and if you send just one message using one key, you are safe as you used full 16bytes of entropy on IV. Deciding how big IV you need is based on how many messages attacker can see with same key and how big of problem such IV reuse is in your case.

But, as you send more messages smaller IV have problem that there is chance for collision in IV, which allows attacker to distinguish same starting blocks in ciphertext. So if you send two ciphertexts "message1" and "message2", attacker would be able to see that both ciphertexts started with some common start and then it changed. He won't be able to learn what that common start was, and if messages were same after first change, he won't be able to detect those. So it will only grant attacker minor help in breaking your cryptosystem.

Another problem that isn't directly related to size of IV, but it's predictability is choosen-plaintext attack. If your IV changes in predictable enough way and you have access to service that encrypts data with predictable IV, you can xor first block of your message with IV of message you wish to decrypt and with IV you predict to check if encrypted message was encrypted already. So if your IV is predictable, you can check if ciphertext X was encryption of plaintext P you have, even if they have different IV's.

So basic problem with smaller IV is that you increase chance that you will reuse it, which is only small problem in cbc. You should too make steps to make sure it isn't predictable. But beware: IV reuse attacks can be far more devastating, for example in ctr mode.


Does there exist a Cipher / Hash identification tool? Let's suppose I have two strings

One string is plaintext

The other is the result of running the plaintext through an unknown cipher.

Does there exist a tool where I can enter the pre and post-cipher text and have the tool spit out which cipher or hash may have been used?

I understand that such a tool isn't guaranteed to be accurate, but if it exists, it would be very useful to me right now.

No, such a tool does not exist and could not exist for any modern, secure cipher. If you do not have access to the key, you cannot correlate plaintext with ciphertext. For a hash algorithm, you can heuristically guess what the algorithm may be based on the length of the output, but that would only allow you to classify the digest as being from one of any number of possible hash algorithms. For example, a 160-bit output could be SHA-1, or maybe RIPEMD160, but not MD5.

If you have the input to the hash algorithm as well as the digest, then you can determine with certainty which hash algorithm was used to create it simply by running the input through all candidate hash algorithms and seeing which one results in a matching digest for that input.


Does google's Crypto.JS AES encryption use PBKDF2 as default? Does google's Crypto.JS AES encryption use PBKDF2 as default?

Some references, but I can't figure out the answer myself:

https://code.google.com/p/crypto-js/#The_Cipher_Algorithms

https://code.google.com/p/crypto-js/source/browse/tags/3.1.2/src/aes.js

The documentation says it's OpenSSL, not PBKDF2:

  When you use a CipherParams object in a string context, it's automatically converted to a string according to a format strategy. The default is an OpenSSL-compatible format

This can be verified in the source code. The implementation of the OpenSSL KDF is in evpkdf.js.

The key derivation function is usually referenced as EVP_BytesToKey which is the higher level function in the API that implements the KDF.


What is the PRG period of stream ciphers such as RC4 or Salsa20? I am confused about how long a stream cipher can be used before you should change the key. To be concrete, let me use the stream cipher based on RC4 as an example.

Let's say I want to encrypt a very long message. I pick a key with 128 bits and start encrypting using the RC4 stream cipher. How many rounds does RC4 have to run before its PRG starts over again? How about Salsa20: how long can that run with the same key before running the risk of leaking information?

I realize that as a practical matter the period will probably be far longer than any real-world message, but I am still interested in knowing the bound.

The internal state of RC4 consists of a shuffled 256-element array and two pointers into that array.  Thus, there are a total of $$256! \times 256^2 \approx 2^{1700.00}$$ possible states.  Since the state update function of RC4 is reversible, it acts as a permutation on this set of possible states, so that every starting state will eventually recur after sufficiently many iterations.

How many is sufficiently many?  Well, if we assume that the update function behaves like a random permutation (which it, of course, does not, but it's a good first approximation), then the expected cycle length is approximately $2^{1700}/2 = 2^{1699}$ iterations(!).  Indeed, the probability that the cycle length starting from a random state is at least $k$ iterations is approximately $1 - k/2^{1700}$; this means that hitting a cycle of less than, say, $2^{200}$ iterations should happen less than once in $2^{1700-200} = 2^{1500}$ initializations, i.e. basically never within the lifetime of the universe.

Of course, as noted, the RC4 state update function is not a random permutation.  For example, there's a known class of $254!$ short cycles of $256^2-256 = 65280$ states each; fortunately, the standard RC4 key setup is guaranteed never to hit them.  For more information on the actual cycle structure of RC4, see e.g. "Cryptanalysis of RC4-like Ciphers" by S. Mister and S. E. Tavares.


Is it a variant of Strong RSA assumption? Informally, the hardness of RSA/Strong RSA assumption lies in the hardness of factoring a large composite number $N$ having two large primes as its factors. If RSA modulus $N$ is a prime number, then the system is trivially breakable.

But, what about this variant of the Strong RSA problem presented in Ben Lynn's PhD dissertation? Here it says, given $c$, it's hard to find a pair $(g,a)$ such that $c = g^a$. RSA modulus $N$ hasn't been talked about here.

Are the above two notions synonymous?

The modulus $N$ is implicit in the group $\mathbb Z_N^\ast$ that $c$ and $g$ are chosen from. That is, in this context, $g^a$ is taken to mean "the residue class represented by $x^a\bmod N$ where $x$ denotes some representant of $g$'s residue class".

Therefore, when additionally requiring that $a\geq3$ and odd, this notion is equivalent to the strong RSA assumption as defined in Rivest's paper.


Does ShaCrypt have the properties which make BCrypt slow on GPUs? Sha256Crypt / Sha512Crypt are designed based on ideas of BCrypt but use SHA instead of Blowfish because of political requirements.

The Sha*Crypt algorithms have the advantage that they are used in /etc/shadow on all common Linux distribution.

Do the Sha*Crypt algorithms have the same properties concerning memory use which slows BCrypt down on graphic cards?

From the answer you linked to:

  For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward unrolled SHA-1 implementation).

What that tells us is that it is fairly easy to get big performance gains on SHA-256 (which also implicates SHA-512) using a GPU. The question then is, does ShaCrypt do anything special to slow GPU's down?

Looking through the example source code you liked to, it doesn't look like it. What I was looking for was a large (a few kilobytes) data structure that would be constantly accessed and modified. That doesn't exist from what I could see. Sure, there are data dependencies, which would slow down a single password calculation, but nothing to prevent parallelization of multiple passwords.

On an interesting note, there are JtR patches which would give you ShaCrypt GPU capabilties in John the Ripper. I was unable to find performance numbers, however.


Are there any non Canonical Verifiable Cryptographic MACs In the 2. edition of the Modern Introduction to Cryptography, by Katz and Lindell, there is a definition for MACs;

  Canonical verification. For deterministic message authentication codes
  (that is, where $\text{Mac}$ is a deterministic algorithm), the canonical way to perform verification is to simply re-compute the tag and check for equality. In other words, $\operatorname{Vrfy}_k(m, t)$ first computes $\tilde{t} := \text{Mac}_k (m)$ and then outputs $1$ if and only if $\tilde{t} = t$.

Then, later

  It is not hard to see that if a secure MAC uses canonical verification then it is also strongly secure. This is important since all real-world MACs use canonical verification.

All of the cryptographic MACs, that I know, use canonical verification.

Is there any non Canonical Verifiable Cryptographic MACs?
If not, then this definition is redundant, or is this definition is defined for future MAC schemes?

See Message Authentication, Revisited. This paper presents MACs with different properties, and in order to achieve these properties randomization is used. Since the MACs are probabilistic, the verification cannot be canonical.


What are the differences Between “White-Box Cryptography” and “Code Obfuscation”? I have been reading the question "What is a white-box implementation of a cryptographic algorithm?" and it led to this short article / Q&A which states in question 2:

Q2: What is the difference with code obfuscation?
Related and
complementary techniques for protecting software implementations but
with different security goals include code obfuscation and software
tamper- resistance. Code obfuscation is aimed at protecting against
the reverse engineering of a (cryptographic) algorithm while
software tamper-resistance is aimed at protecting against modifications
of the code. All these techniques have however in common that the
resulting implementation must remain directly executable.

Now, it shows the differences between obfuscation and temper-resistance, but it says nothing about the difference between white-box cryptography and code obfuscation.
So I guess my question is: are those two completely different things? Or is code obfuscation a way to achieve white-box cryptography? If the second is true, are there other ways to achieve it?

As you suspected, there's a very close relationship between white-box cryptography and obfuscation.  (Good instincts!)  White-box cryptography is basically all about obfuscating an encryption implementation.

White-box cryptography is obfuscation of crypto code. Imagine that you took an AES implementation, picked a random AES key, and then hardcoded that AES key into the code.  Obviously, publishing this code would be insecure, because it would immediately reveal the AES secret key.  It might be nice if we could obfuscate the resulting code, hardcoded key and all, in a way that preserves its function but hides the encryption key.  In other words, the result should be obfuscated code, which still computes the same function, but no longer reveals the AES key.  This is exactly what "white-box cryptography" does -- or, at least, what it tries to achieve.

So you can view white-box cryptography as a special-purpose obfuscation method, designed for obfuscating a very specific kind of code.

More background. There's a lot more that can be said about white-box cryptography.  For instance, many published methods for white-box cryptography have been broken; both white-box AES and white-box DES have been cryptanalyzed and are now known to be insecure.  As far as I know, every published approach to white-box cryptography has subsequently been broken, so it is not known whether it is possible to achieve the goals of white-box cryptography securely.

Here is an outstanding overview and introduction to white-box cryptography:

Marc Joye, On White-Box Cryptography.  Security of Information and Networks, 2008.


Generating Diffie-Hellman parameters efficiently I am working on an Android project for school and I am supposed to do a DHKE (Diffie Hellman Key Exchange). Everything works well.  The problem is that it takes a lot of time (really a lot) to generate DHParameters. Basically, in my code, this is the part that is the most time (and battery) consuming:

KeyPairGenerator kpgDH = KeyPairGenerator.getInstance("DH");
kpgDH.initialize(512);
KeyPair kpDH = kpgDH.generateKeyPair();

As you can see, the key length is only 512 bits, so it's not long, and it still takes at least 30-40 seconds (best case scenario), but it can go up to 400 seconds. I've tested it on several phones: Samsung Galaxy s2 (quad core), Samsung Galaxy s4 (quad core), Samsung Galaxy note 10.1 (quad core).

Does anybody know an alternative to generate more quickly the $p$ and $g$ for the Diffie-Hellman in order to speed up the process?

The standard solution is to generate $g$ and $p$ once during application development, then hardcode $g$ and $p$ in your code.  There are standard choices for $p$ and $g$, e.g., documented by NIST in their FIPS series.  I suggest using one of those.  There is no need to re-generate $g$ or $p$ each time.  You can use the same $g$ and $p$ for everyone.  See also Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526? for more details in this vein.

And make sure you use larger parameters.  For security, I recommend that the prime $p$ should be at least 2048 bits long, and $g$ should generate a subgroup of size at least $2^{128}$ (or generate the whole group).

ECDHE will provide even better performance than Diffie-Hellman, but you can try the above first.  Hardcoding the parameters should already make a huge difference.


Can Poly1305 be used with block ciphers running in CTR mode? Is the use of Poly1305 limited to stream ciphers? (note, I'm not talking about Poly1305-AES )?  Can it be used with block ciphers running in CTR mode?  If so, what other considerations/limitations are there?  I like the simplicity of using a single key for encryption/authentication, but authenticated modes like GCM are limited to block ciphers.

Q2: No, Poly1305 not limited to stream ciphers.  Yes, Poly1305 can be used with block ciphers running in CTR mode, if you use it appropriately.

I don't know whether the NaCl use is secure (whether NaCl uses it appropriately); I haven't tried to analyze NaCl.  Given that NaCl was built by reputable cryptographers, I would be inclined to guess that it's probably fine.  I realize this doesn't answer your full question.

Alternatively, if you were asking because you were thinking of designing your own scheme that makes use of Poly1305, my reaction is: if you're designing it, you should just use some reputable authenticated encryption scheme.  From an engineering perspective, that's probably the best solution: it minimizes the chances you foul things up somehow.  If you try to use Poly1305 in some custom way you design, the risk of introducing security problems is higher.


Encryption algorithms larger than 256 Bit for “big data” encryption? I'm somewhat new to encryption. When looking at encryption programs for big data, I frequently see a maximum of 256 bits.

Why do we generally restrict our (symmetric) keys to 256 bits? Can more powerful encryption algorithms be used practically, or is there a specific reason for that 256 bit maximum?

There is no need to go beyond 256 bits if the cypher is strong (can only be attacked by brute force).

This is because there are fundamental physical limits on the energy required to perform a computation. The Landauer limit is one: to switch one bit takes $kT\ln2$, where $k$ is the Boltzmann constant ($1.68\times10^{-23}$), $T$ is the temperature in Kelvin, and $ln2$ is the natural log of 2. On average brute forcing a 256-bit key will take $2^{255}$ operations (half of $2^{KeyLength}$).

Assume a computer exists which operates at this limit, is at the temperature of the cosmic microwave background (about 3K), and only needs to do one operation to test a key. It will then take $2^{255}\times 1.68\times 10^{-23}\times 3 \times \ln 2$ Joules, which comes out to about $2.02\times 10^{54}J$.

For comparison, the if the entire mass of the Earth were converted to energy it would only release $5.4\times 10^{41}J$. So you'd be annihilating 10,000,000,000,000 earth-sized planets just to brute force one key. Or building a Dyson sphere and capturing the total energy output of the Sun for 10,000,000,000,000,000,000 years.

In short, there are so many possibilities that the key length is sufficient, presuming you want your secrets to outlive the Sun.


compact rsa private key format As shown in Why does my SSH private key still work after changing some bytes in the file? a typical RSA private key file contains.

  The public modulus $n$ and exponent $e$;
  The private exponent $d$;
  The prime factors $p$ and $q$ of $n$;
  The "reduced" private exponents $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$;
  The "CRT coefficient" $q_{\text{inv}}=q^{-1}\bmod p$.

Looking at his annotated file I see

$e$ is negligible in size
$d$ is roughly the same size as $n$
$p$ and $q$ are each half the size of $n$
$d_p$ and $d_q$ are similar in size to $p$ and $q$
$q_{\text{inv}}$ is roughly the same size is $q$

Overall the parameters stored in the file seem to be just over 4.5 times the size of $m$.

From the RSA key generation process we can clearly see that all you really need to store are $p$, $q$, and $e$. All the other parameters can be derived from them. This results in a keyfile that is only slightly larger than $m$.

Now for the question:

Has anyone specified a format for storing such a "compact" private key and/or produced tools for converting between compact and regular keys?

In some ways, PuTTY's private key format is more concise as it doesn't include the "reduced" private exponents. BUT, because it includes the OpenSSH formatted public key, it basically has the modulo twice. See this URL for details.

Beyond that I don't think there's any standardized / widely used format that format stores keys in the way that you're proposing. Not MSBLOB, not PKCS1, not PKCS8 (which, for RSA, is basically a wrapper for PKCS1) and not XKMS. If there's a widely used RSA private key format that I missed lmk but of the ones I know about none support the kind of minimalist key you're describing.


Hash Collision Probabilities Please give help! how can I calculate the probability of collision? I need a mathematical equation for my studying.

Assume, I am using SHA256 to hash 100-bits. Thus:

SHA256 {100} = 256-bits (hash values) I would like to know the probability of collision.

This website:
https://preshing.com/20110504/hash-collision-probabilities/

Gave an equation: $K^2 / 2N$

But I could not know what is $K$ and $N$? Is K is the output which is (256-bits) and $N$ is the input which is (100-bits)

Please Help and Thanks in advance...

$n$ is the output size of the given hash function. To find a collision you try randomly generated $k$ different inputs. When we say the output size is $n$, it means that the output space has $2^n$ elements.

What you see on that website is the general case of the collision probability. We normally talk about the 50% probability (birthday attack) on the hash collisions as

$$ k = \sqrt{2^n}$$
You can also see the general result from the birthday paradox.

To have birthday attack with 50% percentage you will need $k = 2^{128} \approx 4.0 × 10^{38}$ randomly generated differently input for a hash function with output size $n= 256$


Is this method for exchanging private key using RSA sound? Bob know's Alice's public key, and he wants to make sure he's connecting to the one which has that key. Furthermore, Alice wants to verify when she gets a connection from Bob who'll give his public key that he is indeed the one who has that key.

Bob will send Alice half the AES private key and half the initialization vector which he generated randomly, both encrypted using Alice's public key.

Alice would reply by sending back what Bob sent + the other half of the AES private key and the initialization vector which she generated randomly as well.

Afterwards communication begin using AES crypto stream with a key composed of the two halves both exchanged. If a crypto exception was thrown at either side at any point, the connection will be terminated. No third message will be sent from Bob to Alice to verify that he got her part of the key, the AES stream will begin directly after Alice's message.

Note: I thought about using Diffie-Hellman, but what I didn't like what that the private key agreed upon would be the same for every session assuming the two parties will not change their public keys.

Is this enough for both to verify that each one is the actual owner of the claimed public key, and to exchange the AES symmetric key safely without creating potential security issues ?

You are inventing your own protocol.  Don't do that!  You're likely to get something wrong.

Instead, use SSL.  You can use SSL with a server cert and a client cert.  That solves exactly this problem; each party can verify the public key of the other end of the communication and verify they're talking to who they want to talk to.  If everything checks out, they have a secure connection they can use for their communication.  It solves the problem, and it has been vetted far more thoroughly than anything you invent yourself ever will be.


Key clamping in curve25519 not evident in generated key's binary representation I understand with curve25519 that the private key for secret.box is clamped...

I understand that this clamping process to clear the lower 3 bits in order to ensure the key is a multiple of 8, ensuring it's part of the right cyclic subgroup.

However, as I generate example keyPairs using sodium such as:

a67e2d949d00606d2b6d0d9114d3ee273f118a078151c7aad2b55694ea18bb39 // 1010011001111110001011011001010010011101000000000110000001101101001010110110110100001101100100010001010011010011111011100010011100111111000100011000101000000111100000010101000111000111101010101101001010110101010101101001010011101010000110001011101100111001

or

b2c80def0dc392671e5143e9804c1083a39c751eec7348383eb586d708b374cc // 1011001011001000000011011110111100001101110000111001001001100111000111100101000101000011111010011000000001001100000100001000001110100011100111000111010100011110111011000111001101001000001110000011111010110101100001101101011100001000101100110111010011001100

I noticed that despite being able to positively confirm they are part of the multiple of 8 subgroup, their binary representation does not have the lower three bits cleared...

So as you can see above, the binary representation of these random private keys doesn't have 000 for the lowest three bits. Yet when I check in SageMath, I can confirm both of these keys are multiples of 8.

Update:
I generated the keys using the libSodium->SecretBox->KeyPair()...

Which internally calls the clamping/scalar multiplication.

I also verified that despite not ending in three zeros (000) - the private keys are always of order 7237005577332262213973186563042994240857116359379907606001950938285454250989 and as such are of the correct subgroup.

Any idea why?

The clamping happens as part of the key agreement / signing procedure. The private key itself isn't clamped when stored.

(How did you test the numbers you have provided? None of them seem to be multiple of 8. Also recall that curve25519 keys are in little endian.)


AES CBC MAC splicing attack I'm trying to implement AES CBC MAC splicing attack in Python, the idea is:

given a message M, its tag Tm (MAC(M) = T), a new message N and its tag Tn we build a message such as: M||N = (M1, ..., Mn, N1 ⊕ Tn, N2, ..., Nn) that has the same tag with N (that is because you inserted a block which resets the algorithm).

The idea is quite clear, but I still cannot get the correct tag.

Here is my code (I'm new to Python, sorry):

from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from binascii import hexlify
import argparse
import pickle

AES_KEY_SIZE = 16
BLOCK_SIZE = AES.block_size

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("f1", type=str, help="f1")
    parser.add_argument("f2", type=str, help="f2")
    parser.add_argument("tag1", type=str, help="tag1")
    parser.add_argument("tag2", type=str, help="tag2")
    parser.add_argument("k", type=str, help="key")
    args = parser.parse_args()
    with open(args.tag2, "rb") as tag2:
        stored_tag = pickle.load(tag2)
    with open(args.k, mode="rb") as f:
        key = pickle.load(f)
    assert len(key) == AES_KEY_SIZE
    cipher = AES.new(key, AES.MODE_CBC, b'\0' * BLOCK_SIZE)
    with open(args.f2, mode="rb") as f2:
        f2_block1 = f2.read(BLOCK_SIZE)
        b1 = cipher.encrypt(strxor(f2_block1, stored_tag))
        with open(args.f1, mode="rb") as f1:
            file1 = f1.read()
        file2 = f2.read()
        the_rest_of_the_file = file2[BLOCK_SIZE:len(file2)]
        new = open('newfile.file','w')
        s = file1 + b1 + the_rest_of_the_file
        new.write(s)

if __name__=="__main__":
    main()

Just for completeness sake, CBC is defined as follows:

The error you have made is that:

$$M;N = (M_1, ..., M_n, N_1 ⊕ \mathbf{T_m}, N_2, ..., N_n)$$
(I've changed notation from M||N to M;N to reflect this isn't just concatenation)

You need to cancel the tag from the message $M$, not the tag from the $N$ message.
In that case, $T_{M;N}=T_N$ as required.


Is a signature scheme using a hash considered a hybrid cryptosystem? In Wikipedia there is a page on hybrid cryptosystems. However, although cryptography contains a lot more than just encryption, only hybrid encryption using key encapsulation and data encapsulation is discussed.

So my simple question is: should I consider a signature scheme using a hash a hybrid cryptosystem? Or is the term not that well defined and is it up to the entity that uses the term?

What I didn't directly see is that a hybrid cryptosystem is not the same thing as hybrid cryptography. A cryptosystem is commonly targeting encryption: it exists of a key generation function $\operatorname{Gen}$, an encryption function $\operatorname{Enc}$ of course a decryption function $\operatorname{Dec}$.

So although signature generation could probably be called hybrid cryptography, it commonly isn't a hybrid cryptosystem because it lacks the $\operatorname{Enc}$ and $\operatorname{Dec}$ function.


Where is the password hash calculated, locally on or the server? My computer security professor uses the following notation, where S denotes a server and A denoted Alice. Alice wants to authenticate herself to the server. The hash function is a hash chain where $h^n(x)$ denotes a hash function $h(h(h(..h_n(x)..)))$. $n$ is stored on the server.

Assignment:

  The following authentication protocol makes use of the Lamport hash
  construction (sometimes simply called ‘hash chain’). The construction simply consists of repeat-
  edly applying a hash function to an input value. We write h n (x) to denote hashing x n times,
  e.g. h 3 (x) = h(h(h(x))). Each user chooses a password pw and hashes this n times. He/she then
  sends it to the server. Let us assume that initially, n = 10 000. The server then stores a tuple
  (user, n, Y = h n (pw)) for each user in a database. Users can now authenticate to the server using
  the following protocol: The server checks if h(X) = Y , then decrements n and sets Y := X. So, after a successful run of
  this protocol the server holds a new tuple (user, n − 1, Y = h n−1 (pw)).

$ A \longrightarrow S : \text{I want to authenticate} \\
S \longrightarrow A : n\\
A \longrightarrow S : X = h^{n-1}(\text{password})
$

So now the hash is calculated on the device Alice uses. I am a bit confused now, because I always would receive the user's plain-text password and then hash it and store it in a database instead of receiving the password from the user. Also, I don't think this is possible at all in a web application.

My question is whether or not this protocol is used, and if so how would it be implemented. Also, what is more secure, hashing on the user side or the server side?

I can imagine a protocol like this, where $n$ starts from a high value, and gets decremented by the server at each login attempt. Characteristically:

The system has a degree of resistance against passive eavesdropping, which is no more susceptible to password search than server-side iterated hash is should the hashed password leak. That's a significant security benefit (especially if the client implements a minimum on $n$, which at least prevents a Man-in-the-Middle to find the password without heavy search; beware however that it does not prevent the MitM from obtaining a hash allowing to log-in many times).
The server can verify the password with one hash (or $k+1$ hashes if there has been $k$ consecutive failed logins). The bulk of the password hashing work is on the client side, which is a benefit for the server.
As long as $n$ remains high, and salt is used (there's none in the question), leak of the password database is no worse than in a normal system with hash on the server.

I have never seen this used. Main problem is, there's no support in browsers, thus the code doing the hashing on the client side will be JavaScript (for acceptability by users/prescriber), thus

that code is at best authenticated using https, and then there is little security benefit compared to password in clear over https, which is the norm.
JavaScript is sizably less efficient than native (the difference used to be huge, and still is on many platforms/devices), and the number of iterations much be chosen low enough to be acceptable on the less efficient platform.

About the same issues have killed all attempts to use PAKE that I have seen.

Also, the question's system is not really immune against active attackers able to impersonate the server, which is a serious drawback compared to some other PAKE. And password search is still possible from passive eavesdropping, which other PAKE manage to avoid.


How to break homophonic substitutions and nomenclators with too many symbols? Early attempts to thwart frequency analysis attacks on ciphers involved using homophonic substitutions, i.e., some letters map to more than one ciphertext symbol.
The earliest known example of this, from 1401, is shown below:

[Source: “Quadibloc” cryptography blog]
One variant is the nomenclator, where codewords are used to substitute many common words and names. The example below was used by Mary Queen of Scots in 1586.

[Source: Simon Singh]
According to Wikipedia,

By the late eighteenth century, when the system was beginning to die
out, some nomenclators had 50,000 symbols.

What is the best way to go about cracking those kinds of ciphers as the number of symbols used increases?

Regarding the first part of the question, I will just link to another answer I wrote in the past:
Why don't homophones hide multiple-letter patterns?

Summary: If you adjust the frequencies so that every single symbol is equally likely, then bigrams can be used for frequency analysis because they won't be uniform distributed. The structure of language is much more complex than frequencies of single symbols.

The second one is probably much easier to break: Let's assume you know that this kind of cipher is used. The list of the most common words in English should be fairly easy to generate. And then just pick arbitrary plaintexts and calculate the frequencies. When you consider the most common words as one symbol that will change the frequencies of the other letters to some degree, but the symbols for most likely words are between the most likely symbols of the alphabet.

To further improve this process:

Look at bigram frequencies. If you consider the symbols for (of, the), that is surely one of the most likely bigrams in such a cipher.
Adding more and more words as single symbols has no meaningful effect: Language is very, very non-uniform over words. See These lists on Wikipedia to get an idea:

In the "TV list", first is you with $1,222,421$ counts, 1000th is worst with a mere $2276$. That's a factor of $537$ times higher. Total count was $29,213,800$ for that list.
In the "Project Gutenberg list", first is the with $56,271,872$ per billion words, 1000th is names with $79,366.6$ per billion words. That's a factor of $709$ in those frequencies.
In the first list, the 1000th word has frequency $\approx 0.0000779$, and in the second list it's $\approx 0.0000794$. So if you consider every word a single symbol, this is the frequency. If you use multiple symbols of the normal alphabet for other words, the frequency of this special word would be even less.

On the nomenclators, there is also the problem: Since you assign one symbol per word, if you change the key you need to update the entire lists for both parties.

Frequency analysis can be applied to more than just single letters, and not all patterns of natural language can be hidden at the same time. This makes substitution ciphers really weak, especially if you use the same key (in the nomenclator this is the entire list) for more than a single, very short message.


Attack MD5 with partial information? If I generate an MD5 hash from 2 pieces of information – i.e. by concatenating two strings – how easy is it to guess what that hash is, assuming an attacker has knowledge of only 1 piece of those info?

It all boils down to the amount of entropy in the second string.

How is that second string generated?

If a human generates it, you can be pretty sure that most of the time it will be easy to figure it out. If a computer generates it using a cryptographically strong random number generator, and the string has sufficient length (say more than 80 bits), it will not be feasible for an attacker to guess it.


AES storing the length within the encrypted data versus storing it outside I need to strip off padding after decrypting AES(CBC)-encrypted data (I have control over encryption and data transmission), so have looked at adding the length of the original data to the payload being transmitted.

Option 1:
[ IV | Length | Encrypt(original data) ]

Option 2:
[ IV | Encrypt([ Length | original data ]) ]

Where:
"Length" is the 4-byte length of the original data

Would either of these approaches compromise the security of the message?

My concern with Option 1 is that you're giving away information for free: is there a way in which a potential attacker might be able to utilize the length of the data in attempting to compromise the message?

My concern with Option 2 is that a potential attacker (after determining by decompiling source code that the first 4 bytes indicate length) might try a brute-force approach, only needing to go through a much smaller part of the data for each potential key to determine if the message for that particular key is valid; i.e. that he only has to try one block or only the first 4 bytes of the message until he ends up with a block for which the first 4 bytes are relatively close to the size of the payload (hence effectively reducing the amount of time it would take to determine the message's key)

Are any of the aforementioned concerns valid?

What are the best-practices to store the message length / strip away padding?

First, the advice:

  What are the best-practices to store the message length / strip away padding?

Use standard padding, like PKCS#7 padding. It handles finding the length uniquely for you.
Use encrypt-then-MAC to prevent padding oracle attacks.

(Or better yet, don't use CBC. Use an authenticated encryption mode like GCM, or use CTR+MAC which doesn't require padding.)

  My concern with Option 1 is that you're giving away information for free: is there a way in which a potential attacker might be able to utilize the length of the data in attempting to compromise the message?

Maybe not, since the length in number of blocks is known anyway. However, in some cases it would be a problem, like if the attacker was expecting either 'no' or 'yes' as the message. It depends on your messages. You likely shouldn't rely on it remaining secret, though.

  My concern with Option 2 is that a potential attacker (after determining by decompiling source code that the first 4 bytes indicate length) might try a brute-force approach, only needing to go through a much smaller part of the data for each potential key to determine if the message for that particular key is valid; i.e. that he only has to try one block or only the first 4 bytes of the message until he ends up with a block for which the first 4 bytes are relatively close to the size of the payload (hence effectively reducing the amount of time it would take to determine the message's key)

This one is not a valid concern. AES has 128+ bit keys so a brute force attack is impossible. Whether they have to test one or several blocks for each key does not matter. Even if AES was broken somehow, such a small factor shouldn't matter, and the attacker could likely guess some other details about the message instead to gain a similar advantage (like all-ASCII for a certain part of it).


How much information do I leak if I upload multiple ciphertexts with cleartext overlaps? Suppose that $t_1, t_2, \ldots, t_n$ are my clear texts.  Suppose that for any $(i,j) \in \{1,2,\ldots,n\}^2$, $t_i$ and $t_j$ only differ in, say, the 1st $m$-many characters. Finally, suppose that I got an encryption function $\texttt{enc} : t_i \mapsto c_i$.  By function I mean a programming function, not necessarily mathematically.
To make it clearer, from the point of the adversary, the following is known:

The encryption algorithm is $\texttt{enc}$.
He knows all ciphers $c_1, c_2, \ldots, c_n$.  E.g. he sniffed them over the network.
While he does not know the clear texts $t_1, t_2, \ldots, t_n$, he does know the fact that they only differ in their 1st $m$-many characters (without actually knowing the 1st $m$-many characters, nor the other $m+1, m+2, \ldots$ characters).

My question is:  how much information would the adversary gain, given that he learned that the original clear texts are mostly identical and only vary in their 1st $m$-many characters, for these algorithms:

AES for various modes of operation,
RSA and its variations,
and scrypt?

Just to rephrase the question: suppose that $H(\{c_1,c_2,\ldots,c_n\}|\texttt{enc})$ is total number of information bits that the adversary managed to gain about the ciphertexts by simply knowing their encryption algorithm, the question is:

How bigger is $H(\{c_1,c_2,\ldots,c_n\}|\texttt{enc}, m)$ (information gain after also knowing that the original clear texts are mostly identical except for their 1st $m$-many letters)?

I don't know much about encryption, and I don't know how easy or hard this question is.  Any guidance is also highly appreciated.
The reason I'm concerned about this is due to me having multiple backups of my encrypted files, which their cleartexts have differed only slightly.  I'm concerned that I'm leaking information by keeping multiple encrypted copies of my slightly-modified cleartexts.

The question has opposite answers, depending on if we consider adversaries computationally bounded, or not.

Actual adversaries are computationally bounded, that is have limited computational resources. Against these, any cipher that is secure against Chosen Plaintext Attack has the property that similarities between plaintexts are undetectable and unexploitable¹: the adversary gains no useful information (about the key or the plaintexts) from such similarities. With a properly chosen key, and a correct implementation (no side channel leakage, secure Random Number Generator for Initialization Vector, salt, …), that's believed² to be the case for all modern ciphers, including the ciphers in the question:

AES in any of the standard modes of operation except Electronic Code Book.
RSA encryption per one of the PKCS#1 mode (RSAES-OAEP and the legacy RSAES-PKCS1-v1_5), or using an otherwise secure hybrid encryption. Textbook RSA $c_i\gets {t_i}^e\bmod n$ is not CPA-secure.
The scrypt tool, which really uses AES in counter mode³. For this tool, "properly chosen key" means that the entropy in the password, combined with the workfactor parameters used, must make brute force password search far exceed the computational capabilities of adversaries.

Against computationally unbounded adversaries (theoretical all-powerful things), practical cryptographic schemes including those in the question become insecure no later than when what's known about plaintext exceeds the key entropy. In that case, learning that $k$ original plaintexts are mostly identical in a certain location reveals $k-1$ times the length of the common plaintext, and when that exceeds the key size it becomes theoretically possible to find the key, by enumeration of all keys, decrypting the ciphertexts, and keeping the (probably, single) key that makes all the tentatively decrypted plaintexts match in the stated location.
The situation is even worse for RSA and public-key encryption in general: knowledge of the public key, which is assumed, allows a computationally unbounded adversary to decipher any ciphertext.

¹ Including with any amount of known plaintext.
² Moderns ciphers are believed (without mathematical proof) to be resistant against mathematical attacks; that is, when the key is random and unknown, it is believed there is no attacks much more computationally efficient than trying all keys (brute force), absent side channels. AES is among such modern ciphers, despite two decades of intense analysis.
³ According to this description of the format, the bulk of the ciphertext is data xor AES256-CTR key stream generated with nonce == 0. The later means that a multi-targets attack applies (assuming redundancy in plaintext, it is possible to test if a 256-bit AES key matches any of the ones used in multiple ciphertexts using a single block encryption), but that's unlikely to be a practical weakness.


Is "reused one time pad" safe to encrypt a message like "random number + mod"? I want to encrypt a message that contains a fixed length random number and a long mod.
i.e. 1234564284 (created like this 123456 + (123456 mod 9931))

I assume that reusing the same key is not a problem if the message is purely random but is the fact that the message is always given with a mod is opening a hole to find the key?

Here's my understanding of the encryption process you're talking about:

You take a random number $r$, and compute $t = r \bmod n$
You concatinate the two numbers $r$ and $t$, and express the concatination as a bitstring $u$
You then xor that bitstring $u$ with a secret bitstring $s$

You do the same for two different random numbers $r$ and $r'$, using the same values for $n$ and $s$.

If that is correct, then here is one way that someone with the two encrypted strings can recover a short list of possible $r, r'$ values:

Consider all possible $r$ values (in your example, $r$ was a 6 digit number, so that would be trivial; I don't know how long you would make $r$ in the real case)
For each such $r$, compute the corresponding $t = r \bmod n$, and combine them to form the bitstring $u$.
Exclusive-or $u$ with the first ciphertext to create the corresponding bitstring $s$.
Validate that guess on $s$ by attempting to decrypt the second ciphertext with it; recovering the corresponding $r'$, $t'$ values.  If $t' = r' \bmod n$, then add $r, r'$ to the list of plausible values.

In the simple example you gave (and depending somewhat on how you encode the numbers as bitstrings), that would give you a list of approximately 100 $r, r'$ values, one of which are the correct one.  It would be possible to list this to only the correct value given 1 or 2 more ciphertexts.

One time pad (where you use the secret bitstring $s$ only once) is safe because, while can reconstruct the possible values of $s$ (based on what the original message might be), you have no way to verify any possible $s$ value.  By reusing $s$, you provide such a way, and thus lose the security guarantees that you have when you use $s$ only once.

It is likely possible to design a more efficient attack method; however that method would likely depend on the details of how you encode an integer as a bitstring


SCRAM Iteration Count Attack I'm not sure if this questions belongs here or in the Information Security Stack Exchange, but here goes...

With SCRAM (RFC5802), is there anything that prevents an attacker masquerading as the server from sending an iteration count of one?

If there's nothing preventing this, then it seems that such an attacker could get hold of a weakly hashed password and easily crack it:

Client              Server
------              ------
username,nonce  ->
                <-  nonce,salt,iterations=1
ClientProof     ->

then, offline,

AuthMessage     = client-first-message-bare + "," +
                  server-first-message + "," +
                  client-final-message-without-proof

foreach password in dictionary
    SaltedPassword  = Hi(Normalize(password), salt, i) // with i==1
    ClientKey       = HMAC(SaltedPassword, "Client Key")
    StoredKey       = H(ClientKey)
    ClientSignature = HMAC(StoredKey, AuthMessage)
    ClientProof     = ClientKey XOR ClientSignature
    check(ClientProof == StolenClientProof)

The problem I see with SCRAM is that the client has to trust the server with the iteration count before the the client can even authenticate the server.

I suppose the client could enforce a minimum iteration account to mitigate this attack, but this is not mentioned anywhere in the SCRAM spec.

You are correct.  This is mentioned somewhat obliquely at the beginning of §9 ‘Security considerations’:

  If the external security layer used to protect the SCRAM exchange
     uses an anonymous key exchange, then the SCRAM channel binding
     mechanism can be used to detect a man-in-the-middle attack on the
     security layer and cause the authentication to fail as a result.
     However, the man-in-the-middle attacker will have gained sufficient
     information to mount an offline dictionary or brute-force attack.

Thus, you should really avoid using SCRAM to authenticate the server to the client.  You might prefer to look into a password-authenticated key exchange like SRP or SPAKE2+ instead.


Related-key attacks on AES According to Wikipedia:

  Related-key attacks can break AES-192 and AES-256 with complexities $2^{176}$ and $2^{99.5}$, respectively.

What are the requirements for these attacks (i.e how many related keys, what should the relationship between the keys be)? Optionally, how do the attacks work in summary?

The attack is described in the article Related-key Cryptanalysis of the Full AES-192 and AES-256 and applies in the following situation:

There is a key owner; the key is $K_A$ and the attacker tries to guess it.
The key owner can somehow be persuaded to compute three other keys $K_B$, $K_C$ and $K_D$, from $K_A$, using a specific derivation algorithm ($K_B$ is equal to $K_A$ XORed with a constant that the attacker chooses; $K_C$ and $K_D$ use a more complex but equally deterministic derivation algorithm).
Then, the attacker can make the key owner encrypt and decrypt arbitrary blocks -- that the attacker chooses -- with the keys $K_A$, $K_B$, $K_C$ and $K_D$. The key owner will accept to process up to $2^{99.5}$ blocks (that's 16-byte blocks, hence a grand total of about 14 thousands of billions of billions of gigabytes).
Finally, the attacker has access to some storage space of about one million of billions of gigabytes.

Under those conditions, the attacker can guess $K_A$. For details, see the article.
The name "related-key attack" comes from the involvement of several distinct keys, linked together by known relations. Resistance to such attacks were not part of the evaluation criteria during the AES competition (when Rijndael was chosen as AES). Related-key attacks are not very practical (even if the $2^{99.5}$ chosen plaintext/ciphertext value was not ludicrously large, the conditions on the four keys would still make the attack only theoretical).


How to enforce data privacy, integrity and authenticity of distributed firmware images for an embedded device? I'm developing a bootloader for an embedded device, with which it should be possible for customers (i.e. device owners) to update the device's firmware.
It is required that:

the firmware is distributed encrypted
the firmware's integrity is protected
the firmware is authentic, meaning that it was released by us (the manufacturer).

Based on my limited knowledge about cryptographic schemes, I came up with the following potential solution (see below for explanation):

For enryption and data integrity the firmware would be encrypted using AES256 in EAX mode using a key, which is shared between the manufacturer and the bootloader on the device, in addition to a nonce (i.e. initialization vector), which is encrypted (signed) using a private RSA key
The AES encrypted firmware and the RSA encrypted nonce are then distributed to the customer
The bootloader on the customer's device would then decrypt the nonce with the "public" RSA key (to ensure authenticity), and decrypt the firmware using the AES key and the nonce

Does this constitute a valid scheme for a secure bootloader (in terms of data privacy, integrity and authenticity)?

I am aware that using AES in EAX mode already provides data authenticity, however I would like to make sure that authenticity is still ensured in case the AES key is compromised.

First, if you mean to sign something, you should use a signature algorithm, rather than "RSA encryption" with private key, which on its own may be very weak.

Now the main issue here is that the RSA part is only authenticating the nonce. Anyone who knows the AES key can just encrypt an arbitrary firmware image with a nonce they've already seen. This allows them to reuse the earlier signature. So there's no guarantee of authenticity if the AES key is compromised.

To fix this you could sign the whole encrypted image – nonce, authentication tag and all. With a strong signature algorithm (e.g. RSASSA-PSS) using a strong hash function, there is no way even knowing the AES key to encrypt another image with the same signature.


Seed/key algorithm security Currently I'm working on implementing a seed/key algorithm to limit access to a tool for authorized users. My understanding of the algorithm is that its strength is derived from the seed itself. However the majority of articles say "The basic idea is that the server provides a seed -- a short string of byte values -- and the client is required to transform that seed into a key using a secret algorithm." If the algorithm's security is based on the seed, why is it "a short string of byte values" instead of the longest possible string of byte values?

"Short" and "long" are relative terms.  If I secretly make 128 coin flips and write down the results, that sounds like a lot of coin flips, doesn't it? There's $2^{128} > 10^{38}$ combinations I could get, a number bigger than 1 with 38 zeroes after it, so you have no hope of guessing what results I got.

Yet that unguessable result fits in $128 ÷ 8 = 16$ bytes, which almost everybody would call short byte string.  That is, it's short if you're trying to store it in a computer, but impossibly long if it was picked at random and you're a bad guy trying to guess it.

Modern symmetric cryptographic algorithms come in 128-bit and 256-bit strength, whose keys fit in 16 and 32 bytes respectively, and there's no need for their keys to be any longer.  Many public key algorithms do use longer keys (for technical reasons) but even there we're talking about kilobytes at most for popular ones.


Adding identical homomorphically encrypted inputs What would happen if you added two inputs, one known and one unknown, both encrypted with a fully homomorphic encryption scheme, and then checked the result by dividing it by two? Wouldn’t this tell you if the data is identical?

Maybe you are looking for something like MPC, where parties want to compute a shared result, but need to keep their data private. Well, as you observed, the result of the computation can reveal more or less information depending on the security model and the number of parties involved. However, you can achieve secure multi-party computation using homomorphic encryption, as indicated in this paper On-the-fly Multiparty Computation on the Cloud via Multipkey Homomorphic Encryption. Unfortunately, the scheme described in the paper is no longer secure for practical computation as recent work by Ducas et.al proved.


Proxy Re-Encryption with provable re-encryption target Suppose Alice has encrypted some plaintext $P$ to Bob. Bob wishes to re-encrypt this information to Charlie via proxy, in such a manner that:

The proxy cannot obtain $P$
The proxy can prove that Bob has provided a valid re-encryption key, meaning that Charlie will be able to obtain $P$ by decrypting with his private key
The proxy can prove that the ciphertext originated from Alice

Is such a scheme possible?

PRE schemes guarantee Q1, if they are even remotely worthwhile.
Alice could add a signature over her public signing key and the ciphertext to accomplish Q3.
I haven't seen any works that guarantee a re-encryption key from B to C is valid.


Translation based block cipher The paper "On the group generated by the round functions of translation based ciphers over arbitrary finite fields" states:

  Definition 3.3. A block cipher $C =  \{ \tau_k | k ∈ K \}$ over $F_q$ is called translation based (tb) if:

  each $\tau_k$ is the composition of $l$ round functions $\tau_{k,h}$ , for $k ∈ K$, and $h = 1, . . . , l$,
  where in turn each round function  $\tau_{k,h}$ can be written as a composition $\gamma_h\lambda_h\sigma_{φ(k,h)}$ of three permutations of $V$ , where:

  $\gamma_h$ is a bricklayer transformation not depending on $k$ and $0\gamma_h = 0$
  $\lambda_h$ is a linear permutation not depending on $k$,
  $φ : K × \{1, . . ., l\}→ V$ is the key scheduling function, so that $φ (k, h)$ is the $h$-th round key,  given the master key $k$;

  for at least one round index $h_0$ we have that

  $\lambda_{h_0}$ is a proper mixing layer, and
  the map $K → V$ given by $k → φ (k, h_0)$ is surjective, that is, every element of $V$ occurs as an $h_0$-th round key

How do I check if this map is surjective? Is AES a translation based block cipher?

Well, you probably cannot check this without a somewhat explicit specification of $\varphi.$ In general, if the key scheduling function has a simple structure, and if $|V|=|K|$ this becomes easier; In that case, if  $\varphi(h_0,\cdot)$ is a permutation you are done.


On Proving That a Primitive Does Not Exist In the paper of Hsiao and Reyzin, Section $1.4$:

  Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $Q$ does not exist

Since the statement is about trying to rule out the implication $Q \rightarrow P$, showing that $Q$ does not exist will indeed do the opposite: it makes the implication true for the trivial reason that $(\mathsf{false} \rightarrow \mathsf{proposition})$ is $\mathsf{true}$ for any $\mathsf{proposition}$.

Could someone explain?

(Note that this attempted answer contains a significant amount of guessing and must not be considered reliable!)

If one assumes "there is a general reduction from $P$ to $Q$" to mean "existence of $Q$ implies existence of $P$" (which is up to interpretation since the authors do not clearly define that term, but it seems somewhat reasonable), then the statement in question is wrong: Under this assumption, it can be reformulated as

  If the existence of $Q$ does not imply the existence of $P$, then $Q$ does not exist.

...whose contrapositive

  If $Q$ exists, then the existence of $Q$ implies the existence of $P$.

is equivalent to "there is a reduction from $P$ to $Q$", and this is clearly untrue in general.

My best guess is, still under the assumption mentioned in the beginning, that this is a simple typo and they actually meant

  Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $P$ does not exist

...which is true (and still conveys the point they are trying to illustrate) since its contrapositive

  If $P$ exists, then the existence of $Q$ implies the existence of $P$.

is obviously a tautology.


Is it bad design to reuse an AES key? The company I work for needs to develop a simple system where, for each client, we encrypt a token on our server, which is then transmitted to the client. The decryption is performed by the server itself when the client transmits the token (thus the only machine that performs crypto is the server).

The token is for an external service, so integrity checking is not an issue.

I wrote code that encrypts these tokens using AES/CBC, using the same key and a unique IV; I am not aware of any practical attacks against AES, even with an arbitrarily large number of known ciphertexts.

My colleague insists that an adversary could break this (i.e. get the key and decrypt stuff) after collecting a (possibly large) amount of ciphertexts; thus, he argues that we should have one key per client on the server.

Who is correct?

Now, on to your question.
But, since reusing the IV with the same key is something that you should never, ever, ever do, I'm going to assume that instead, you are generating a new random IV for each encryption, but using the same global encryption key.

The answer really depends on what your colleague means when he says break. There are academic breaks and there are practical breaks.

Your colleague is correct if we are referring to academic breaks. Assuming you are generating good, random IVs for each encryption, after capturing $2^{64}$ ciphertexts, we can expect to have had one duplicate IV (this comes from the birthday problem). Given the two ciphertexts that have duplicate IVs, the attacker can distinguish whether or not the two ciphertexts encrypt the same plaintext. Or even more accurately, the attacker can determine the number of blocks starting from the beginning that are the same. Once one block is different, however, the attacker cannot distinguish any further. That is an academic break. Capturing $2^{64}$ ciphertexts would be a very noisy attack and would require lots of disk space to store. But is not outside the realm of possibility.

That said, I don't see any way an attacker could feasibly break the key or a plaintext only given access to a huge (but practical) number of ciphertexts.

A better design
What would probably be a better design would be to generate a new, random key and IV for every encryption. Encrypt the plaintext with those (and use HMAC or an authenticated encryption mode). On the server you should have an asymmetric key pair (for example, an RSA key pair). Encrypt that random symmetric key using the public (RSA) key. Send the ciphertext and the encrypted symmetric key to the client.

When the client sends this back, you would decrypt the symmetric key using your private (RSA) key. Then decrypt the ciphertext with that key and check the HMAC or authentication tag.

My final suggestion is to hire somebody very knowledgable in this area to review your design and implementation (or even to help out with the design process) so you are not putting your customers at risk. I doubt it would cost very much.


Is this a correct way of use symmetric encryption? If I want to encrypt some block of text in AES, but at the time of decryption I don't have a way to check if the symmetric key is the correct one. So I:

Generate a randomKey, and use that to encrypt the text.
Encrypt the randomKey plus its hash using the user provided Key.
Save everything to a file.

Encryption

var userKey;
var plainText;

var randomKey256 = generateHexString(256);
var hash256 = sha(randomKey256);
var signature512 = concat(randomKey256, hash256);
var header = AES256_encrypt(signature512, userKey);

var cipher = AES256_encrypt(plainText, randomKey256);

var encryptedFile = concat(header, cipher);

Decryption

var userKey;
var encryptedFile;

//split encryptedFile in header|dataCipher
var header = encryptedData.substring(0,512);
var dataCipher = encryptedData.substring(512, null);

var signature512 = AES256_decrypt(header, userKey);

//split signature512 in RandomKey|Hash
var randomKey256 = signature512.substring(0,256);
var hash256 = signature512.substring(256,256);

if(SHA(randomKey256)==hash256){
    //valid key

    var plainText = AES256_decrypt(dataCipher, randomKey256);
}
else{
    //invalid user key
}

Obviously this is not real code. I understand that I will not be implementing my own security. I'm assuming that the whole thing would be encrypted in a safe environment. The user key is NOT going to be transmitted or stored anywhere.

What you did seems fine for verifying the key is correct.

However, unless AES256_encrypt uses an authenticated mode of encryption (in which case the whole exercise would be unnecessary), there is nothing that prevents an attacker from modifying the message. And depending on the mode of encryption used, that can even compromise the privacy of the message.

It would be best to use authentication. For example, you could calculate an HMAC over the data. That immediately proves that the HMAC key is correct if the message authenticates. To prove the AES key is correct as well you can derive them both from the same base key, e.g. a = HMAC(k, 'auth'), e = HMAC(k, 'enc') and then use key a for an HMAC over the ciphertext and e for AES encryption.


Combining keys after key expansion: is it secure? I've found an algorithm taht performs the following: expand the two keys using cryptographic hashing functions so the final keys will look like nonsense ASCII, then XOR them together to create a single key.

Is this algorithm secure?

Is there any benefit to xor together two keys rather than one with the message?

Well, yes.

The output of the cryptographic hash functions is indistinguishable from random - although not perfectly secure. So if you have $c = \operatorname{H}(K_1) \oplus \operatorname{H}(K_2) \oplus p$ then the result should be dependent on both keys, and you would almost have doubled the key size. This is similar to use two iterations of a block cipher and XOR them together. The XOR function itself should not leak any information about the hash values themselves.

There are however (quite) a few practicalities:

hash algorithms are sometimes not designed to be resistant to side channel attacks, and hashing keys may leak information about the keys themselves;
if the keys themselves are not very secure - e.g. relatively short or non-random - then having a hash could be used to distinguish the valid key values;
key reuse, as in a one time pad, is obviously catastrophical to security.

Using a key derivation function KDF such as HKDF over the concatenation of both key a values and then a trusted cipher would of be a much better way of accomplishing the same level of security, although I would imagine that the scheme in the question is more efficient on restricted platforms. Obviously a cipher has the advantage to be able to encrypt almost any amount of data instead of being restricted to the output size of the hash.

Finally, if the keys are already fully secure, they could be directly used in a one time pad. If the keys are passwords then a password based KDF should be used instead to strengthen the key material before it is used.


Recovering public key with small R parameter I use for tests small toy 16-bit elliptic curve:
Modulus prime p: 65167
a:       0
b:       7
order:   64879
G:      (62171,14828)

(generated by brichard19/ecdl on Github)
I use procedures:
bool Ecdsa16::sign_simple(const uint16_t privateKey, const uint16_t msgHash, const uint16_t nonce, uint16_t &outR, uint16_t &outS) {
    if (nonce==0 || nonce>=CurvePoint16::ORDER) return false;
    CurvePoint16 p = CurvePoint16::G;
    p = CurvePoint16::privateExponentToPublicPoint(nonce);
    uint16_t r = p.x.value % CurvePoint16::ORDER;
    if (r == 0) return false;
    outR = r;
    uint16_t s = (int64_t)reciproc(nonce, CurvePoint16::ORDER) * (msgHash + (int64_t)r * privateKey) % CurvePoint16::ORDER;
    if (s == 0) return false;
    s = std::min((int)s, CurvePoint16::ORDER - s);
    outS = s;
    return true;
}

bool Ecdsa16::verify_simple(const CurvePoint16 &publicKey, const uint16_t msgHash, const uint16_t r, const uint16_t s) {
    if (publicKey == CurvePoint16::ZERO || !(publicKey.z.value==1) ||
        !(publicKey.x*publicKey.x*publicKey.x+FieldInt16(7)==publicKey.y*publicKey.y))
        return false;
    CurvePoint16 checkzero = publicKey;
    checkzero.multiply(CurvePoint16::ORDER);
    if (checkzero!=CurvePoint16::ZERO) return false;
    if (!(0 < r && r < CurvePoint16::ORDER))  return false;
    if (!(0 < s && s < CurvePoint16::ORDER))  return false;
    uint16_t  w = reciproc(s, CurvePoint16::ORDER) % CurvePoint16::ORDER;
    uint16_t u1 = ((uint32_t)msgHash * w) % CurvePoint16::ORDER;
    uint16_t u2 = ((uint32_t)r * w) % CurvePoint16::ORDER;
    CurvePoint16 p = CurvePoint16::G;
    CurvePoint16 q = publicKey;
    p.multiply(u1);
    q.multiply(u2);
    p.add(q);
    p.normalize();
    return r == p.x.value % CurvePoint16::ORDER;
}

bool Ecdsa16::recovery(const uint16_t msgHash, const uint16_t r, const uint16_t s, CurvePoint16 &publicKeyA, CurvePoint16 &publicKeyB) {
    const uint16_t &order = CurvePoint16::ORDER;
    const uint16_t &zero = 0;
    if (!(zero < r && r < order && zero < s && s < order))
        return false;
    FieldInt16 rf(r);
    CurvePoint16 R1(rf);
    CurvePoint16 R2 = R1;
    R2.negate();
    uint16_t rinv = reciproc(r, CurvePoint16::ORDER);
    uint16_t negmsg;
    negmsg = CurvePoint16::ORDER - msgHash;
    if (msgHash>=CurvePoint16::ORDER)
        negmsg+=CurvePoint16::ORDER;
    uint16_t u1 = ((uint32_t)negmsg * rinv) % CurvePoint16::ORDER;
    uint16_t u2 = ((uint32_t)s * rinv) % CurvePoint16::ORDER;
    CurvePoint16 u1G = CurvePoint16::G;
    u1G.multiply(u1);
    CurvePoint16 u2R1 = R1;
    u2R1.multiply(u2);
    CurvePoint16 u2R2 = R2;
    u2R2.multiply(u2);
    publicKeyA = u1G;
    publicKeyA.add(u2R1);
    publicKeyA.normalize();
    publicKeyB = u1G;
    publicKeyB.add(u2R2);
    publicKeyB.normalize();
    return true;
}

I notice, that for some nonces recovery is bad, although verification is good. Bad nonces seems to be random, but r parameter for bad recovery is always small: maximum is 285.
modulus_p - order = 65167-64879 = 288. It is error in my recovery procedure or signing should be bad for nonce which generate small r parameter?

It is error in my recovery procedure, or signing should be bad for nonce which generate small $r$ parameter?

The issue happens because the recovery procedure is a simplified version of the standard method, attributed to Daniel R. L. Brown of Certicom.
Problem happens I guess when in signing, r does not match p.x.value; that is when p.x.value lies in $[n,p)$, where $n$ is the Elliptic Curve group order, and $p$ is the field order.
That has probability about $1-n/p$ to occur by chance. With non-toy parameters that's negligible, e.g. $\approx2^{-127.65}$ for sepk256k1.
If that needed to be avoided for small parameters, we could use the full method, or I guess fix the signature to fail (thus be retried with a different nonce) when the problematic condition arises. Just replace r==0 with p.x.value >= CurvePoint16::ORDER (and perhaps move that up one line).


Why SHA-256 (or any other) is too fast for passwords but "slow" for collisions to be found? Normally, the standard answers of why passwords shouldn't be stored using a groups of hash algorithms, including SHA-256 or higher, even if salted, are "because they are 'fast' hashes", "the attacker has access to specific hardware", and so on.

Why SHA-256 (or some other hashes) is too fast for passwords but "slow" for collisions to be found?  Other ways of asking the same question are: When SHA is "slow" enough for being useful? Why can't that special hardware that the attacker used to crack passwords can't be used to find SHA collisions too?

I suspect the answer is related to the fact that passwords are, in general, small.  If so, the question gets more accurate: What's the size of the message where it starts being worthy using SHA-256 (for example)?

I suspect the answer is related to the fact that passwords are, in general, small.

No, actually, the answer is related to the fact that passwords are, in general, predictable.  Meaning that out of the set of all possible inputs to the hash function, a relative few of them are vastly more likely to be somebody's password than others.  For example, Password1 is vastly more likely to be somebody's password than act chance past language (generated using the XKCD comic method), which is in turn vastly more likely than <Cj{Vm7&Jr5y9< (generated with this page).  And that last one in turn is significantly more likely to be somebody's password than any randomly-selected 14-byte sequence (which is unlikely to even be printable ASCII).

What makes passwords weak is that the fact that some candidate passwords are vastly more likely than others means that the attacker can effectively avail themselves of this strategy:

Prioritize guesses that are very likely to be passwords over guesses that are less likely to be so.
Do this guessing process at very high speed using specialized hardware.

You've probably heard the term "dictionary attack," which is a very simple and effective technique for #1.  Just make a list of likely passwords and try them all.  Or download one from the Internet; this one, which collects "every wordlist, dictionary, and password database leak that [the author] could find on the internet" has 1,493,677,782 entries, which is about $2^{30}$.

The equivalent of this in the collision resistance scenario would be if we had some procedure that was able, for the hash function that we are attacking, to prioritize pairs of inputs that were more likely to collide than others.  There's some knowledge about how to do that sort of thing for broken hash functions like MD5 or SHA-1, but not for SHA-256.  Given the state of our knowledge, there isn't any way we know of prioritizing the search so that we try pairs likelier to collide ahead of unlikelier ones.

Since we don't know of a clever way to prioritize the search, then, generic math (the Birthday Problem) tells us that it should take us about $2^{128}$ guesses to find a SHA-256 colliding pair.  That's a number vastly bigger than the $2^{30}$-entry password dictionary I cited above.  Since SHA-256 is much faster than dedicated password hashing functions, you can test guesses for colliding pairs much faster than you could test password guesses, but definitely nothing even close to $2^{98}$ times faster (about $3 \times 10^{29}$).


Shor's Algorithm Values I'm studing Shor's algorithm, and I have a question regarding the following step:
$$a^r -1 = (a^{r/2}+1)(a^{r/2}-1)=0 \pmod n$$
What would be the result if ${r/2}$ was -1? This will mean it's going to be like this: $(1/a+1)(1/a-1)$.
Will it also be $= 0 \pmod n$?

What would be the result if $r/2$ was -1?

I assume you meant "how does this work if $a^{r/2} \equiv -1$?
Yes, that does not give us a factorization; however there's an easy fix - use a different value of $a$.
I don't mean "go back to the Quantum Computer and rerun Shor's algorithm with a different base"; instead, select a different value $a'$ and check if $a'^{r} \equiv 1$.  It turns out (if the original value of $a$ was randomly selected) that a random selection of $a'$ has a good probability of making this work; once that works, you can then look at $a'{r/2} \pm 1$; those have a good probability of yielding a factorization.
The other possible complication is "what if the $r$ value that Shor's algorithm hands you happens to be odd?"; it turns out a similar approach works; select a random $a'$, and compute $a'^{2^{\lambda}r}$ for $\lambda$ small (0 until, say, $\log_2(n/r)$); if you find a $\lambda$ with $a'^{2^{\lambda}r} \not\equiv 1$ and $a'^{2^{\lambda+1}r} \equiv 1$, that has a good probability of yielding a factorization (and, yes, this looks a lot like how the Miller Rabin primality test works).
In addition, if you can't find a value $a'$ for which $a'^{2^{\lambda}r} \equiv 1$, you can also compute $\gcd(n, a'^{2^{\lambda}r}-1 \bmod n)$; that also yields a factor in some rare cases.
The bottom line is that, given an output of Shor's algorithm, we have good fast probabilistic methods for obtaining the factorization (which fail with low probability if $a$ was selected randomly [1]); the method isn't quite as simple as "plug in $r$ and $n$ into this simple deterministic algorithm, and out pops the factorization."

[1]: The failure case happens if the order of $a$ modulo $p-1$ happens to be significantly smaller than $p-1$ (and the same modulo $q-1$; that final test covers the case that only one of them is significantly smaller).


Why do stream ciphers use a nonce? My question maybe will be stupid, but my problem is that I do not understand why stream ciphers need a key and also a nonce. As far as I understand, the keystream is generated with the nonce. The same key can be reused with a different nonce.

Wouldn't be simpler just to use a new key each time? If I understand good, to decrypt the message the recipient needs the nonce. Is communicating the nonce simpler than communicating the key?

By the modern definition of a cipher, it must be possible to encipher several messages with the same secret key. That's also a practical necessity, due to the difficulty of securely establishing a shared secret key. That issue is solved with the nonce, which is not secret, and can be transferred as part of the ciphertext (typically: at the beginning).

Without nonce, or if the nonce repeats, the keystream would repeat, and that would allow breaking the cipher, e.g. with a single known plaintext.

Because the nonce is not secret, communicating the nonce is simpler than securely communicating the key. Altering the nonce would alter the deciphered message, but a generic stream cipher is not supposed to allow detection of alterations anyway.


How do I construct variable length input (VIL) in a block cipher mode? I've just been skimming NIST's "Five Confidentiality Modes". I understand those block cipher modes are used to securely encrypt input longer that the block cipher length. However, the common block cipher modes all assume my input length is evenly divisible by my block cipher length.

What is a recommended way to deal with my non-block-cipher-length-divisible input to safely encrypt it? Are implementors prepadding it using data length? Or are there other common block cipher mode standards that deal with this?

In the document Five Confidentiality Modes, in section 5.2 it says:

  For the ECB and CBC modes, the total number of bits in the plaintext
  must be a multiple of the  block size, $b$; in other words, for some
  positive integer $n$, the total number of bits in the plaintext  must be
  $nb$

...

  For the CFB mode, the total number of bits in the plaintext must be a
  multiple of a parameter,  denoted $s$, that does not exceed the block
  size; in other words, for some positive integer $n$, the  total number
  of bits in the message must be $ns$

...

  For the OFB and CTR modes, the plaintext need not be a multiple of the
  block size. Let $n$ and $u$  denote the unique pair of positive integers
  such that the total number of bits in the message is  $(n-1)b+u$, where
  $1≤ u≤ b$.

So we can see that for three of the five confidentiality modes, ECB, CBC and CFB respectively, some sort of plaintext padding scheme is called for. But for two of five modes, OFB and CTR respectively, no such padding scheme is needed. However you still operate on 128 bit blocks of data in these modes.

In OFB and CTR modes, if you have a single message that is shorter than the block size, you still encrypt 128 bit blocks of data, but you may not use all 128 bits since you are XORing your plaintext with the cipher output, so you only end up with the number of bits in your smaller message.

See Message lengths with AES CTR mode?


Why is a HMAC using a 32bit tag not prone to birthday attacks? Why is a HMAC using a 32bit tag not prone to birthday attacks?

I have read that it has something to do with the fact a birthday attack isn't really possible if the output size is not large enough. But then that asks the question of at what size does it become valid and a practical attack can be carried out?

If it isn't prone to birthday attack then what would be the probability of guessing a valid tag value for something as weak as a 32 bits in length?

Probability of a single hash collision$$\frac{1}{2^{32}}$$

However the birthday paradox mathematically suggests that this probability should be n^32/2...

Or am I missing something here?

Update: The goal of the attack is just guess what the tag might be.

"Birthday attacks" relate to the mathematical phenomenon colloquially known as the birthday problem, which states that if you generate random value in a space of size $N$, you expect to hit your first collision, i.e. generating a value that you already generated previously, after having produced about $\sqrt{N}$ values. This can lead to actual attacks in some contexts. It so happens that the normal usage context of HMAC is not one of these contexts.

HMAC is about checked integrity: it is a keyed function that is computed over a given message. In the most generic model, the attacker is allowed to submit $n$ messages $m_i$ of his own choice, and obtain the corresponding HMAC value $h_i$; and his goal is to achieve a forgery, i.e. a new message $m$ distinct from all submitted $m_i$, and the corresponding HMAC value $h$.

HMAC being what it is, it operates as a random oracle: from the point of view of the attacker, every time he submits a new message $m_i$, the obtained HMAC value $h_i$ is indistinguishable from a newly generated random value. Thus, when considering an as yet unsubmitted message $m$, the attacker's chances at predicting the HMAC value are essentially $1/2^r$, where $r$ is the length (in bits) of the HMAC output. In your case, $r = 32$, so anytime the attacker tries to predict the HMAC output for a message, then either he already submitted that exact message, and thus he can predict with probability $1$, or he did not submit that exact message previously, so his prediction will be true with probability $2^{-32}$ only.

The birthday problem, here, says that once the attacker has observed (or submitted) more than about $2^{16}$ messages, he can expect collisions, i.e. two distinct messages that map to the same HMAC value. But this does not change anything for the attacker, in that he still has no clue about what will be the next HMAC value for any given (new) message.

In fact, one can say that the birthday problem really incarnates how much collisions do not help the attacker. If you imagine a MAC system that takes care never to produce the same MAC value as previously (e.g. by remembering all produced MAC values in a database), then, message after message, the space of remaining possible MAC values get thinner. Ultimately, with such a system, once $2^{32}-1$ message+MAC have been obtained, the attacker could predict the next MAC value with probability $1$, since that would be the only MAC value not produced yet. But HMAC is not such a system, and will produce collisions just like it was a random source, thereby not incurring this "thinning space" effect.


DH prime size required to force an attack of $2^N$ steps Why the size of a DH prime $p$ should be about 6800 bits long to force an attacker to perform $2^{128}$ steps to attack the system?

How is this relationship 6800-128 established?

How do we pick a group size for a 128-bit security level?

Estimate the cost of mounting an attack as a function of the group size.
Find the group size that puts that cost estimate above $2^{128}$.

In this case, for appropriately selected groups, without back doors, like the RFC 3526 groups, the best attack algorithm is the general number field sieve, GNFS.  The usual (single-target) cost estimate for the GNFS is $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ where $L = e^{(\log p)^{1/3} (\log \log p)^{2/3}}$ and $p$ is the modulus.  Where 6800 came from is unclear to me; the usual consensus is that 3072 is plenty for a 128-bit security level, even if the $\sqrt[3]{64/9}$ figure is optimistic.  Of course, you can get much better performance, and much better implementation security, if you use X25519 instead.


Commiting to a linear relation over a finite field Suppose I have some finite field $k$. I am wondering if there exists a way to commit to a linear relation $a_1x_1 + a_2x_2 + \cdots + a_mx_m = b$ over $k$ , such that I can later reveal that a certain $m-$tuple $(c_1,\cdots ,c_m)$ satisfies $a_1c_1+\cdots a_mc_m = b$, but without revealing the coeficients $a_1 , \cdots , a_m$?

If it helps you can assume that the finite field is of prime order, but if you know a way to do this in an arbitrary finite field that would be even better.

If we can assume that $k$ is a large prime order (say, 256 bits or larger), one way is with Pederson commitments.

Assuming $g, h$ are two unrelated bases of order $k$ in $Z_p$ (for some large (2048 bit or more) prime $p = kn+1$), then the commitment are the values $g^{a_1}h^{r_1}, g^{a_2}h^{r_2}, ..., g^{a_m}h^{r_m}, g^{-b}h^{r'} = d_1, d_2, ..., d_m, d_b$, where $r_1, r_2, ..., r_m, r'$ are random values between 0 and $k-1$.

Then, to prove that a specific $c_1, c_2, ..., c_m$ satisfies the linear relation, you generate a zero knowledge proof that you know the value $x$ such that $h^x = d_b \cdot d_1^{c_1}d_2^{c_2} ... d_m^{c_m}$

This is equivalent to starting that $h^x = g^{a_1c_1 + a_2c_2 + ... + a_mc_m - b}h^{c_1r_1 + c_2r_2 + ... + c_mr_m + r'}$; if $a_1c_1 + a_2c_2 + ... + a_mc_m - b \equiv 0 \pmod k$, the prover can do this (assuming he remembers the values $r_1, r_2, ..., r_m, r'$ that he used); if $a_1c_1 + a_2c_2 + ... + a_mc_m - b \not\equiv 0 \pmod k$, then this reduces $h^x = g^yh^z$ for a nonzero $y$ and some $z$; as we assume no one knows the discrete log of $g$ to base $h$, the prover cannot know $x$.

I don't immediately see how to make this work in smaller groups (working in a larger subgroup that has $k$ as a proper factor doesn't work), but at least it's a solution that works in some cases...


Why aren't public-private keys sufficient to build a block chain? Why do we need proof of work/stake? Taking the simple case of Bitcoin here:
If all nodes can validate published transactions by checking the signature (created using the private key of the sender) of the transaction against the public key of the sender, why isn't that sufficient to validate a block?
I understand that we also solve the puzzle of finding a nonce that when combined with a block's contents, gives us a hash that has N number of leading zeroes. Why do we need this at all? Isn't it enough to check the validity of each transaction in the block?
As for double spending, if a miner decides erroneously to include both transactions, nodes can see there isn't enough balance and reject such blocks. As for which transaction of the two to take, the code could have a way to order transactions and if an attacker decides to do the opposite intentionally and decides to spam the network (since there's no proof of work cost) but how does the attacker benefit from that?

Since Blockchain is a decentralized system, it has to stop malicious behaviour [which may just be disruptive if not benefiting the attacker directly] and collusion.
Proof of work achieves that by introducing a very large computational cost.
It also removes the burden on the nodes of checking transaction ordering. Also the code is running in parallel in multiple nodes so how is theany transaction ordering going to be universal without local copies being different?


For calculating the index of coincidence for each sequence I was learning about the finding the key length reading the following web site...
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-vigenere-cipher/

and I really don't understand some part of the example shown in the web.
They assume the key length is 2 and extract the two sequence 1,3,5,7.... and 2,4,6,8...
and from these two sequences they calculate the I.C.

I wasn't sure how they calculate the I.C. for each sequence. Do they find the frequency count of each letter from a to z, and calculate the I.C using the following formula?

As explained on the link you posted, the Vigenere cipher with a key on length $n$ encrypts every $n$-th symbol with the same key under the Caesar  cipher. So to calculate the IC you should take all the $n$ sub-sequences separately: $\{1, 1+n, \dots, 1+kn, \dots\}$,  $\{2, 2+n, \dots, 2+kn, \dots\}$ and so on and compute the IC for every sub-sequence.


How to detect changes in data while preserving confidentiality (under constraints)? Suppose party $A$ has two pieces of data, $X$ and $Y$, either of which may change separately, or they may change together.

Given the following constraints:

$A$ knows its current $X$ and $Y$ but has no further knowledge about its previous or future values, nor can it store anything else
There is only one-way communication, from $A$ outward
$X$ can be publicly shared (yet doesn't need to be), but $Y$ needs to be strictly confidential
$Y$ comes from a limited set $S$ of possible values; therefore even from a hash $H(Y)$ it would, in theory, be possible for $Y$ to be determined (see 6.) $X$, in contrast, is infeasible to brute-force.
$A$ does not know $S$
$A$'s algorithm/method $M(X,Y)$ cannot be kept secret

Is there a way for party $B$, receiving messages from $A$, to track exactly which of the values changed?

Changes in just $X$ are trivial, because $X$ could be transmitted in the clear.

Changes in $Y$ are also easy if and only if it is known that $X$ has not changed. In that case $A$ would not send $X$ in the clear, but $H(X)$ and $H(Y||X)$. This way, $B$ knows that if $H(X)$ has not changed, but $H(Y||X)$ has, the change must have been because of $Y$. By not knowing the actual $X$ ($B$ doesn't need to), $B$ can't brute-force $Y$.

However, when $X$ did change, $H(Y||X)$ changes too, at least because of $X$. Yet, $B$ needs to know whether $Y$ also changed, without being able to brute-force it. If $H(Y)$ were sent as well, $B$ could then try different $Y$s and see if $H(Y)$ matches, because it knows the design of $A$.

The question therefore mostly concerns detecting changes in $Y$ when it is known that $X$ has changed. I fear this is theoretically impossible, but I'd like some extra eyes on the problem to either confirm that or (preferably) prove otherwise.

I'm going to try to make a handwavy argument that this problem doesn't have any great solution.  Criticisms are welcome!  A major assumption here is that my definitions are general enough to cover any possible solution to your problem.

Suppose there exists a scheme consisting of three deterministic algorithms $\operatorname{Broadcast}(X, Y)$, $\operatorname{CompareX}(B_1, B_2)$ and $\operatorname{CompareY}(B_1, B_2)$.  $\operatorname{Broadcast}$ is run by party $A$ and accepts $X$ and $Y$, outputting some "broadcast" value $B$.  $\operatorname{CompareX}$ and $\operatorname{CompareY}$ compare two broadcast values to determine if they were generated from the same $X$ or $Y$ values, respectively, and output $0$ when matching or $1$ when different.

Suppose a broadcast value $B_0$ is received by the attacker, who wishes to determine the secret value $Y$ from which it was generated.  The attacker can use the public algorithms $\operatorname{Broadcast}$ and $\operatorname{CompareY}$ to brute force the $Y$ value as follows:

Choose some arbitrary fixed value $x$ for use as an input to $\operatorname{Broadcast}$.
For each $y$ where $y$ is a guess for $Y$, call $\operatorname{CompareY}(\operatorname{Broadcast}(x, y), B_0)$.  Halt and output $y$ iff $\operatorname{CompareY}$ outputs $0$.

This suggests the option of making $\operatorname{Broadcast}$ or $\operatorname{CompareY}$ slow.  Consider the following scheme:

$\operatorname{Broadcast}(X,Y) = (X, \operatorname{PBKDF}(Y))$, where $\operatorname{PBKDF}$ is a password-based KDF such as scrypt, but using a fixed salt.
$\operatorname{CompareX}$ and $\operatorname{CompareY}$ are simply an equality check on the appropriate field.

If $S$ (the set of possible $Y$ values) is large and $\operatorname{PBKDF}$ is sufficiently slow, this might afford a modest level of security.


Consider the use of double encryption applied to the AES algorithm with two 128-bit keys Actual Question below.

Consider the use of double encryption applied to the AES algorithm with two 128-bit keys. How much storage and computation would be required to execute a meet-in-the-middle attack?

Double encryption applied to the AES-128 algorithm and two random keys is theoretically breakable from 3 plaintext/ciphertext pairs by the generic Meet-in-the-Middle attack with 2128 encryptions for building a dictionary, and an expected 2127 attempts each requiring a about one decryption and two encryptions (the later is for checking an average of one candidate key pair). This totals to an expected 5⋅2127 AES-128 operations. That's so large as to be currently impossible: the realm of feasibility nowadays stops somewhere a 275 to 2100, with the later acknowledged good to 2020 by many authorities. Thus we have a margin like a thousand millions, which I guess is fine for a good two decades, save for fairies or imminent breakthrough in quantum computers making them useful for such tasks.

The amount of memory required for the schoolbook MitM attack is 2128 words each 128-bit, that is 2135 bits. Nowadays, a silicon wafer is seldom less than 80µm 50µm thick (these are used in Smart Cards, and obtained by milling normal wafers rather than by using ultra-thin wafers), a DRAM cell occupies an area of at least 4F2 with feature size F=10nm, thus we are talking 0.9⋅1021m3 of silicon; that's 80% of the volume of earth, which contains only 15% silicon. Quick, make these wafers even thinner or (more realistically) start making 3D silicon that is not stacked wafers!

Computing that silly amount of RAM is pointless, because there is a well-known (but seldom taught) refinement of MitM that requires a feasible amount RAM, and only slightly more computation than the generic MitM. See Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999).

Interestingly, it is not known any generic technique that uses moderate amount of RAM and breaks two-key triple encryption of some b-bit block cipher with cost commensurate to 2b or even 23 b /2 encryptions.


EAX vs CTR vs XTS + cascade ciphers in disk encryption hell Often when I stumble across something interesting, I lose myself in the most overkill ways of implementing it. Today it was full disk encryption: I'm about to move to QubesOS, and I want to secure my data as much as possible, to a point where unauthorized viewing or even touching of the data becomes overly hard/nearly impossible. I don't care if it takes me minutes to decrypt my system on boot as long as it benefits my security.
As outlined in this answer I read (yes, I base my research mostly on StackExchange and wikipedia), there are three fundamental components of disk encryption I will have to decide on. These are the choices I've narrowed it down to:
Block cipher primitive: Serpent-256 (considered unbreached by Wikipedia), Twofish-256 (considered unbreached by Wikipedia, but is potentially more vulnerable to side-channel attacks) and AES-256 (considered theoretically breached by Wikipedia, but more mature). Seeing advantages in all three of these ciphers, I'm considering using them in a Cascading fashion like VeraCrypt offers. This would allow my system to stay secure even if one of these ciphers has been broken, right?
Mode of Operation: XTS seems pretty compelling (fixing issues from CBC->LRW and XEX), but is vulnerable to tampering (I'm using btrfs, so I'll at least be able to detect data manipulation) and traffic analysis. CTR also looks interesting, but yet again it is missing community support. To prevent tampering, I would have to use a diffuser. However, yet again, apart from Microsofts proprietary BitLocker diffuser (Elephant) there aren't any resources on this. Then there's EAX, assuring confidentiality and authenticity of the data. If so, EAX is arguably better than XTS, isn't it? Why is it so unpopular? Are there maturity issues?
Initialization vector: Anti-watermarking ESSIV for CBC-based modes, plain64 for XTS
As to be seen above, I'm especially insecure concerning the most secure Mode of Operation. Additionally, I'm not sure if there even is a disk encryption tool that provides f.e. cascade-serpent-twofish-aes-eax-plain64 (VeraCrypt supports the cascading part, but only allows for XTS). Also, most people use sha512 for hashing with a high iteration count. Is it possible to use a more sophisticated hashing algorithm like bcrypt instead?

This would allow my system to stay secure even if one of these ciphers has been broken, right?

Most likely, however one can construct situations where the cascade is only as strong as the first cipher.

  If so, EAX is arguably better than XTS, isn't it?

It is.

  Are there maturity issues?

No, it actually has a security proof for the strongest notion for a symmetric encrytion scheme, namely as an authenticated encryption scheme assuming the used block cipher is secure.

  Why is it so unpopular?

In general because AES-GCM / ChaCha-Poly1305 is faster with similar security properties. In this specific case of disk encryption because it incurs 16 bytes of overhead per authenticated message. These 16 bytes are really annoying in disk encryption. They mean that either the disk encryption software has to offer a smaller, non-standard sector size which may not be supported by the OS or it has to remove a linear amount of storage from your disk as well as completely break most performance assumptions by requiring two sector accesses by logical sector access.

Most people are not willing to sacrifice ~1% of their disk space and take the high performance stemming from the extra sector accesses for a defense against a rare attack scenario of manipulation attacks.

  Is it possible to use a more sophisticated hashing algorithm like bcrypt instead?

Theoretically? Absolutely. Practically? Your disk encryption software simply has to support it.