Does knowledge of SHA256(secret ∥ known constant) in addition to SHA256(secret) give any information about the secret? Does knowledge of SHA256(secret) and SHA256(secret ∥ known constant) give any more information about the secret than just knowledge of SHA256(secret)?

In the first case; the attacker has this knowledge

$\operatorname{SHA256}$
$x = \operatorname{SHA256}(\text{secret})$

While brute-forcing this hash value $x$, there is one problem. One cannot determine whether this is the pre-image or it is a second pre-image. For password cracking, that is not really important since you find a valid password for the target. For your case, assuming the secret has to be determined exactly, there is no way for the attacker. Actually, finding more than one break the collision property of SHA256, see in Fgrieu's answer. Therefore, it is hard to find more than one.

In the second case; the attacker has

$\operatorname{SHA256}$
$x = \operatorname{SHA256}(\text{secret})$
$\text{the known constant}$
$y = \operatorname{SHA256}(\text{secret}\mathbin\|\text{the known constant})$

This additional knowledge gives the attacker extra information that can be exploited. While brute-forcing to find the secret, this time the attacker has a new mechanism to distinguish the second pre-images from the secret. Given a secret candidate $candidate_s$ check;

$$ y = \operatorname{SHA256}(candidate_s\mathbin\|\text{the known constant})$$

Apart from the pre-image, the probability of this equality is negligible since
 we expect that SHA-256 has collision resistance.

As a result, this gives extra information about the secret that can be exploited.

Side note: if the entropy of the $secret$ is larger than 128-bit, it is not possible to execute brute-force on-the secret.


Why is recipient hashed in this Sign/Encrypt/Sign proposal? Own research

In my journey into trying to understand PGP, and public key signing and encryption as a whole, I came across this answer on CE. It is an answer to a question with the title: Should we sign-then-encrypt, or encrypt-then-sign? Although this satisfies my original quest, it has an interesting link to an article called: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.. The article as a whole explains why "naive sign & encrypt" systems are not as secure as most people think. Also, it proposes some solutions to the issue.

Question

A proposal which caught my attention from section 5.2 Sign/Encrypt/Sign of the article.

  Surprisingly, we can get an effective repair for S&E, if Alice signs
  and encrypts the plaintext, and then she signs the ciphertext, too:

A ---> B   :   {{{msg}a}B , #B}a

  (Here, #B means Alice hashes Bob's key, not his name.)

  This message means:

  Inner Signature: "Alice wrote the plaintext;"
  Encryption: "Only Bob can see the plaintext;"
  Outer Signature: "Alice used key B to encrypt."

  [...]

Is there any cryptographic / security reason why Alice would Hash Bob's public key? If I would implement something like:

A ---> B     :   {{{msg}a}B , B}a

(B is Bob's public key, not hashed)

Would I still benefit from the security offered by this fix?

Background

I'm in the research phase of developing a messaging platform based on public-key encryption. My first intention was to use the OpenPGP standard. However, this standard alone would make it impossible to identify the sender until the message is decrypted. I want to offer end-to-end encryption, but at the same time, offering my servers to verify the sender is a registered user.

Off course, this could (and will) be done by client - server authentication. But even in such a case, using openPGP and authentication alone, a client can still misbehave:

  PGP's strongest security option is naïve Sign & Encrypt, so PGP is
  vulnerable to surreptitious forwarding:

A ---> B   :   {{ "The deal is off." } a}B
B ---> C   :   {{ "The deal is off." } a}C

The server wouldn't know that Bob is illegally forwarding Alice's massage and gladly forward the message to Charlie on Alice's behalf.

I know that most of this can be prevented on the application level. Like e-mail is doing with authenticated SMTP and fields like From: and To. But as an experiment, why not fix these issues directly in the cryptography protocol? I think, the server reading the intended receiver's public key would be a nice solution.

I don't fully understand the notation in that link you posted, but as far as hashing the public key instead of signing it directly, some public keys are pretty long, making signing expensive. Public keys for RSA can be 4096 bits, which is too long for most signing schemes. Hashing the public key allows it to be signed more efficiently without losing security.


Diffie-Hellman Secret Exponent Size and Shared Secret Usage I'm developing my own protocol and I'll use Diffie-Hellman to achieve PFS. It will work in this way:

The symmetric encryption algorithm will be AES_256_CBC.

The DH parameters will be:
P: a 2048-bit safe prime as defined in RFC 3526.
Generator: 2 (also defined in RFC 3526).
Secret Exponent: a 512-bit ephemeral random number *

If it is true that the secret must be twice the security level, it should be OK

Only the secret exponent will be different every time and P and G will be always the same (forever).

The key-exchange will be authenticated with RSA-2048.

Once the shared secret is computed, it will be used to derive a 256-bit symmetric key (perhaps with HKDF) to setup a AES-256 cipher that will run in CTR mode to generate a 1024-bit random material that will be splitted in four parts:

2 x AES-256 keys (write and read keys)
2 x HMAC-SHA256 keys [write and read keys, 256-bit each]

The scheme itself seems pretty standard, so it should be secure, if defined and implemented correctly. A simple textual descripion as you have provided here is not enough to prove your protocol secure. The authentication part only describes the RSA algorithm and key size - it does not specify how trust is established, nor does it define how the session keys are to be used.

I don't really understand your key derivation part; if you use HKDF and use the expand funtionality (with different info fields) you can generate multiple keys without having to resort to AES-CTR.

You may want to adhere to to NIST SP 800-56A Rev 2. This document also defines extract-than-expand key derivation schemes. One important issue with it is that it defines a lot of KDF's, so it will lead to another choice. It does certainly contain a lot of security hints regarding Diffie-Hellman which you may want to consider.

[EDIT]

As for the secret exponent size, the size of 512 bit is certainly enough, but the size of the modulus is very small. This means that the security is bounded by that of the modulus. It is very tricky to talk about effective key sizes within Diffie-Hellman. To get a good idea about possible key sizes, please take a look at the NIST or ECRYPT recommendations, e.g. at http://www.keylength.com/ . For good performance at higher key sizes, it is recommended - also by NIST - to switch to Elliptic Curve Diffie-Hellman. A 521 bit or 512 bit Elliptic Curve seems more appropriate for your needs.


Why is writing your own encryption discouraged? Say I want to write an encryption algorithm to communicate between me and my friend for this private use. How is that bad?

E.g. I can take the word Hello and encrypt it with a simple algorithm – for example –  take each letter and multiply its value by 2 and add 13 so that it becomes completely unreadable.

Is writing a private encryption that stays between two people discouraged or not? What's wrong with it?

Your question, MikeAzo's comment, and your reply practically could not be a better example of Schneier's Law in practice. Schneier stated:

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

To answer your reply

How can you break it if I send you this "QTCPIGXKUXTGG" ciphertext encrypted by a merely a simple algorithm which you have no idea about how it was encrypted?

Because even though we might not know exactly what your secret algorithm is, the first thing an attacker is going to reach for are common tools to attack substitution ciphers or polyalphabetic ciphers. Given even a few sentences of ciphertext is likely enough to fully recover every plaintext.
The fact that you don't know how to break it is irrelevant. It's trivial to create a cipher that you yourself can't break, but it's another thing entirely to create a cipher that others can't break. And the odds that you are capable of doing it when you're not aware of even the most basic attacks against ciphers hundreds of years old — not to mention modern concepts like indistinguishability under different attack models — puts you at an insurmountable disadvantage compared to ciphers designed by researchers with decades of experience in the field who are building off of modern notions of security and the discarded remains of thousands of failed ciphers that came before.
As an example, even if your cipher is somehow secure against a ciphertext-only attack (it's not), is it secure if I can trick you into encrypting a message of my choosing? What if I can trick you into decrypting a message of my choosing? What if I know part of or all of the plaintext for a particular encrypted message you've sent? What if you encrypt multiple messages with the same key? What if I can do any or all of these things hundreds or even millions of times in a row? These are all situations that are extremely common in the real world, and under which modern ciphers remain completely secure.
I'll leave you with another Schneier classic, Memo to the Amateur Cipher Designer:

A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to "fix" it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. "In each of these envelopes is an attack against your cipher. Take one and read it. Don't come back until you've discovered the other two attacks." The amateur was never heard from again.

So here's your first envelope: given a paragraph or two of ciphertext, your cipher will fail to language-based frequency analysis.
Let me know when you've figured out the other two attacks.
Edit: The comment about indistinguishability under different attack models is one reason why most "decipher this message crypto challenges" are completely bunk. They often simply give an attacker some ciphertext, ask them to decipher it, and declare victory when nobody produces the plaintext after some amount of time. Unfortunately that's not how crypto works in the real world; attackers have many more tricks up their sleeve in practice. They can trick computers into encrypting data of their choosing, they can trick computers into decrypting data of their choosing, and they can usually even do these things thousands, millions, or billions of times. Moxie's post shows how even the most terrible, horribly-designed, and obviously insecure ciphers can be effectively impervious when you restrict an attacker to a single ciphertext-only attack, which aren't representative of attackers' capabilities against ciphers as they're actually deployed in practice.


What is the most secure way to check that a given masterkey is valid? For the purposes of learning, I'm writing a small utility that allows encrypting a list of passwords using a single master key (using AES-256 and PBKDF2)

Before encrypting or decrypting any password user has to enter the master key (which will be used to derive a key for AES).

I would like to know what is the best option to know if a user has entered a valid master key :

To salt and then hash the master key (once). The resulting salt and hash are stored somewhere - for instance in a DB. Later on, when the user has entered his master key, I add the stored salt and compare the computed hash with hash stored in DB.
To generate a salt. The salt is encrypted using the master key. I store both the salt and the encrypted salt in a DB. Later on, when the user enters the master key, I try to decrypt the encrypted salt value with the master key and compare it with the salt stored in DB.

Let call a user's Master Key for AES as $\mathit{MK}_u$ and generated as;

$$\mathit{MK}_u = \operatorname{PBKDF2}(\mathit{passwd}_u, \mathit{salt}, \mathit{Iteration})$$

where $\mathit{Iteration}$ between 40K to 100K

  1.  To salt and then hash the master key (once). The resulting salt and hash are stored somewhere - for instance in a DB. Later on, when the user has entered his master key, I add the stored salt and compare the computed hash with hash stored in DB.

$$\mathit{hashed} = \operatorname{SHA-256}(\mathit{salt} \mathbin\| \mathit{MK}_u)$$

A passive attacker can look at the DB and;

Password search on $\mathit{MK}_u$ with hashcat.

A better solution is also using;

a pepper which is stored in the application server: this totally prevents the passive DB attacker
$$\mathit{hashed} = \operatorname{SHA-256}(\mathit{salt} \mathbin\| \mathit{MK}_u \mathbin\| \mathit{pepper})$$
Key-Stretching as PBKDF2 or Argon2: this also prevents and make it harder even pepper is accessed from the applications server.

$$\mathit{hashed} = \operatorname{PBKDF2}(\mathit{MK}_u, \mathit{salt} \mathbin\| \mathit{pepper}, \mathit{Iteration})$$

  2. To generate a salt. The salt is encrypted using the master key. I store both the salt and the encrypted salt in a DB. Later on, when the user enters the master key, I try to decrypt the encrypted salt value with the master key and compare it with the salt stored in DB.

$$\mathit{salt}_e = E_{\mathit{MK}_u}(\mathit{salt}),$$
and store $\mathit{salt}$ and $\mathit{salt}_e$ on DB.

For the second approach, the attacker can execute a password search for $\mathit{MK}_u$, this is almost the same as the attack shown against the #1 case since the attacker only deals with one AES encryption. To increase the iteration, one can modify this as in bcrypt.

The modified #2 approach is the winner due to the pepper in the passive DB attacker model.


Zero-Knowledge Proof of a Turing Machine Quesstion:
Suppose Peggy claims to have a Turing Machine (TM) such that when the tape starts with I the machine will halt with tape O for one or more (I, O) pairs.
Peggy would like to prove to Victor that she know the TM, but would like to convince him via a Zero-Knowledge Proof (ZKP).
Is there an algorithm $\Pi$ that Peggy and Victor can run that will accomplish this?  If so what is it?
Example:
Let's say that I write a function $f(x)$ in some programming language.  Now I would like to prove to you that $\forall x f(x) = 2 x^2-x+5$ but I don't want to disclose any information about the source code.  (I know that this is a silly example but you could imagine that $f(x)$ is a much more complicated function)
Ideas:
Maybe there is a way to convert this into another problem that we have a algorithm to proof in zero-knowledge
Clarifications:
Let's start with an application for an example.
Peggy is a student and Victor is a teacher.  Victor assigns a homework in which Peggy is supposed to design a TM to compute some function, $f(x)$.  Peggy designs a very elegant solution and no longer wants to disclose her TM to Victor. (Maybe Peggy is afraid that Victor will steal her idea)  Instead she wants to convince him that she did the assignment via a ZKP so she can get credit.
Another example is proprietary software.  A company wants to convince its users that their software does what the users expects it to so.   One popular solution is currently to release the software (e.g. open-source), but this allows anyone to easily steal the software.  An alternate could be to provide a ZKP that the software satisfies certain properties.
What information do Peggy and Victor have?

Peggy and Victor know all the (I,O) pairs.
Peggy knows some TM such that $\forall i \forall o ((i \in {\bf I} \wedge o \in {\bf O}) \rightarrow {\bf TM}(i) = o)$
Algorithm $\Pi$ should ideally run in polynomial time of the runtime of the TM
Ideally Victor should not learn the number of states of the TM or the number of steps needed to compute the function, but if there is an algorithm that works except for these properties that would still be great.

Learning some upper bound of the number of states or runtime is fine though

If needed Peggy and Victor have access to a Random Oracle

In principle, any language in NP can be proven in zero knowledge. Furthermore, any language in NP can be proven with a zero knowledge proof of knowledge. Thus, in order to answer your question, the only issue remaining is whether or not the language you have defined is in NP. In order to verify this, one needs to define a relation that can be verified in polynomial time. The way you have formalized the question is such that this is not the case. In particular, you have not included a requirement that the machine run in polynomial time. However, even if you do add this, it has to be done carefully. If you define: $(I,O)\in L$ iff there exists a polynomial time TM $M$ such that $M(I)=O$, then what you are really writing is $(I,O)\in L$ iff there exists a polynomial $q$ and a TM $M$ that runs in time $q(|x|)$ upon input $x$ such that $M(I)=O$. However, in this case there is no fixed polynomial-time upper bound on the running-time of the verifier (since the polynomial $q$ in the witness can be any polynomial). This can be solved by either defining the language $L_q$ to be $(I,O)\in L_q$ iff there exists a TM $M$ running in time $q$ such that $M(I)=O$. Alternatively, one can define $(I,O,1^t)\in L$ iff there exists a TM $M$ such that $M(I)$ outputs $O$ within $t$ steps. Since these languages are in NP, you can prove a zero-knowledge proof of knowledge and get what you want.

I note that in fact any language in $IP=PSPACE$ can be proven in zero knowledge, but then the proof isn't efficient.


Which area of Maths should I pursue? I would like to know which area of Mathematics would be most beneficial to cryptography. Surely Algebraic Number Theory and maybe to a lesser extend, Elliptic Curves, are closely linked to Cryptography; but are there more fields that would apply neatly to Cryptography?

What topics would you recommend to a Maths graduate who is looking for a career in Cryptography?

(I wanted to tag this as a "soft-question" as they do in math.stackexchange)

Abstract Algebra
Number theory
Statistics
Computer/Network security (so you can see the application)


What do we need white box crypto for? I am familiar with white box cryptography, but somehow I still fail to see its potential applications? Which situations would necessitate using it? Maybe you can even give me an example or two?

I know it is used to protect keys, but one could say: “Hey, come-on, derive a scheme where you don't need secret key”. Or, we could simply use what we have: public key encryption. All that’s to it is to maybe generate session keys and then encrypt/decrypt things using those keys.

It could enable a key exchange based off of symmetric primitives alone. For example, suppose I can provide to you a program that will allow you to perform AES-256 encryption of a single plaintext block. I could send you this program, you could perform your encryption and send me the result, and due to the whitebox nature of the algorithm, only I can decrypt it (not even you can).

This basically creates a public key encryption scheme using only the white box symmetric primitive. This is valuable because the hardness assumptions that underlie traditional public key primitives versus that of symmetric primitives. There is no known way to scratch the surface of the security of a single AES encryption. This is contrary to ordinary public key crypto, which is based on problems that more or less have very clear solutions, and only work because there are no known algorithms that are efficient enough to handle the key sizes involved.

The key size for AES are significantly smaller then say an RSA keypair, and the operations are significantly more efficient. A white box implementation might be different then a traditional implementation in this respect, but we'll have to wait and see.

This is not possible with a traditional implementation of AES because anyone who knows the key can perform both the encryption and decryption operations. With a white box implementation, the key is embedded into the program in a manner that makes it (ideally) impossible to extract. Of course, this also implies the program is constructed to only posses the encryption capability, and not decryption.


Does having a bunch of plaintext/ciphertext pairs help you break a ciphertext with unknown plaintext? Let say we have $N$ ciphertexts and each of them looks like this:

2iob3gRLvabM0QnMtgtMG5y4kCm=2xmLkasBUasLkQkjyQtQ3NFhU5UNkQ95U1nmk5UltxwZt1DltaojkQuHkxyXQI7=GYzYYf7t25ymQd7wtHJ52xWM3NJR3QTLUxmI3IZMU54NkitMGHz=2xmLvQnVtQUBk5Wa

assume it's encrypted URL string and we know output (actual URL) of each $N$ ciphertexts. In addition we know that the key is $m$ digits. So my question is how to assess complexity of breaking the $N+1$ ciphertext?

The known plaintext is only a useful tool for establishing that you actually found the right key if we assume a secure cipher (and mode of operation, etc.). It won't help you creating a faster than brute-force attack, as ciphers are assumed to be secure against known plaintext attacks.

So the complexity of breaking the cipher is simply still $m - 1$ (half the key space) on average, i.e. no change from normal brute forcing.


How does Clifford Cocks 'Non-Secret Encryption' work? I have read Clifford Cocks "A Note on 'Non-secret Encryption'" and thought I would try to implement this, but I don't seem to be able to get it to work. I'm obviously missing something.

From the paper:

  The receiver picks 2 primes $P$, $Q$ satisfying the conditions:

  i. $P$ does not divide $Q-1$.

  ii. $Q$ does not divide $P-1$.

  He then transmits $N = PQ$ to the sender.
  The sender has a message, consisting of numbers $C_1, C_2,\dots, C_r$ with $0 < C_i < N$
  He sends each, encoded as: $D_i$ where $D_i = C_i^N \mod N$.
  To decode, the receiver finds, by Euclid's Algorithm, numbers $P\prime$, $Q\prime$ satisfying:

  i. $P\cdot P\prime = 1 \pmod{Q - 1}$

  ii. $Q\cdot Q\prime = 1 \pmod{P - 1}$

  Then
  $C_i=D_i^{P\prime} \pmod Q$ and $C_i = D_i^{Q\prime}\pmod P$ and so $C_i$ can be calculated.

In my program I don't seem to be able to reverse back to the original message. I don't see how I can recover $C_i$ using this method? Do I need to combine the two calculations of $C_i$ in step 3?

Any ideas where I am going wrong?

The two last equations don't directly give you the value of $C_i$, they are telling you the values of the remainder of Ci when divided by $P$ and $Q$. You then use the Chinese Remainder Theorem with this information to produce the value of $C_i$ (modulo $N$) that you are looking for.

See en.wikipedia.org/wiki/Chinese_remainder_theorem (there is an algorithm for solving it for the case of two equations)


How Hermite Lattice reduced basis implies LLL reduced basis? Hermite reduced basis is defined as

A basis $\{b_1,\dots,b_n\}$ is reduced if it satisfies

$|\mu_{i,j}| \le \frac{1}{2}$ and
$||\pi_i(b_i)|| \le ||\pi_i(b_j)||$ for $1\le i \le j \le n$

where $\pi_i(x)=\sum_{j=i}^{n}\frac{(x \cdot b_j^*)}{b_j^* \cdot b_j^*)}b_j^*$ i.e., component of $x$ orthogonal to $b_1,\dots,b_{i-1}$

Since the algorithm to find Hermite's reduced basis not known to be in polynomial time for varying dimension.

Lenstra $et\;al$ defined the reduced basis and an algorithm to find the reduced basis in polynomial time.

LLL reduced basis is defined as

$|\mu_{i,j}| \le \frac{1}{2}$ and
$||\pi_i(b_i)|| \le ||\pi_i(b_{i+1})||$

How the second condition of hermite reduced basis implies second condition of Lenstra $et\;al$ reduced basis. Second condition of Lenstra $et\;al$ reduced basis satisfies only some inequalities in second condition of hermite reduced basis. What about the other inequalities? Does other inequalities are satisfied? If not, how does it output nearly orthogonal basis?

Ignoring the trivial case $j = i$, for which the second condition is automatically satisfied, the conditions for Hermite-reduced bases can be formally written as:

For all $1 < i \leq n$ and for all $1 \leq j < i$: $ \qquad \quad \quad \ \ |\mu_{i,j}| \le \frac{1}{2}$.
For all $1 \leq i < n$ and for all $i + 1 \ {\color{red}\leq} \ j \leq n$: $\ \quad \|\pi_i(b_i)\| \le \|\pi_i(b_j)\|$.

The conditions for LLL-reduced bases can be slightly rewritten as:

For all $1 < i \leq n$ and for all $1 \leq j < i$: $\qquad \quad \quad \ \ |\mu_{i,j}| \le \frac{1}{2}$.
For all $1 \leq i < n$ and for all $i + 1 \ {\color{red}=} \ j\leq n$: $\ \quad \|\pi_i(b_i)\| \le \|\pi_i(b_j)\|$ .

The only difference in the definitions, highlighted in red, is on the values $j$ for which the second condition must hold; for Hermite-reduced bases it must hold for all $j \in \{i+1, \dots, n\}$ while for LLL-reduced bases it must hold for $j \in \{i + 1\}$ (provided $i + 1 \leq n$). Since $\{i + 1\} \subset \{i+1, \dots, n\}$ this means Hermite-reduction is a stronger notion than LLL-reduction. So Hermite-reduction implies LLL-reduction.

As for your last questions:

  What about the other inequalities? Does other inequalities are satisfied? If not, how does it output nearly orthogonal basis?

For the case $n = 2$, the sets $\{i + 1, \dots, n\}$ and $\{i + 1\}$ are equal for $i = 1$, while for $i = 2 = n$ the second condition does not apply. So for $n = 2$, both notions of reducedness are equivalent. (Many other notions of reducedness also collapse to the same definition in case $n = 2$.)

For $n > 2$, setting $i = 1$ shows that the conditions are not necessarily equivalent. I am not sure whether already for $n = 3$ there are examples of LLL-reduced bases which are not Hermite-reduced, but certainly for larger $n$ there are many such examples - by the second condition, the vector $b_1$ of a Hermite-reduced basis must be a shortest non-zero vector of the lattice, while for LLL-reduced bases the vector $b_1$ is only known to be at most a factor $2^{O(n)}$ longer than a shortest non-zero vector in the lattice. In high dimensions, an LLL-reduced basis will look quite skewed compared to a Hermite-reduced basis, so in that sense it does not really output a "nearly orthogonal basis" - only a "somewhat orthogonal basis".


What is the largest parameter broken for NTRU? The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission.

Security
N
q

Moderate
107
64

High
168
128

Highest
503
256

What are attacks done so far that have broke the moderate and high security level parameters? The papers I came across mainly talks about the theoretical aspects of the attacks but are there any papers that did an actual implementation and manage to break the parameters?
Or in other words, what are the attacks that have caused the secure parameters to change? What is the largest parameter broken for NTRU?

1996 - NTRU patent,

1998 - NTRU article

Lattice Attacks

1996 - Lattice attack on the Rump Session of Crypto'96

1997 - Don Coppersmith and Adi Shamir. Lattice attacks on NTRU. In EUROCRYPT, pages 52–61, 1997. No need to find the exact secret key to be able to decrypt

2008 - Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Proceedings of the theory and applications of cryptographic techniques 27th annual international conference on Advances in cryptology, EUROCRYPT’08,
It has been shown in that the ability to locate a unique shortest vector
in a lattice depends on the root Hermite factor of the lattice,

2011 -  Yuanmi Chen and Phong Q Nguyen. BKZ 2.0: Better lattice security estimates. In ASIACRYPT 2011, pages 1–20. Springer, 2011.
Fastest NTRU-107. 214-dimensional lattices within $2^{42.62}$ clock cycles. Dimension of the lattice is the double of $N$

2016 - Shi Bai, Thijs Laarhoven, and Damien Stehlé. Tuple lattice sieving. IACR Cryptology ePrint Archive, 2016:713, 2016.
Best lattice attack with  $2^{0.292n}$ cost.

The below are the cost estimates from the NTRU PQC team.

N
m
b
Known Classical
Known Quantum
Best Plausible
Space Requirement

443
390
321
93
85
66
>$2^{66}$

743
613
603
176
159
125
> $2^{125}$

1024
1870
747
218
198
155
> $2^{155}$

Search attack
Searching the keyspace ${N \choose df,df}/N$  NTRU-743, we have $2^{1158}$ candidates. Impossible!
Hybrid attack
the hybrid attack is a hybrid of a lattice attack and a meet-in-the-middle search attack.

2007 - Nick Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack
against NTRU. In CRYPTO, pages 150–169, 2007.

BKZ with classical enumeration, hybrid attack vs. uSVP

N
hybrid attack Cost
uSVP

443
>128
>189

743
>267
>443

1024
>811
> 590

BKZ with quantum sieving, hybrid attack vs. uSVP

N
hybrid attack Cost
uSVP

443
>84
>85

743
>163
>159

1024
>289
> 198


Basic encryption question: Why does 128/256 bit encryption have set length keys? I've read about 128 and 256 bit encryption (I obvioulsy haven't read enough). I believe 128 and 256 refer to the size (in bits) of the keys used to encrypt.

Why are these of set length? Surely an encryption key can be any length you want to encrypt with? What part of encryption am I misunderstanding here? Or am I confusing encryption with hashing?

The first  thing that you really need to understand is that cryptographic keys are not the same thing as passwords.  Many newcomers to cryptography are familiar with passwords, and identify keys as an analogous concept—which it is, but the differences are very important:

Passwords are generally chosen by humans; cryptographic keys are randomly generated with a good source of randomness (dice are good, brains are not);
Passwords are generally memorized by humans; but no strong cryptographic key can be memorable.  Keys are instead stored in secure hardware.
Passwords are text that humans can read and type easily; keys are binary data and not generally printable in their raw form.  You need to format them as hexadecimal, Base64 or similar for display.  (Actually, you really shouldn't display them at all, since they're not memorable anyway!)

If your AES key is something like PASSWORDPASSWORD (which I've actually seen ), somebody has likely made a terrible mistake.  A 128-bit key should be 128 randomly chosen bits!

With that out of the way, now we can say: practical cryptographic systems are built by assembling together well-studied primitives (e.g., AES, SHA-2, RSA, etc.), into complete protocols (e.g., SSL, SSH, OpenPGP) for achieving the users' goals.  And given this sort of architecture:

Fixed key sizes generally make the primitive simpler to design, implement and evaluate.
If arbitrary-length key sizes are needed, this can generally be accomplished at the protocol level.  For example, the AES-CMAC-PRF-128 function is based on AES-128 but uses variable-length keys.  So part of the function's definition is a method for converting the arbitrary-length key into an AES-128 key.
There's no earth-shattering advantage to supporting arbitrary-length keys, so most protocols don't bother with it.
For cryptographic systems that work with passwords, there's an area known as password-based cryptography—cryptographic constructions and protocols for generating cryptographic keys out of human-supplied passwords.  A protocol for encrypting files based on user-supplied passwords works this way—it uses a password-based key derivation function like PBKDF2 to convert the password to a key, and then uses that key to encrypt and decrypt files.  So this is another example of cryptographic modularity—the primitives support only fixed-size keys, but their combination supports arbitrary-length passwords.


Asymmetric cipher with multiple public keys Asymmetric cryptography is well known.
You generate a private key.
Using the private key you generate a public key.
Then you can sign a message with the private key and check signatures using the public key.

I have different process which is as follows

On the one side are a lot of people that create messages (senders).
Each sender has only one private key which used to sign his messages.
Each sender knows only his own private key.
Each sender makes many signed messages.
Each message contains public key which can be used to check signature of that message. Message can be verified only by the key that inside in the message.

On the other side are o lot of people that read messages (readers).
Each reader can read all messages of all senders.

Our goal - no one among readers should be able to conclude for any two messages whether they created by the same sender or by different senders.

So generally we need an asymmetric cipher which allow to generate many public keys for one private key.

Do you know such asymmetric ciphers? Maybe we can use combination of known ciphers to achieve this result?

Merely receiving a message and seeing that it has a valid signature does not provide any useful information. You also need to know who made the signature, or at least to have some information about them. If you don't know anything about who made the signature, then an adversary can generate their own message using whatever key they like.

In your scenario, there is apparently a group of trusted people. You want these people to be able to sign messages such that:

a recipient can verify that the message is a genuine message from a member of the group (as opposed to a message modified crafted by someone outside the group);
ordinary recipients do not know which member of the group produced a given message.

With just these conditions, you could make all senders use the same private key. However this would usually be a bad idea because it precludes many desirable properties, such as the ability for certain participants to tell who produced a given message, the ability to revoke the credentials of a participant who's defected, etc.

A common, relatively simple way to build such a system is to allow each participant to generate as many private keys as they like (possibly one for each message), and send the corresponding public keys to a certification authority (CA). The CA can choose what information it puts in the certificate. CAs for websites put the website name in the certificate, because that's what website certificates are for. A CA in your scenario would not put any identification in the certificates. The CA is thus an anonymity broker: it knows who is who but doesn't tell.

This scenario occurs with TPM: a TPM needs to be able to generate keys which cannot be tied to a specific TPM, but can be used to identify it with a particular service. What I described above is how multiple identities for TPM version 1 works. TPM 2 adds another method: direct anonymous attestations (DAA). I'm afraid that explaining the mathematics of DAA is beyond me. DAA may be a solution for you.


Example of a problem for which Zero-Knowledge proof is not sequentially composable There are notions that a Zero-knowledge proof with auxiliary input is necessary for sequential composition. However, the authors here give a very convoluted example of a system which is not sequentially composable under the original ZK definition. Could you please give me an example where the original definition by Goldwasser et al. is not enough for sequential composability?

The paper you cited gives that exact example. It shows that zero-knowledge that is NOT zero-knowledge for auxiliary input is not strong enough. The fact is that most known zero-knowledge proofs are secure for auxiliary input and thus are secure under sequential composition.


Creating SHA256 constant values on the fly without memory usuage Is it possible to create the constants used in SHA256 on the fly? Meaning I dont have to reserve 64 32-bit words of space? It would result in a slower implementation, but at the profit of using less memory. I know it is possible to do it with AES Sboxes, but how about the SHA256 constants?

If you look at the specification to understand how those constants were chosen, you'll realize you waste more memory generating them "on the fly".
SHA-256 compression function key schedule constants are calculated as the fraction part of cubic-root of the first 64 prime numbers. You said you coud delete them after use (in the comment), but wouldn't that overlap with DRAM allocated for message buffer or something else? If you need a memory-compact implementation, this would be an anti-optimization.
If you desire a hash function without large memory footprint, you could consider SHA-3/Keccak, it too has some constants, but generating them "on the fly" requires only few additional registers to hold values from a LSFR.


Stuck on finding M2 knowing M1 in One Time Pad Lets say I have a plaintext M1 and a plaintext M2, I know both the ciphers C1 and C2 from these M1 and M2. But from M1 I also know a piece of M1 or maybe even the whole text. And I also know C1 XOR C2 = M1 XOR M2. But how can you get M2 if you know M1. So is it possible to do 'something ' to M1 XOR M2 knowing M1 to get M2?

If you know M1 XOR it to both sides of M1 XOR M2 = C1 XOR C2 which gives you M2

  M2=C1 XOR C2 XOR M1

Even if you didn't know M1, if it is long enough it (or M2) might have a common substring, i.e., a crib such as "the", "this".

You might use the crib as an estimate of part of M1 to obtain a guess for a part of M2 by using the equation above focusing on 3 letter substrings.

If you obtain as M2 a substring that looks like it could be English, you may have guessed part of the OTP key.


What are the implications of an encrypted private key being released? An application owner at my organization requested a java keystore to be built around specific parameters and provide them with both the JKS and pkcs12 versions of the keystore.  Weeks later and after many changes they were troubleshooting some issues.  The application admin, not thinking of the security implications, blasts an email with the output of the OpenSSL command: pkcs12 -info -in .

In the output of that command the first key listed shows.

-----BEGIN ENCRYPTED PRIVATE KEY-----
blahblahblahblahblah
-----END ENCRYPTED PRIVATE KEY-----

To me this looks nuclear and appears to expose the private key.  My recommendation initially is to burn the entire keystore and start over rekeying everything.  As this is a significant amount of work I wanted to be sure my reaction was accurate.  It does say Encrypted so perhaps as long as the password is still secure maybe we're okay?  I'm pretty solid on OpenSSL and keytool but this slips past my expertise.  Can anyone here help me define the exposure for my mangement?

Since the encrypted key file is (potentially) leaked, and adversary is able to run an offline dictionary attack against your key. So you have to answer the question: Is the strength of the password used to encrypt the key, weaker than the strength of the key itself?

So what you should do, is calculate the strength (entropy) of your password (KeePass can do this, for instance) and compare it to current strength estimations for the itself (RSA 2048 has 112 bits, for example). If the password's result is weaker then the key, you should drop it and revoke the certificate.


64 bits cipher and birthday boundaries in ECB I am using a 64 bits symmetric ciphers (blowfish), to encrypt a plain block using ECB.

The plaintext is always 64 bits long, but due to some limitations I have to use the same key (448 bits long) everytime.

The plaintext is always different.

I was looking to birthday attack but I find papers related to CBC mode only.

Is my scenario affected by this kind of attack?

First, remember that any cipher must be functionally correct, that is for any valid plaintext $$\operatorname{Dec}_k(\operatorname{Enc}_k(m))=m$$

This effectively means you must be able to properly decrypt any properly encrypted message. This also means that it cannot happen that $m_1\neq m_2$ with $\operatorname{Enc}_k(m_1)=\operatorname{Enc}_k(m_2)$ can happen. After all, how would you decrypt the result deterministically? To $m_1$ or to $m_2$? You can't decide, thus such a scheme would violate funtional correctness and thus this situation can't happen. Now Blowfish is functionally correct and as per the above argument you'll never see any collisions under the same key. Also you're using ECB where each block is encrypted individually meaning the above argument also applies to longer messages.

With CBC the situation is different, you encrypt as $c_{n}=\operatorname{Enc}(m_n\oplus c_{n-1})$ (where $\oplus$ denotes bitwise XOR). Which means if you find any two $(m_1,c_0),(m_2,c_1)$ such that $m_1\oplus c_0=m_2\oplus c_1$ you've got two resulting cipher texts looking the same (ie a "collision"). Note that $c_0,c_1$ are essentially random, and they're being combined with an unrelated value meaning the result will be essentially random again and you expect a collision among two random strings of length $l$ after $2^{l/2}$ samples.

One final note: If you're trying to use ECB for production, chances are you have the wrong mode. If you need something with random-access and no overhead, use AES-XTS, if you need something with random-access and authentication, chunk it with AES-GCM and in any other case just use (chunked) AES-GCM because it also takes care of authentication for you and will be much faster than Blowfish-ECB if your CPU supports AES-NI.


Comparing plaintext to contents of ciphertext Given an authenticated mode of encryption, when comparing a plaintext string against the contents of a ciphertext, which approach is typically considered safer?

Encrypt the plaintext and compare against the ciphertext, or
Decrypt the ciphertext and compare against the plaintext in $O(n)$

The former appears better to me since the contents of the ciphertext are never decrypted and loaded into memory. However, given that it's an authenticated mode of encryption, this bypasses the authentication checks that would normally occur during decryption.

So, which is hypothetically worse? Potentially allowing Eve to load decrypted ciphertexts into memory, or potentially allowing Eve to force my system into comparing plaintexts (either under Eve's control or unknown to her) to forged ciphertexts?

2 is considered better, because the probability of the comparison in 1 returning $\:\text{true}\:$ is always at most $$\frac1{2^{\operatorname{len}(\text{IV})}}$$


When the salt is applied before the text is salted , then what is "that"? In all the documentation I read that the salt is applied before the text is hashed and the salt is stored somewhere in the database in plain text.

So for example bcrypt generates the following structure:

$2y$10$M8z/Bcli/eh3ay5.4w4Y5.hbTZ2wrwDKdJXkCQ7HuFazAzOqZzl4`.

$2y$10$M8z/Bcli/   <-- this does not look like a part of the hash

What kind of structure is this?

It seems you are looking at Modular Crypt Format.

2y identifies a specific version of the bcrypt algorithm
10 specifies the number of rounds
M8z/Bcli/eh3ay5.4w4Y5. is the salt

and the rest is the hash according to the modular crypt format bcrypt page.

It seems the Modular Crypt Format is "deprecated" in favor of PHC-SF which does however look similar.


Lyra2 sponge construction and random numbers? I have a Lyra2 project and I still have some problems understanding its principle.

I really found a problem when I read about sponge contruction. I found out that it's composed of 3 steps: absorbing, squeezing and duplexing and then we xor the (password, salt, ... ) with random numbers (state) so finally we get the password encrypted but then my problem is: it's not possible to decrypt it, isn't it? So probably I'll decrypt it using a dictionary but the thing is since I'm xoring with just random numbers then for the same word I'll have different encryption each time, won't I?

From what I can tell, you've found the salt input to modern password hashing schemes which indeed accepts random numbers to hash the same password to different results on distinct invokations.

Now the idea of the salt is indeed to prevent the dictionary attacks you envisioned (if you keep the salt secret, in which case it becomes pepper) or at least force you to go throgh your entire dictionary for every single salt you encounter, which will take time and slow you down in breaking large databases of passwords. However, normally, all parameters for password hashes are specified (including the salt) and as such it is an entirely deterministic computation from the password and the stored parameters to verify the stored password hash.

Finally, yes: It's impossible to directly recover the password (or a valid password) from its hash as then the function would have failed its most important role which is to make it hard to recover the password.


Randomness re-use in LWE encryption scheme Let me describe the scheme first, it is the scheme proposed by O. Regev when he introduced the LWE assumption.

$sk = \textbf{s} \in \mathbf{Z}_q^n$
$pk = \textbf{A}\textbf{s}+\textbf{e}$ where $\textbf{A}\in \mathbf{Z}_q^{m\times n}$ and $\textbf{e}\leftarrow \chi^m$
$ct=(\mathbf{r}\mathbf{A},\mathbf{r}pk+\lfloor \frac{q}{2} \rceil x)$ where $\mathbf{r} \leftarrow \{0,1\}^m$ and $x$ is the message

I know that this scheme is secure under randomness reuse, that is for 2 different messages $\mathbf{x}_1$ and $\mathbf{x}_2$ and secret keys $\mathbf{s}_1$ and $\mathbf{s}_2$, the following scheme is secure against chosen plaintext attacks:

$ct = (\mathbf{r}\mathbf{A},\mathbf{r}pk_1+\lfloor \frac{q}{2} \rceil x_1,\mathbf{r}pk_2+\lfloor \frac{q}{2} \rceil x_2)$

Here is my question: If an adversary has one of the secret keys, say $s_1$, is the message $x_2$ still secure against him?

I've been searching around but I only found about security when the adversary doesn't know any key.

I give another simple proof using the leftover hash lemma.
The proof goes as follows, where I'll abuse the notation and assume that q is prime.

Game0

The adversary can see
$$(A,b,c,u,v,w,s)
= (A, As+e, At+f, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s).$$

Game1

The view is changed as
$$(A,b,c,u,v,w,s)
= (A, As+e, c, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s),$$
 where we change $c = At+f$ with random $c$.
From the LWE assumption, Game0 is indistinguishabe from Game1.

Game2

The view is changed as
$$(A,b,c,u,v,w,s)
= (A,As+e,c,u,rb+x\lfloor q/2 \rceil,z+y\lfloor q/2 \rceil, s)$$
where we replace $rA$ and $rc$ with random $u \gets \mathbb{Z}_q^n$ and $z \gets \mathbb{Z}_q$.

In this game, $y$ is completely hidden, since $z$ is chosen uniformly at random.

Game1 vs Game2

If the term $v=rb+x\lfloor q/2 \rceil$ disappears,
 then we can invoke the leftover hash lemma as Regev originally did.

We can still invoke the generalized leftover hash lemma in [DORS08] even if the term $v$ remains.
Very roughly speaking,
 if $m \geq (n+2) \lg{q} + 2(1/\epsilon) + O(1)$,
 then we can say the distance between Game1 and Game2 is at most $\epsilon$.

Generalized leftover hash lemma

Let us define the average min-entropy of $R$ given $I$ as follows:
$$\tilde{H}_{\infty}(R \mid I)
 = -\log\left(\mathrm{Exp}_{i \gets I}\left[
  \max_{r} \Pr[R = r \mid I = i]
  \right]\right).
$$
Intuitively speaking, this entropy is the logarithm of predictability of $R$ given $I$. As we expected, if $I$ leaks the information of $R$, the average min-entropy of $R$ given $I$ decreases.

Let us consider the average min-entropy of $r$ given $v = rb + x\lfloor q/2 \rceil$.
By invoking  [Lemma 2.2 (b), DORS08], we have that
$$
 \tilde{H}_{\infty}(r \mid v)
  \geq H_{\infty}(r) - \lg{q}.
$$
That is, the average min-entropy of $r$ given $v$
 is at least the min-entropy of $r$, which is $m$, minus $\lg{q}$.

Now, let us review the generalized leftover hash lemma in [DORS08]:
For a family of universal hash functions $\{H_d : \{0,1\}^n \to \mathcal{S}\}$
for any random variables $R$ and $I$,
we have
$$
\Delta\Big(
 (H_{D}(R),D,I),
 (U_{\mathcal{S}},D,I)
\Big) \leq \frac{1}{2} \sqrt{2^{-\tilde{H}_{\infty}(R \mid I)} \cdot \#\mathcal{S}},
$$
where $U_{\mathcal{S}}$ is a random variable distributed according to the uniform distribution over $\mathcal{S}$.

By replace $D$ with $(A,c)$, $R$ with $r$,
 $H_{D}(R)$ with $(rA,rc)$, and $I$ with $v$,
 $\mathcal{S}$ with $\mathbb{Z}_q^{n+1}$,
 we obtain the upperbound of the statistical distance as $\frac{1}{2} \sqrt{2^{\tilde{H}_{\infty}(r \mid rb)} \cdot q^{n+1}}$, which is at most $\epsilon$ if $m = (n+2)\lg{q} + 2\log(1/\epsilon) + \Omega(1)$.

[DORS08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith: "Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data" in SIAM Journal of Computing, 38(1):97--139, 2008. (Prelim. version is Dodis, Reyzin and Smith in EUROCRYPT 2004).


Is it possible to create a zero-knowledge proof that a number is more than zero, and less than x? Note: This might be similar to this question.

I'm thinking about a hypothetical cryptocurrency where the blockchain doesn't store any transactions. The balance of an address would be stored by the owner, and the blockchain would only contain the root hashes for Merkle trees with hashes of "{address}{balance}". Each block would also contain a list of invalidated hashes. The "miner" nodes would execute a transaction by invalidating the previous hash for an address, send both parties the new Merkle tree leaf nodes for the updated balances, and create a new block with the root hash. It would also be a proof-of-stake algorithm.

I would like to know if there's some way to generate a zero-knowledge proof that your address contains more than 0, and at least x? (x can be an integer, since this hypothetical cryptocurrency has a fixed number of decimal places.)

This would allow people to send transactions without disclosing their actual balance. They could also provide a sequence of verified transactions to prove that their address contains the original amount, minus x, y, z, etc.

I've read some of the other zero-knowledge answers on here, so I'm pretty sure that the answer is "yes". I found this paper, and I've also found some answers like this. However, I would love to see an answer that is relevant to this specific case. I would also find it easier to understand some code examples (any language, or even pseudocode.)

EDIT: I forgot to mention something: the implementation must also include a nonce, otherwise it would be very easy to bruteforce balances for some addresses. For example, if there was no nonce, then it would be easy to find a list of all addresses that have a specific balance of 1.00000000. So the range proof / verification must also consider a secret nonce (or salt).

What you want is usually called a range proof: proving in zero-knowledge that some value (committed, or encrypted) is in a given public range. I had written a detailed answer on existing techniques for range proofs where answering this question.

I'm not sure I understood exactly how your scenario would work, but one possible issue with standard solutions is that they are based on algebraic primitives (like, commitments over abelian groups), while you seem to look for a proof related to something hashed in a Merkle tree, without any specific (algebraic) structure. Such statements are harder to prove, but this can be done, using techniques based on garbled circuits to prove knowledge of a satisfying assignment for a given boolean circuit (in your case, this boolean circuit would first check that the input is in the correct range, then hash it the way you want). The most relevant techniques are the recent protocols ZKBoo and Ligero.

One last thing: if you want access to a specific paper that seems relevant to you, but that is behind a paywall, you can contact me by MP (my institution gives me access to the database of most editors).


What is the smallest plaintext/ciphertext size for an algorithm like? When I read about a choosen plaintext attack, for example on AES the block size is always 128 bits, does it mean the attacker will only supply 128 bits data words as "plain text" ?

"Known plaintext" means that the attacker has knowledge of some data and its encrypted counterpart, but he did not choose either (it is "chosen plaintext" when the attacker chooses the plaintext and obtains the corresponding ciphertext, and "chosen ciphertext" when he chooses the ciphertext and obtains the corresponding plaintext). What is "plaintext" depends on what the attacker is trying to attack.

AES is a block cipher: it operates on fixed-size values (the "blocks", 128 bits for AES). When encrypting arbitrary messages, a mode of operation is used; the mode decides how the input data is to be split and mangled and reassembled; the block cipher being only the central part of the process. However, whatever the mode is, at some point some block-sized values will go through the block cipher, because the block cipher cannot use anything else.

So, when discussing attacks on a block cipher (as opposed to: attacks on a symmetric encryption scheme which uses a block cipher and a mode of operation and possibly many other things), we concentrate on the number of (distinct) block values for which the attacker needs to know the plaintext and the corresponding ciphertext. For instance, linear cryptanalysis, when applied on DES, requires $2^{43}$ known plaintexts, i.e. 64-bit plaintext blocks and corresponding ciphertext (DES uses 64-bit blocks). With common modes of operation such as CBC, a block cipher with $n$-bit blocks will be invoked once every $n$ bits of input data, so this requirement translates to $2^{46}$ bytes worth of data (somewhat over 70 terabytes).

Huge amounts of known plaintext are of course impractical. Cryptographers still consider an attack to be "genuine" as long as it requires less than $2^n$ known plaintext and $2^{k}$  effort: if, for $n$-bit blocks, you have $2^{n}$ plaintext/ciphertext pairs, then you have the complete codebook and you do not need the key anymore; and with a $k$-bit key, trying out all possible keys has cost $2^{k}$ invocations of the block cipher. An attack is "real" (in an academic sense) if it does better than that, even by a small margin.


What characters are valid in PGP encrypted and signed messages? What characters may be present in a PGP encrypted message or a PGP signature? For example, do encrypted messages only use the Roman alphabet + some numbers and symbols? Can the character set be configured by the user? Is everything Base64 encoded?

Also, are there special characters that will never be used in a message?

OpenPGP as defined by RFC 4880 knows two different encodings.

Binary encoding

Obviously, there is no reasonable limitation to an (ASCII) character subset in binary encoding.

Radix 64

Radix 64 is also often called ASCII armored. In the end, it is a base64 encoding with a checksum. The content may consist of [a-zA-Z0-9+/=].

ASCII-armored OpenPGP messages also include a header, which may contain arbitrary UTF-8 strings.

An example message in ASCII-armor (modified from the one in the RFC):

-----BEGIN PGP MESSAGE-----
Version: OpenPrivacy 0.99
Comment: An example for an UTF-8 string with arbitrary characters

yDgBO22WxBHv7O8X7O/jygAEzol56iUKiXmV+XmpCtmpqQUKiQrFqclFqUDBovzS
vBSFjNSiVHsuAA==
=njUN
-----END PGP MESSAGE-----


Complexity of ECB and OFB What is the complexity of ECB in terms of Time and Memory?

and also in OFB? I can't find it in the internet, so I decided to ask it in here.

Well, assuming that you have a fixed block cipher (that is, you don't change the block cipher as the length of the message increases), then given a message of length $N$:

Both ECB and OFB take $O(N)$ time for both encryption and decryption.
Both ECB and OFB take $O(1)$ space in addition to the space to hold the encrypted/decrypted message (which is $O(N)$).


Point-at-infinity in the scalar multiplication Is it possible to hit point-at-infinity while performing scalar multiplication in Weierstrass curves?

According to this reply this is only possible when the scalar k is bigger then the order of the curve n. Is it so? If yes why?

Yes, it is possible.

The smallest scalar $k$ for which $[k]P = \infty$ is called the order of $P$.

For every non-zero point $P$ on the curve there is such a $k$.

This is simply due to the fact that there is only a finite amount of points so if you keep increasing $k$ at some point you must get a repetition $[k]P = [k-i]P$ for some $i$. Now $[k]P - [k-i]P = \infty \iff [i]P = \infty$.

No, $k$ does not have to be bigger than the group order $n$.

In fact for any prime $p$ dividing $n$ there is a point $Q$ such that $[p]Q = \infty$. This is Cauchy's theorem.

On the other hand Lagrange's theorem tells us that the order of every point divides the group order: $[k]P = \infty \Rightarrow k|n$. Therefore, if the group order $n$ is picked to be prime it follows that the order of every non-zero element is $n$.


Attacking AES without transposition using ShiftRow and Mixcolumn layers How can we attack by using chosen plaintext attack (and which plaintext should we choose) if AES didnt have the ShiftRow and Mixcolumn layers. I know each byte would be independent in the 16 byte scheme but couldnt figure out a way to attack.

After the key expansion, there would be 16 different mappings for each of the 16 bytes in a block.

Suppose we are attacking the block cipher itself (in ECB mode), with each byte having 256 different values, we can query 256 ciphertext blocks (all-bytes-0, all-bytes-1, ... all-bytes-255) to get the exact plaintext-to-ciphertext mapping for all 16 bytes's 256 values.

To decrypt future blocks, you just need to have a 16x256=4096 byte (1 memory page) table of the inverse map which you can easily create now.


Algorithm for binary less than in MPC Given binary shares $[a_{l-1}]_p,...,[a_0]_p, [b_{l-1}]_p,...,[b_0]_p$ such that $a = \sum_{i=0}^{l-1} a_i2^i,b = \sum_{i=0}^{l-1} b_i2^i $
for $a,b \in Z_p$, how to compute $a \overset{?}{\lt} b$ in MPC (the result is not closed)?

find the positions where $a$ and $b$'s bits differ: $c_i=a_i\oplus b_i=a_i+b_i-2a_ib_i$

compute partial or-sums: $d_{l-1}=c_{l-1},\quad d_i=d_{i+1}\vee c_i=a_i+b_i-a_i b_i$

isolate the first differing bit: $e_{l-1}=d_{l-1},\quad e_i=d_i-d_{i+1}$

the result is the corresponding bit in $b$: $\sum e_i b_i $


Is the order of applying transformations in SP cryptosystems significant? SP-cryptosystems Is the order of applying transformations in SP cryptosystems matter? What will change if we first apply the P-transformation and then the S-transformation? Will cryptographic strength be less? And if yes, why?

Let call the Substitution by $S$ and Permutation by $P$ in the Substitution Permutation Network (SPN). Let consider an SPN block cipher with $4$ rounds where $K$ represents the $\oplus$ round key.

With $S$ applied first

|KSP|KSP|KSP|KSP|

The last $P$ has no effect on security. The attackers simply discard it. So we can consider it like;

|KSP|KSP|KSP|KS|
With $P$ applied first

|KPS|KPS|KPS|KPS|

The initial permutation has no effect in the view of the attacker. Similarly, we can consider it with some changes in the key schedule.

|KS|KPS|KPS|KPS|

Now we can swap K and P that will require a change in the key schedule.

|KSP|KSP|KSP|KS|

That is turned into the simplified version of S applied first. Consequently, they did not differ.


Writing your own Encryption algorithm? Simple answer (and I know this is a simple yes or no) is it possible to write an encryption that is 100% uncrackable, as long as I keep certain parts private? It's just for personal use.

I'm a computer programmer and need my own encryption to encrypt things like my passwords. Is this possible so that its 100% uncrackable, or is it simply not possible?

I'm a computer programmer and need my own encryption to encrypt things like my passwords.

This does not imply that you need to write your own encryption algorithm. Being a programmer does not make you a cryptographer, cryptography is a skill unto itself that takes lots of experience and practice.

Plenty of experienced cryptographers have gone through the trouble of designing and analyzing algorithms for people in your situation, precisely so that you don't have to write your encryption algorithm.

More importantly

It's inappropriate to encrypt passwords. Standard good practice dictates the use of a slow, memory-hard password hashing function such as scrypt or argon2 (or pbkdf2 at the very least).

"Unbreakable encryption"

  is it possible to write an encryption that is 100% uncrackable, as long as I keep certain parts private?

The One Time Pad in theory provides information-theoretic security, which means that no amount of computational advantage or sophisticated algorithm can help an adversary who has a ciphertext learn more about the plaintext than they already know.

Using the One Time Pad in practice is clunky and prone to failure (and here's another Q/A supporting that conclusion if that was not sufficient). It is difficult to fulfill the assumptions that the proof rests upon, and so it is not used very often in practice despite the theoretical guarantees.

In practice, algorithms such as AES and Salsa20 will remain unbroken when implemented and used correctly.

While solid encryption algorithms do exist, encrypting passwords is a poor idea.

If you want to succeed

If you care about fulfilling your security goals, then it is a good idea to stick to battle-hardened algorithms and pre-existing software libraries that implement them. Libsodium is a solid recommendation.

Do not create your own implementation (except as a learning experience) - your information and/or your users information is at stake, and there exists a non-negligible probability of failure.


Is it possible to reverse Diffie-Hellman key exchange? Is it possible to reverse Diffie-Hellman key exchange to get the private key of one of the parties, given a large prime number 'p' .

It is certainly possible given enough compute resources.

However, if you mean to ask whether it is computationally feasible for an eavesdropper to derive the private keys, then- no, it is not.

Refer to the secrecy chart on Wikipedia:

The private keys a and b are meant to be known only to Alice and Bob respectively.

In the real world, the Logjam attack is one example of how adversaries with nation state-level compute resources (such as the NSA) could theoretically break Diffie Hellman implementations, relying on the fact that a small set of primes were used across most common implementations.


Why should one use a cypher-based message authentication code (CMAC) instead of symmetric encryption and CRC? What are advantages/disadvantages for using a CMAC that proofs the integrity and authenticity of a message but doesn't encrypt the payload itself? Why should it be used instead of symmetric encrypted payload and CRC (CRC is encrypted as well)? This could also proof authenticity, integrity AND confidentially.
From my point of view the only reason is when one has a huge amount of data, encryption takes too long and confidentially is not required. But what about short message? In both situations the same key is used and using a symmetric encryption fulfills the security goal confidentially...

The main reason to use a proper cryptographic authentication code is to ensure the very properties you listed. Your proposal of ciphertext and CRC (encrypted or not) fails to provide those.
Let's consider three possible arrangements of data transmission with CRC:

Plaintext message and CRC:
CRC (Cyclic Redundancy Check) is meant to detect errors in transmission or storage.
It is a straightforward algorithm with a single input (the message) and a single output (the CRC code). As such it cannot provide protection against willful modification of the data as anyone can compute the new CRC code.
This means we would need to ensure the CRC cannot be manipulated.
Let's take up your first proposal:

Encrypted message, plaintext CRC:
One big problem here: CRC is not a cryptographic hash function, nor was it ever supposed to be. It has too many chances of leaking information about the plaintext.
The properties in the next section also mean that they can modify the encrypted message AND properly modify the CRC.

Encrypted message and CRC:
One notable property of CRC is that $\operatorname{CRC}(x \oplus y) = \operatorname{CRC}(x) \oplus \operatorname{CRC}(y)$.
block ciphers modes operate using the XOR operator over a mix of plaintext, key, IV, previous ciphertext, etc...
In some cipher modes, XORing the ciphertext is the same as XORing the plaintext. For example, the counter block cipher mode boils down to: $\text{ciphertext} = \text{plaintext} \oplus \operatorname{AES}(IV)$
To fake the message, I can compute $\text{diff} = \text{plaintext} \oplus \text{desired_plaintext}$ and return the following:

new ciphertext: $\text{ciphertext} \oplus \text{diff}$
new encrypted CRC: $\text{encrypted_crc} \oplus \operatorname{CRC}(\text{diff})$

I have effectively modified the message and its CRC without having to break the encryption.
You can find further reading and references in the data integrity section of the CRC wiki page.

[EDIT: credit goes to Maarten Bodewes] CRC size limitations:
CRC's are generally limited to 32 bits (although 64 bit CRC's have been defined), which is not enough to provide 128 bits security. Just trying in the order of $2^{32}$ random messages (or separate connections) would give you a chance of ~0.63 to get one right. That's simply to high of a chance even if CRC could not be attacked by other means.
Now it is possible to create a MAC by performing a relatively fast operation over blocks of 128 bits / 16 bytes and then encrypt the result. These kind of techniques are used for GMAC (in AES-GCM) and Poly1305 used within ChaCha20/Poly1305 used in - for instance - TLS 1.2 and 1.3. These still rely on a block cipher for security, but the block cipher is only used once or twice instead of for each block of the message.
Note that GCM and ChaCha20/Poly1305 operate on the ciphertext rather than the plaintext, but that can be considered an implementation detail. Generally you want to verify message authenticity before decryption.

You may also be interested in one of the secure OCB modes (1 & 3) which integrates both authentication and encryption, doing away with any additional (computationally intensive) operations on the data.


Spurious keys filter Is there any possible way to filter a key space in a crypto-system to get a set of keys that decrypts out a valid text (text that is in same language or readable)?

I tried a random approach and got certain set of keys but its not that appreciative to actually required text size

code

from Crypto.Cipher import ARC4
import base64, string, time, random
key = ''.join(random.choice(string.ascii_letters + string.digits ) for i in       range(8))
obj1 = ARC4.new(key)
obj2 = ARC4.new(key)
text = 'abcdefgh'
cipher_text = base64.b64encode(obj1.encrypt(text))

decoded_text= obj2.decrypt(base64.b64decode(cipher_text))

Dict={}
count=0
valid = set(string.ascii_letters + string.digits )
def test(s):
    return set(s).issubset(valid)

print; print 'plain text: ', text
print; print 'Actual key: ', key
print; print 'Cipher text: ', cipher_text

timeout=time.time()+60
while time.time()< timeout:
   count+=1
   key = ''.join(random.choice(string.ascii_letters + string.digits ) for i in range(8))
   obj2 = ARC4.new(key)
   decoded= obj2.decrypt(base64.b64decode(cipher_text))
   if test(decoded):
       Dict.update({'key: '+key : 'Valid Decrypted Text: '+decoded})
import pprint
print; print 'Analysis: '
pprint.pprint(Dict)
print;print 'Number of valid Decrypted Text: ', len(Dict)
print;print 'Total number of decryption performed: ', count

Output:

plain text:  abcdefgh

Actual key:  go6oMkCG

Cipher text:  JB1a3osG+es=

Analysis:
{'key: 0UUvjzLw': 'Valid Decrypted Text: mzptBVo4',

 'key: 2beOXKN1': 'Valid Decrypted Text: Yhz3jIL8',

 'key: 3Eq7MKwu': 'Valid Decrypted Text: GA9BTdzy',

 'key: 3jUQPXs8': 'Valid Decrypted Text: 3gCa3KBG',

.

.

Number of valid Decrypted Text:  36

Total number of decryption performed:  2275140

Is there any better to sort out such keys. Such keys may be valuable to strengthen cryptography by introducing confusion

Here is the problem. For a specific ciphertext, sure you could try a bunch of keys and output the couple that result in the type of plaintext you want. But what does this really get you? For a different ciphertext, likely these same keys will not result in the same type of plaintext you desire.

Recent work on honey encryption might be what you are really looking for. It is still very new, so it should not be used in a production system without understanding all the intricacies. The authors of the paper also provide some nice theoretical foundation for the area.


For a typical n-bit symmetric key, how many keys would be considered too weak to use? I understand that all zeros or all ones would be weak for any cipher. And certain ciphers, e.g. DES, have a list of weak keys. But I assume that there would many 'patterns' that would be detected (if that is the correct term) as weak. For example, 0x0505 ...05, 0x1010...01 and 0x0A0A...0A. Or other patterns such as half the key being 0s and the other half being 1s or half the keys being 3s and the other half being Cs (i.e. the compliment of 3.

A key must have a large number of patterns, so is there a way to calculate this number?

Are the patterns I mentioned above (and similar) weak keys?

I understand that all zeros or all ones would be weak for any cipher.

This isn't actually true. For good cipher there are no weak keys.

  And certain ciphers, e.g. DES, have a list of weak keys. But I assume that there would many 'patterns' that would be detected (if that is the correct term) as weak. For example, 0x0505 ...05, 0x1010...01 and 0x0A0A...0A. Or other patterns such as half the key being 0s and the other half being 1s or half the keys being 3s and the other half being Cs (i.e. the compliment of 3.

This isn't true for most algorithms.

More specifically you fall into thinking that number can either be random or not. Is 3 random? On a 1-10 scale? We humans easily assume that "1234" or "1111" isn't random. But what if it's just what came our of good RNG? Is RNG broken?

No, instead we are broken. We easily consider some things "too simple", while computers can just draw random number in range that is always random (if proper algorithm is used). It doesn't really matter if the number is 1, 5 or 283921. Algorithm design decides if numbers generated are good, not the number itself. Algorithm doesn't have to check for only 0bit keys, because chance that it generates this key is just as high as all other keys.

Now, why DES has "weak keys" then? Because those are keys that make algorithm perform poorly (encrypting again can undo effect for example). This shouldn't be case with good ciphers. We hope that Enc(K1,text) can only be undone with Dec(K1,text), not Dec(K2,text), nor Enc(K3,text) and especially not with Enc(K1,text) again!

  A key must have a large number of patterns, so is there a way to calculate this number?

Yes, random key in 128-256bit range is good. Any attempt at excluding keys like only zeros just limit how random your algorithm is.

  Are the patterns I mentioned above (and similar) weak keys?

No, DES weak keys come from how DES performs with those keys, not from how they look. If we found AES weak key of 0x28357129912581823923, this would be weak key because of how it works in algorithm, not because it looks non-random.

If we speak of "weak key" as in keys that aren't random enough, then it only comes down to how you generate those keys, not what those keys are! (Any key you get is not random then).


NIST SP800-108 KDF modes comparison According to NIST SP800-108, there are three modes that can build KDF from PRF: counter mode, feedback mode and double-pipeline iteration mode. Assume that the same PRF and input distribution are used, will the three different modes make any difference on security strength of the resulting KDF? Here the security strength aims at the unpredictability of the output and the threat model includes side-channel attacks. Thanks.

It is very likely that in practice this doesn't make much of a difference. I haven't seen any implementations in hardware devices of the more intricate modes (check the FIPS certification pages for info on this). Mostly the CTR mode is used, then the feedback mode. Many HSM's only implement one of the three, making all HSM's nicely incompatible to each other (thanks NIST for not indicating a default, even after being pointed out the problem!).

As indicated in the comments, these KDF's are build upon primitives which should already be protected against side channels. If unsure which primitive to choose, it would make sense to choose the one where the primitive is most resistant. In principle even a copy of bytes to another memory location (write!) can be vulnerable to side channel attacks. However generally speaking the KDF is secure if the underlying primitive is secure. It could be wise to go for a hash function if no hardware acceleration is available for a block cipher, as most hashes seem less vulnerable to side channels in software. On the other hand, the cipher may receive more attention to protect against them - without a specific system there is no strong recommendation can be made.

KDF's build from a PRF (instead of a hash) are relative strong constructions. So it may be that the double pipeline KDF is stronger than the other two, but basically the constructions are strong enough for any purpose anyway, so it makes some sense to choose the one that is easiest to implement. More complexity / a higher learning curve generally leads to a less secure system, after all.

Finally, as indicated, not every system implements all of the KDF's. It might be a good idea to look at the entire domain to see which implementations are available / secure / can be agreed upon with any other participants. Many systems won't have them at all, which again promotes simplicity over complexity. It's better to spend the time testing.


Strange modular expression in paper on group signatures I've come accross the following expression in a paper:

$$A_i=(C_2 * a_0)^{1/e_i} \bmod n$$

How to calculate $1/e_i$ in modular arithmetic?

Or does it have some different meaning that I do not know?

The paper is "A Practical and Provably Secure
Coalition-Resistant Group Signature Scheme" by Giuseppe Ateniese, Jan Camenisch, Marc Joye, and Gene Tsudik", on page no.9, step 4 of JOIN.

In this context $1/e_i$ (more commonly written as $e_i^{-1}$) stands for the multiplicative inverse of $e_i$ modulo the relevant modulus, which in this case is $\lambda(n) = \text{lcm}(p-1,q-1)$.  That is, $1/e_i$ is that value $f$ such that $f \cdot e_i = k \cdot \text{lcm}(p-1, q-1) + 1$, for some integer $k$.

Given the factorization of $n$, we can compute $1/e_i$ using the Extended Euclidean method.

We also believe that that $(C_2 \cdot a_0)^{1/e_i} \bmod n$ cannot be computed without knowing the factorization $n = p \cdot q$ (for general $C_2, a_0, e_i$); in fact, this is precisely the RSA problem.


How many blocks can securely be encrypted with XTS I could not find in the NIST recommendations on XTS how many blocks can securely be encrypted with XTS-AES.

Through the recommendations, I've found:

  The length of the data unit for any instance of an implementation of XTS-AES shall not exceed $2^{20}$ AES blocks.

The specification cited in NIST The XTS-AES Tweakable Block Cipher states:

  The number of 128-bit blocks in the data unit shall not exceed $2^{128}-2$. The number of 128-bit blocks should not exceed $2^{20}$.

From what I understood, data units are sectors, so a sector can have at most $2^{128}-2$ blocks but you can only encrypt $2^{20}$ blocks which cannot be correct (it seems too little compared to a disk's capacity).

From what I understood, data units are sectors, so a sector can have at most $2^{128}-2$ blocks but you can only encrypt $2^{20}$ blocks which cannot be correct (it seems too little compared to a disk's capacity).

The data unit is the sector, yes, but both of those quotes only talk about the length of a single data unit. The larger number in the latter reference ("shall not"), is an absolute bound, while the second ("should not") is a recommendation.

The recommendation from the second reference is that a sector should be no larger than $128 \cdot 2^{20}$ bits, i.e. 16 MiB. SP 800-38E makes this recommendation a requirement:

  The length of the data unit for any instance of an implementation of XTS-AES shall not exceed $2^{20}$ AES blocks. Note that Subclause 5.1 of Ref.[2] recommends this limit but does not require it.

(The ref above is to the IEEE standard based on the draft spec you linked.)

The total disk capacity encrypted can be much larger, since it consists of many sectors. For recommendations, you can see appendix D.4 of the second specification, where $2^{36}$ and $2^{40}$ (1 TiB and 16 TiB) AES blocks are mentioned.


Create broken chain certificates for testing In our software we receive certificates in binary DER format from our clients. They are in advance used to perform certain identity checks between server and client. To ensure the certificates are valid and trustable, we verify the certificate chain. Using the APIs we have available this is easily possible.

But the main question is: How can we create certain certificates which actually have a broken chain of trust or any integrity problems which should be validated. It seems easy to generate valid ones, but for testing our validation system we need invalid ones.

I would like to understand what to change on my valid certificate to introduce the previously mentioned errors. Can it be easily done on binary level or are there maybe tools for it? I tried to search for explainations but all I found was about how to fix already broken certificates. I expect either I need to change some bytes of the public key, or change the issuer details.

Personally I wrote a generic ASN.1 decoder/encoder tool. It is called DDer. It transforms a DER-encoded object into a structured text representation (with parenthesis, somewhat reminiscent of Lisp). The interesting part is that it comes with a companion tool, MDer, which performs the reverse transform. Thus, you can edit certificate contents with a text editor, and MDer will work out the encoding subtleties.

Now a tricky remaining part is the signatures. Certificates are signed, and changing any bit in a certificate invalidates the signature, so this calls for a signing tool. I happen to have written my own crypto library (in C#, not published yet) that can apply a signature on an arbitrary DER-encoded object, even patching the inner SignatureAlgorithm in the to-be-signed structure of a certificate.

In a hurry, though, a RSA signature can be computed "by hand" with the help of the dc utility which is standard issue in Unix-like systems. That calculator can use hexadecimal input and output, process arbitrarily long integers, and compute modular exponentiations with the integrated | operator. Workflow would be:

Create the to-be-signed structure in the text representation of DDer, and use MDer to convert it to DER. When dabbling with certificates, you usually start with an existing certificate, so DDer-ize that.
Use sha256sum (another standard command-line tool on Linux) to compute the SHA-256 hash of the to-be-signed.
Assemble the hash value in a properly padded structure as befits RSA. You want to make it in hexadecimal, in a text editor. Make sure that all your hexadecimal is uppercase with no extra spaces, because that's what dc feeds on.
Use DDer on the private key file to obtain the key elements, specifically the modulus (first big integer) and the private exponent (third big integer in the structure)(the second big integer is the public exponent and is usually not that big).
Use dc to compute the modular exponentiation. You switch dc to hexadecimal input and output with 16 i 10 o (which reads as "set input radix to 16, then set output radix to 10"; that "10" is interpreted in hexadecimal, since you just switched the input radix to 16!). You then copy&paste the operands (padded hash, private exponent, modulus, in that order), and compute the modular exponentiation (|). You use p to print the result, which will be in hexadecimal.
Back to the DDer text representation of the to-be-signed, you write the wrapping structure, which is a SEQUENCE that contains the to-be-signed, an AlgorithmIdentifier that identifies the signature algorithm, and a BIT STRING whose contents are the signature value. MDer will expect the BIT STRING contents to be in hexadecimal, just like what you just obtained from dc, so it's a matter of copy&paste (again).
And a final MDer to produce the final certificate, DER-encoded.
If you need the new certificate in PEM format, convert with with openssl, or directly with the base64 tool (again a usual command-line tool in Linux) and add the -----BEGIN CERTIFICATE----- and -----END CERTIFICATE----- lines manually (this may be necessary in case you purposefully made an incorrectly encoded certificate, that openssl won't accept to convert).

If you can go through all these steps in due order, then you know enough about RSA and ASN.1 to write your own tools to apply signatures. If using C#, you can reuse the ASN.1 library from DDer, as well as the big-integer class (ZInt) for some very basic and perfunctory RSA implementation (not secure enough for use in production, but usable for making test cases).


Can I use a block cipher in CTR mode to generate keys from a master key? Suppose I have an AEAD mode based on a block cipher that requires two or more keys.

In some cases, there is a complex proof that one key suffices.  But finding such a proof is hard.

An alternative is to use the block cipher in CTR mode to generate a pseudorandom stream from a master key, which is then split as needed into the needed keys.  It seems to me that this is always secure (assuming that the block cipher is itself secure, which you almost always are assuming anyway).  It is also simple to implement in both hardware and software, allows you to use a longer nonce, and helps with birthday attacks if the extra nonce (used for CTR mode to generate the subkeys) is itself a "nfewtimes" (I don't think the distinguisher against CTR mode is of any use to an attacker until most of the full codebook is exhausted).

Is this recommended?  Assuming you can't just use EAX or CCM, that is.

As Maarten Bodewes points out, you should use a known key derivation function instead of this method (i.e. don't roll your own crypto). Having said that we can still try to understand what happens if you do use this method.

I assume that the method you're describing is something as follows. You take a block cipher $E:\mathsf{K}\times \mathsf{X} \to \mathsf{X}$, and a master key $K\in\mathsf{K}$ and then generate subkeys using
$$K_0 = E_K(0), K_1 = E_K(1), K_2 = E_K(2), \ldots\,,$$
where $0$, $1$, $2$, $\ldots$ are distinct strings in $\mathsf{X}$.

If you only use the subkeys $K_0,K_1,K_2,\ldots$ as keys in the mode, there should not be an issue, since you're basically using the block cipher as a key derivation function. In order to do this, all you need to assume about the block cipher is that it is a secure pseudorandom permutation when keyed with $K$, $K_0$, $K_1$, $\ldots$. This, of course, also assumes that it is meaningful to use the output of $E_K$ as its key, which you can do for AES128, but not immediately with AES256 (you would have to use two block cipher outputs as a key).

However, the downside to the above approach is that you have to switch keys a few times, which might not be so bad depending upon the application, but is undesirable in general. The optimizations performed by modes such as GCM, EAX, and OCB make it so that you do not need to switch block cipher keys. Their trick is to use $E_K$ and the value $L = E_K(0)$ (or something similar) alongside each other in the mode, without ever using $E_L$. In particular, to ensure security this means that the mode needs to avoid outputting $E_K(0)$ as part of a ciphertext or tag, since then you've released $L$ to the adversary.

Just to be clear, neither method will help you against birthday attacks on the mode. As long as the master key stays the same, you will still find attacks with birthday bound complexity. Also, I don't immediately see the benefit in using a longer nonce, since the number of messages you can process using a key is often well below the number of nonces you can generate using half of a block length. For example, your nonce does not need to exceed 64 bits when using AES128 in GCM, since the birthday bound limits you anyway.


Signature based on public key cryptography and forgery In the definition of existential unforgeability, there is no detail about the following questions.
In general, can we suppose that a signer is also a possible adversary? When generating a signature, can we suppose that the signer behaves well?
More precisely, suppose that a signer can generate a signature that is valid for another document of his choice. Despite this, for a correctly generated signature, suppose that the signature scheme used is secure when considering an adversary who is not the signer; that is to say, this adversary cannot generate a signature for any other document. Is this signature scheme considered secure?
What is the standard (conventional) hypothesis about that?
I update in reaction to the comment:
In fact,

If the signer behaves well, then the signature is unforgeable (for the signer or any adversary who is not the signer).

If the signer misbehaves, then the signature is forgeable (for the signer, without using the key, and for any adversary).

Is this kind of scheme considered secure in the sense of existential forgeability? Can we suppose that the signer behaves well?

The standard definition of existential forgery allows the adversary to ask and obtain the signature of any message she wants, and claim success if she can exhibit (with sizable odds) any acceptable (message, signature) pair, for any message for which she did not ask signature.

Update: There is also strong existential unforgeability, where the adversary should not be able to exhibit any acceptable (message, signature) pair for which she did not obtain that signature by asking for the signature of that message. For a use case making the headlines where that strong makes a huge difference, see these links.

Note: in a signature scheme with message recovery, any fraction of the message embedded in the signature needs not be exhibited by the adversary, and is as obtained by the verifier for the purpose of comparison to what the adversary submitted.

Corrected: If "a signer is able to generate a signature which is valid for an other document (that is, message) of his choice", then that scheme is vulnerable to existential forgery. The adversary obtains the signature of the first message, submits that signature unchanged together with the second message, and wins with 100% odds the existential forgery game. Oh no, only the signer could do this, using access to the private key!

Existential forgery is the strongest a strong theoretical criteria for signature. However, it assumes that the signer does not misbehave beside allowing the signature of arbitrary messages; in particular, it is assumed that the signer (or the Smart Card used for signature) does not leak the private key only uses the private key as prescribed, and properly implements every step in the algorithm, like generating truly random numbers.

Update: This spot-on comment by Ricky Demer gives names of security criteria for signatures protected from some attacks by the signer / private key holder.

Update: as pointed by DrLecter in a comment, the standard way to model the signer for a scheme secure against existential forgery (we also say: secure under chosen message attack) is as an oracle that accepts any message and outputs its signature. That oracle is assumed to implement the signature scheme exactly as specified. For more details, I refer to DrLecter's thesaurus of signature security models.


How use multiple keys to sign the same document? I’m thinking about create one software, that will need the user to sign each document, using Ed25519. I need to create something that is secure and simple. Requering use a HSM is not viable and hardware implementation of Ed25519 is closely to nonexistent, and common users not have it.

Considering it, the key will be stored (in the encrypted way) on the computer and the signature operation will occur in the same machine. I don’t think it is safe enough. To create something “more secure”, and still accessible: the user can add more devices, more keys, that need to sign the same document.

One user can have two keys, one it is stored on the computer and another key on the smartphone, for instance. The attacker, in this situation, need to steal two keys, which can increase the difficult, a little bit.

What is the best (the safest and easiest) way to create a multi-signature?

I can use something like S(M, K1), S(M, K2) ... S(M, Kn). I think it will work, because the Message will be Signed by multiple Key, and we only need to append all these signature at the end. To verify, only require to compare all signatures with the same text and check against the public key. I'm not a cryptographer, so I'm a little bit worried if something is wrong.

Have a more elegant solution? Have something that can be wrong in this previous approach?

The main goal is:

Stealing all keys, except one, we still safe. We are safe until the attacker gets access to all the keys.
Signature operation need to occur where the key are stored, we can’t share a private key between the devices, or trust in a single device to perform the operation.
Uncomplicated way to verify the signature. Everyone, including the software, can easily verify that was signed by all these keys.

Note:

Keys, already compromised or not, can't be removed/revoked. All keys will be trusted forever, or until the signature algorithm has been broken.

Teach the verifier what set of keys must sign a document for it to be valid.  When the verifier receives a document, it must have a valid signature by every one of those keys affixed to it.

Then before a verifier will accept a signed document, the possessor of every one of the signing keys must sign it.

That's it.  That's enough for the security properties you've described.

It's not the most efficient scheme.  There are more efficient schemes, e.g. in an earlier answer I wrote to a related question, but this will satisfy the security properties you asked for and can be built out of any ordinary public-key signature scheme.


Is MAC required with Sign-then-Encrypt? Consider a scenario where a message is sent encrypted and signed using public-key cryptography.

When using asymmetric encryption, you end up also using symmetric encryption if the message is large (hybrid encryption), which raises the question: is a MAC required?

I'm aware that not using a MAC when using Encrypt-then-Sign can lead to vulnerabilities such as the one described in the "Dancing on the Lip of the Volcano: Chosen Ciphertext Attacks on Apple iMessage" paper.

However, if you use Sign-then-Encrypt, are there any known attacks when not using a MAC?

As with all things, the answer is "it depends".

If you're using a block mode with no padding (such as CTR or CTS) then you're probably fine.  The ciphertext length is the plaintext length, your hashing time is a function of the known length, and you return "error" on tamper.

If you use a block mode WITH padding (CBC, ECB, etc) then you're not so fine.  By using StE (or MtE) the recipient has to deal with the padding BEFORE knowing if it was a tampered message.  So let's say that I'm a bad actor and I tamper with your message en route.  I tamper wherever I need to tamper to mount a padding attack and observe results:

If you reply "padding failure" then you are a true padding oracle, and I chortle and attack you very quickly.
If you reply "error" sometimes in 'significantly' less time than others then you are checking the padding before starting the hash, and you have a noisy timing-based padding oracle.  I smirk and attack you.
If you reply "error" at almost always the same rate, but some more slowly than others, then I have hit the boundary condition between your plaintext interpreted padding length and the digest's padding length.  You have a whispering oracle, and I grumble and attack you anyways.  For good measure I fire up a botnet and DDoS you when I'm done, because you pointlessly annoyed me.

There's no situation where you win in online scenarios.

Note that this answer didn't care if you did asymmetric signature, MAC, or just a simple digest.  You processed untrusted data and leaked info via a side (or direct) channel.

In offline scenarios there's not much room for oracle attacks, so you will reliably detect an error induced in the storage layer.  Huzzah?

The right answer for padded block cipher modes is always EtM.  That way every tamper is rejected at the same time interval, and now the attacker is left with brute forcing for success (which is fairly improbable if your MAC is in the 128+ bit space).

To relate to the Apple problem:  An asymmetric signature is a valid message authentication code (some people reserve "MAC" for excluding asymmetric signatures).  The problem, as also related in Do I need to use a MAC with asymmetric encryption?, is when you don't have an association of WHO is allowed to sign the particular message.  Using a HMAC/etc only changes the equation by forcing the recipient to know a priori what key will be used. Binding the public key of the expected signer a priori solves the problem similarly.


Intuitively what makes indistinguishability obfuscation useful? I am reading some papers about the application of indistinguishability obfuscators (IO). As far as I know, there are two techniques which enables the application of IO: shell game of secrets and punctured programs. It seems to me obfuscators are meant to make the program as close to a black box as possible, but it is known black-box obfuscation is not possible for some circuits.

I think the question is about how to force the adversary to learn by making queries. For example, standard PRFs are built upon black box model, and it is straightforward to prove the security based on some query complexity lower bound. To apply IO in the non-black-box case, PRFs are built to be puncturable to preserve functionality and randomness. Though I can follow the mathematical proof, I don't see why punctured PRFs along with IO makes the adversary see the program like a black box. Could anyone give me some intuition how IO programs differs from black boxes?

Bottomline: it is more appropriate to think in terms of indistinguishability rather than (black-box) simulation as indistinguishability obfuscation (IO) guarantees the former.

To see how IO can be useful, think of IO as a mechanism that "encrypts" the circuit (with the "encrypted" circuit being functionally equivalent to the original circuit), and its security requirement to be that for any two circuits that are functionally equivalent, the corresponding encrypted ciruits are indistinguishable.

In most applications of IO, the security argument involves showing that the adversary cannot tell the case where it is given the encryption of the actual circuit from the case where it is given the encryption of a "bogus" circuit.  As certain crucial parts have been removed from the bogus circuit, an adversary cannot have a significant advantage in breaking the bogus circuit. (And since the encryption of the actual circuit is indistinguishable (by IO) from that of the bogus circuit, security ensues.)

The above uses two ingredients: punctured programs and hidden sparse triggers.$^*$
The bogus circuit is usually constructed from the original circuit by "puncturing" the underlying PRF at the challenge. As a result, the bogus circuit behaves "randomly" at the punctured point. This modification could, inadvertently, lead to the bogus circuit behaving differently from the original circuit (and the security guarantee of IO goes out of the window). The way-around is to ensure that the point at which the puncturing takes place is hard to find using, for example, a PRG (i.e., sparse hidden triggers).

The construction of public-key encryption (PKE) from secret-key encryption (SKE) given in [SW14,§1,§5.1] is an excellent example which encapsulates the usefulness of this approach, and which I'd reccommend for further reading.$^{**}$

$^*$To quote [SW14], "the idea of the technique is to alter a program (which is to be obfuscated) by surgically removing a key element of the program, without which the adversary cannot win the security game it must play, but in a way that does not alter the functionality of the program."

$^{**}$ This highlights another point of why IO is so powerful: it is known that PKE cannot be constructed from SKE in a black-box manner, but since IO uses the circuit of the underlying SKE, the constrcution is non-black-box and helps bypass the separation.