AES in OFB mode and IVs I'm trying to understand cryptosystems and their implementations to understand how to properly implement them. I have a function implementing AES-128 in OFB mode. Let's call it

encrypt(plainText, key, iv)

and assume everything else is properly implemented within the function.

Assume I'm going to encrypt 3 messages: 'a', 'b', and 'a' again, using the same key, k. The outputs are not realistic, I'm just trying to show that this function outputs the same character for the same message, with the same IV.

encrypt('a', k, 1) // outputs 'j'
encrypt('b', k, 2) // outputs 'f'
encrypt('a', k 1) // outputs 'j'

The question is: is my choice of IV for the 1st and 3rd invocation insecure? I've been told to make sure that the IV is unique, but how so? If the same message is supplied, should the IV be unique to that message, or globally unique?

I say it is insecure because I should never get the same ciphertext for the same message, but I do not know how to prove this. Furthermore, I do not know how to generate OR store a properly generated IV for each message.

If anything, I think the proper way to do this would be like so:

encryptWrapper(plainText, key):
    iv = // get some random bytes from /dev/urandom
    cipherText = encrypt(plainText, key, iv)
    //store the IV and the ciphertext in the same database table

So that my decrypt function would look like this:

decrypt(databaseIndex, key)
    //the databaseIndex is used to retrieve the ciphertext and its corresponding IV

Is it safe to store the IV with the ciphertext?

For each message position or role, such as a different time in a conversation or a different field in a database, you must use a distinct nonce, sometimes also called IV.

It doesn't matter what the content of the message is: in your database, you might store the same record content in two different places, in which case if you use the same nonce an adversary can tell that the two places contain the same content.  Worse, if you use the same nonce for two different places and two different message contents, an adversary can learn something about both messages or use information about one of them to learn information about another.

Your obligations in the AES-OFB security contract are simple:

You must pick the key $k$ uniformly at random and keep it secret.
For each distinct message position that you encrypt with the same key $k$, and each time if you can reuse message positions, you must use a distinct nonce.

Both the sender and recipient must share $k$ and, for each message position, the nonce in that position.  You can make the nonce for each message position public and transmit it alongside the ciphertext, or you can make it a function of where the message is, such as a message sequence number in a conversation or a record number in a database.  Note that if you ever reuse a message position, e.g. by overwriting a field in a database, then the nonce must also change from the first time you use it to the second time you use it; otherwise an adversary with two snapshots of the database can learn information about the old message and the new message from the two ciphertexts.

In exchange, AES-OFB guarantees that for up to a terabyte of data (240 bytes) under a single key, an adversary with read-only access to your database won't learn anything about the content of what you have encrypted, with the adversary's distinguishing advantage bounded by about $2^{-64}$.

Out of scope:

an adversary with write access to your database;
an adversary impersonating the database on the network;
concealing access patterns of your database;
concealing the lengths of the messages in your database;
etc.

If write access might ever be relevant—and it often can be in ways you didn't think of—then you must also use authenticated encryption: for example, AES-GCM, or NaCl crypto_secretbox_xsalsa20poly1305.  If you're not sure, err on the side of using authenticated encryption.

If access patterns and message lengths must be concealed, you have to think carefully about how to engineer your application.  Beware that compression makes the message lengths a function of the message content, which can cause lengths to reveal information about content!

In the special case where it is safe for an adversary to learn when two distinct message places hold the same message content, you can use a nonce-misuse-resistant authenticated encryption scheme such as AES-SIV or AES-GCM-SIV, which is usually constructed out of a nonce-based authenticated encryption like AES-GCM with the internal nonce chosen to be a pseudorandom function of the message and the caller-specified nonce, at the cost of some performance.

But although the concept has been formalized for some time, nonce-misuse-resistant authenticated encryption schemes are not widespread yet, and the CAESAR competition muddied the waters by not making NMR AEAD a distinct goal from AEAD, and the IETF barged ahead with adopting AES-GCM-SIV, and it's a bit of a mess.  Sorry!  In any case, it's safer if you can uniquely label all your message positions by a short string of bits (96 bits for AES-GCM, 192 bits for crypto_secretbox_xsalsa20poly1305) and never worry about it again.


How does the secret key in an HMAC prevent modification of the HMAC? Just as a preface: I'm not implementing a HMAC - I just want to understand it, as it is part of of my Computer Science course.

When using Hash-based message authentication codes, I understand that you need to protect the front and back of the MAC to prevent an adversary from modifying the HMAC while in transit.

HMAC (K,m) = H((K ⊕ opad) ∥ H((K ⊕ ipad) ∥ m))

As such, a HMAC is constructed by hashing the XOR of the secret key K with the outer padding opad concatentated with the hash of the secret key K XORed with the inner padding ipad concatenated with the message.

Can someone explain how these “secret keys XORed with padding” protect the HMAC from modification by an adversary (such as appending data to the end of the MAC)?

To attack a MAC in general, the attacker needs to find a valid MAC of a message that they do not have the MAC for (or find a message collision that allows a different message to have the same MAC digest). In this case, the attacker would be appending data to the original message, not the MAC itself, and trying to obtain a valid MAC for the new message. In specific, it sounds like you are thinking of length-extension attacks.

In HMAC, the inner hash by itself would be vulnerable to a length-extension attack and the attacker could successfully calculate a valid inner hash digest without access to the key. However, the outer hash isn't vulnerable to a length-extension attack since the client performing the HMAC authentication is only going to input the fixed length string key || inner_hash into it. The attacker only controls variable-length input to the inner hash, not the outer hash.

This is more-or-less addressed by this answer to another question. Relevant excerpt:

  the role of the inner function is to provide collision-resistance (to compress a long message down to a short fingerprint, in a way so that someone who does not know the key cannot find a pair of messages with the same fingerprint), and the role of the outer function is to act as a message authentication code on this fingerprint.


Secure password reset In my model I use two different keys, one for authentication and the other for the encryption / decryption of the data that the user saves, each derived from the master password with a KDF function.

How can I safely manage the password recovery for the user if I have no trace of the  master password on my database?

What do you think about https://mega.nz mode? In a nutshell:

When registering, it makes you download a file containing a key (I think your password or encryption / decryption key is encrypted with this random key and stored in their database).
In case of loss of the access password, it asks you to upload that file containing the key to reset the password.

Is it a good option? It can be done better?

You probably don't want to encrypt data with a key derived from a password directly with a KDF. This makes changing the password require rencrypting everything. You can instead encrypt data with a strong random key. And encrypt the key with a password derived key. This encrypted key is what you keep.
You can also encrypt this key with other keys. Including a random key the user downloads and keeps wherever, possibly on paper. Or you can possibly split a key into multiple shares to be kept separately.

Obviously if you have multiple ways to decrypt your key, it is only as secure as the weakest method.


Statistical Tests for Pseudorandom Functions Say I have an implementation of a potential Pseudo-Random function and I want to test whether my implementation does at least not contain any obvious flaws. As far as I understand, in other cryptographic settings, statistical tests are employed to ensure the correctness of the encryption algorithm.
What kind of statistical tests could I use for Pseudo-Random functions?

Nobody uses generic statistical tests to verify correctness of encryption algorithms.

To verify correctness of an implementation, engineers write proofs of correctness for their code, tr running it on known-answer tests, confirm round-trips on randomized inputs, etc.

None of this involves statistical tests, since the point is to implement a specific mathematical function, not to sample stochastically from a distribution—indeed, if you did use generic statistical tests you'd have to decide what to do in the case of false alarms, which would be an absurd way to approach verification of software implementing deterministic mathematical functions.
To assess security of a cryptosystem, cryptographers study specialized statistical tests.

Assuming, following the advice of Kerckhoffs, that the adversary knows the system, what's the best they can do to attack it with that knowledge?  Generic statistical tests like $\chi^2$ tests are stupid because they don't even know the system.  For example, here's a test for distinguishing a 256-bit AES-CTR stream under a uniform random key from a uniform random 256-bit string:

Guess a key $k$ uniformly at random.
Check whether the string $s = s_1 \mathbin\| s_2$ is of the form $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1)$.  If it is, guess AES-CTR; if it isn't, guess uniform random.

This test has distinguishing advantage $2^{-256}$ (or $2^{-128}$ if you use AES-128 instead of AES-256, which I don't recommend[1]), so the best distinguishing advantage for AES can't be worse than $2^{-256}$, but a lot of smart cryptanalysts haven't found a way to do any better than that.  Obviously, you could spend more computation—try it twice, with two different keys $k_1$ and $k_2$—to raise the advantage linearly, so this number should be qualified with a cost factor.

Any putative pseudorandom function family should come either with the paper droppings of a horde of cryptanalysts demonstrating failure to find a better-than-generic distinguisher, or with a proof of a theorem relating the security of the PRF to the security of some underlying primitive.  For example, the best PRF-advantage attainable against AES by any distinguisher making $q$ queries is bounded by the best PRP-advantage attainable against AES, which cryptanalysts have studied for decades now, plus $q(q - 1)/2^{129}$ because AES is always a permutation.

So, put your generic statistical tests in the garbage.  Find the literature on the putative PRF.  Write a proof of correctness of your code.


How does the birthday attack work in AUTH and UF-CMA games? In the AUTH and UF-CMA games, an adversary is required to forge a ciphertext or message/tag pair to win the game.  Given an encryption scheme $E$ and a PRF $F$, let $\hat{E} = C || F_k(C)$ and $C = E(x)$ (encrypt-then-MAC with PRF as MAC), how is the birthday attack mounted?  I understand it is sufficient to ask ~ $\sqrt{2^n}$ queries to find a collision in a MAC, but it's not clear how we can forge a new ciphertext/tag pair even if we have collision, because if we have found such a collision, we have already asked the oracle the two colliding messages.  I also see how certain block ciphers can be exploited by finding internal collisions, but how is the birthday attack mounted in the general case?

There is no generic attack that works against all PRFs (for exactly the reasons you mentioned -- if the PRF is secure beyond the birthday bound, there's no attack).

There is an attack on many of the specific PRF schemes that are used in practice, precisely because those specific ones are not secure beyond the birthday bound.  These attacks involve taking advantage of specific details of the design of that particular PRF (e.g., finding internal collisions).


How should one refer to the smallest remainders generated by a modulus within DH or DLP? It's my understanding that the integer base and exponents chosen to create the initial public keys in DH are from the remainders of a modulus.

For example, if the value of the modulus is $N=11$, a set of remainders "produced" is  {0,1,2,3,4,5,6,7,8,9,10}, however, I could also refer to the remainders of $N$ as 11,12,13,14,15,16,17,18,19,20,21.

Is there a way to differentiate by name the remainders {0,1,2,3,4,5,6,7,8,9,10}?

For example, is it accurate to refer to {0,1,2,3,4,5,6,7,8,9,10} as the canonical remainders of $\pmod N$? If yes, then can I refer to a particular base used as the canonical base and the exponent used the canonical exponent? Or is there a different terminology for these elements?

The space $\mathbb Z/n\mathbb Z$ is usually taken to consist of equivalence classes modulo $n$ called residue classes—equivalence classes of integers under the equivalence relation $a \sim b$ if and only if $n$ divides $a - b$.  For example, $\mathbb Z/3\mathbb Z$ consists of the three equivalence classes

\begin{align}
  3\mathbb Z &= \{\dots, -3, 0, 3, 6, \dots\}, \\
  1 + 3\mathbb Z &= \{\dots, -2, 1, 4, 7, \dots\}, \\
  2 + 3\mathbb Z &= \{\dots, -1, 2, 5, 8, \dots\}.
\end{align}

Residue classes are sometimes also called cosets in group theory.

Any set of distinct representatives of all the equivalence classes modulo $n$ is called a complete residue system modulo $n$.  For example, $\{0,1,2\}$ is a complete residue system modulo 3, as is $\{99,-26,-1\}$.

Usually if we want to choose particular representatives for computation, we choose the least nonnegative residues like $\{0,1,2\}$, where each number is taken to represent the equivalence class it is an element of.

There are also more exciting systems like Montgomery residues in radix $r$, where a coset $a + n\mathbb Z$ is represented by the integer $a \cdot r^{-1} \bmod n$, where $r^{-1}$ is an integer such that $r \cdot r^{-1} \equiv 1 \pmod n$.  For instance, in radix 8, modulo 5 we have the representatives

\begin{align}
  0 &\mapsto 0 + 5\mathbb Z, \\
  2 &\mapsto 1 + 5\mathbb Z, \\
  4 &\mapsto 2 + 5\mathbb Z, \\
  1 &\mapsto 3 + 5\mathbb Z, \\
  3 &\mapsto 4 + 5\mathbb Z.
\end{align}

This peculiar-looking function has the property that we can compute a representative of its image by $$\rho(x) = \bigr(x + n\cdot[(x \bmod r) \cdot n' \bmod r]\bigr)/r,$$ where the only divisor involved in the computation is $r$.  Here $n' n \equiv 1 \pmod r$, and the result is either the least nonnegative residue modulo $n$, or the next one greater, so you can get the least nonnegative residue with a single conditional subtraction.  The form $a \cdot r^{-1}$ is preserved by addition and subtraction, $(a \pm b) \cdot r^{-1} = a \cdot r^{-1} \pm b \cdot r^{-1}$, and while it is not preserved by multiplication, it can be restored by evaluating $\rho$: $$(a \cdot b) \cdot r^{-1} = \rho\bigl((a \cdot r^{-1}) \cdot (b \cdot r^{-1})\bigr).$$  This technique is called Montgomery multiplication.  When $r$ is a natural machine word size like $2^{32}$, this representation can be considerably faster without timing side channels than reduction modulo a general odd $n$.


Calculating differentially private average of a dataset I was looking into Google's DP library and its implementation of bounded DP-average. The library implemented DP-average following the algorithm presented in Li et al.[1].
Algorithm 2.3, calculates the DP-average from DP-Sum and True-Count. My question is if it is possible to improve it by adding noise to the true mean?
For instance, Let's assume there are N sets and each set can have 0 to 100 elements in it. Then the sensitivity of the DP-average should be (100/N). On the other hand, the sensitivity of sum-mechanism is 100. Instead of using the sum-mechanism, we can add Laplace noise with true average as follows.
DP-average = True average + laplace (100/N*epsilon)
Isn't this going to add less noise to the DP-average compared to Algorithm 2.3? This will further allow for smaller epsilon.
[1] Li, Ninghui, Min Lyu, Dong Su, and Weining Yang. "Differential privacy: From theory to practice." Synthesis Lectures on Information Security, Privacy, & Trust 8, no. 4 (2016): 1-138.

Welcome to Crypto.SE, and thank you for your interest in our open-source DP tooling! To implement BoundedMean, we actually use Algorithm 2.4 from Differential privacy: From Theory to Practice, not Algorithm 2.3.
The reason is because Algorithm 2.3 is not actually differentially private. To the best of my knowledge, the reference that exists for this fact is a footnote in my PhD thesis (at the bottom of this HTML page, or on page 211 of the PDF version). When implementing BoundedMean, we also tried some of the others algorithms proposed in this book, and Algorithm 2.4 was the one that seemed to work best empirically.
Now, to answer your question about adding noise directly: when building DP algorithms, you are only allowed to make decisions based on differentially private data. Even something as simple as "what is the scale of the noise we are adding" can actually leak more information than expected. In your question, $N$ is a private quantity, since it can go up or down by one if a user is added or removed to the dataset. This means that you can't use it as an argument to the noise without adding noise to it first, to make it differentially private as well (and count it towards the privacy budget).


Why is the following RSA PRNG cryptographically secure? One requirement states that the generator has to withstand the next-bit test.

Consider the following PRNG, where we calculate next output $x_i$ via the formula
$x_i = x_{i-1}^ e\mod n$.

I can see that this PRNG withstands the "state compromise extensions" (can't guess previous states).  However, given $x_i, e, n$ an adversary can easily compute all future numbers.

Why is this generator still considered cryptographically secure?

Perhaps you are thinking of the Micali-Schnorr PRNG, as described in Algorithm 5.37 of the Handbook of Applied Cryptography?
Algorithm 5.37 in HAC never states that $e$ is known to the adversary, or even that $n$ is known. Also, Algorithm 5.37 outputs only the least significant bits of the number, on each iteration. So I think you are confusing RSA as typically used and RSA as used in the Micali-Schnorr PRNG. What you describe does not match what is found in Algorithm 5.37.  Yes, for the generator you describe, given $x_i$, $e$ and $n$, the adversary could compute $x_{i+1}$, but in the Micali-Schnorr PRNG, it appears that we assume that $e$ (and even $n$) is unknown to the adversary.

Note 5.39 states that the security of this PRNG is based on stronger assumptions than just the intractability of the RSA problem. In general, this is not a good thing. In crypto we generally want as weak of assumptions as possible.


how does OpenSSH use bcrypt to set IV's? I generated an encrypted OpenSSH private key for test purposes:

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAACmFlczI1Ni1jYmMAAAAGYmNyeXB0AAAAGAAAABCX18gzzE
urqzviTpYwDuLjAAAAEAAAAAEAAAAzAAAAC3NzaC1lZDI1NTE5AAAAIL3fL8j3ilzDkr/O
7rBBCIYaH/pE1VvU3r2IEy7M2vBaAAAAoAHqj8gYr4dNtxmQyoC+md10ZwY+GOuWIYmOxl
vDYQkGZWYAU4zeiu+GnWhJr935cR1IrJUdsPWkjtdYRh4HksY5DjFngSHxEYr5/HyfJN52
tCN4zoxVe9bHyWVAs/XdnfHAMSUL7f+tXXhSIOitwggn1/bUDqX3bYMk8qtEYbDweE0lS4
Q5TcIJEn3A255WyCJ+WKXTglTaKpDNXCucV9E=
-----END OPENSSH PRIVATE KEY-----

(key type is ed25519; password is "key")

PROTOCOL.key describes the format of the key. In decoding it they're using bcrypt with 160 rounds.

Quoting PROTOCOL.key,

  The KDF is used to derive a key, IV (and other values required by the cipher) from the passphrase. These values are then used to encrypt the unencrypted list of private keys.

That's kinda vague. How do the IV / key get generated? Are they the same?

If I am reading the code right, it does indeed use the key as the IV, here are the relevant functions:

sshkey_parse_private2 from sshkey.c is the function that performs the KDF and decrypts the private key blob. The KDF takes the
The first decryption function called within sshkey_parse_private2 is cipher_init, as follows:

r = cipher_init(&ciphercontext, cipher, key, keylen, key + keylen, ivlen, 0)) != 0)

The format of that function from cipher.c:

cipher_init(struct sshcipher_ctx **ccp, const struct sshcipher *cipher, const u_char *key, u_int keylen, const u_char *iv, u_int ivlen, int do_encrypt)

That means the IV passed to cipher_init is simply key + keylen

Additionally, the round count for bcrypt is 16


Which is more secure using a CSPRNG for a One-time pad, or AES? In reading about the One-time pad it appears to need truly random key for the pad. Since true random values are not practical to generate this presents a problem (thus making One-time pad less practical). If instead I use the operating system provided CSPRNG to generate the key, is that any better than using AES in GCM mode?

Update: Just to be clear, a One-time pad cannot be done with a CSPRNG.

First of all, a terminology nit: please don't say "a One-time-pad generated by a CSPRNG"; a one-time pad must, by definition, be generated randomly, and an important part of its security proof is that it was generated randomly (and so an attacker cannot disqualify any potential pad, even if that attacker had infinite computational resources).  Exclusive-or'ing a CSPRNG output with the plaintext to form the ciphertext is a stream cipher; while it is a perfectly usable primitive, it isn't the primitive known as OTP.
In addition, if we use a stream cipher, we usually don't generate the entire key stream on one side, and send that to the other.  Instead, we usually send the key (initial CSPRNG state) from one side to the other; that drastically reduces the amount of keying material that needs to be sent, and is no less secure.
Now, with those nits done, the answer to your question (which is more secure, GCM or a secure stream cipher) depends on what you mean by "secure".
If by "secure", you mean privacy (that is, an eavesdropper cannot obtain any information of the encrypted message), well both GCM and secure stream ciphers are perfectly secure against real potential adversaries; on this score, they are even.
If by "secure", you mean integrity (that is, someone in the middle that can intercept messages, and inject modified versions cannot fool the receiver into accepting a message that the sender did not send), well, classic stream ciphers run into a problem.  That's because stream ciphers are malleable; specifically, an attacker can flip a bit in the ciphertext. On decryption, the corresponding plaintext bit will be flipped (and thus an attacker who guesses what the plaintext is can modify the ciphertext so that it decrypts to whatever he wants).  This doesn't work with GCM; if the attacker modifies the ciphertext in any way, the integrity check within GCM will fail, and so the receiver will reject the message.  Yes, this means that an active attacker can cause messages to be rejected; an active attacker can do that in any case.
Now, there are standard constructions (such as a MAC) on top of the standard stream cipher apparatus which also provides integrity protection.  So, if we ask CSPRNG+MAC vs GCM, well, there isn't a great deal of difference from a security standpoint (but there may be practical differences, such as "what happens if a message gets lost; do you need to handle that case?").


How is PBKDF2 so much better than normal Hashing or even using HMAC I do not know how the Key Length extension attack works. So if we leave that aside for once, and say just about usual brute-force attack on the hash, I don't really know how is PBKDF2 so much better than usual hashing.

Mathematically I know that PBKDF2 is so better against rainbow table attacks and also slow to recreate, but as computing power is moving up in the world, how it's still keeping its integrity?

For an HMAC we use a salt, also we can do the same for an usual hash.

So, SHA256('Hello'), is easily rainbow tabled. So if I prepend a salt, it's a little bit better, like SHA256(salt+msg), but Salts are usually kept in DB as clear text, so if some hacker is able to crack that salt, he can manually append the salt and perform the same operation.

Now in HMAC, -> H(key(opad) + h(salt + key(ipad))) is mathematically secure, but one can easily brute-force all possible password by running it through an HMAC operation (if he knows the salt), and he gets the key. A bit slower, but possible, and in pbkdf2, this whole process is looped maybe a million times even, with that much mathematical complexity, yet, if one gets the salt. He could simply run a big list of passwords with through another pbkdf2 function, and maybe very slow, but still possible, right?

So what's the use of this much complex algorithms by hashing and hashing with previous results of HMAC and so on, if it's still very much prone to a slower bruteforce?

The point is not to make the attack infeasible time-wise. Computational resources (usually, area*time, which is roughly a measure of the monetary cost) needed for the attack is the only thing you can hope to increase here.

As you observed, it is always possible to parallelize brute-force search of passwords, so the best you can do is increase the computational effort it takes to check a single password. Sure, even if checking one password required 10 seconds, the attacker could always put millions of ASICs in parallel and bruteforce everything in 10 seconds. To put it differently: the adversary can always get the password using little time, but this requires a lot of area (i.e., number of parallel computing units used simultaneously). Essentially, the adversary is forced to always invest a large quantity of area $\times$ time.

The point is that doing so will cost a lot of money to the adversary: it is usually considered that area $\times$ time is a decent (rough) approximation of monetary cost of the attack. So the hope is to make this attack less interesting money-wise.

A further note: the quantity area $\times$ time does in fact not perfectly measure monetary cost, as experiments with modern ASICs have shown. However, a lot of research has been devoted to find much better measures that map more closely to monetary cost (e.g. 1, 2). There are a bunch of satisfying candidates, and several constructions of hash functions which provably maximize this measure for the adversary. PBKDF2 does not seem to be the best one out there - but it is an old, well-established alternative which, experimentally, does not perform too bad with respect to the monetary cost it incurs to the adversary.


Can a 1 byte difference in AES 128 bit keys make huge difference in output? If we take some randomly generated key of AES-128 and we change any random 1 byte of that 16 byte key, will this make huge difference in the AES cipher text generated over same input string?

Does this 1 byte change makes output look like uniformly random? Does it have an effect on security?

If we take some randomly generated key of AES-128 and we change any random 1 byte of that 16 byte key, will this make huge difference in the AES cipher text generated over same input string?

Yes. The outputs with different keys differ greatly. If you pick two random keys the outputs must look completely uncorrelated, or an attacker could gain an advantage just by generating his own key.

With some changes the picture is a bit more complicated, because there are related-key attacks on AES. There the attacker would have to get access to encryptions with keys derived from the original, but if they did they would have an advantage since the outputs aren't totally independent.

However, that's not a very realistic attack in practice, and anyway AFAIK they only exist on AES-192 and AES-256, not (the full 10 rounds of) AES-128.

  Does this 1 byte change makes output look like uniformly random? Does it have an effect on security?

In the absence of better attacks, yes. It would be good for security if it was always true, but it's not a huge problem if it isn't, as long as random keys still produce unrelated-looking ciphertext.


Zero byte header in RSA-OAEP vs. RSA-PSS PKCS#1 v2.1/RFC3437 defines the OAEP padding mode for encryption and the PSS for signature padding. Both schemes are based on the generic constructions not specifically tailored to RSA by Rogaway & Bellare.

One of the alterations done for RSA-OAEP is, that the actual padding is only done to a length of $n-1$ (where is the octet length of the modulus) and a single zero byte is prepended to the whole string. This is done, since a message padded to $n$ bytes could be larger than the modulus, thus creating an ambiguity when decrypting.

My question is: The same argument could be raised for RSA-PSS, but here no zero byte is prepended to the padded hash. Why is that not necessary for signatures?

I think it actually is, lets read through chapter 8.1.1 Signature generation operation:

EMSA-PSS encoding: Apply the EMSA-PSS encoding operation (Section
9.1.1) to the message M to produce an encoded message EM of length
\ceil ((modBits - 1)/8) octets such that the bit length of the
integer OS2IP (EM) (see Section 4.2) is at most modBits - 1, where
modBits is the length in bits of the RSA modulus n:

    EM = EMSA-PSS-ENCODE (M, modBits - 1).

Note that the octet length of EM will be one less than k if
modBits - 1 is divisible by 8 and equal to k otherwise.  If the
encoding operation outputs "message too long," output "message too
long" and stop.  If the encoding operation outputs "encoding
error," output "encoding error" and stop.

Now the sentence "Note that the octet length of EM will be one less than k if modBits - 1 is divisible by 8 and equal to k otherwise." clearly indicates that this is similar to OAEP encryption.

Furthermore, if you look at the encoding operation in 9.1.1:

11. Set the leftmost 8emLen - emBits bits of the leftmost octet in
maskedDB to zero.

12. Let EM = maskedDB || H || 0xbc.

You'll see that the leftmost (most significant bits) are set to zero.


What does TLS 1.2 mean by SHA functions? I'm looking at the technical docs for TLS 1.2 and it says it uses SHA (so hashing algorithms):
7.4.1.4.1.  Signature Algorithms
But hashing just digests an input, to do things like user authentication.
TLS is supposed to provide "communications security." Is the info itself encrypted over with TLS? What encryption algorithm does it use?

You're looking at just one small part of the protocol. TLS, like any other communication protocol combines several cryptographic primitives to provide communications security. The algorithms used to secure the communication channel are described by a cipher suite, which combines a key exchange method (usually some form of Diffie-Hellman), an authentication method (usually a signature algorithm), a symmetric authenticated encryption method, and a hash algorithm which is used together with the authentication method. (This is the format of typical TLS 1.2 cipher suites. There are several variations which I won't go into here. TLS 1.3 uses the same building blocks but encodes the choice differently.)
The TLS protocol starts with a handshake where the client and the server set up a secure channel. For signature-based cipher suites, which is the most common case, the client and the server conduct a Diffie-Hellman key exchange, which lets them obtain a shared secret (the premaster secret). They then derive secret keys for authenticated encryption from this shared secret. An adversary observing the exchange cannot obtain the shared secret. However, an active man-in-the-middle can open a connection with the client and another one with the server. To prevent that, the server calculates a hash of the data exchanged during the handshake and signs it with its private key. The client calculates the hash of the data that it has exchanged and verifies the signature with the server's public key. If the two sides were talking to each other, they have seen the same data, so the signature is correct. If the two sides were each talking to a man-in-the-middle, they have seen different data, so the signature is incorrect and the client aborts the connection.
There are many different methods for authenticated encryption. In the old days (up to TLS 1.2), encryption was done with either a block cipher in CBC mode or the stream cipher RC4, and authentication of the data was done with HMAC. Since TLS 1.2, it is possible and preferred to use a proper AEAD construction such as a block cipher in GCM or CCM mode, or some other authenticated cipher (ChaCha20+Poly1305).
I've left out many parts and variants. For a more detailed overview of TLS, read How does SSL/TLS work?
.


How secure is passing a MAC to Python's random.seed before using random.choice to generate a MAC? I'd like to use Python's random.choice seeded with a HMAC-SHA1 tag to generate a MAC encoded in a variable set of chars.

import random, hmac, hashlib, string

SECRET = 'something secret'
MESSAGE = 'some message'
MAC_CHARS = string.ascii_letters + string.digits
MAC_LEN = 10

random.seed(hmac.new(SECRET, MESSAGE, hashlib.sha256).digest())
mac = ''.join([random.choice(MAC_CHARS) for _ in xrange(MAC_LEN)])
random.seed()  # resets seed from /dev/random

Are the properties of the mac variable at equivalent to that of an HMAC tag?

No. It looks like random.seed uses the hash of the argument, which is a 4-byte int.


Fiat-Shamir security problem question I am trying to understand the Fiat-Shamir identification protocol, but have a problem with understanding how this protocol is supposed to be save, even if you repeat it several times. I am using algorithm's description from http://www.cs.rit.edu/~jjk8346/paper.pdf.

If I do the maths, A can always convince B without knowing s. The problem here is step 4. A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B. Because now B will always accept this, since his condition is $y^2 = x*v^e \operatorname{mod} n \Longleftrightarrow (x*v^e)^{\frac{1}{2}*2} = x*v^e \operatorname{mod} n \Longleftrightarrow x*v^e = x*v^e \operatorname{mod} n$, which is always going to be true.

The problem is that on the right side of the equation $y^2 = x*v^e \operatorname{mod} n$ there are only values A knows, so for A it is no problem to put in something for $y$ so that the equation will always be correct.

A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B.

Yes, if that was easy, the protocol would be breakable. However, finding square roots modulo a composite number is as difficult as factoring that number.

See: Quadratic residue problem on composite integers


Creating an encryption key from several other keys and using hash functions I want to combine two or more keys to create a single encryption key that relies on all of them.  What is the proper method for doing that? Simple XOR? Using hash functions?  Something else?

I personally used this: k = md5( key1 || key2 ).  Note: || means concatenation.  I used md5 because I use 128-bit encryption and thus need a 128 bit output key.

Some other questions arise here for me:

Is using MD5 secure for this specific purpose?
I don't know of any other standard 128-bit output hash functions. It seems newer cryptographic hash functions all have 256-bit and more output lengths.
So is using another hash function that has a 256/512-bit output and then truncating the result down to 128 bits secure to an equal or more degree than using MD5?

Note that key1 and key2 are random keys, not passwords, and thus key stretching is not relevant or applicable.

If it is relevant, I generated both keys, and I know that both keys are cryptographically random.  Neither key was supplied by an untrusted party.  At present both keys happen to be the same length, but I'd prefer a more general solution that does not rely upon this assumption, if possible.

If the keys have constant, known length, I'd concatenate them, and then apply SHA256. If they have variable length, applying some separation mechanism might be useful.

Truncating hash functions works well. If the original hash function is good, a truncated hash function has the same properties, albeit at a correspondingly lower security level. Truncating SHA-256 is certainly better than using MD5.

I recommend something like:

Truncate(SHA-256(output-size || number-of-keys || sizeof(key1) || key1 || sizeof(key2) || key2 ...), output-size) where output-size <= 256


Debug client certificate authentication on path with openssl Website on https://example.com/login will request client certificate authentication.

If it was directly on https://example.com then using openssl s_client example.com:443 will show client certificate names.

How to get client certificate names on subpath with openssl commandline?
Checking with browser and Wireshark I see that there is GET query made in http-over-tls and then server asks Hello Request

I thought this would be a (probably cross) dupe, but the best I can find is https://unix.stackexchange.com/questions/29402/most-straightforward-way-of-getting-a-raw-unparsed-https-response or https://unix.stackexchange.com/questions/370932/openssl-command-s-client-always-says-400-bad-request . So:

What is an HTTP request? The original version of HTTP used a very simple request format: one line of text consisting of 'GET', a space, and what was originally called the document address (now generalized to resource identifier (URI) locator (URL) name (URN) or path), followed by a line terminator. Because of its severe limitations 0.9 was quickly replaced, and now is often not supported.

HTTP/1.0 in ~1995 expanded this to allow several methods (not just 'GET') and the first line (request line) also includes another space and the protocol version 'HTTP/1.0', and it is followed by zero or more headers each in the form 'name: value' and then (always) one empty line, followed for some requests by a body or 'entity' whose format depends on the headers (and possibly method). In 1.0 none of the headers are mandatory, only the request line and the empty line.

1.0 was quickly superseded by 1.1, which remained predominant, with some tweaks and evolution, until recently, and although formally superseded by 2.0 is still widely used and almost universally supported. 1.1 adds numerous options which can be ignored, but one mandatory request header, namely Host: to specify, you guessed it, the logical host, allowing multiple websites on one physical server, a practice that is now very common -- enough so that some servers still accept a specification of 1.0 and otherwise follow 1.0 rules but require the Host header to work correctly. (rfc1945 section 19.5 'major differences [from 1.0]' has only one subsection, about requiring the Host: header and allowing absoluteURIs.)

All of these standards specified the line terminator(s) to be the common Internet standard of CRLF (not just LF), but implementations vary on whether they enforce this; see more below.

The simplest way to send an HTTP request over TLS with openssl s_client is to use its default interactive mode and simply type the HTTP request on the terminal, and wait for the response. If the server chooses to do so, it can renegotiate at this point. An example on my test system, lightly redacted and with comments added:

$ openssl s_client -connect virt2.localdomain:443 -servername virt2.localdomain \
>   -CAfile trustvirt2 -cert certs/clix.pem -prexit
          <- some servers require SNI and some don't; openssl below 1.1.1 only sends SNI if you specify -servername
          <- even though the client cert won't be requested initially I must provide it on the commandline
          <- on Unixy systems may need to add -crlf; on Windows don't because it results in CRCRLF which is wrong
CONNECTED(00000003)
depth=0 CN = virt2.localdomain, L = here, C = XX
verify return:1
---
Certificate chain
 0 s:/CN=virt2.localdomain/L=here/C=XX
   i:/CN=virt2.localdomain/L=here/C=XX
---
Server certificate
-----BEGIN CERTIFICATE-----
[snip]
-----END CERTIFICATE-----
subject=/CN=virt2.localdomain/L=here/C=XX
issuer=/CN=virt2.localdomain/L=here/C=XX
---
No client certificate CA names sent
          <- server doesn't do client auth on initial handshake
Server Temp Key: ECDH, prime256v1, 256 bits
---
SSL handshake has read 1550 bytes and written 399 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-RSA-AES256-GCM-SHA384
Server public key is 2048 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-RSA-AES256-GCM-SHA384
    [snip]
    Verify return code: 0 (ok)
---
GET /secur/good.txt HTTP/1.0
Host: virt2.localdomain

          <- I typed those two lines and the empty line
depth=0 CN = virt2.localdomain, L = here, C = XX
verify return:1
          <- this output from verify callback shows there was a renegotiation
          <- but it is NOT dumped in detail like the initial handshake
read R BLOCK
HTTP/1.1 200 OK
Date: Tue, 05 May 2020 16:27:40 GMT
Server: Apache/2.2.15 (CentOS)
Last-Modified: Mon, 04 May 2020 07:21:53 GMT
ETag: "8066f-7-5a4cd62a20c85"
Accept-Ranges: bytes
Content-Length: 7
Connection: close
Content-Type: text/plain; charset=UTF-8

secret
          <- that was the response header and body sent by the server
closed
          <- that was output by s_client because my server closed the connection
          <- some 1.1 servers might not close immediately here, but will usually timeout fairly soon
          <- now s_client -prexit prints the _final_ session data, including the renegotiation:
---
Certificate chain
 0 s:/CN=virt2.localdomain/L=here/C=XX
   i:/CN=virt2.localdomain/L=here/C=XX
---
Server certificate
-----BEGIN CERTIFICATE-----
[snip]
-----END CERTIFICATE-----
subject=/CN=virt2.localdomain/L=here/C=XX
issuer=/CN=virt2.localdomain/L=here/C=XX
---
Acceptable client certificate CA names
/CN=demoCA2.mytestdomain
/CN=demoCA2b.mytestdomain
          <- including the CAnames you want
Server Temp Key: ECDH, prime256v1, 256 bits
---
SSL handshake has read 4252 bytes and written 1909 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-RSA-AES256-GCM-SHA384
Server public key is 2048 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-RSA-AES256-GCM-SHA384
    [snip]
    Verify return code: 0 (ok)
---
$

There are 2-3 disadvantages to this method:

you must type the request exactly correct, with no mistakes. s_client sends each line as you enter it, and once sent it cannot be corrected.
depending on the server, you may have to type quickly. Due to widespread denial-of-service attacks, many webservers today only allow a limited time, often 30 seconds or less, to receive the request. This makes the previous bullet even harder.
on Unixy systems, terminal input lines end with only LF, not CRLF. If the server is strict, either you must manually enter the CR, typically as control+V control+M although this can vary depending on your tty driver settings, or (much easier!) add -crlf to s_client and it adds CR for you.

The less simple way is to supply the request data automatically: from another command (piped), or a file or heredoc. This avoids the problems of making a manual typing mistake, or being too slow. On Unixy systems where scripts and most commands are LF-only, and files may be, you again have the issue of either adding CR explicitly or using -crlf. But now after sending the request, you must make s_client keep the connection open long enough to process the renegotiation -- and maybe, but not necessarily, the server HTTP-level response; this can be done by waiting for terminal input (which you don't immediately provide), by an explicit sleep (at least on Unixy systems), or by adding -ign_eof to s_client. Combining these options, some possibilities:

(printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' ''; cat) | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; cat) | sed 's/$/\r/' | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; cat) | openssl s_client ... -crlf

(printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' ''; sleep 5) | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; sleep 5) | sed 's/$/\r/' | openssl s_client ...

(echo GET /resource HTTP/1.1; echo Host: myhost; echo; sleep 5) | openssl s_client ... -crlf

printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' '' | openssl s_client ... -ign_eof

(echo GET /resource HTTP/1.1; echo Host: myhost; echo) | openssl s_client ... -crlf -ign_eof

openssl s_client ... -crlf <<END -ign_eof
GET /resource HTTP/1.1
Host: myhost

END

printf '%s\r\n' 'GET /resource HTTP/1.1' 'Host: myhost' '' >>filewithcr

(echo GET /resource HTTP/1.1; echo Host: myhost; echo) >>filenotcr

cat filewithcr - | openssl s_client ...

(cat filewithcr; sleep 5) | openssl s_client ...

(sed 's/$/\r/' filenotcr; sleep 5) | openssl s_client ...

<filewithcr openssl s_client ... -ign_eof

<filenotcr openssl s_client ... -crlf -ign_eof


Programming language for modular arithmetic over large numbers I'am trying to implement algorithms on integer factorization.This involves dealing with integers of 200-500 digits and doing modular arithmetic over them.Which programming language has inbuilt support for large numbers?Does C++ support large number arithmetic?

Yours is a perfectly legitimate question.

I know that C#, F#, Java and Scala have an in-built support to handle arbitrarily large numbers, i.e. as large as your computer’s memory.


SSH rekey security implications When an SSH session is rekeyed due to either the time limit or data limit for rekeying having passed, does the Diffie-Hellman exchange take place within the encrypted channel provided by the existing session, or does it take place "in the open" the way it does when the client first connects to the SSH server?

Looking at the RFC for SSH and having read the output from ssh with the -vvv option during a rekey, I still can't figure out the answer.

For the sake of this question, I'm mainly thinking about openssh in version above 6, if that matters.

I think you overlooked some words in section 9:

  Key re-exchange is performed using whatever encryption was in effect
     when the exchange was started.  Encryption, compression, and MAC
     methods are not changed before a new SSH_MSG_NEWKEYS is sent after
     the key exchange (as in the initial key exchange).

Note that it is better to keep to the naming of the methods within the protocol, i.e. use key re-exchange instead of re-keying. That makes searching and conversation much easier...


Weakness in a CBC-like XOR cipher A simple symmetric encryption algorithm can be written as follows:

Input message M and 64 bit key $K$
Divide M into 64 bit size blocks $B_1...B_n$
Get first block $B_1$ and perform bit-wise $\oplus$ with K
to produce encrypted block $E_1$
Repeat
 Get next block $B_i$ and perform bit-wise $\oplus$  with
 $E_{i-1}$ to produce encrypted block $E_i$
Until End of message

Q) What is the weakness in the above Algorithm if $K = B_1$(first 64 bits in message)

This may seem like an assignment question because it is. I think I know what is happening here. From the algorithm,

$E_1= Key \oplus B_1$ and $E_i=E_{i-1} \oplus B_i$ for all $i>1$

If encrypted text is known, it is possible to get plaintext using $B_i =  E_{i-1}  \oplus E_i$. With the help of this formula, we can derive the entire plain text without having any knowledge of the key.

The algorithm is weak even if $K \neq B_1$ because even then we are able to get the plaintext from ciphertext without any knowledge of the key. However, can we use the fact that Key is equal B1 in this scenario and get any meaningful outcome?

I know that if $K = B_1$, $E_1$ will become 0, then $E_2=B_2$. I am stuck here. So can I draw any other conclusion from it?or is my approach completely wrong?

Fundamental ideas:

$ a \oplus a = 0$

$ a\oplus 0 =  a$

also if $K = B_{1}$ , $E_{1} = 0$ and as per your scheme $ B_{2} \oplus E_{1} = E_{2} = B_{2} $

As a result of you setting $K = B_{1}$  you cannot decrypt the first block if you do not know $B_{1}$.
This system is fundamentally broken, it can never be used in practice. This assignment question sadly does not give the correct idea of CBC . Practical CBC mode of Block Ciphers like AES work in a very different way.
For example if we have an Encryption function $E_{k}$ then this is how CBC encryption works.

$C_{0} =E_{k}(IV\oplus M_{0})$

$C_{1} =E_{k}(C_{0}\oplus M_{1})$
and so on...
As you can see there is an application of a very strong encryption function $E_{k}$ which could be something like AES. Here you are doing a simple XOR.
Prima facie, your your scheme is subject to known - plaintext attacks and a 64 bit key is always brute force search able. I might have missed some crucial points but this is what I can think of now !!!


RSA encryption exponent In RSA public-key material (e, N), why must the encryption exponent e be relatively prime to $\phi(N)$? Why must any public key encryption algorithm resist CPA?

why must the encryption exponent e be relatively prime to $\phi(N)$

If it's not, then the decryption will not be unique.  That is, there will be multiple messages $M_1 \ne M_2$ such that $M_1^e \bmod N = M_2^e \bmod N$; hence if the decryptor receives that common value, he will not be able to determine if the original message was $M_1$ or $M_2$

  Why must any public key encryption algorithm resist CPA

When we're analyzing the security of a public key algorithm, we assume that an attacker has the public key (after all, we assume that we can give it out freely, so it is not unreasonable that the attacker can get a copy).  With that public key, the attacker can pick list of message he wants, and encrypt those messages.  Hence, a public key encryption algorithm must resist CPA because, practically speaking, an attacker can actually perform that attack.


Tell me like I'm 5: How are algorithms secure if people can see them I have a limited understanding of encryption of data. I know that servers and clients can encrypt and decrypt information through a variety of methods. I also know that security through obscurity is not a good idea and that there are very reliable open-source encryption options.

That said, I've been told (or read somewhere) that the type of encryption used is non-reversible. i.e. you can't decrypt something by knowing the algorithm. This is the bit that I can't grasp. How can an algorithm not be reverse engineerable? Why are open source encryption options considered more secure than proprietary equivalents?

Thanks

A modern cipher algorithm concentrates the required secrecy into the key instead of the algorithm. This is helpful because a key is relatively short, compared to even the most compact binary representation of a simple cipher. This means there is actually less to protect then the algorithm itself. Only the person(s) who know the key can encrypt or decrypt messages.

Physical Locks work the same way. A lock can only be opened or closed with the key. Knowing that there is a lock on the door does not help in getting past it, even if you know what type of lock it is.

People learned a while ago that obscurity and quantifiable security are not the same thing. This is usually referred to as Kerckhoffs's principle.

As for your question about open source/proprietary algorithms:

Firstly, the open source equivalents aren't just open source, they are industry/government standards, like the Advanced Encryption Standard and Secure Hash Algorithm families
A proprietary algorithm may not have seen review by any or more importantly enough other cryptographers, for long enough.
There exists snake oil cryptography, which advertises itself as being supremely secure, but is sometimes outright silly to those who understand well enough.


Cipher text only attacks on deterministic fully homomorphic encryption schemes If we have encryptions of additive and multiplicative identities in the corpus of cipher text of a deterministic fully homomorphic encryption (FHE) scheme, I guess we can break it.

If the FHE scheme is deterministic and works over integers and if the corpus of cipher text has $enc(1),enc(0)$ where $1$ being multiplicative identity and $0$ is additive identity for integers, I am thinking it is easy to break such scheme.

First we can verify if there any below inferences in the cipher text

if $eval(enc(x) + enc(y)) = enc(x)$ this means $enc(y)$ is encryption of $0$.

if $eval(enc(x) * enc(z)) = enc(z)$ this means $enc(z)$ is encryption of $1$.

if $eval(enc(x) + enc(a)) = enc(0)$ this means $a$ is additive inverse i.e $-x$.

if $eval(enc(x) * enc(b)) = enc(1)$ this means $b$ is multiplicative inverse i.e $1/x$.

if $eval(enc(x) + enc(c)) = enc(1)$ this means $x+c = 1$

Now it is easy to identify all the numbers without decrypting them.

if $eval(enc(w)+ n\times (enc(1)) = enc(0)$ this means $w= -n$.

Is this understanding correct ?

Yes, your understanding is correct.

It is well-known that homomorphic encryption schemes are vulnerable to cipher text attacks if they are deterministic. See, for example, the section 2.4 of the paper A Survey of Homomorphic Encryption for Nonspecialists

Consider that the attacker has a value $c_1$ that is known by him to be a encryption of some clear text $m$.

So, if this scheme accepts at most $L$ additions in sequence, the attacker can find the encryption of $L$ multipes of $m$ by adding $c$ to itself:

$c_2 = c_1 + c_1 \Rightarrow dec(c_2) = 2m$

$c_3 = c_1 + c_1 + c_1 \Rightarrow dec(c_3) = 3m$

...

$c_L = c_1 + c_1 + c_1 + ... + c_1 \Rightarrow dec(c_L) = L \cdot m$

Note that the attacker can combine the "intermediate" ciphertexts too (I mean, add the ciphertexts $c_2, c_3, c_4, .., c_{L-1}$ to themselves).

With just this, the attacker can learn a lot of pairs of cleartexts and correspondent ciphertexts. Then, since the scheme is deterministic, he will able to identify a lot of the ciphertext that are being sent.


How do I calculate the maximum plain text length allowable for a certain cipher text length? I am encrypting and storing sensitive values in the database. I have a set max length in the database, but in order to provide useful user feedback, I'd like to know the max input I should allow for a given database length.

I can throw together a test that brute forces an answer, but I'd like to understand more generally how to go about calculating.

In my specific case, I'm using Twofish in CBC mode with PKCS7 padding. The result is stored as base64 encoded string. The database column is a VARCHAR(512) column.

I know base64 has an overhead of about 137% of input so, roughly, 512/1.37 = ~373.
But now where? is 373, which happens to be 23 blocks, the maximum size, or is there more to it?

Thank you very much for you patience. :)

Well, to figure out this sort of thing, it's easier if we work backwards.

So, we start at the back (the fact that we can store up to 512 characters in a database field), and consider how much binary data we can store.  Well, base-4 takes 3 bytes of binary data, and encodes it in 4 bytes of base-64.  Thus, we can store 3*(512/4) = 384 bytes of binary encrypted data in 512 bytes of base 64.

Now, once we can store up to 384 bytes of encrypted data, we need to consider how much plaintext that corresponds to.  Well, you don't specifically mention an IV; in this situation, we might guess that the encryptor selects a random 16 byte IV and sets the first 16 bytes of the ciphertext to that.  The second thing to consider is whether the encryptor adds a message authentication code; that is a cryptographical check value that will allow you to detect if someone else modified the database field.  Now, you don't mention that you have one, so we'll assume that you do not.  This gives us a ciphertext region of 384-16 = 368 bytes.

Lastly, you mention that you use CBC mode with PKCS7 padding.  CBC mode always generates a ciphertext that's a multiple of 16; 368 is already a multiple of 16, so we don't loose any room there.  In addition, the length of the ciphertext is exactly the length of the padded plaintext; you mention PKCS7 padding, which always adds at least 1 character of padding; this gives us a final value of 367 bytes of plaintext which can fit.


Problem with AES-128 AddRoundkey Step I'm trying to self-learn the AES-128 algorithm and ran into a snag while following these slides I found online: https://kavaliro.com/wp-content/uploads/2014/03/AES.pdf

For the sixth round in the example given, during the AddRoundkey step, the third word of the matrix after MixColumns (F0) is XOR-ed with the third word of the 6th RoundKey (B7). This apparently results in (77) which doesn't correlate with my calculation of 47. However, the process seems to proceed with this error and still gets the right ciphertext in the end (I put the ciphertext through an online decoder and got the original plaintext back).

I'm very confused as to what I am missing here?

You are not missing anything, the calculation is wrong. The calculation of the key schedule that is.

If you postulate the round calculations are correct, the round keys must be wrong, and in fact that byte of the round key is indeed wrong. Reversing the AddRoundKey calculation from the round example, the valid round key byte resulting in 0x77 is 0x87, not 0xB7.

Therefore the slide was just wrong, the values may have been entered by hand, and 8 looks like a B, so that is very likely.


Why does my SSH private key still work after changing some bytes in the file? I (for a test) just randomly altered a private RSA key by opening it up in Vim and changing a few bytes. It is the private part of an SSH key pair used for logging in on a remote system. Puzzlingly, it still allows me to login.

I did some research and found that it is a base64 encoded ASN.1 container, so I pulled all the relevant integers out with OpenSSL and it seems only $d$, the private exponent, has changed (and only slightly at that). Is it possible the additional cached values are therefore being used to decrypt the value sent from the server, in order to still allow me to be logging in? The public key can (as expected) still be derived due to the other integers in the ASN.1 still being the same.

As I'm an encryption dufus I'd appreciate some guidance on how the above is possible. I've found when I modify the key in Vim by larger amounts it rejects me as expected. Thanks.

An ASN.1-encoded SSH private key contains the following integers in order:

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$.

The observation that the value of $d$ in such a key may be irrelevant is due to the following: To speed up exponentiation modulo $n$ by a factor of about $4$, the Chinese Remainder Theorem can be utilized to compute the result modulo $p$ and $q$ separately and subsequently combine them to obtain the "real" result modulo $n$. With this optimization, the values of $n$, $e$ and $d$ are not required, hence are ignored by typical implementations whenever $p$, $q$, $d_p$, $d_q$ and $q_{\text{inv}}$ are available*. This is why changing some characters in the middle of the key need not necessarily destroy it, depending on which of the components you change.

*) at least for OpenSSH, they do not have to be present: setting $p=q=1$ and $d_p=d_q=q_{\text{inv}}=0$ makes the implementation use $n$ and $d$.

To visualize the arrangement of the individual components, I created the following graphic from a typical 4096-bit RSA private key file:

The grey part right in the beginning is ASN.1 header data (encoding the fact that a sequence is about to follow, etc), followed by the integers forming the key as described above. The ASN.1 header data associated to each component (mostly a length field) is colored slightly brighter than the data representing the integer itself. Note that the pictured subdivision is not 100% accurate as one Base64 character encodes roughly $3/4$ raw bytes, hence some boundaries should actually run strictly within a single character.


Is perfect-forward secrecy achieved with RSA? I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl.

From what I understand Symmetric key distribution systems like Kerberos do not provide PFS because an attacker will be able to decrypt every session key ever encrypted with a compromised KEK.

In the book, on page 342, they say that Asymmetric ciphers like Diffie-Hellman or RSA, when used for key distribution, will provide FPS. I understand that Diffie-Hellman will provide PFS because each session key will have nothing to do with any other session key. However I've been stumped for a few days now trying to figure out how RSA will provide PFS. Am I missing something or just misunderstanding what they wrote?

This expands CodesInChaos's comment into an answer.

Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and encryption, that's inefficient, thus unusual.

As an example: Bob has a long-term RSA key pair $(Mpub_B,Mpriv_B)$ used for signature, with $Mpub_B$ trusted by Alice (perhaps by way of some certificate). In order for Alice to send a confidential message to Bob:

Alice

draws a 256-bit random $R$
sends $R$ to Bob

Bob

generates a new RSA key pair $(Tpub_B,Tpriv_B)$ used for encryption,
RSA-signs the (hash of the) message $R\|Tpub_B$ using $Mpriv_B$ giving signature $S$
sends $Tpub_B\|S$ to Alice

Alice

gets $Tpub_B$ and $S$
verifies that $S$ is a valid signature with respect to $Mpriv_B$ for $R\|Tpub_B$, where $R$ is from the recent first step
generates a random symmetric session key $K$
RSA-enciphers $K$ using $Tpub_B$ yielding $X$
enciphers the plaintext message $M$ using key $K$ by a symmetric algorithm (say, AES-CTR will implicit zero IV) yielding ciphertext $C$
forgets $K$
sends $X\|C$ to Bob

Bob

gets $X$ and $C$
RSA-deciphers $X$ using $Tpriv_B$ yielding $K$
forgets $Tpriv_B$
deciphers ciphertext $C$ with key $K$ yielding plaintext message $M$
forgets $K$.

$K$ allows $M$ to be large, when RSA encryption only directly allows short messages. $R$ protects against replay of an earlier $Tpub_B$.

The scheme is inefficient because the generation of a new RSA key pair is relatively expensive (and normally rare, thus not optimized for speed). That's a good reason why (EC)DH is most used in practice.

It is possible to send several messages using the same $K$, or/and reuse $(Tpub_B,Tpriv_B)$ across multiple sessions, improving performance. But Forward Secrecy triggers only when $K$ and $Tpriv_B$ are forgotten, and $R$ is no longer accepted.

Note: the scheme provides confidentiality, but not integrity or proof of origin; that can be added.


Will the ECDSA with SHA-3 implementation be quantum-proof? I know, that ECDSA could be broken by quantum computers, but since there is post-quantum hash function SHA-3, does not this make the digital signature resistant to them?

No.  Anyone who can compute elliptic-curve discrete logs, such as an adversary with a quantum computer powerful enough to run Shor's algorithm, can immediately recover an ECDSA private key and forge arbitrary signatures of their choice.  It doesn't matter if you use SHA-3 or floss each day.


What is the most computationally efficient way of generating pseudo-random permutations? I have an application in which I need to create up to J randomly shuffled-copies of an array of length N. Then I will have millions or even billions of iterations such that, in each iteration, I will have to fetch the value of K << N entries of the J permuted copies of the original array. The K entries that need to be accessed are the same for all the J shuffled-copies but that set of K entries changes from one iteration to another.

To give an approximate idea of the dimensions of the problem, assume J = 25000, N = 500000 and K = 50 even if those numbers are not fixed a priori.

The naive approach, which I've been following so far, is to use the Fisher-Yates algorithm (also known as Knuth shuffle) to create the permuted versions of the array, storing them as a NxJ matrix in memory. However, that matrix tends to be too large in many cases, which is problematic. Also, recomputing the entire matrix in each iteration would be painfully slow.

As an alternative, I have started to consider using pseudo-random permutations instead. Using a block-cipher for which the enciphering process had complexity O(1), I could ideally fetch the K entries I need with an extra complexity O(KJ) per iteration. Which appears to be acceptable empirically.

My question, as someone with an extremely rudimentary understanding of cryptography, is which scheme would you recommend me to perform such a task. The key point is that I would rather have a scheme for which enciphering is really fast, even if the security is very poor for cryptographic standards. As long as the set of distinct permutations which can be generated (and look random enough) is in the order of 2^32, it's perfectly fine. AES-like security levels would be a clear overkill.

As a reference, I am currently using a "handmade" 4-round Feistel network with ceil(log2(N)) bits and very simple round functions (16-bit round keys, 8-bits are XORed with one half of the plaintext and the result is passed through a S-box, the other 8-bits are used as an index for a set of 256 random bit shifts). I am also using a cycle-walking scheme to deal with the (common) cases for which N is not a power of 2.

I guess the scheme is a bad joke for cryptographic standards but, for my application (statistical hypothesis testing) it appears to be random enough. It would be great if I could reduce the complexity of the encryption scheme a bit.

I would be really thankful is any of you could provide some advice!

TL;DR I am looking for the fastest possible way to generate pseudorandom permutations of a set of size N. I care much more about the speed than the security of the scheme (about 2^32 "truly" random permutations is more enough).

Use format-preserving encryption. The current NIST standards-track mode FFX should be sufficiently fast for your purposes. For your domain size, you might also want to try the swap-or-not shuffle, a new construction that is also pretty fast and dead simple to implement. To get the absolute best speed form these schemes you should use a single AES call as your PRF, preferably with AES-NI instructions if you have them.
EDIT: Any PRP generator based on an oblivious card shuffle should work for your purposes. Here's another reference explaining what that is.


CBC key lifetime, or, "how big is too big?" IPSec recommends rekeying SA's figuring in both time and amount of data sent. Even when using AES-256 in CBC mode, the key and IV commonly get re-negotiated after 100MB.

My case isn't using IPSec, the above is just for comparison.

Assuming a plaintext is encrypted and stored to disk using AES-256 in CBC mode, is there a maximum 'safe' size? Fear not, each plaintext gets its own randomly generated IV. I'm just having a hard time finding what the upper bound is for practicing safe encryption.

as the previous comment said, due to the birthday paradox/problem, after 2^64 blocks (for block ciphers with 128 bits block size) collisions start to get very likely, the authors of cryptography engineering suggest for CBC "2^32 blocks or so", according to them that leaves a residual risk of 2^-64 that there will be leakage of a full block (when a collision happens in cbc, you leak 128 bits of information about the plaintext)

this is for CBC, of course, other modes of operation have other characteristics.


Does concatinating mutliple digests of hashes from CSRN result in a CSRN? Kind of a noob question. Suppose;

We generate 1,000 cryptographic-ally secure random numbers & store each of them in an array1.
For each number in this array1, we take the hash sha256(CSRN) then store the digests in array2

For simplicity, lest say array2 has 3 digests,

array2 = [a22110a41f165b6b0f3cc053b50214b284add1b0f8628f78c7522906c8f78da0, d160c64b851dfa1606283ce84799c83c237e0cebfc8e210eb2eaf5ba24f845cb,
35bf775fe6ff7c97520d76665059e21023d9f8de094a3b6c351143241cc7649b]

My question is, if I concatenate the items in array to to form a longer hex such as;

longhex = a22110a41f165b6b0f3cc053b50214b284add1b0f8628f78c7522906c8f78da0d160c64b851dfa1606283ce84799c83c237e0cebfc8e210eb2eaf5ba24f845cb
35bf775fe6ff7c97520d76665059e21023d9f8de094a3b6c351143241cc7649b

Is longhex also considered a CSRN?

Yes it most certainly is, on the assumption that the hashing algorithm used is cryptographically secure and uniform in its output.

As a thought experiment, consider that after Elliptic Curve Diffie Hellman, the shared secret's (curve point) x co-ordinate is recommended by good practice to be passed through a hashing algorithm to derive a key.

This is because the shared secret, whilst a random element of the curve generators cyclic subgroup, may not be uniform key material.

Thus, we can trust that good hashing algorithm's will not erode the underlying entropy of an input (beyond truncation), and should provide uniform output.

Thus I would deduce that concatenated hashes of cryptographically secure input should result in a cryptographically secure output of equal entropy to the input (assuming the hash output length is approximately equal to the CSRN input length).


Base Point on elliptic curve How can i define the base point of the elliptic curve group element used as the elliptic curve domain parameter over Fp (prime)

The "base point" is conventional. When using El Gamal or similar algorithms with an elliptic curve, you want to work inside a group with a prime order (either the complete curve has a prime order, or you work in a subgroup of the curve). Within a group of prime order, any element (except the neutral element, which is the "point at infinity" for an elliptic curve) is a generator for the group, so any point will be appropriate. The only requirement here is that all parties agree on the point to use.

It can easily be shown that any base point is as good as any other with regards to resistance to discrete logarithm: if you can solve DL efficiently in base $G$, then you can solve it efficiently in any other base $G'$ by first solving $G'$ with regards to $G$: first, use your efficient DL solving algorithm to compute $k$ such that $G'$ = $kG$; then, given $xG'$, solve it in base $G$ to get $xG' = rG$, then the solution will be $x = r/k \pmod n$ (where $n$ is the group order).

In practice, the "base point" is considered to be part of the curve definition, along with the other curve parameters. For instance, FIPS 186-4 defines the "NIST curves" (in annex D); for each of them, it lists the field modulus ($p$), the curve order ($n$), the curve equation parameters (NIST curves in a prime field use $y^2 = x^3 -3x + b$, so the only equation parameter is $b$), and the two coordinates $G_x$ and $G_y$ of the conventional base point.


A situation where security by obscurity might be the best solution - or am I wrong? Imagine the following situation. There is an application for a microcontroller-driven system. The profits are made from manufacturing and selling the device itself. However, it is expected, that the users can later download software-updates from a public website, and install it (using a USB-connection, for example).

Now, the problem is, if the updates were released as raw compiled binaries, anyone could just copy the hardware, and spare themselves the costs of a long software development.

Now, let the update be encrypted in some way, and the bootloader in the microcontroller (which is of course not part of the update, and will never be changed) The whole program sits in the internal flash which is protected against reading.

The problem is, there is so little space (measured in a few dozens of words or in best case up to maybe a hundred or so) in the bootloader that no cryptographically secure decryption algorithm can be implemented there.

So, let's release an update which has valid but random and nonsensical instructions inserted at random but pre-determined places. The bootloader knows it, and will remove them. The idea is, that even if an attacker knew this method (but did not knew the positions where these instructions are inserted), it would be near impossible to get the real program, as you cannot know you got the right one until you tested it (and even then, some hidden bugs might be still lurking if the "cracking" was not perfect).

The main objective in this scenario would be, to make it more time-consuming for the attacker to steal the software, than it would be to develop it on its own.

Is there an obvious flaw in this way of thinking?

In summary: the premise "there is so little space in the bootloader that no cryptographically secure decryption algorithm can be implemented there" is likely wrong; thus security-by-obscurity is not the way to go.

The method described in the question attempts to "prevent theft from the publicly released update"; but it fails to do that if an adversary manage to extract the bootloader and include it verbatim in a clone of the hardware: the clone and bootloader will happily load the software updates, no matter what clever and effective security-by-obscurity is performed.

Thus, something secret is needed in the bootloader, else this (or any) technique is doomed to allowing clones of the hardware to run the software updates. Once you assume that, even only 10 bytes of secret data, you no longer need security-by-obscurity: you can use that secret data as a key to a block cipher in e.g. CBC mode, and release the software updates encrypted with that, and perhaps signed integrity-protected with a MAC. Complete decryption with an appropriate block cipher, such as TEA (which is designed to be compact and reasonably efficient), can be implemented within less than 200 bytes on about any micro-controller.

Unfortunately, it is hard to keep something secret in a standard micro-controller: all data, including secret keys, tends to be readable using widely available tools, such as a JTAG port. And when that won't do, side-channel attacks will typically succeed. The premise "the internal flash which is protected against reading" might be true, but protected does not imply safe.

For this reason, in the integrity-protection part (if desired), it is best to use a public-key signature scheme, which does not need a secret (but will only marginally help towards the goal in the question: it will not prevent use of the software on unauthorized hardware, only prevent use of modified software on authorized hardware or exact clone thereof). An RSA signature with public exponent $e=3$ together with a proper padding scheme based on a hash can be implemented in say 800 bytes including 2048-bit public key (which will use less than 128 bytes; that's not a typo), and run at acceptable speed (run time is typically dominated by the hashing).

You are unlikely to get support for security-by-obscurity here: we officially believe in Kerckhoffs's principles. I would only condone security-by-obscurity as a second line of defense.


Difference between $Z^*_n$ and $Z_n$ When studying cyclic groups I stumbled upon the following sentence:

The ∗ in $Z_n^*$ stresses that we are only considering mulitplication and forgetting about addition on this site of stanford.

I don't really understand this definition, as I was learned that $Z_n^*$ just consists out of all elements of the elements of a cyclic group, minus the 0. Where does this the multiplication and addition come in?

$\mathbb{Z}_n^*$ doesn't mean $\mathbb{Z}_n - \{0\}$. You must remove all elements that are not invertible mod $n$, which is equivalent to keeping only the elements that are coprimes to $n$.

So, $\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n : \exists x^{-1} \in \mathbb{Z}_n \} = \{x \in \mathbb{Z}_n : gcd(x, n) = 1\}$.

This is necessary since all elements in a group must have inverse elements (regarding the group operation). In $\mathbb{Z}_n$, the group operation is $+$, so, any $x$ has $-x$ as inverse mod $n$. But in $\mathbb{Z}_n^*$, the operation is the multiplication, so, some elements might not have inverses mod $n$.

For instance, take $\mathbb{Z}_9$. The elements $0, 3, $ and $6$ are not invertible mod 9 (we can't multiply them by other element and reduce mod $9$ to obtain $1$). Therefore, $\mathbb{Z}_9^* = \{1, 2, 4, 5, 7\}$.


Information theoretical lower limit on the size of public and private keys When we consider public key algorithms, those usually require keys that are much longer than their security level.
According to the Crypto++ Security Level page, for example, integer factorisation algorithms (RSA et al.) require 3072 bits of modulus for a security level of 128 bits.
After RSA, we started to have more efficient systems (both in terms of speed and size), like the very efficient (to todays standards) Curve25519 elliptic curve. This curve requires around 256 bits of storage for the public key, and around 256 bits of storage for the secret key for the equivalent security level of 128 bits.
While RSA doesn't accept any bitstring as secret key, Curve25519 (give or take three bits) does. EC can be broken in $\mathcal{O}(\sqrt n)$, which sadly halves the security level.
So, while practically all public key algorithms have longer keys than symmetric counterparts, I wonder whether this is explicitely necessery. In short: is it (provably) impossible to devise a public key system wherein the public key and private key only take $k$ bits, with the security level equal to $k$, the information theoretical limit?
Bonus:
(If the answer to the above question is "yes, it's is provably impossible", this question gets redundant)
Notably post-quantum algorithms (thinking about SIDH) are heavy on key sizes (NTRU takes a few kB, SIDH a few kb). I restrict the above question to post-quantum public key algorithms: is there a (formal) reason for the requirement of large key sizes in post-quantum cryptography?

The private key can be reduced to $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance to brute force of $O(2^k)$ steps (on a conventional, non-quantum computer). Proof sketch: replace the RNG used for key generation by a PRNG with at least $k$-bit security and seeded with a $k$-bit key. And that bound can't be much improved since there must be at least $O(2^k)$ private keys to avoid a brute force search. Note: that does not apply to already generated private keys.

On a quantum computer, that goes reducing private key to $2k$-bit for $O(2^k)$-something quantum resistance. Argument: a symmetric cryptosystem secure to $O(4^k)$ classical steps is widely believed to require at least $O(2^k)$-something (time or/and qubits) on a quantum computer.

The public key must be at least about $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance $O(2^k)$ to brute force (on a conventional, non-quantum computer). Argument: we could use the above compressed form of the private key, and there can't be much less public keys than there are private keys, since that would allow finding by enumeration with effort $O(2^k)$ a private key matching a given public key.

But there is doubt that a $k$-bit public key is achievable. All known asymmetric cryptosystems actually have their public key $2k$-bit or more, for security as above. $2k$-bit is achieved by schemes based on the Discrete Logarithm in an Elliptic Curve group, and that's a plausible lower bound for the public key size. I vaguely remember having seen it conjectured at sci.crypt(.fr?), but without a convincing argument; and I fail to dig it up.


Homomorphic Encryption Arithmetic Operations I am looking to do arithmetic operations on encrypted values that will decrypt to be the result of the value decrypted. Does anyone know of any code examples of this in use? Usage of the equation would be nice as well.The psuedo from the below link is rather obscure. The specific reason behind asking the question is that I am having difficulty implementing this programmatically in a secure application I am working on. I understand math lingo somewhat but would like a working example involving real data.

Homomorphic Multiplication/Addition

So ideally given v1 and v2

v1 = 5; v2 = 4;

Decrypt(v1Encrypted + v2Encrypted) = 9;

The way to solve the problem in the question is to change the question slightly (beyond changing "Psuedo" to pseudo-code).

What really is wanted most likely  is

A public-private key pair generation method
An encryption function $E$; accepting as input any integer in $\mathbb Z_N$ (the plaintext), a public key generated as above, and a random number; producing as output an integer in $\mathbb Z_R$ (the ciphertext); so that knowledge of the ciphertext without the private key and the random number essentially won't reveal anything about the plaintext (with the possible exception of negligibly few plaintext). We'll note encryption $E$ functionally, omitting both it's public-key and random inputs: $E(5)$ will thus be different from one invocation to the other, including for a fixed public-private key pair.
A decryption function $D$, accepting as an element of $\mathbb Z_R$ and the private key, with the property that for $\forall x\in\mathbb Z_N, D(E(x))=x$ (when the public and private keys match).
An operation $\boxplus$ on $\mathbb Z_R$, such that
$$\forall x\in\mathbb Z_N,\forall y\in\mathbb Z_N,\ \ x+y<N\implies D(E(x)\boxplus E(y))=x+y$$

Pallier encryption provides just that, with $R=N^2$ and $\boxplus$ defined as $u\boxplus v\ =\ u\cdot v\bmod R$.

Note: notation in this answer was adjusted to better match standard texts on Pailler encryption; refer to e.g. Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (2nd edition) section 13.2.


PRP vs PRF for the F-function of a Feistel network A Feistel network is generally defined with a PRF for its F-function, but PRPs have been used as well. What are the theoretical cryptographic implications of using a PRP instead of a PRF? Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions?

Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions?

No.

  What are the theoretical cryptographic implications of using a PRP instead of a PRF?

We have a bound for the security of Luby-Rackoff based on the PRF-Security of F.
We have a bound on the PRF-security of a PRP ("PRP/PRF-Switching-Lemma").
We can simply plug one into the other to get our answer!

So, first the switching lemma:

  Let $E:\mathbb K\times \mathbb X\to\mathbb X$ be a family of permutations and $N:=|\mathbb X$|. Further let $\mathcal A$ be an efficient adversary against the PRF-security of $E$ making $q$ queries. Then there exists an adversary $\mathcal B$ such that $$\mathbf{Adv}^{\text{PRF}}_E(\mathcal A)\leq \mathbf{Adv}_E^{\text{PRP}}(\mathcal B)+\frac{q^2}{2N}.$$

Now the Luby-Rackoff-Bound (for three rounds):

  Let $F:\mathbb K\times \mathbb X\to\mathbb X$ be a family of functions with $N:=|\mathbb X|$. Further let $\mathcal A$ be an efficient adversary against the PRP-security of $\operatorname{LR}(F)$ making $q$ queries, then there exists an adversary $\mathcal B$ such that
  $$\mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(F)}(\mathcal A)\leq 3\cdot \mathbf{Adv}_{F}^{\text{PRF}}(\mathcal B)+\frac{q^2}{N}+\frac{q^2}{N^2}.$$

And now finally the combined bound:

$$\mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(E)}(\mathcal A)\leq 3\cdot \mathbf{Adv}^{\text{PRP}}_E(\mathcal B)+\frac{3q^2}{2N}+\frac{q^2}{N}+\frac{q^2}{N^2}$$

So as you can see, nothing substantially changed here.

The switching lemma and the luby-rackhoff bound can eg be found in the Boneh-Shoup book.


Undecrypt using the OpenSSL EVP API? I'm writing a client-server encryption scheme for homework, and I've stumbled upon what might be a fatal blow to my current implementation.

When using AES-256-CBC on the two sides, it's important that the client's encrypt context and the server's decrypt context remain in sync. However, my protocol allows for rejection of messages if they fail an HMAC test.

If a message were to fail the HMAC test, then the two contexts fall out of sync because the state of the context was polluted by the garbage ciphertext. All subsequent decrypts will fail. Is there any way to rollback a decryption, i.e. bring it back to the state in which it was before the decrypt happened? Alternatively, is there any way to copy an decrypt context?

The same goes for the client when it receives word of the failure. It's going to want to roll back its encryption.

Should I use something other than CBC mode?

You should packetize, or recordize, the messages into discrete units of a size reasonable for your protocol. Each record should be independently encrypted with its own IV. As an example, look at TLS 1.2 record or IPsec ESP packets. If a record is corrupted it can be discarded without impacting other records.

EDIT:

As pointed out by @poncho, TLS incorporates an implicit sequence number in the MAC calculation. Thus this may not be a good example. He also points that DTLS includes an explicit sequence number, and thus may be a better example.


Practical quantum attacks on SHA256 MAC and HMAC Is SHA256 MAC (or HMAC) vulnerable to any quantum attacks?

Game setup:

The attacker's goal is to produce a valid MAC to be accepted by other devices in the ecosystem.  The ecosystem consists of many devices with a shared secret key (named "key).  The attacker can query an oracle with messages and get MACs.  The oracle only accepts 32 byte messages.  Oracle queries are rate limited to 10ms.  Can the attacker find "key" so that he can produce valid MACs faster than any classical attack.

MAC = H(message[32] | key[32])

There are two points. First the MAC you are using is not HMAC and the way you construct it (first message than key as input without any padding) is only ok if you assume that a) the SHA2 compression function is a random oracle and that b) verifiers check that messages are no longer than 32 bytes. Otherwise one can forge messages at the cost of an intermediate inner state collision without learning key. Hence, it might be a safer choice to put key first, an even safer choice to additionally pad key to the block length (64 byte), and the safest choice to use HMAC from the start.

Second, quantum attacks: Of course you can run grover against this: Just collect, say three (message, tag)-pairs and build an oracle out of it that for a key $k$ outputs 1 if it maps all three messages to the respective tags. This function is a boolean function as needed by Grover. Hence, you can break this in $\mathcal{O}(2^{128})$ queries to SHA2. How long this actually takes is a different story and depends on the size of the quantum circuit to implement the boolean function.

Note that the rate limitation does not help in any way here as we only need sufficiently many pairs that there exists only one solution $k$ with sufficiently high probability.

Add-on:
What is the probability that a key that works for two message tag pairs works for a third?

If we model $SHA2-256(m \| k) = t$ as a random function and assume we obtained pairs $(m_1,t_1), (m_2,t_2)$ which were computed using some key $k$ then the probability that a given key $k' \neq k$ maps $m_1$ to $t_1$ is $2^{-256}$. The probability that $k'$ maps $m_1$ to $t_1$ AND $m_2$ to $t_2$ is $2^{-(2*256)}$ and so on. (Here the 256 comes from the output length).

The probability that $k'$ does not map $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$(1-2^{-(2*256)})$. The probability that all possible $2^{256}-1$ keys $k'\neq k$ do not map $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$(1-2^{-(2*256)})^{2^{256}-1}$ (here the outer 256 exponent comes from the size of the key space). So, the probability that there exists a key $k'$ that maps $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$$1-(1-2^{-(2\cdot 256)})^{2^{256}-1} \approx \frac{2^{256}-1}{2^{2\cdot 256}}\approx 2^{-256}.$$


Use of salt to hash a password In a few implementations of hashed passwords, I have seen that the length of the random salt is chosen to be, say, 10 or "some constant". Is there any specific reason why the salt is chosen to have a fixed length? Can a smart attacker take advantage of it?

Does hashing a password with a random salt make the password stronger?

Well, the reason we add salt when hashing passwords is not to make a single hashed password stronger (it doesn't, except in a way I'll explain below), it's to fix up some weaknesses that appear when you have a collection of hashed passwords.

If the attacker somehow gets a single hashed password, then adding a salt doesn't really slow the attacker down (assuming that he gets the salt as well; since the salt is commonly stored with the hashed password, this is a reasonable assumption). Without the salt, the attacker can guess various passwords, hash them, and see if any of them hashes to the target value.  With the salt, the attacker simply includes that when he hashes his guesses, and so that doesn't make his job any harder.

However, if the attacker gets a list of hashed passwords, then adding a salt does make the attacker's job harder.  Without the salt, the attacker can guess various passwords, hash them, and see if any of them hashes to a value on the list; if he has a collection of 1000 hashed passwords, he has just checked 1000 passwords with a single hash.  On the other hand, if each hashed password includes a salt, and if each salt is different, then to check to see if a guessed password is accurate, he has to run 1000 hashes (with each hash using a different salt); this does make his job harder.

In addition, there are clever ways that an attacker can use to precompute hashes of various possible passwords (and store those in a manner that is considerably more compact than the list of hashed passwords).  Without salt, the attacker who has spent the time to create the table can quickly check if any of the hash passwords happen to be one of the ones he has precomputed.  It turns out salt interferes with those as well (because the salt is another thing that the precompute method would need to guess, and if the salt is of reasonable size, this is impractical).

Now, when I mentioned above that there is a way that a salt makes even a single password stronger, it's because of these precomputation methods.  It makes the use of a precomputed table impractical.  The attacker can still do a dictionary search on the hashed password, but he has to do the computation after he has obtained the hashed password (and he can't reuse that effort to attack anything else).

Finally, the other thing that salt helps with is to obscure whether two passwords happen to be the same.  Without salt, two identical passwords will hash to the same exact value, which an attacker that gets the hashed values can see.  Even if the attacker can't tell what the common password is, it may give him information that we don't want him to have (such as "User X" and "User Y" are the same physical person).  With salt, there is no such information leakage.

You also asked about salt length; from the above discussion, it should be obvious that we want salt values to be unique.  One easy way to make them unique is to choose them randomly, and make them long enough that collisions (that is, two passwords get the same salt) are unlikely.  In general, if we can expect to have $N$ different hashed passwords, we'll want at least $N^2$ different salt values (with more being better); 10 random alphanumeric characters does this nicely.  As for always picking the same salt length, well, since we assume that the attacker can see the salt values, we don't want the salt lengths to leak any information about the password.  Choosing the same length for all salts achieves this nicely.