Distinguish messages Since i cannot comment on questions, I give my own:

If a secret key encrypt algorithm can encrypt messages of arbitrary length and the encrypt algorithm is probabilistic then: suppose the adversary selects two messages of different length, $||m_0||=n$, $||m_1||=l$ and $n<l$. She gets back a ciphertext $c$. How can she tell which message was encrypted? Cause I thought that since the encryption is probabilistic the length of $c$ might as well be $n$ (which is not likely, but just to show that $c$ can have any length), while message $m_1$ was the one encrypted. Right? or very wrong?

The encryption algorithm is probabilistic but the length (or better the entropy) of the ciphertext must be at least the length of the message. If the length of the ciphertext is shorter than the length of the plaintext, then you loose information about the plaintext while encryption process and you cannot decrypt it correctly. And the encryption algorithm is memoryless and does not know anything about older or other messages.

Now, suppose you have the two messages $||m_0|| = l_0$, $||m_1|| = l_1$ and $l_0 << l_1$ (say $l_0 = 1 \, bit$ and $l_1$ is very large $>10G \, bits$). If you receive a ciphertext shorter than $l_1$ you know that $m_0$ was encrypted. I think you can see, that an encryption algorithm, that produces ciphertexts longer than $l_1$ when you only encrypt a single bit, is very inefficient.

The only way to cancel this effect is to restrict the length of the plaintext messages and produce ciphertexts equal or longer than this maximum input length. But in this case, the plaintext of a single bit will be padded and you can directly define the security with equal length messages.


LOR implies unpredictability? It should be true that classical LOR(Left or Right)-indistinguishability of some mode of operation implies unpredictability. However I've got stuck with the proof of this fact.

LOR-indistinguishability of some mode of operation E means the following:
an adversary has access to the oracle, she can query pairs (m1, m2) to the oracle;
the oracle would respond by encrypting either left message (m1) or the right one (m2).
The mode E is LOR-indistinguishable iff the adversary has hard time to guess whether the left message of the pair was encrypted or the right one.

By unpredictability I mean the following. The adversary is allowed to ask queries of the type M and to obtain the response E(M). The goal is to find a message M*, which was never queried, with the corresponding ciphertext E(M*).

The intuition is that if the adversary A can predict the output of the oracle with "high" probability, then the mode leaks some information, and this adversary can be used to construct LOR-adversary B.

The idea is simple: if we have some oracle (left/right), then we take M (which was asked by A) and we take completely random r with the same length as M, and give this pair (M,r) to our (LOR) oracle. The answer is then goes to A directly.

If A will successively predict the new message, then we bet that the oracle is LEFT, otherwise that it is RIGHT.

In the LEFT universe the probability to predict correctly is the probability of success of A in real-world.

However, I was stuck how to bound the probability of "false positive" in the RIGHT world.
The adversary A have some "trash" values E(r) instead of E(M) he was asked for. How much does it helps him to predict E(M*) correctly for some M*?

The reduction will not work. The reason is that any $E$ that is LoR indistinguishable has to be randomized. But then, the adversary's output might be different from the outcome of the oracle, even if it evaluates the correct $x$ (the one picked by the adversary).

In fact, there is a family of $E$'s that is predictable but still LoR indistinguishable. For example consider a public-key encryption scheme that is LoR indistinguishable and let $E(x)=(\mathit{Enc}(\mathit{pk},x),\mathit{pk})$. Then also $E$ is LoR indistinguishable. However, you can easily find pairs $(x,E(x))$ since with one query you can retrieve the public key.


AES: keylength and password length? What is the difference between the keylength and the length of a password for AES-256?

AES is a block cipher, a cryptographic primitive that is meant to be used in a larger framework. Its sole purview is encrypting a single block of data given a certain-sized key. In the case of AES-256, the key size is 256 bits.

Notably, there is no password involved in AES. So, there is no password length to discuss. AES itself just uses keys.

If you are using a service which claims it uses AES-256, and you are forced to enter a password, what is likely happening is that your password is used to derive a key. This is often done using a key derivation function, like PBKDF2, which stands for "password-based key derivation function 2". (Some KDFs are meant to expand real, uniformly-random keys, while others are intended to have "human"-like passwords for inputs.)

So, in this hypothetical scenario, the direct key used for AES-256 is likely the output of the KDF given your password as an input. If this is the case, then your password can be whatever length you so desire, although longer passwords are more difficult to guess (i.e., stronger). The job of a KDF is take the input and produce a "good" key from it.


If RSA Signature is not Decryption, why is it not advisable to use same keys for enc/dec and sig/ver? If RSA Signature is not Decryption, why is it not advisable to use same keys for enc/dec and sig/ver? What is the proof where you may be exposing your private key when you use the same one for decryption and signing? This is for RSA OAEP.

The advice to use different key pairs is not because there is a risk of exposing your key, just that enc/dec and sign/ver often have a different security level, or can become so in future.

E.g. If you are using signed and encrypted email for your job, it's not unreasonable for the company to have a copy of the decryption key so that they can read the emails sent to you (as a representative of the company). Where as there is no legitimate reason for the company to impersonate you, so there is no reason to provide them your signing key.

Even if this doesn't occur now, you may need to change this retrospectively. E.g. Even if a company doesn't keep a copy of the decryption key proactively, they may ask for it when you leave. If you've kept the keys separate there isn't really a problem with this (as long as you use separate keys for work and personal purposes), but you wouldn't want to hand over a key that could also be used for signing as that would allow you to be impersonated.

Similar situations can crop up in most contexts. E.g. I may want to make provisions for my heirs to decrypt my personal communication when I die, but would not want to enable them to impersonate me. By keeping the keys separate I can make provisions to release my decryption key on my death, but ensure the signing key dies with me.


Is it secure to cascade KDFs I would like to know if the following process to generate keys for a set of devices is secure.

Let’s say I have a 128-bit master key MK with high entropy. I use a KDF to generate a 128-bit device key DK for each device:

DK1 = KDF(MK, salt1)
DK2 = KDF(MK, salt2)
…

where the salt is, for example, the serial number of the device.

The device key is assigned to the device. They use their Device Key and the same KDF to produce message keys with 128bit:

K1 = KDF(DK1, mc)

where mc is a message counter.

The key is used for encryption or CMAC authentication.

When the devices communicate with the back end system, the back end can derive the K1 by

K1 = KDF( KDF(MK, salt1), mc)

Is this secure? The proposal for the KDF is CMAC according to NIST/SP 800-38B.

You can do this: essentially, if the initial key is uniform random and you use it for no other purpose, you can safely treat keys derived from it by distinct labels as independent uniform random from one another.  The only danger is if you might accidentally use the same sequence of labels for two different purposes, which would be catastrophic.  So make sure that each sequence of labels uniquely identifies the role that a key might be used for.  (Formally, a KDF is a PRF, so if the key is uniform random, the output is hard to distinguish from uniform random.)

But what are you going to use mc for?  Most authenticated ciphers, like AES-GCM, like AES-OCB, like NaCl crypto_secretbox_xsalsa20poly1305, etc., are designed to handle more than one message under a single key.  Except for ‘SIV’ schemes which specifically don't conceal repeated messages, these all require some additional input to distinguish them—a random initialization vector, or a unique nonce.  And if you aren't repeating message counters, a message counter makes an excellent nonce.

So while there's no problem with this as long as the labels uniquely identify key roles, you shouldn't need to do it—just use a standard authenticated cipher with the message counter as a nonce!


Is a cryptographic key of size $N$ equivalent to $N$ bits of entropy? Are there any caveats to the claim that a cryptographic key of size $N$ bits and $N$ bits of entropy are equivalent?

Yes, there are caveats.

The key 982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224 is 256 bits long but has zero bits of entropy to anyone who knows you are using it.

Suppose you designed a cryptosystem where every legitimate user's secret AES-256 key started with a 192-bit prefix known to you, the designer, which which you chose uniformly at random.  To an adversary who doesn't have access to the system, the keys have 256 bits of entropy.  But to you, each key has at most 64 bits of entropy.  The United States government imposed this kind of requirement on Lotus in the international editions of its proprietary Lotus Notes software system in the 1980s, albeit with much smaller key sizes, back in the days when men were men and they all agreed that encryption was a munition used outside the United States only by terrorists and that 56 bits oughta be enough for anyone who's not a terrorist.

The number of bits in an RSA modulus may be 2048 (not counting the exponent bits, the private key, and any ASN.1 formatting or what-have-you to store it in a practical system), but it may reasonably be generated from a 256-bit seed.

Entropy is a property of a process or state of knowledge when the process or unknown may have many possible outcomes.  For a cryptosystem to be useful, from the adversary's perspective, in the adversary's state of knowledge, the legitimate user's key has to have a distribution of possible values with a nonnegligible min-entropy, which is formally defined as $-\max_k \log p(k)$ where $k$ ranges over all possible keys and $p(k)$ is the probability of the key $k$.  If the min-entropy is too small, then the adversary has a good chance of guessing the key on the first try.

But the length of the key is necessarily related to its entropy only in that the length in bits cannot be smaller than the entropy in bits, because you need to have at least $2^n$ possibilities in order to have an entropy of $n$ bits.


Trying to understand the use of ECC in TLS certificates I was looking the certificate of this website: https://www.cloudflare.com that has an ECC based certification.

I'm just curious to know if is possible to understand which elliptic curve is used and which point is used.

Another thing: I don't understand why in the certificate there is a RSA 2048 public key and not an ECC key.

ECC is indeed used by CloudFlare's website but only for the session key agreement. The authentication is performed using an RSA 2048 bit private key. The corresponding RSA public key is in the certificate. In other words, although ECC is being used, it is not used for authentication and therefore not part of the certificate.

The ciphersuite is:

TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256

Which means TLS with ECDHE (ephemeral Elliptic Curve Diffie-Hellman) key agreement, RSA based authentication (and thus certificates). The ephemeral part means that no static private ECDH key is used on the server and no public ECDH key is therefore present in the certificate.

Or, as specified by RFC 4492 section 2.4:

  2.4 ECDHE_RSA

  This key exchange algorithm is the same as ECDHE_ECDSA except that
     the server's certificate MUST contain an RSA public key authorized
     for signing, and that the signature in the ServerKeyExchange message
     must be computed with the corresponding RSA private key.  The server
     certificate MUST be signed with RSA.

To state that the CloudFlare website is using ECC certificates (not certification, that term means something else) is therefore incorrect. It uses a cipher suite that performs ECDH key agreement.

The used explicit or named parameters are determined during the handshake. The client has the ability to include a list of supported curves, ordered to preference RFC 4492 section 5.1.1. The point format - uncompressed (default) or compressed - can also be indicated. As the EC points themselves are ephemeral (short-lived) you can only retrieve them by analyzing the handshake.

For completeness the rest of the ciphersuite: AES-128 bit encryption using GCM authenticated (AEAD) mode encryption. The final SHA-256 is used as definition of the keyed hash (HMAC) used for key generation (or key derivation) and validation.


Proving multiple products "in the exponent" I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement.
I'll start by giving an example.

The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$.
The verifier only has $g^a, g^b$ and $g^c$.
Nobody (not even the prover) knows the exponents $a,b,c, ab, ac, bc, abc$.
The prover gives $g^{abc}$ to the verifier and wants to convince him it has done so.

To convince the verifier, the prover can give him a proof consisting of $g^{ab}$.
The verifier can check with a bilinear map that $e(g^a, g^b) = e(g^{ab},g)$ and $e(g^{ab}, g^c) = e(g^{abc}, g)$.
(I believe we also need to make all group elements "extractable" for this to be secure, but I'm ignoring this for now.)

Assuming this approach for proving $n=3$ "products in the exponent" is sound, the first challenge is it doesn't scale to large $n$: the proof size is linear in $n$.

To see this, let's extend the above example to arbitrary $n$.
Specifically, suppose the prover and verifier have $g^{a_i}$'s for all $i\in [1,n]$.
In addition, the prover has $g^{\prod_{i\in S} a_i}$ for all subsets $S$ of $[1,n]$.
The prover gives $c$ to the verifier and wants to convince him that $c = g^{\prod_{i=1}^n {a_i}}$.
Then, the proof will be a tree whose root is $c$, its leaves are the $g^{a_i}$'s, and its internal nodes with their children are DDH tuples (i.e., parent is $g^{\alpha \beta}$ with children $g^{\alpha}$ and $g^{\beta}$).
The proof consists of all the internal nodes in this tree, of which there are $O(n)$.
Unfortunately, this is too large.

The second challenge is we want the prover to pick a subset of indices $S \subseteq [1,n]$, compute $c = g^{\prod_{i\in S} a_i}$, give $c$ to the verifier and convince him that there exists some subset $S$ of $[1,n]$ such that $c = g^{\prod_{i\in S} a_i}$, without actually having to reveal $S$ itself, which is too large.

Questions:

Can Groth-Sahai NIZKs [1] be used to efficiently prove such a statement in bandwidth $o(n)$? (Maybe $O(\sqrt{n})$?)
Can you think of other cryptographic techniques that can be applied here?

Unfortunately, improving over the $O(n)$ solution seems to require the use of non-standard assumption. More precisely:

No, Groth-Sahai NIZKs cannot be used for proving this statement with communication less than $O(n)$, because the witness held by the prover is already of size $O(n)$. In fact, even if the prover knew all the discrete logarithms of the group elements (i.e., all the $a_i$'s), Groth-Sahai proofs would still produce proofs of size $O(n)$. The main reason for this is that Groth-Sahai proofs are... Well, proofs (more precisely, they can be either proofs or arguments, depending of the mode of the crs, but they have the same size in both cases since the modes must be indistinguishable). An interactive proof (meaning, with statistical soundness - as opposed to interactive arguments which have computational soundness), zero-knowledge or not, non-interactive or not, cannot have communication sublinear in the witness size unless NP can be decided in subexponential time.
It does not seem to be straightforward to obtain a shorter proof for your problem without using "heavy hammer" tools, or the random oracle model. If you are ok with using the random oracle model, then there are sublinear interactive proofs which can prove this statement with logarithmic communication complexity, and can be made non-interactive using Fiat-Shamir (1, 2). In fact, very recently, it was shown here how to build such succinct interactive public-coin arguments directly for bilinear equations a la Groth-Sahai. If you do not want to use random oracles, then you will have to rely on the non-standard and non-falsifiable assumptions underlying the constructions of all SNARGs - there are many available. However, none of them will provide a very good concrete efficiency for your specific problem, and I'd strongly suggest to rely on a solution in the random oracle model instead.


Shamir secret sharing with two types of parties Consider the Shamir Secret Sharing scheme based on polynomial interpolation.

In this scheme, every part has the same right: one piece of information of same value as the other ones.

The idea is to adapt this scheme in following way:

Suppose that we want to share a secret among politicians and generals.
The secret can only be retrieved if 3 elements are united and if in that group at least one is a politician and at least one is a general.

How can we do that? It is not clear to me what to do. Thanks in advance.

Let's say your secret is $S$. Split $S$ into 3 parts (say $S_1,S_2,S_3$) such that $S=S_1\oplus S_2\oplus S_3$.

Give each politician a copy of $S_1$, each general a copy of $S_2$, then split $S_3$ using 3-out-of-n Shamir Secret sharing.


How to use SHA-1 as a PRNG? Is there any special parameters for using SHA-1 for generating pseudo-random numbers? What are the differences between SHA-1 as a PRNG and original SHA-1?

There are many possible constructions but the simplest is probably to initalize a counter with a random seed and hash the counter to produce more random bits and then increment the counter.


Why does l'Ecuyer reject p-values close to 1? When applying several tests to a given generator, p-values smaller
than 0.01 or larger than 0.99 are often obtained by chance even if the
RNG behaves correctly with respect to these tests (such values should
normally appear approximately 2% of the time). In this case,
suspicious values would not reappear systematically (unless we are
extremely unlucky).
(Source,
page 6.)

Here's result where the test MaxOft AD produces a p-value close to 1 and so the RNG fails that test.
========= Summary results of SmallCrush =========
[...]
The following tests gave p-values outside [0.001, 0.9990]:
[...]
Test p-value
----------------------------------------------
[...]
6 MaxOft AD 1 - 3.6e-06
[...]
----------------------------------------------
All other tests were passed
[...]

NIST SP 800-22 calls such values "perfect randomness" (page 1-4, that is, PDF-page 16).

If a P-value for a test is determined to be equal to 1, then the
sequence appears to have perfect randomness. A P-value of zero
indicates that the sequence appears to be completely non-random.

So, what's wrong with a p-value close to 1?

So, what's wrong with a p-value close to 1?

Because random sequences don't look 'perfectly random' (or, rather, they have a low probability of doing so).  We're checking if this sequence quacks [1] like a perfectly random sequence; acting 'too uniform' is evidence that it is not.

[1]: from the proverb "if it acts like a duck, and it quacks like a duck, then it is a duck".  Fairly common where I am; however you never know how regional sayings like this are..


Matsui's Linear Cryptanalysis Lemma 1 In Matsui's paper (Linear Cryptanalysis Method for DES cipher), lemma 1.

$NS(a, b)$ is even
if $a=1,32$,or $33$, then $NS(a,b)=32$ for all $b$

He said that the following lemma is now trivial from the definition of S-boxes.

But I can't prove this lemma. How can I prove this lemma?

The following apply to all DES Sboxes.

Note that $\overline{a}\cdot \overline{x}$ and $\overline{b}\cdot \overline{S(x)}$ are both linear boolean functions which thus have truth tables with even Hamming weight.  The xor of the two quantities is also even, since if they have hamming distance $d$ this is 64 minus (the difference of two even hamming weights) by inclusion exclusion.
The $a=1,32,33$ masking patterns are the ones where either LSB or MSB or both of input bits in the corresponding vector $\overline{a}$ are set to one while the remaining bits are set to zero. Recall that for each of the four such possibilities ($a=0$ as well) the DES Sbox output is a permutation of four bits. This also gives a balanced hamming weight, for all output masks $b$.


What are linear and non-linear elements in cryptography? I was reading this answer, How secure is XOR for encryption, and it stated that XOR's aren't good for securing messages as they are linear in Nature. And therefore should be paired with some non-linear elements like Substitution box to provide strength to the encryption.

My question is, what are linear/Non-linear elements, in context of cryptography? And what are advantages and disadvantages of each over the other.

A mathematical function $f$ is linear if it is of the form $f(t) = c + g(t)$ where $c$ is a constant and $g$ has the property that $g(a + b) = g(a) + g(b)$.  (Strictly speaking, in math one usually considers only $g$ to be linear and $f$ to be merely affine, but we don't make that distinction here.)  We also say that a function $\phi(s, t)$ of two arguments is bilinear, or again just linear, if for each $s_0$ and $t_0$, the functions $t \mapsto \phi(s_0, t)$ and $s \mapsto \phi(s, t_0)$ are linear.

  Exercise. Prove that the function $(s, t) \mapsto s + t$ is bilinear.

If we're talking about real numbers, like 0, −3, 1/48, $\pi$, etc., linear functions are of the form $f(x) = mx + b$ for constants $m$ and $b$, which you may recognize as the equation of a (nonvertical) line.  But we don't have to talk about real numbers; we can consider integers too, or even the remainders of integers after dividing by 2 (‘modulo 2’), where $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, and $1 + 1 = 0$.  The linear functions in this case are still of the form $f(x) = mx + b$, but the only two possible values for $m$ and $b$ are 0 and 1, so there are only four such linear functions.

We can also do addition and multiplication of polynomials, or of matrices of higher dimensions.  Each space has its own notion of linear functions, defined in terms of that space's notion of addition.  Linear functions are easy to compute—and easy to invert, or at least partially invert: in spaces where we have a notion of division (like rational numbers), we can recover $x$ from $f(x)$ by $x = (f(x) - b)/m$; in other spaces, like matrices, we have easy algorithms like Gaussian elimination to solve linear systems.

Suppose you have a string of bits, say 10110 or 00111.  One way to interpret the bits is an integer, in this case 22 or 7 (in decimal).  Another way is to interpret the bits as a polynomial with coefficients modulo 2, in this case $x^4 + x^2 + x$ or $x^2 + x + 1$.  If we add these in their respective spaces and convert back to a string of bits, we get different answers:

\begin{gather}
  22 +_\mathbb Z 7 = 29 \longrightarrow \mathtt{11101} \\
  (x^4 + x^2 + x) +_2 (x^2 + x + 1) = x^4 + x + 1 \longrightarrow \mathtt{10011}.
\end{gather}

  Exercise. Why did the $x^2$ term disappear?

Here I have labeled the integer addition operation as $+_\mathbb Z$ and the polynomial modulo 2 addition operation as $+_2$.  We could also write both sides of the equation as a string of bits; when we use $+_\mathbb Z$ and $+_2$, we may get different answers, as strings of bits:

\begin{align}
  \mathtt{10110} +_\mathbb Z \mathtt{00111} &= \mathtt{11101} \\
  \mathtt{10110} +_2 \mathtt{00111} &= \mathtt{10001}.
\end{align}

  Exercise. Is there another name for $+_2$?

  Exercise. Find two bit strings $s$ and $t$ such that $s +_\mathbb Z t = s +_2 t$.

Although $+_\mathbb Z$ is linear (or, more precisely, bilinear) in integer addition, it is not linear in polynomial modulo 2 addition—in other words, although, e.g., $t \mapsto s_0 +_\mathbb Z t$ is linear over $+_\mathbb Z$ meaning it is of the form $t \mapsto c +_\mathbb Z g(t)$, specifically with $c = s_0$ and $g(t) = t$, this function is not of the form $c +_2 g(t)$ for any $c$ or $g$.  Conversely, $+_2$ is linear in polynomial modulo 2 addition but not in integer addition.

In other words, xor is linear in polynomial modulo 2 addition, but not in integer addition; conversely, integer $+$ is linear in integer addition, but not in polynomial modulo 2 addition.  When you combine the two—e.g., consider the function $(u, v, w) \mapsto (u +_\mathbb Z v) +_2 w$—the result is a function that is nonlinear in both spaces, which means it does not admit any neat algebraic simplification or inversion like $(f(x) - b)/m$ or Gaussian elimination.  This in turn means that cryptanalysis can't take advantage of neat algebraic simplification or inversion, and so may be much harder.


Does adding a salt to the message before HMAC processing add any security? An HMAC function is designed to verify message integrity, i.e., that the message has not been tampered with. It is generally (always?) implemented by using a hashing function H, and calculating the hash H(key + H(key + message)), where + signifies concatentation (Source). The key is secret, and is reused for multiple HMAC calculations.

A related cryptographic technique is "salting." This is commonly used when storing passwords: each password will have a unique salt (or "nonce"), and you store the hash H(salt + key) and the salt together in the database. The salt is not encrypted, is not reused for other passwords, and is not a "secret" like the HMAC key.

My question is: does it add any security to add a random salt to the message you are validating with HMAC?

In my situation, the "message" I am validating is a six digit number. My "gut" was to use a salt (perform HMAC on salt + my six digit number) to protect against rainbow tables, but then it occurred to me that, since I'm using a 512-bit HMAC key generated by a cryptographically secure random number generator, there may be no added security. If I'm understanding it correctly, this answer (to a question about HMACing short inputs) means that there is no added security.

However, I am not completely certain. So, can someone clarify? Is there any value in adding a salt to your message prior to determining the HMAC?

My question is: does it add any security to add a random salt to the message you are validating with HMAC?

This depends on what the HMAC is used for.

If you use a key to sign more than one secret message, a salt will prevent an attacker from knowing whether two of them are equal. (Or brute forcing a message if the key is revealed...)

It is more common that you send the message and its HMAC value through the same channel, in which case protecting the secrecy of what is authenticated does not matter (unless you encrypt and use encrypt-and-MAC). What may matter, however, is that an attacker could do replay attacks, reusing a previous message and HMAC pair.

To protect against replay attacks you need to add not just a salt, but one that the receiver can verify has never been used before. For example, an incrementing counter (that both parties store and compare), a close enough (monotonic) timestamp, or a salt that the receiver chooses e.g. randomly.


How to decrypt AES in CBC i am having problems understanding how CBC works! I know that it is a chain and the IV is XORed with the PT but then what? I mean we encrypt it with key k and the result is the CT which we use for the next chain-XOR but my question is HOW the encryption works? For example in Stream ciphers i just had to XOR the K with the M (or C) to get my result, but on block ciphers i am completely lost...

CBC is a block cipher mode of operation, not a cipher. It can work basically with any block cipher - the choice of the block cipher itself is independent (to a large extent) from the choice of the mode of operation.

Examples of well known block ciphers include AES, DES, TripleDES, Serpent, Blowfish etc.

The title of your question, however, asks about decrypting AES using CBC mode operation. In which case you should be using AES, $P_t = \operatorname{AES-128-DEC}_k(C_t) \operatorname{XOR} C_{t-1}$. AES decryption is available in many crypto libraries (for example libtomcrypt, Crypto++, openssl, Java Cryptography Extensions, Python Cryptography Toolkit), and you can even use online AES "calculators" such as this one.


How should I generate secure random numbers deterministically? I have a 256-bit seed; call it P. From P, I need to derive 219 256-bit numbers deterministically.

There's a catch, however: I want to derive them in any order. For example, I might need the 7878th number, followed by the 51st number. For that reason, deriving them with a stream cipher is inappropriate for me. Also, if one output is revealed to the attacker, it should not be possible to derive a different output.

My intuition is that I could use a hash function to derive each number, but I'm concerned that it wouldn't have the properties necessary to prevent an attacker from deriving one output from a different output.

What type of cryptographic construction should I use?

Your idea of using a hash function to expand your seed is a reasonable one.  If you want a standardized method of doing so, try HKDF from RFC 5869.  Specifically, I'd suggest something like the following:

PRK = HKDF-Extract("custom salt value", P)

output[i] = HKDF-Expand(PRK, string(i), 256/8)

where "custom salt value" is a unique string identifying your application and, where applicable, any other relevant context, so that reusing the same seed P in different contexts won't yield the same output.  (If you already know that the seed P is unique, entropy-dense and only known to your application, you can skip the HKDF-Extract step and just set PRK = P; see the RFC for more information.)

Of course, any other secure key derivation function, such as the counter, feedback and double-pipeline mode KDFs from NIST SP 800-108, could be used in a similar way.

Alternatively, since your seed P is a random 256-bit string, and the number of outputs you require is relatively small (≪ 264), you could simply generate your outputs using a block cipher with a 256-bit key (e.g. AES-256) in counter mode, using P as the key, e.g. like this:

output[i] = AES-256(P; 2*i) || AES-256(P; 2*i+1)

where || denotes bitstring concatenation, and AES-256(P; c) denotes the encryption of a 128-bit block encoding the counter value c with AES-256 using the key P.

Note that, since a block cipher like AES is a pseudorandom permutation, not a pseudorandom function, the output of this method will never contain duplicate blocks.  Fortunately, in your use case, this bias will not be practically detectable, since (per the birthday problem) the expected number of random 128-bit blocks one would need to observe to actually see a duplicate is approximately 264, i.e. far more than the number you intend to generate.


Generation of strong primes It seems that this is pretty difficult to find large (above 1024 bits) strong primes, or at least such primes $p$ where $(p-1)$ has a very large prime factor. Is there any information regarding the distribution of strong primes vs. other primes? The GNU library generates strong primes for RSA?

Quoth Messrs. Rivest, Shamir, and Adleman in 1978:

  To find a prime number $p$ such that $(p - 1)$ has a large prime factor, generate a large random prime number $u$, then let $p$ be the first prime in the sequence $i \cdot u + 1$, for $i = 2, 4, 6, \dots$.  (This shouldn't take too long).  Additional security is provided by ensuring that $(u - 1)$ also has a large prime factor.

  A high-speed computer can determine in several seconds whether a 100-digit number is prime, and can find the first prime after a given point in a minute or two.

Quoth Messrs. Rivest and Silverman two decades later in 1999:

  We argue that, contrary to common belief, it is unnecessary to use strong primes in the RSA cryptosystem.  That is, by using strong primes one gains a negligible increase in security over what is obtained merely by using ‘random’ primes of the same size.

The latter reference also contains a handful of citations on methods for generating strong primes and their expected performance—admittedly, for numbers of somewhat smaller magnitudes, but the paper should explain why everyone may have been sapped of the motivation for more recent studies on the subject.  Specifically, citing John Gordon in 1984 (whose primitive typography renders the original paper nigh illegible), they summarize:

  The naive algorithm for finding a $k$-bit prime by testing random $k$-bit numbers for primality thus requires time $\Theta(k\,T(k))$.  Gordon's algorithm requires finding one $k$-bit prime after finding three $k/2$-bit primes, taking a total time of $$k\,T(k) + 3(k/2)\,T(k/2) = 1.1875 (k\,T(k)).$$  This justifies Gordon's claim that finding strong primes requires only 19% more work than the naive algorithm for finding strong primes.

Gordon's analysis assumes there is nothing remarkable about the distribution of strong primes among all primes.  While that's not a priori clear, any interesting properties of that distribution would likely be a remarkable result worthy of publication in a mathematics journal, at least, even if cryptographers don't care any more.

How to weigh the lack of interest of practical cryptographers against the excitement of pure mathematicians about completely useless but difficult trivia in number theory in the fine tradition of G.H. Hardy is a question I leave to the sociologists.


Breaking a Modified Caesar Cipher Does anyone know of an efficient way of breaking a modified Caesar cipher (where the key is a set of numbers (the amount of shift) that is repeated throughout the plaintext, e.g. {1,2,3,4,5}) via brute-force?

The way I'm currently trying to crack it is as follows:

Generate all possible key combinations ( 5 numbers between 1 & 25)
Use the generated key to "decipher" the message
Use frequency analysis on deciphered messages to see which one is the best fit

As you can probably guess, the way I've come up with is the least efficient (in terms of time and memory) and I was wondering what would be the best way to decipher the message.

Assume the length is $n$. If the cipher text is $c_0, c_1, c_2, \ldots, c_N$ then consider the sub-text consisting of the characters $c_0, c_n, c_{2n},\ldots$. These have all been encrypted with the same Caesar, and you can break it by frequency analysis (the shifted 'e' should be the most common in standard English texts, or else maybe the 't' etc.). Suppose the shift you find is $s_0$. Then try the shifts $s_0 + 1, \ldots s_0 + (n-1)$ for the next sub-texts and see if you have a result. If not, try another $n$. This way you only brute force over $n$, essentially.

You could also determine the length $n$ by a statistical method (index of coincidence) or Kasiski (finding long repeats) as well. These will work for any Viginère cipher. But the above might be simpler if you already know that the shifts will be cyclic and consecutive.


Why is the polynomial in AES MixColumns multiplied modulo a reducible polynomial? I know that the AES MixColumn step is calculated as follows

$b(x) = (a(x)c(x)) \mod l(x)$

with $a(x)$ being the column to encode, $c(x)$ the fixed polynomial $c(x) = 3x^3 + x^2 + x + 2$ and $l(x) = x^4+1$ which is reducible over $GF(2^8)$ since $x^4 + 1 = (x+1)^4$.

I wondered about the purpose of the reducibility property of $l(x)$ and so I looked it up in my text book as well as on the internet but I could not find any further explanation on this. As it is my understanding only an irreducible polynomial $f(x)$ would be able to create a field $GF(2^8)[x]/(f(x))$. So my question is:

Is there a particular reason why l(x) must be reducible over $GF(2^8)$ in AES MixColumns?

The reason it is not irreducible is because it does not have to be.

For MixColumns, the result must be a polynomial of degree 3 or less, which requires a degree 4 reduction. We are not reducing the elements of the finite field here, but the coefficients of the polynomial generated by multiplication of the fixed and input polynomials. With reduction by $x^4+1$, the reduction can also be represented as replacing the coefficient of $x^0$ with that of $x^4$.

The choice of degree 4 reduction polynomial does not have to be irreducible in $GF(2^8)$ if the fixed polynomial in the matrix multiplication has an inverse, which it does. In the case of $c(x)=3x^3+x^2+x+2$, $c^{-1}(x)=11x^3+13x^2+9x+14$.


Finding Vigenere's keys with part of decrypted text? I have a text that was encrypted twice with two Vigenere keys.
However, I know the seven first characters of the decrypted text.

I have already implemented a function displaying for the five first characters the two keys that were possibly used but there are so many possibilities (265 if I am correct)...

I think the answer is no but I'd like be sure. Is there a way of finding the two keys that were used ? Can I use a statistical method even if I don't know the lengths of the keys ?

P.S.: The text is not in English but in German (not very important but for statistical methods, it obviously depends on the language of the text you analyze)

UPDATE: According to the analysis of the text, the LCM of lengths of the keys seems to be equal to 12. If the two keys have 12 characters then it is as if the author had used only one key with 12 characters right ? So if two characters are separated by 11 characters, then they have the same Caesar's shift, don't they ? And if the two keys have different lengths, does it mean that the lengths are either (4,6) or (2,12) or (3,4) ?

The key lengths are important, also if it's the Vigenère cipher is applied twice its the same as once with a different keyword. If the two keys are the same length then the new key is that length, if the two keys are different lengths then the new key is sometimes = k1 length * k2 length. If the key length is longer than the message there isn't much analysis you can do.


Why does the time complexity of RSA encryption and decryption depend on the size of the modulus? I would think that the time complexity would depend on the exponent, not the number of bits in the modulus. For example, if the exponent were 5, using the "naive" method, we would perform 5 multiplications. Squaring and multiplying would reduce the number of multiplications dependent on the exponent as well. However, I don't see where the number of bits in the modulus comes in to play.

The number of CPU cycles required to perform each multiplication increases with the size of the modulus $N$, since the operands can be as large as $N$, and also multiplication is followed by reduction modulo $N$.

Depending on what exactly you are analysing, you may sometimes consider $N$ to be constant (e.g., if you are comparing two exponentiation algorithms) and discard it when doing asymptotic complexity analysis, but if $N$ can vary, then certainly a larger $N$ means your computation will take more CPU cycles.


Is this RSA signing and verification process secure? I need to verify that messages in a communications program are from valid senders. Below is a highlevel outline of how I think the process would work. The connections themselves are done over TLS. The process here is just using RSA signing/verification on top of that. The data itself is actually not that important so the extra AES encryption is somewhat redundant. Can someone confirm whether this is the general approach or set me straight if not?

Sending host

plaintext = "Hello World!"

#SIGN
digest = SHA256(plaintext)
sig = rsa_encrypt(sender_priv_key,digest)

#ENCRYPT DATA
iv = generate iv
key = generate random key
ciphertext = aes_encrypt(iv,key,plaintext)

#ENCRYPT KEY
encryptedKey = rsa_encrypt(recipient_pub_key,key)

#SEND
send(sig+iv+encryptedKey+ciphertext)

Receiving host

#RECEIVE
sig+iv+encryptedKey+ciphertext = recv()

#DECRYPT KEY
key = rsa_decrypt(recipient_priv_key,encryptedKey)

#DECRYPT DATA
plaintext = aes_decrypt(iv,key,ciphertext)

#VERIFY
sigDigest = rsa_decrypt(sender_pub_key,sig)
msgDigest = SHA256(plaintext)

if sigDigest == msgDigest
    #valid sender so long as we can trust where we got the public key
    #data integrity is good

Comments already pointed out, that encryption and signing are not the same and should not be exchanged deliberately. Of course in practice specifically for RSA, not PKE in general, and only in the textbook variant (no padding), encrypt/decrypt are bascally the same operations as sign/verify: For all of them, you just do modular exponentiations; and the defining properties of the keys (the product of the public and private exponents equals $1$ modulo $\phi(N)$) are analogously.

But considering your algorithm, there are flaws. First, your algorithm for signing is actually this:

Hash the message
"rsa_encrypt"the hash with a private key

First, if we interpret "rsa_encrypt" just as modular exponentiation, this is still just textbook-RSA without any proper padding , which is vulnerable to certain attacks and usually the padding scheme PSS is recommended. (also see wiki)

And then you have the implicit assumption, that your function call actually is the plain modular exponentiation: If you call "rsa_encrypt" from a cryptographic library, are you actually sure that it is just the modular exponentiation? It could e.g. already have soem kind of padding in there, which might be unsuitable for signatures. Or did you implement the function yourself? Because then of course there is the old saying "don't implement crypto yourself" (and the question doesn't sound like homework), and for good reasons any proper cryptographic library will offer separate methods for signatures and encryption. In the implementation details, there are quite a lot more differences when it comes to side-channels, performance improvements, etc.

I would recommend, try to get rid of your current primitives, and use a cryptographic library instead, which gives you proper signature algorithms. Other than that, you are e.g. generating the random key for the symmetric part of the hybrid encryption. You shouldn't have to do that manually, because it is another possible weakness (you have to ensure that you're using a proper CSPRNG). But most cryptographic libraries should also have that functionality.


ElGamal in $\mathbb Z^*_p$ with $g$ not a generator of $\mathbb Z^*_p$ Let $G$ be a subgroup of $\mathbb{Z}^*_p$, $p=23$. The order of $G$ is $|G|=11$. Let $g=4$ be a generator of $G$. Consider the key generation algorithm of the ElGamal encryption scheme. Assume that the secret key is $x = 3$. Compute the corresponding public key $y$?

Apparently the solution is the following:

  For the ElGamal encryption scheme we have that the public key $y = g^x$ in $G$. Hence$$\begin{align}
y&=g^x\bmod 23\\
&=4^3\bmod23\\
&=64\bmod23\\
&=18
\end{align}$$

However this doesn't make sense to me. Indeed, the ElGamal scheme requires that the calculations be done in $\mathbb{Z}^*_p$ and not in $G$ and that we use a generator of $\mathbb{Z}^*_p$ and not a generator of $G$. So either we can write $G$ as some $\mathbb{Z}^*_q$ and then we calculate modulo that $q$ or we have to find a generator for $G$.

Am I wrong in my reasoning or is the correction of this exercise wrong?

Because in the exercise $g$ is is not a generator of $\mathbb Z^*_p$, the exercise would indeed be incorrect in a context explicitly giving a definition of ElGamal encryption that both

requires $g$ to be a generator of the group the message belongs to,
and chooses the message in $\mathbb Z^*_p$, here as an integer in range $[1,22]$.

Otherwise, the exercise and it's (now reformatted) correction are OK.

A common definition of ElGamal encryption (note: $h$ is used where the question uses $y$) has the message (representative) $m'$ in a finite cyclic group $G$ with generator $g$. In the question's examples, the message would be restricted to $G=\{1,2,3,4,6,8,9,12,13,16,18\}$. That makes the exercise fine.
Note: We do not need to rewrite that set as $\mathbb Z^*_{11}$, and cannot do this while keeping the same multiplication law as in $\mathbb Z^*_{23}$.

Another possible definition of ElGamal encryption makes no such restriction on $m'$, allows it to take any value in any finite commutative group (including $\mathbb Z^*_p$, possibly without restriction to prime $p$), and picks an element $g$ in that group that needs not be a generator of the full group (but needs to generate a large cyclic subgroup in which the discrete logarithm is hard, and other properties often associated). That still allows decryption of any message in the base group. In that definition, the question's message could be any integer in range $[1,22]$. That also makes the exercise consistent.

However, in that second definition, security suffers somewhat. When as in the question the base group is $\mathbb Z^*_p$ with $p$ prime, and $g$ generates a subgroup $G$ of prime order $(p-1)/2$, it is possible to test if the message $m'$ belongs to the subgroup $G$ generated by $g$. That's because ElGamal's ciphertext includes $c_2=m'\cdot g^z\bmod p$ for some integer $z$, therefore $m'$ belongs to $G$ if and only if $c_2$ does, and we can test that by checking if $c_2^{(p-1)/2}\bmod p\,=1$. That's a one-bit information leak about a message $m'$ picked randomly in $[1,22]$. Such information leak is against modern definitions of a cipher's security. We can:

Ignore that issue. That's reasonable in the example, since it has a much worse security issue: $p$ is small enough that finding the private key $x$ from public key $g^x\bmod p$ is easy, thus deciphering is easy. $p$ would need hundreds of decimal digits for true security.
Restrict to messages $m'$ that belong to $G$. When the order of $|G|$ is prime $(p-1)/2$ as in the example, that's easy. We can test if $m'$ belongs to $G$ by checking if $m'^{(p-1)/2}\bmod p\,=1$, and if it does not use $\tilde m'=p-m'$ (which does) instead of $m'$. We can get back to $m'$ after decryption (e.g. by requiring $m'<p/2$ which allows recognition of if decryption yielded $m'$ or $\tilde m'$).
Have the sender make $m'$ a random element of $\mathbb Z^*_p$, then hash it (which makes the leak immaterial) to obtain the key of a symmetric cipher used to encrypt the true message. That's hybrid encryption.
Have the sender choose a random $r\in\{1,\dots,|G|\}$, then compute $m'=g^r\bmod p$, which is a random member of subgroup $G$ (but we can not chose $m'$ directly representing a long message to send, thus typically that's still used with hybrid encryption).

It is common (and desirable for security to some degree, for at least the reason above) to use $g$ such that $G$ is a group of prime order. When using $\mathbb Z^*_p$ as the base group, it is typical to use a Schnorr group, perhaps with $p$ 2048-bit and $|G|$ 256-bit, both prime.


Repeatedly using same key on different plaintexts Symmetric encryption:  Does using the same key over and over again introduce a vulnerability?

Meaning, if I transmit a different piece of plaintext encrypted with the same key every day, will an attacker eventually be able to deduce the key?  (In what lengths of time?)

It depends greatly on what form and mode of encryption you use.

For any stream cipher or a block cipher used in a psuedo-stream mode such as CTR or GCM then reusing a key/IV pair even once is absolutely fatal. Never, ever use a static key with them, and if you do, never, ever reuse an IV. They are strictly for one time use keys negotiated via a key exchange algorithm for a particular session.

For modes such as CBC key reuse isn't a big issue even if you accidentally use the same IV again. Re-using the same key/IV will let an attacker determine whether two messages have a common prefix, but won't inherently leak information leading to a breach of the key or plaintext.

So, if you are using temporary keys AND trust your random number generator to be secure and strong then the advantages of CTR or stream mode are compelling especially if speed/parallelization is a concern. If either of these are not the case, such as a pre-shared key or there is no good entropy source, or you don't benefit from the stream cipher characteristics then something like CBC is the way to go.


Exercise: Attack on a Two-Round DES Cipher Working through the exercises in Cryptography Engineering (Schneier, Ferguson & Kohno) I have stalled on the following exercise:

  Consider a new block cipher, DES2, that consists only of two rounds of
  the DES block cipher. DES2 has the same block and key size as DES. For
  this question you should consider the DES F function as a black box
  that takes two inputs, a 32-bit data segment and a 48-bit round key,
  and that produces a 32-bit output.

  Suppose you have a large number of plaintext-ciphertext pairs for DES2
  under a single, unknown key. Give an algorithm for recovering the
  48-bit round key for round 1 and the 48-bit round key for round 2. Your
  algorithm should have fewer operations than an exhaustive search for
  an entire 56-bit DES key. Can your algorithm be converted into a
  distinguishing attack against DES2?

With regards to the first sub-exercise ("Give an algorithm…"), I have proceeded in the following way:

If I assume an initial input of 64 bits giving us two 32-bit blocks $L_0$ and $R_0$, I know that after the first round we have

$L_1 = R_0$
$R_1 = L_0 \oplus F(R_0, K_0)$

Then, after the second round, we have:

$L_2 = R_1 = L_0 \oplus F(R_0, K_0)$
$R_2 = L_1 \oplus F(R_1, K_1) = L_1 ⊕ F(L_0 ⊕ F(R_0, K_0), K_1)$

My thought was that I could then XOR $L_2$ with $L_0$ which is the output of $F(R_0, K_0)$ and then use $R_0$ to retrieve $K_0$. But I'm not sure how to do that… and not at all sure whether I am on the right path.

Any thoughts would be greatly appreciated.

Added

Tylo has pointed out that the $F$ function is to be treated as a black box.

Updated

I’m afraid that I have come so close but can’t seem to get any further. I can get the output of $F(R_0, K_0)$ and I know $R_0$. But I just don’t know how, since I can’t call $F$ directly I don’t know how to get the 48-bit $K_0$.

Can anyone help?

Your Formulas are alright, but there is some additional information from the exercise/setup:

The exercise states, that $F$ should be considered as a blackbox (otherwise you could use the internal stages of $F$, as poncho already suggested). However, as I understand it you can stil evaluate $F$ on any input of your choice.

At this point, you can do a couple of things. First, you're already done without knowing it. As a hint: Read the goal of the exercise and compare the complexity with a brute force on your formulas. You only need 1 ciphertext/plaintext pair.

A more complex idea: If you have a lot of ciphertext/plaintext pairs, and you just want to distinguish the permutation from a random oracle, then you can do the following: Look for two plaintexts, where $R_0$ (32 bit) is equal. What happens then to the output? And what would happen in a truly random permutation? This is a distinguishing criteria.


Prevent a Man-In-The-Middle attack whilst transmitting a PSK for first time I'm developing a network where two parties that want to join both compute ephemeral ECC keys for a key exchange, to create an encrypted connection. I plan to authenticate these keys by signing them with a pre-shared ECC key. However, how should these PSKs be transmitted in a secure way to prevent MITM attacks that change the PSKs??

There is no magic solution. Either both parties are in a direct contact to exchange a PSK, or they use authentication based on PKI. Otherwise there is no guarantee that there is no man in the middle.


How to encrypt file with RSA and AES that anyone with RSA key can decrypt them? How to encrypt a file with RSA and AES-256 that anyone with RSA key can decrypt them?.

It sounds like you're looking for a hybrid crypto solution.  Some libraries provide APIs for this, e.g. libsodium.  Others, you have to build it yourself with the RSA and AES primitives provided, e.g. OpenSSL.

Without more information from you on your environment (e.g. programming language) it's really hard to provide any specific help.


structure in modular arithmetic I was playing around with modular arithmetic when I noticed something.

\begin{align}
g^k &= a \bmod n\\
g^{k+0.5(n-1)} &= b \bmod n
\end{align}

Then $a + b = n$, so you can also write

$$g^{k+0.5(n-1)} = n - a \bmod n$$

This seems to hold if $n$ is prime and $g$ is the primitive element of $n$, according to randomly trying sets of $n$ and $g$. I have tried to see the theory behind this, but was not able to do so. None of the properties (Wikipedia: Modular arithmetic properties) of modular arithmatic seems to relate to this. Can someone explain why this holds?

If you know the Fermat's little theorem, that is, $g^{n-1} = 1 \mod n$, then you can understand what you found.

The point is that

$$b^2 = g^{2k + n-1} = g^{2k}g^{n-1} = g^{2k} = a^2 \mod n$$

Therefore, $b = a$ or $b = -a$ in $\mathbb{Z}_n$. But $b = -a$ means that $b = n-a$, since $n = 0$ modulo $n$.


How do you test the security of your cipher? I got asked this question and I didn't know what to answer.

  How do you test the security of your cipher?

What comes to my mind now would be to test it with famous attacks: padding attacks, exhaustive searches by modifying the input and expecting the output, timing attack…

Any idea?

This somewhat reminds me of “How do I test my encryption?” but that question was more specific than this one, which seems to be too broad in it’s current state.

Nevertheless, there’s an easy answer to your question:

Check and verify all the security aspects you target with your cipher.
When done, simply respect Kerckhoffs' principle and make your cipher public… that way, others can check on the security of your cipher and either confirm it’s security (which builds public trust) or they can show you what’s wrong with it.

If you need any help or have any questions while checking and verifying your cipher algorithm, please feel invited to ask more specific questions that can be answered more on-point.


Byzantine agreement implies Broadcast channel [Consesus] I am not sure if this is the right place to ask but I will give it a try. If not, let me know and I will ask somewhere else :)

We discussed the byzantine agreement and broadcast channel in class. We showed that broadcast implies byzantine agreement if $t < \frac{n}{2}$, where $t$ are dishonest parties and $n$ are the honest parties.

We designed a protocol for the byzantine agreement

All parties send input $p_i$ over broadcast channel
Parties output majority of received values

All parties receive same message $p_i$ via broadcast channel -> Majority is unique.

Now I have to show that byzantine implies broadcast. That means I have to design a broadcast protocol which uses Byzantine agreement as subroutine. At the end we have to explain why it satisfies the security properties of the broadcast channel.

I am stuck with designing the protocol. From what I understood is the byzantine agreement based on point-to-point channels. I had the idea to have it based on a PKI structure. Each sender owns the public key of the other parties, encrypts the message and sends it.

This would simulate a point-to-point channel, but on the other hand it means a lot calculation and time. Not sure if the last point is important to consider in this kind of view but I took it into consideration due to the "Termination" security property.

Would be nice if someone is able to help me.

Note that if the dealer in broadcast is corrupted, then we don't need to guarantee anything except that all honest parties agree on the output. In contrast, if the dealer is honest, then all honest parties must output the dealer's input. Now, think about what happens if the dealer is instructed to send its input first to all parties over the point-to-point channel. What can the parties do after receiving this message (note that a corrupted dealer can send different values to different parties)? How can they ensure the properties... Of course, you should use agreement. I think that this is more than enough of a hint.


When using CBC-ESSIV for disk encryption, why does the generation of IV require a hash then encryption instead of only one hash? The CBC-ESSIV algorithm specifies how to calculate the IV to use for a given key (K) and sector number (S) as the following:

$$\text{IV} = \operatorname{Enc}(\operatorname{Hash}(K) , S)$$

https://en.wikipedia.org/wiki/Disk_encryption_theory#Cipher-block_chaining_(CBC)

This is to ensure that the IV is unpredictable to an attacker.

I am wondering why not simply hash the key followed by the sector number and eliminate the extra computation required by the block encryption:

$$\text{IV} = \operatorname{Hash} (K \mathbin\| S)$$

Would not this be equally secure but more efficient?

Block cipher encryption $$\operatorname{Enc}(K,P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n$$

is a permutation where a $K \in \mathcal{K}$ select a permutation from all possible permutations of $\{0,1\}^n$. Using

$$\text{IV} = \operatorname{Enc}(\operatorname{Hash}(K) , S)$$ will guarantee that the output is unique, not repeating, since the $\operatorname{Hash}(K)$ is fixed key for the operation. This will also guarantee that the output is 128-bit as a required IV size for CBC.

If you use

$$\text{IV} = \operatorname{Hash} (K \mathbin\| S)$$ then due to the collision property - birthday attack - of the hash functions some sector can have the same IV that is not wanted. One has to trim the output of the hash function to 128-bit so for a $2^{64}$ sector numbers we expect an IV collision with 50% probability. This probability is not negligible and one must stop way earlier.

For a 3TB disk, there are 5,859,375,000 sectors which make around 33 bits. The probability of collision is quite low for this, like $$1-e^{-\big(\frac{{(2^{33})}^2}{2\cdot 2^{128}} \big)} \approx 1.08\cdot 10^{-19}$$

by using the approximation formula for the Birthday attack

$$p(n;H) \approx 1 - e^{-n(n-1)/(2H)} \approx 1-e^{-n^2/(2H)}$$

But never zero!.

Conclusion: the first guarantees that there is no collision and therefore the first approach is preferable to the second approach.


Automated testing of cipher security for import/export compliance What do we know about systems that automatically test and grade cipher security. The application in mind would be for checking for compliance with import/export regulations.

I imagine a system that automatically tests for known plaintext, chosen plaintext and the like, presumably by some kind of cryptanalysis operating on the cipher as a black box function, or subroutines of it.

The OpenSSL export ciphers are "exportable with respect to old US crypto regulations". I want to consider other countries import/export policies.

This question supposes that import and export compliance is still a real concern in the industry, despite many articles claiming otherwise.

No.  There is no known automated method to determine whether some cipher is secure or not.  So, given some new cipher you've never heard of there's no automated way to test whether it meets your particular security requirements.

Instead, normally you would rely upon a cryptographer expert (e.g., a consultant or in-house expert) or upon standards or best practices to select a cipher that is widely believed to meet your security requirements -- then you implement the cipher, and use test vectors and other methods to test whether you have correctly implemented that cipher.  For instance, you might use one of the export-strength ciphersuites in SSL.

This answer is not intended to advise you on the export regulations of any country.  If you need to know what they are, consult a lawyer.


Is it safe to encrypt a part of the message with RSA and the rest with AES? The structure can be the following:

A signature (on the sha-256 of everything else).
RSA-encrypted random AES key (or none) and as much data as it fits into an RSA block.
AES-encrypted blocks with the rest of the data (or none at all).

The point is that an RSA block can hold a lot. Seems like a waste of space.

Is it worse than this?:

A signature (on the sha-256 of everything else)
RSA-encrypted random AES key
AES-encrypted blocks with the data

You can put in as much data into RSA as it can hold, bar the padding. The padding is required to keep RSA (provably) secure - presuming that RSA is secure itself of course.

So yes, what you are supposing is perfectly possible. It actually has a name: encryption with partial message recovery.

I found one paper that claimed that the security is may not be be provable secure, so beware that you're threading on largely uncovered ground here; there aren't any standardized schemes out there.

It may not be optimal to use current padding techniques as you would about double the randomness in the encryption scheme: once for the secure padding itself and once for the AES key. On the other hand, this is the best you can do with standardized functions libraries.

That said, the overhead of RSA-OAEP is only about 42 bytes, so for a 2048 bit RSA key and a 128 bit AES key (about the minimum key size) there would only be a static overhead of 42 + 16 = 58 bytes, leaving 256 - 58 = 198 bytes for the message itself.

If you require protection against active attacks that may alter the ciphertext you may need to include an authentication tag over the rest of the message, adding another 8 to 16 bytes for e.g. AES-GCM.

I'd propose a scheme such as this:

R = M | RSA-PSS-SHA256(Sk, M)
K = Rand(k)
r1 = s / 8 - 42 - k / 8
R1 = Sub(R, 0, r1)
R2 = Sub(R, r1)
C = RSA-OAEP(Pk, K | R1) | AES-GCM(K, R2)

Where:

M is the message
R is the signed message (using the sender's private key)
K is an AES key of length k bits
Rand is a cryptographically secure random number generator (or key generator operating in bits)
s is the receivers key length in bits
o is the OAEP overhead in bytes (using SHA-1 for the underlying MGF1)
r1 is the size of R1, r2 is the size of R2
R1 is the partial message encrypted using RSA-OAEP
R2 is the partial message encrypted using AES-GCM
Sub takes a substring of the given array and offset, and optional end offset
C is the resulting ciphertext, including the AES-GCM tag

The IV for AES-GCM can be left at 12 zero bytes (as the AES key gets regenerated each time anyway).

Notes:

if you use normal PKCS#1 signing that you leak information about the message that you encrypt. So you should use PSS padding or you should encrypt the signature as well. Above scheme uses a combination of both;
while you're at it you might want to look for RSA-PSS-R, which is a scheme for signatures giving message recovery, defined here and in IEEE P1363a;
to show a more efficient scheme, try this if you're academically inclined - it also includes a proof of security;
it is also possible to use RSA-PKCS#1 and AES-CBCbut beware that those are not IND_CCA secure and that you should not allow padding oracle attacks.


What is the exact meaning of revocationWarning and revocationNotification in RFC 3161? The RFC 3161 (Internet X.509 Public Key Infrastructure Time-Stamp Protocol) specifies that a time-stamping response has a PKIStatusInfo and, optionally, a timeStampToken. In turn, the PKIStatusInfo contains a PKIStatus, which is an integer in [0, 5]. For the values 4 and 5, the following descriptions are provided:

  revocationWarning      (4),
  -- this message contains a warning that a revocation is imminent

  revocationNotification (5)
  -- notification that a revocation has occurred

Both descriptions refer to "a revocation". What is this revocation referring to?

My guess is that it refers to the revocation of the TSA certificate... Is this correct? May any other revocation cause this response?

According to a discussion on the PKIX mailing list, it means the TSU (Time Stamping unit) certificate which signs the time stamp responses.


Encrypted text length in AES I have created an application that will be able to read any file and encrypt it using AES Encryption. For efficiency, I am reading a block of data, encrypting it and so on. So for decrypting, I just have to read each block and decrypt using the same key to get the data back. This was what I had in mind.

But it turns out that the size of each encrypted block varies, so I am currently saving the encrypted block size before each block into my encrypted file.

And my question is: Is it normal that AES produces encrypted blocks of varying lengths or am I overlooking something?

(I'm using a padding, as my input block size is not always a multiple of the AES block size.)

I faced the same issue when I had used C++ a few years back, and now as3crypto library for an AIR application while implementing the same application.

Plain AES is a block cipher, which can only encrypt 128-bit blocks (i.e. 16 bytes at once).

To encrypt longer pieces of data, one would normally create a stream cipher from the block cipher, by using one of several modes of operation. The simplest (and most insecure) one is the electronic code book mode (ECB), which (for the same key) always produces the same ciphertext for the same plaintext block. Normally one thus would use one of the other modes (like CBC, CTR, ...), each having different advantages.

If you need only sequential access to the whole file, any of these modes will do, as you can always decrypt the file sequentially.

If you need some kind of random access to specific parts of the file, you would break it down into parts which each could be accessed individually. Each of them would then be encrypted as essentially a separate stream, i.e. starting with the initialization vector, and including (if necessary) the padding to fill the last 128-block.

You would also want an index to the parts, so you know which part to access.

Alternatively, you could use CTR mode, which essentially allows random access to the file, only knowing the nonce and the block index, without the need to read or decrypt the blocks before or after the desired block.


Decrypting an Affine Cipher with known characters I am trying to cryptanalyse multiple cipher–texts that I know are encrypted by different Affine ciphers. I have already analysed the frequency that each character occurs, and compared it to a frequency table of the languages the plain-texts could be in and as a result have a pretty decent idea of what a few characters could correspond to. For example I know in one cipher-text:

  X = e, S = t, V = s

Converting those into their numerical correspondences yields

  23 = 4, 18 = 19, 21 = 18

I have therefore deduced that:

$4a+b=23 \pmod{26}$

$19a+b=18 \pmod{26}$

$18a+b=21 \pmod{26}$

I figure I could probably calculate the values of a and b by manually trying every iteration of a (which wouldn't be terrible since I can rule out all even values) and hoping once they all match with the same b it works for all characters, but I was just wondering if there was a faster/more reliable way of doing it Mathematically. Is there some way I can solve for $a$ and $b$ that I am unaware of?

You have 3 equations and 2 unknowns, so it is solvable, assuming a solution exists. You can plug this into any linear equation solver.

If you subtract equation 3 from equation 2, you get $a=-3$, and can solve for $b=75$. This fits equation 2 and 3, but not equation 1. So, no solution exists.


Can a TLS client perform any DH regeneration? I have only the barest understanding of cryptography, but I've been following the Logjam issue; some posts and articles (elsewhere) imply that a client can regenerate DH keys. Is Logjam solely a server issue? Is there a way for the client to perform DH regeneration on a regular basis; if so, how? Is there any way the client can circumvent the Diffie-Hellman Logjam issue?

A client can indeed "regenerate" DH-keys.
But this simply means he re-connects to the server. The Logjam attack works by recording the connection establishment and then compute the derived private key. For this attack to work the domain parameters of the DH-exchange need to remain unchanged as precomputation is neccessary. If you just reconnect the server will present you with the exact same group and the attack will only take seconds to decrypt the session key. For Logjam to be defeated one needs new domain parameters, which take a while to be generated, hence this isn't done on every connection, usually this isn't even done in years.

Logjam isn't solely a server issue. If the vulnerability is fixed on either the browser (how-to: next paragraph) or server-side it's closed. Both sides need to support it and all major browser companies (Mozilla, Google,...) already announced patches to close this vulnerability.

The client can circumvent the issue by requiring 2048-bit+ primes for the domain parameters of DH, if the client decides to use DH-exchange.
The best way to avoid Logjam is to avoid DH, by choosing ECDH, which isn't vulnerable.This is also the way recommend by the authors of the accomplying paper.


Is Bruce Schneier Applied Cryptography, Second ed. up to date? I like Applied Cryptography, and I am returning to cryptography after a while. So I am wondering if that book is up to date or can be complemented with other references.
I am looking for a book, authoritative, well documented. Possibly including code.
I would prefer to have a book as a reference, instead of asking naive questions to the community for something I could find in a book like Schneier’s. I wish to ask the community for help to understanding what’s in the book or ask for help on specific real world problems.
I have a background in cryptography, number theory, data, and coding.

The Applied Cryptography Second Edition goes back to 1996.  Although there is a 20th-anniversary edition, 2015, it is not updated as one thought. If you look for Schneier's style, you may look at the

Cryptography Engineering: Design Principles and Practical Applications, 2010

There is also another nice practical book by Jean-Philippe Aumasson

Serious Cryptography: A Practical Introduction to Modern Encryption, 2017

And, another one by David Wong as pointed by SAI Peregrinus

Real-World Cryptography, 2019

All three books are good for one to understand the cryptographic techniques at work in common tools, frameworks, and protocols. This will help to make excellent security choices for systems and applications. They are especially good for engineers and IT.


Can you explain what an NP statement is when they refer to it in Zero knowledge proofs? When I read about zero knowledge proof, I keep encountering the term NP-statement. I am aware of complexity classes but I am a little unclear on how it ties up to NP-statement.

I came across the following here: C++ library for zkSNARKs

A computation can be expressed as an NP statement, in forms such as the following:

"The C program foo, when executed, returns exit code 0 if given the
input bar and some additional input qux."
"The Boolean circuit foo is satisfiable by some input qux."
"The arithmetic circuit foo accepts the partial assignment bar, when
extended into some full assignment qux."
"The set of constraints foo is satisfiable by the partial assignment
bar, when extended into some full assignment qux."

A prover who knows the witness for the NP statement (i.e., a satisfying input/assignment) can produce a short proof attesting to the truth of the NP statement.

Can any body show how an NP problem can be described in the form of an NP statement with an example?

Intuitively, an NP problem is one
 that if you have a solution it is computationally easy to verify it, but it is not known if it is also computationally easy to find. Of course there exist formal definitions, based on deterministic and non deterministic Turing machines. Any standard complexity textbook will have these definitions.

Their connection with zero knowledge proofs comes from the 1987, Goldreich, Micali and Wigderson paper that proves that all NP problems have zero knowledge proofs (assuming secure bit commitment).
An excellent tutorial on how this is done can be found in Matthew Green's blog.
All this were written for classical zero knowledge systems, but they apply to zkSnarks as well.


How can a recipient recognize which encrypted messages are intended for them? Let's say there's a decentralized email service where parties' public keys are known. A sender sends a message to a recipient by encrypting via RSA with the recipient's public key and posting the ciphertext publicly somewhere where everybody can see, e.g. a public blockchain.
Senders don't want others to know which addressees they're communicating with, so they only publish the ciphertext. Then everyone needs to scan the blockchain for new events and try to decrypt each message with their private key (in the RSA-AES hybrid scheme, they will try to decrypt a one-time AES key the message is encrypted with). If they succeed (and let's say the prefix of the recovered message is their public key per protocol), it means the message is intended for them.
The above scheme requires every participant apply RSA decryption to every message, and the number of messages per time unit are expected to increase. Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?
One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages. This way, each revealed bit splits the number of potential recipients in half (starting from everybody when 0 bits are revealed and halved with each bit), while still not allowing outside observers to determine the exact recipient, but it does allow everyone else to save computing cycles skipping exponentially larger amount of messages.
However, I'm interested to know whether there are even better approaches.

Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?

It doesn't appear that the problem of recognizing the message (without leaking who the message is for) can be significantly faster than public key decryption.  Let me be more precise; suppose we had a way such that:

Alice can publish some public information
Bob can use this information to generate a 'tag'
Alice can check to see if this tag was generated with her public information
No one without Alice's private information can do so (if not, anyone can check if the tag was flagged to be of interest to Alice).

If we have a primitive that can do that, then Alice can use that primitive as a public key encryption method; the method isn't very efficient (in the simplest case, Bob would generate a series of 'tags', where each tag encodes a bit - one bits are tagged with Alice's information, and zero bits are not); however it is sufficient to indicate that the problem isn't inherently easier than the general public key encryption problem.
So, what can we do?  Well, the best I can suggest is use a public key encryption method that's more efficient than RSA; here are two ideas:

ECIES; here, the decryption operation is a point multiplication (and a handful of symmetric operations); significantly cheaper than RSA

NTRU; this is a NIST postquantum level 3 candidate with (to use a technical term) honkin' fast decryption; for example, the ntruhps2048677 parameter set is listed as using only 59,729 Haswell cycles.

Of course, you could also separately RSA encrypt the message along with the tag; however, given that by validating the tag, you've essentially done most of the work, you might want to just use ECIES or NTRU.
Also, one comment on your idea:

One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages

Does that mean that, in the ciphertext, you expose k bits of the public key, where k gradually increases as the number of messages increases?  Well, one problem with that is, while an eavesdropper can't generally be certain who the message is for, he can be pretty sure who it is not for - that many be just as bad...


"Work factor" and "iteration count" nomenclature in adaptive functions In adaptive functions like PBKDF2 / bcrypt I often read people refer to "iteration count" and others refer to "work factor", and they seem to be used interchangeably (even though they're not - the latter is used to calculate the former).

I also see this (commodity hardware circa 2019):

iteration count: e.g. 100,000
work factor: e.g. 16 or 17, i.e. 2^16..2^17 (65536..131072)

I like the idea of work factor as it's simpler to reason with when coding, e.g. I can "increase the work factor" every year, which means go from 16 to 17, etc. So it's a base-2 "order of magnitude".

However, what is the "correct" nomenclature?

There is no international committee on which function / term is correct or not.

Work factor seems to be a more generic term, and I'd prefer that when talking about the relative amount of work that needs to be performed. That - at least internally - an iteration count is used together with a hash algorithm is an implementation detail.

The work factor doesn't really have a generic value in itself.  So any password hash / KBKDF that performs key stretching must have a work factor. But how this work factor reflects the amount of work is algorithm specific. It could be using a logarithmic scale and for many algorithms this is the case. However, the iteration count - which is linear - is also a work factor - even if the specific algorithm specification doesn't explicitly use that name for it.

In the end, the best way to compare the time required (CPU time or user time) is to test the values. You can make a pretty good bet if you know the internal details, but in the end small changes - for instance the specific implementation - may make a lot of difference.


PKCS#7 Signed Data contains always different signature I am wondering why CMS (PKCS#7) Signed Data contains always a different signature of the original data when the SHA256withRSA signature algorithm is used. (using Bouncy Castle by the way)
The SHA256withRSA is using the SHA-256 as a message digest algorithm and EMSA-PKCS1-v1_5 for encoding the message digest before signature generation operation with the RSA private key.
As these algorithms are deterministic, I would expect that each time I would create a CMS Signed Data the signature of the data will be the same. However, it is not. I can verify it with the opposite process. I will decrypt the signature using the RSA public key, decode EMSA-PKCS1-v1_5 and the resulting hash is different than hash of the original message.
Someone able to explain me how it works, why the signature is always different?
This is what should be equal from my point of view:
Message1 -> generate CMSSignedData(private key)
Generated CMSSignedData -> get signature -> decrypt(signature) -> decode -> MD2

SHA256(Message1) = MD1

MD1 != MD2 <---- I would expect that this will be equal !!!

That's likely because the data used for the signature generation actually changes between the signing. That would e.g. be the case if that data contains the signing time. Note that within CMS the data is not directly signed; it is first hashed, put in a structure and then that's what is getting signed.
Also note that inclusion of the local time generated by the system is not the same thing as using a time stamping service.


Ed25519 signature verification as described in RFC 8032 In RFC 8032, section 5.1.7, it is prescribed that an Ed25519 signature is verified if

$[8][S]B = [8]R + [8][k]A'.$

The text then says

It's sufficient, but not required, to instead check $[S]B = R + [k]A'.$

What is the point of the first criterion, if the second one also works and is arguably simpler and less computationally expensive, in general?

If you look at the key generation

Prune the buffer: The lowest three bits of the first octet are
cleared, the highest bit of the last octet is cleared, and the
second highest bit of the last octet is set.

This used to make sure that the key is not in the small groups, those have order 2,4, and 8.
If you use

$[8][S]B = [8]R + [8][k]A'$.

then if the public key is in a small order, sides will get the identity $\mathcal{O} = [8][S]B$ and you can detect with this. This is key validation.
But, it is not your problem right? Maybe the other side chooses the key deliberately instead of using the recommendation. Then just use $[S]B = R + [k]A'$. but not required. Better check it.


Is it necessary to use Fermat's Little Theorem to prove the 'correctness' of the RSA Encryption method? Given a 'message' $M$, a proof of the 'correctness' of RSA encryption means to show that $(M^e)^d \equiv M \pmod{n}$, where $n=pq$ is a product of primes, and $ed \equiv 1 \pmod{\phi(n)}$, where $\phi$ is Euler's totient function, so that $\phi(n)=(p-1)(q-1)$.
Most sources attribute the correctness of RSA encryption to Euler's theorem (a generalisation of Fermat's little theorem), however the end of the intro of the Wikipedia page claims this is erroneous, since it doesn't apply in the case when $\gcd(M,n) \neq 1$, and that actually it is sufficient and necessary to use the "uniqueness provision of the Chinese Remainder Theorem". However, in every proof I can find on the web and on this site, Fermat's little theorem is used as well as CRT.
So, my question is, is it necessary to use FLT? And is it necessary to use CRT?
If so, is there a proof of this, i.e. that FLT / CRT $\Leftarrow (M^e)^d \equiv M \pmod{n}$ ?

The proposition following «show that» in the question's first paragraph requires $p\ne q$ to become true. Problems are that when $p=q$, the expression $\phi(n)=(p-1)(q-1)$ no longer holds, and even fixing it to $\phi(n)=(p-1)\,p$ does not make the proposition true for quite all $M$ and $e$, when $p\ne2$. For example the proposition fails for $p=q=M=3$, $n=9$, $e=d=5$, for both the correct $\phi(n)=6$ and the incorrect $\phi(n)=4$.

This proof of that propostion does without the full Chinese Remainder Theorem. Rather, following a suggestion in comment, it uses the more basic fact that if $p$ and $q$ both divide $Z$ and are coprime (including: are distinct primes), then $p\,q$ divides $Z$.
In a nutshell, this is applied to the quantity $Z\underset{\text{def}}=(M^e)^d-M$, leading to the desired conclusion. To show that $p$ divide that $Z$, we distinguish the easy case $M\equiv0\pmod p$, from the other where that follows from $e\,d \equiv 1 \pmod{\phi(n)}$ rewritten as $\exists k,\ e\,d=k\,(p-1)(q-1)+1$, and Fermat's Little Theorem. We could further integrate one of the proofs of the FLT in the demonstration.

In conclusion, we can rigorously prove that RSA works without explicitly using either the FLT or CRT, by using or proving slightly less general statements along the way. I see no reason to thus circumvent the use of FLT, because it is so useful. For CRT, that makes sense.
From a pedagogical perspective, if the audience can't stand the FLT, it's not ready for a proof anyway, and we can as well proceed by affirmation and example. At least, let's try to affirm only true propositions.

A former version of the question used slightly incorrect notation. It is best as it stands now, with $(M^e)^d \equiv M \pmod{n}$ and $e\,d \equiv 1 \pmod{\phi(n)}$. The opening parenthesis immediately on the left of $\bmod$ is to denote modular equivalence, rather than an operator with restriction of the output range to non-negative integers less than the modulus. That notation is obtained with \pmod in $\LaTeX$. Alternatively, we could write $(M^e)^d\bmod{n}=M$ if we add $0\le M<n$. And we could write $d = e^{-1}\bmod{\phi(n)}$.


Is appending the hash of the plaintext to the end of an encrypted message sufficient to ensure integrity? Is appending the hash of the plaintext to the end of an encrypted message sufficient to ensure integrity?

My reasoning is that the attacker doesn't know all the plaintext, so by having a hash, the attacker will be able to change the message, but will be unable to recalculate the hash.

Are there any flaws in my reasoning, besides the case where the attack knows the whole plaintext?

To be clear, this is $\text{E}(\text{data})|\text{H}(data)$, it is not $\text{E}(\text{data}|\text{H}(data))$

Is appending the hash of the plaintext to the end of an encrypted message sufficient to ensure integrity?

Not in the sense of authentication. Such a construction is malleable for many reasonable encryption algorithms. It also leaks the plaintext to anyone who can guess it, since they can calculate $h(P_i)$ for guesses (brute force or dictionary attack) and compare to the hash value.

As for malleability, if the cipher is a stream cipher and the attacker can guess that the message is $A$, then they can turn it to an equally long message $A'$ by calculating a new ciphertext $C' = C \oplus A \oplus A'$ and replacing the old hash with $h(A')$.

CTR, OFB etc. modes are essentially stream ciphers so the above applies. Similar attacks, perhaps more limited, are possible against some other block cipher modes as well. For example, with CBC the attacker can replace the last message block with some earlier block to make a deterministic change to the message (xor by a xor of certain ciphertext blocks). They can then calculate the new hash and replace.

Even if you encrypted the hash, to avoid guessing, it might still not be a secure MAC. Further, if is was, you would be using encrypt-and-MAC since the hash is over the plaintext. Encrypt-then-MAC has some advantages over it.

If this a real world scenario, consider instead appending an HMAC of the ciphertext or using an authenticated encryption mode.


Is .NET DESCryptoServiceProvider secure in this case? I have the following piece of .NET code (see below). I know that DES is not quite secure, I saw that MSDN does not recommend using DES, only for compatibility with legacy programs. I also saw that some people say that IV has to be regenerated every time new message is encrypted.

Q: How secure is the code? Assuming attacker has several hundred messages and corresponding ciphers (and can get more), how easy to break this and find key/IV?. How could it be done? But most importantly, how it could be made secure? Will change to AES help?
I'm a beginner and any help or references are very appreciated.

internal static class Encryptor
{
  private static readonly byte[] Key = { *** };
  private static readonly byte[] Iv = { *** };

  internal static String Encrypt(string source)
  {
    var des = new DESCryptoServiceProvider();
    var enc = des.CreateEncryptor(Key, Iv);
    var b = Encoding.ASCII.GetBytes(source);
    var encId = enc.TransformFinalBlock(b, 0, b.Length);
    return Convert.ToBase64String(encId);
  }

  internal static string Decrypt(string encrypted)
  {
    var des = new DESCryptoServiceProvider();
    var dec = des.CreateDecryptor(Key, Iv);
    var b = Convert.FromBase64String(encrypted);
    var decId = dec.TransformFinalBlock(b, 0, b.Length);
    return Encoding.ASCII.GetString(decId);
  }
}

The key space for DES is far too small (56 bits). Therefore, any use of DES is not secure. It doesn't matter what mode you use. If the attacker has one plaintext, ciphertext pair, they can brute force the key space and recover the key in a feasible amount of time (24 hours using the cloud).

  But most importantly, how it could be made secure? Will change to AES help?

Moving to AES will definitely help. What will help the most is first, defining the desired protection model (i.e., what does "secure" mean in your context?). Do you only care about confidentiality? Do you also care about integrity? How about authenticity? Deciding this will help you decide which mode to use. In particular, do you need a MAC or authenticated encryption mode?

Once you have this figured out, choose the cipher and mode to match your needs, not just security needs, but also performance needs.


Secret key agreement by public discussion from common information There is a paper: U. M. Maurer, Secret key agreement by public discussion from common information, IEEE Trans. Inf. Theory, 39(3) 733-742 of 1993, with an IMHO fairly impressive title but having apparently for some unknown reasons been hithertofore ignored in the common textbooks on modern cryptography. The material there is way above my humble knowledge, hence my request: Could some experts kindly give a sketch of the main idea of the paper such that one could get at least a certain rough comprehension of it? Are there good open-source implementations of that key agreement scheme?

Maurer is likely making unrealistic assumptions about noise. The following excerpt is from the paper's conclusion:

  The paper suggests the following conclusion for the implementation
  of cryptographic systems on given noisy communication
  channels. Such channels should not be converted
  into error-free channels by means of error-correcting codes,
  followed by a cryptographic protocol based on error-free channels
  because this design strategy would imply that Shannon's
  pessimistic inequality (2) applies and therefore perfect secrecy
  cannot be achieved unless an impractically large amount of
  shared secret key is available. Instead, cryptographic coding
  and error-control coding should be combined, resulting in a
  system achieving virtually perfect secrecy, with a (short) secret
  key being required only for authentication.

  The author hopes that this paper and a subsequent paper on
  practical implementations will help to move perfect secrecy
  closer to being practical.

I'm not an expert either, but have an interest in new and unconventional cryptography. With research papers I find it helpful as a first pass to read the abstract and conclusion. Whatever claims made in the conclusion can then be referenced by going back in the paper. In this paper, the reliance on noise and error coding seemed both its strength and weakness.

What happens if an attacker can manipulate the noise/signal of the system? If they were able to reduce the noise of a channel, wouldn't an attacker be able to derive too much information about the cryptography from the coding? Here's a hypothetical attack: attacker Eve deliberately injects noise into a system, making system seem much noisier than it actually is, which the two communicating parties Alice and Bob then derive their probabilistic models from, but when Alice and Bob start exchanging data, Eve removes the noise.

By comparison Diffie-Hellman is a simpler overall scheme that makes no assumption about the underlying communications channel.


Relation between "P is not equal to NP" and "Existence of One-Way Function" We know that If there exists a one-way function, then P ≠ NP. Why can we not conclude that if P ≠ NP, then there exists a one-way function? Is there a  polynomial time computable function that is hard to invert in the worst case and isn't one-way?

Why can we not conclude that if P ≠ NP, then there exists a one-way function?

Because so far no one has been able to prove this statement, see here.

The statement "if one-way functions exist, then $P \neq NP$" is an implication, which just goes one way. If we build the contrapositive, we get "if $P = NP$, then one-way functions don't exist".

On the list of logical fallacies, we can find:

Affirming the consequent, which is basically just building the converse (turning around the direction of the implication).
Denying the antecedent, which just is an inverse of both sides of the implication.

Those are (more or less) common errors regarding logic, and only the contrapositive does not change the actual meaning of the statement. Both inversion and conversion alone do not preserve the meaning - and thus are invalid if you want to prove a statement.

  Is there a polynomial time computable function that is hard to invert in the worst case and isn't one-way

Any NP-complete search problem gives you a candidate for that. That is exactly the difference between search problems in the class NP and one-way functions: The former are defined with regard to the worst-case and the later are defined for the average-case. This is also why NP-complete problems are less interesting in cryptography, where it can be not enough if only the worst-case of a problem is hard.


Generalize the Merkle–Damgård construction for any compression function I am trying to figure out this question:

  Generalize the Merkle–Damgård  construction for any compression function that compresses by at least one bit . You should refer to a general
  input length £' and general output length E (with £' > E).

It is in my understanding that the Merkle–Damgård  takes an input of 2*l(n) and compresses it to l(n). How would I go about breaking up the input so that an arbitrary hash length L' can be outputted?

You understanding is a bit incorrect. There is no requirement that the output length of the compression function is exactly half of that of the input. Typical compression functions have an output which is much shorter than half the input length.

The Merkle-Damgård construction uses a compression function which takes an input with a length that is the sum of the internal state and one block and an output which is the length of the internal state.

If the size of input and output of the compression function differs by only a single bit, that would lead to a block size of just one bit.

A block size of just one bit would work most of the way. But it would fail in the final block which needs enough room for length padding. You couldn't do length padding in a single bit.

But you could create a new compression function by combining multiple invocations of the original compression function. For example if your original compression function compresses $k+1$ bit to $k$ bits, you could invoke it $k$ times in order to compress $2k$ bits to $k$ bits. Then you could build a Merkle-Damgård construction by using this new compression function.

A different but equivalent formulation would be that you ignore the requirement that the entire length padding fit in a single block in the Merkle-Damgård construction and compensate for any weaknesses that could be introduced from that by still padding to multiples of a block size, which would be large enough to hold the length field.

This construction assumes the compression function is collision resistant, which implies that the output is long enough. If the output was too short a collision could be found by brute force.


Is a function defined as PRF with a given key a PRG? Let $G(s)=F_{0^n}(s)$ ($ 0^n $ is a fixed key given to the PRF F) for any $n∈\mathbb{N}$ and $s∈\{0,1\}^n$.

Is G, defined via PRF as above, necessarily a pseudorandom generator?

I presume that it is a PRG, since we don't really know what is the seed s. But the fact that $ F_{0^n}() $ is known, makes me doubt myself.

I don't seek for a proof, just an intuition or a hint (i do understand how to prove such claims, i just don't get the "catch" in this specific case).

Consider a PRF $F$ which on $n$-bit keys maps $n$-bit inputs to $2n$-bit outputs. Consider $F'$ where $F'_k(x) = F_k(x)$ if $k \ne 0^n$ and $0^{2n}$ otherwise.


If DDH is hard then CCA-secure PKES exist? My cryptography slides describe several relations between cryptographic problems. I don't still have a good justification on the following:

  If decisional Diffie-Hellman problem is hard then there exists a CCA-secure public key encryption scheme.

How is this justified?

The answer is

  Because Cramer-Shoup encryption exists.

The construction of Cramer-Shoup is essentially a modification of ElGamal encryption with an added checksum, that allows to detect tampering of ciphertexts.

The construction assumes a cyclic group $\mathbb{G}$ of order $q$ with two generators $g_1,g_2$ in which the DDH problem is hard, as well as a collision resistant hash function $H : \mathbb{G}^3 \to \mathbb{Z}_q$.

Collision resistant hash functions can be constructed based on the discrete logarithm assumption (See, e.g., Section 121 in these lecture notes by Rafael Pass. There's a bit more work involved in encoding inputs and outputs to match the required domain and range, but it's possible to do.) Since the discrete logarithm problem is hard if the DDH problem is hard, it thus follows that if DDH is hard, then CCA secure PKE exists.


Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant? I'm trying to solve the following problem:

Given two CRHF $H_1:2^{4n}\to2^{2n}$, $H_2:2^{2n}\to 2^n$, construct the following hash function $H^{*}=H_2(H_1(x))$ compressing from $2^{4n}\to 2^n$.
We want to demonstrate that if $H_1$ and $H_2$ are collision resistant then $H^*$ must be collision resistant too.

I made the following reduction

However I'm still unsure on how to calculate ”BAD event” in which $A^{H^∗}$ outputs a collision for $H_{s_1}$, in this case $x^∗=x′$ and the second part of the reduction doesn’t work.

Assume that, $H_1 \text{ and } H_2$ are collision resistant and $H^*$ is not. We will show that one of the $H_1 \text{ and } H_2$ can not be a collision resistant.

Let $x_1 \neq x_2$ be inputs such that $$H^*(x_1) = H^*(x_2).$$ $$H_2(H_1(x_1)) = H_2(H_1(x_2)).$$i.e we have a collision pair.

Now, if $H_1$ is collision resistant then $$y_1 = H_1(x_1) \neq H_1(x_2) = y_2 .$$

Note : The equality holds only with negligible probability, then $H_2(H_1(x_1)) = H_2(H_1(x_2))$ is a collision with a negligible probability.

Now, $H_2(y_1) = H_2(y_2)$ since $H^*$ is not collision resistant. But we found a collision for $H_2$ given a collision for $H^*$. This is a contradiction since $H_2$ is collision resistant therefore this implies that $H^*$ is collision resistant, too.