Zk-SNARK against Sigma Protocols and for Secure Function Evaluation I have a couple of questions on ZK-SNARK:

Based on what I understand, a ZK-SNARK is an "Argument of knowledge". That means that it should be equivalent to Sigma Protocols like Fiat-Shamir and Pederson committments, RSA Accumulators, and even attribute-based encryption, correct?
I've read in a few places, like Prof. Bill Buchanan's intro, that a ZK-SNARK could be used to "delegate" a function in order to have a 3rd-party (call her Alice) to calculate a function without her knowing what she is calculating. For example, we can calculate the function aX + bY, if X and Y are private to Alice. We can do this by using homomorphic encryption around Enc(aX + bY), to which we can calculate Enc(aX) * Enc(aY), given that a and b are public. In this case, we will know the result of aX + bY without knowing X and Y. Is that a correct representation of Zk-snark (AKA: Secure Function Evaluation)?

Did I mix up too many categories together?

Many thanks in advance

Did I mix up too many categories together?

Yes :)

A ZK-SNARK is a method to let a prover demonstrate to a verifier that some statement is true (e.g. "this ciphertext encrypts a number between 3 and 5"), with the following properties:

correctness and soundness: (assuming the prover has bounded computational power) the proof is convincing if and only if the statement is true
zero-knowledge: the proof only leaks the information that the statement is true, nothing more
non-interactivity: the proof is a single message from the prover to the verifier
succinctness: the size of the proof is much smaller than the size of the witness for the statement (e.g. in my previous example, the "witness" could be the secret key of the encryption scheme), and verifying the proof is much faster than directly checking the statement, even given the witness.

A $\Sigma$-protocol is a zero-knowledge proof as well, but with very different properties:

unlike a ZK-SNARK, it is interactive (three moves)
unlike a ZK-SNARK, it is not fully zero-knowledge (but only honest-verifier zero-knowledge)
unlike a ZK-SNARK, it is not succinct

On the positive side, $\Sigma$-protocols exist unconditionally (ZK-SNARK require ultra strong assumptions) and do not need any trusted setup (ZK-SNARKs require a common reference string).

Now, regarding the many things you mentioned:

Fiat-Shamir is not a $\Sigma$-protocol, it is a technique to transform a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). Note that $\Sigma$-protocol + Fiat-Shamir does not give a ZK-SNARK, because the NIZK is not succinct in general.
Pedersen commitments are not $\Sigma$-protocols, they are commitments - a "cryptographic box" in which you can put a message so that it stays hidden, but which cannot be opened to a different message. They are used a lot to construct the statements we want to prove with $\Sigma$-protocols in high level applications. Typically, you will put many secret values involved in the protocol in these "cryptographic boxes", and use $\Sigma$-protocols to demonstrate that these (hidden) values satisfy some relations.
ZK-SNARKs are not "used to delegate functions", but they are useful when you have a delegation scheme and want to make sure that the server was honest. However, we usually don't really care about the ZK part for this application; what we care about is the succinctness. Here is a typical example: there is a super complex function $f$, you have $x$ and want to compute $f(x)$, but it costs too much. So, you send $x$ to a powerful server, who computes $y = f(x)$ for you and send you the result. But you do not trust the server, so to convince you that the result is correct, the server also sends you a proof that the statement $y = f(x)$ is correct. Here, the core property for this scheme to be useful is that checking the proof should be much faster than computing $f(x)$ yourself (otherwise there would be no point in delegating the computation in the first place).

Note that $\Sigma$-protocols are not succinct, so they are useless for the application to delegation of computation. Secure function evaluation has also nothing to do with that. Secure function evaluation is used in delegation when you want to hide the input $x$ from the server (so the server should compute $f(x)$ for you without seeing $x$). This is an orthogonal problem; what ZK-SNARK solve is the problem of letting the server prove that he computed the right value. This can be done independently of whether the server is doing the computation "blindly" (using some secure function evaluation technique, e.g. homomorphic encryption) or in the clear. Hence, SFE and ZK-SNARKs are just completely different, both can be used to solve different problems related to delegation.

RSA accumulators and attribute-based encryption have nothing to do with all of that. If you have ZK-SNARKs, you can build accumulators, but that's it. RSA accumulators are just a specific type of accumulators, and one that does not use ZK-SNARKs. Attribute-based encryption is an advanced cryptographic primitive that might use other simpler primitives in some existing constructions, but in general it has no formal relations to ZK-SNARKs.


The benefit of PBKDF2 for big keyfile? The man page of cryptsetup says:

  Whenever a passphrase is added to a LUKS header (luksAddKey,
  luksFormat), the user may specify how much the time the passphrase
  processing should consume. The time is used to determine the iteration
  count for PBKDF2 and higher times will offer better protection for
  low-entropy passphrases, but open will take longer to complete. For
  passphrases that have entropy higher than the used key length, higher
  iteration times will not increase security.

Does it mean that a binary keyfile of more than 64 random bytes (each having 8 bits of entropy?) is useless with PBKDF2 and a hash of 512 bits like SHA-512? The cost of testing all the hashes directly being cheaper than testing all the keyfiles.

Does it also mean that reducing the iteration time to 1 millisecond (or just to 1 iteration if it's even possible?) for such a keyfile doesn't affect the security?

And finally does it mean that using PBKDF2 with such a big keyfile, by reducing its size to just 512 bits, actually lower the security of a LUKS header?

Does it mean that a binary keyfile of more than 64 random bytes (each having 8 bits of entropy?) is useless with PBKDF2 and a hash of 512 bits like SHA-512? The cost of testing all the hashes directly being cheaper than testing all the keyfiles.

Yes, it does. After 128 to about 256 bits security the amount of security provided by the bits alone doesn't make sense anymore (impossible is impossible).

  Does it also mean that reducing the iteration time to 1 millisecond (or just to 1 iteration if it's even possible?) for such a keyfile doesn't affect the security?

Yes, if the input does indeed have that much entropy (and is therefore not really a usable password or passphrase), then you might as well perform one operation per ms. Or much faster.

  And finally does it mean that using PBKDF2 with such a big keyfile, by reducing its size to just 512 bits, actually lower the security of a LUKS header?

No, that's unlikely. The amount of information lost by performing many, many operations is still minimal, so you will probably maintain the security of the underlying HMAC.

Note that security proofs like salts. Removing the salt entirely may make the calculation - at least theoretically - less secure. So it is probably best to replace the password hash with e.g. HKDF, a key based key derivation function that optionally takes a salt.


Can ChaCha be turned into a collision resistant hash function by xoring keystreams? In his paper about RFSB Bernstein states that the compression function

$(m_1,\ m_2,\ m_3,\ ...\ ,\ m_n) \rightarrow c_1[m_1]\ \oplus\ c_2[m_2]\ \oplus c_3[m_3]\ \oplus\ ... \oplus\ c_n[m_n]$

is surpsingly collsion resistant. Reading this paper, I asked myself weather one can use ChaCha with increasing counter instead of arrays to reach nonlinearity. To do so, one would use the alternative initial matrix

k k k k
m m m m
m m m m
c c c c

where $k$ are the constants provided by Bernstein, $m$ is the message (which takes the place of the key) and $c$ is the counter which was expanded to 128 bit since there is no need for a nonce in this scheme. The usual ChaCha algorithm is applied to this matrix.

Obviously, the maximal message length should be $2^{128}$ message blocks of 256 bits each (minus padding) to prevent counter overflow.

Also an attack who intercepts a hash $h$ and knows one message block and its position is easily able to replace it by calculating $h' = h\ \oplus\ ChaCha(m, c)\ \oplus\ ChaCha(m', c)$.

However, if the attack want's to perform a second preimage attack on $h$, he basically would have to find a $m$ with $ChaCha(m, 0) = h$, which is as hard as recovering a key from a 512-bit ChaCha keystream. The attacker can  control the counter by adding dummy-blocks, which may give him an advantage given that reduced-round versions of ChaCha have differential characteristics.

However, when it comes to finding any collision, I'm not sure whether you would be able to find a collision with less than $2^{256}$ (birthday attack) calls to the compression functions.

The only expectation for each $c_i[m_i]$ is that it's independent and uniformly random. ChaCha20, with the nonce/counter words acting as table index is perfectly fine here, under standard assumptions about ChaCha20. Furthermore, the $m_i$ are expected to be small—in RFSB, they are 8-bit wide—so you can put the message in the counter just as well.

As an example of using a larger message as input to each function, you may also look at Rumba20, $$\text{Rumba20}(x_1, x_2, x_3, x_4) = f_1(x_1) \oplus f_2(x_2) \oplus f_3(x_3) \oplus f_4(x_4)\,,$$ which instead uses different constants to differentiate between the 4 different input blocks, and uses 384 bits of each Salsa20 block as input.

Note that if you let the number of xors ($w$ in the RFSB paper) grow too much relatively to the output size ($r$), the compression function can become weak. This is discussed at length in Section 4.

Note also that either of these compression functions only attempt to be collision-resistant. Other properties, such as preimage resistance, need to be ensured by some other mechanism, as the papers stress.


In differential cryptanalysis for DES, why is F(0...0) assumed to be always 0...0? In this paper about differential cryptanalysis, an attack on 2n-Round DES is described.

The attack is all about finding certain inputs for DES rounds, for which the output of the round function Fis equal to the input with high probability.

For the inputs given in the paper, one half is always assumed to consist of only zeros. Also, it is assumed that the round function for that all-zero input always yields zero with probability one:

F(0...0) = 0...0

To my understanding the round function F works as follows: Expand the input, then xor the key, then perform substitutions. That conflicts with the assumption described in the paper.

How can the round function always yield zeroes for an all-zero input, independently of the key?

The question arises from a misunderstanding: The attack described in the paper does not work with actual inputs and outputs, but with differences between them. Hence Differential Cryptanalysis.

Given two messages m1 = (l1, r1) and m2 = (l2, r2) with equal right halves r1 = r2, it obviously follows that r1 - r2 = 0...0 and F(r1) - F(r2) = 0...0.


Why use $(r,s)$ instead of $(r,s^{-1})$ as DSA signature? A DSA signature consists of two scalars $(r,s)$.

When signing $s$ is generated as:

$s=k^{-1}(H(m)+xr) \mod q$
The signature is $(r,s)$

When verifying $s$ is only used to compute $w = s^{-1}$. So why does DSA store $s$ in the signature instead of $w$?

Using $w$ has no performance effect on signing since computing either $s$ or $w$ requires one modular inversion. $w = s^{-1} \mod q = k (H(m)+xr)^{-1} \mod q$.
It would speed up verification since the modular inversion to compute $w$ isn't necessary anymore.

The only advantage of $s$ I see is that the modular inversion can be computed before the hash is known. Did the DSA designers consider that pre-computation more important than the verification slowdown, or is there some other advantage of using $s$ that I don't see?

Well, it's been an entire day, and no one has given an authoritative answer; I'll throw in my guess as to why the people designing DSA made the choices they did.

With DSA, there are three operations that are relevent to this discussion:

A: do precomputation of a signature (without seeing the message being signed)
B: given a precomputed signature and a message, generate the actual signature
C: verify a signature.

Standard DSA and your variant DSA perform exactly the same operations, except that standard DSA computes a modular inverse during steps A and C, while your variant computes it at step B.

It is true that standard DSA does two modular inverse, while your variant does only one; however, that may not be the only factor.

If we look at step B, we see that the operations involved at quite cheap (a single modular multiplication and addition); if we were to include a modular multiplication operation there, we would increase the cost of that operation by a large percentage.  In contrast, steps A and C are already expensive (involving a modular exponentiation or point multiplication); including a modular inverse only slows down those operations by a small percentage.

That is, DSA has the property that, with precomputation, generating a signature is extremely fast.  Your variant significantly reduces this advantage; the DSA designers designed to keep this advantage, even at the cost of increasing the total computation required.

Now, you may disagree with the above logic; in fact, people have proposed a DSA-variant exactly like what you suggest.


Why the contrapositive proves a given hash is collision resistant? So I am working on a problem as follows, it's a pretty basic standard question that I think I figured out, but I am confused as to why it works out the way it does.

Essentially, we are given a hash function $H$ that is collision resistant and maps to a fixed output length.

We want to create a new hash $H'$ such that

$H'(n) = H(n)||x$

Where we say, $x$ is just a random string of a given arbitrary length $m$.

Now what I think is the right thing to do is to use the contrapositive to say, if $H'$ is not collision resistant, than we can build an adversary to work in time ε. Thus we can alter our adversary easily by just cutting off the last m bites to get an adversary to solve for $H$

My question is that why can't we just use a direct proof to solve this? Must we use a contrapositive? I believe that it has to do with proving something is secure is a lot harder than proving it isn't, but I'm unsure.

The reason is that you are trying to make a statement about the hardness of a problem. You want to prove

  A is hard $\Rightarrow$ B is hard

This is a statement about the non-existence of an easy solution. Every solution for A is hard. You want to show

  every solution for A is hard $\Rightarrow$ every solution for B is
  hard

Constructively tackling this problem would require showing that ALL solutions for B are hard but you probably do not even know all solutions.

By inverting the problem you get

  there is a non-hard solution for B $\Rightarrow$ there is a non-hard solution for A

which only requires a statement about all solutions of A. Which you happen to already have. Namely that there is no non-hard solution.


Differential privacy on multiple queries – what is the behavior? Differential privacy framework still continue to be obscure in the following case:

If I make a set of queries, I can join their output to restore the original data. For this issue we have composition theorems that grants that every query consume just a "piece" of my $\epsilon$, so we can continue to answer queries for the total query "session" until I have pieces of my $\epsilon$.

So, my question is: what does "session" means? An attacker can make many sessions?

I think that is not very realistic that an user (that can be an attacker) can access just for a single "session" of queries (if we intend for "session" a "set of query that an user can make") . He could find a system to make "many sessions" (for example with different identities or similar, or working together with other attackers).

So, in these cases, how differential privacy works? Is there something that I misunderstand?

It would be helpful to have a link to the paper you are referring to. But the basic composition theorem says that each query $i$ an attacker sends to the database will just add its corresponding $\varepsilon_i$ to the total $\varepsilon$ of the entire process: $\varepsilon=\sum_i\varepsilon_i$. So "session" probably means "single query" in the context of your question.

And yes, your objection is a good one. If you use differential privacy in an interactive context, then you need to either:

split your total privacy budget across all users (and when it runs out, stop anyone from querying the database);
or assume that your users are not collaborating, and have some authentication in place to make sure each user cannot go above the privacy budget by connecting to the system as multiple people.


Types of Cryptography for a 4-8 bit microcontroller This is more of a research question.

I was wondering what types of crypto algorithms would work best on a small 4-8 bit micro controller.  I recently read a paper called Security Considerations for 802.15.4 Networks and was wondering if anyone out there can think of any other papers or has knowledge about what types of things to consider when implementing cryptography on a low-power, low-memory system.

I read a 2009 ieee paper on implementing RFID on a 4-bit micro controller, but I am looking for papers that will generally apply towards 802.11 or 802.15 standards.  I will propablly be trying to hook a bunch of these controllers together, so I am looking for more of asymmetric encryption.

Public-key encryption on microcontrollers

Erik-oliver Blaß ,  Martina Zitterbart.
"Towards Acceptable Public-Key Encryption in Sensor Networks". 2005.

"dsPIC DSC Asymmetric Key Embedded Encryption Library"
an implementation of RSA, Diffie-Hellman, DSA, SHA-1, MD5.
(Are such 16-bit microcontrollers in your range of interest?)

"Links to Embedded Crypto Implementations"
lists a few implementations of RSA on 8 bit microcontrollers.

"full size" symmetric ciphers on microcontrollers

Many people implement cryptography on a microcontroller very similarly to cryptography on any other CPU -- write a program to do encryption or decryption using the same ciphers we use on any other CPU.
Quite a few modern 8-bit microcontrollers have enough program memory (often called "ROM" for historical reasons, although today it's usually Flash memory) and RAM and processing speed to handle the full Advanced Encryption Standard (AES)(a)(b)(c)(d), Triple Data Encryption Standard (3DES)(a)(b), Enigma(a), RC4(a),
as well as less-known algorithms
such as Alexander Pukall’s PC1 (a).

symmetric ciphers designed for low RAM

Quite a few microcontrollers have 256 bytes of RAM or less. A few full-size ciphers work just fine, but ciphers like RC4 seem impossible to implement in this environment.
A few symmetric ciphers seem specifically designed for this environment -- KeeLoq, TEA, XXTEA, etc.

Other cryptographic techniques for microcontrollers

A few bootloaders for embedded systems use encryption.( "USB PIC Bootloader with XTEA encryption" )

Rather than doing the encryption in the CPU itself, a few systems have an external chip that does crypto stuff.
( CryptoAuthentication, CryptoMemory, Trusted Platform Module, etc. )
Such dedicated circuitry, hard-wired to perform some calculation, often requires significantly less power than a more general-purpose CPU programmed to perform the same calculation.
This way newly-introduced bugs in the software on the main CPU can't possibly leak the secret keys stored in that external chip, or introduce new flaws (new timing attacks, etc.) in the algorithm implemented in that external chip.


With a true random number generator at hand, how to implement one-time pad? I have a Raspberry Pi single-board computer that happened to have an hardware true random number generator, based on some quantum effects on the processor silicon, baked into its BCM2835 chip and I can pump its randomness by dumping bits from /dev/hwrng device in Raspbian, its Debian-based Linux operating system.

Now let's say I want to implement some sort of one-time pad scheme using this little piece of hardware as a randomness generator. How?

There are four concerns here:

Pad generation
Pad transmission
Message privacy
Message authenticity

Pad generation

The security of the one-time pad depends on the assumption that the pads are generated from a truly random source.

This is actually quite a big ask. Suppose for a moment that you want to exchange a 4 gigabyte pad. Let's say your RNG does that one byte at a time. What you're basically asking is for billions of iterations of the RNG without any kind of generation failure.

Worse, the RNG can fail in a way that is not immediately obvious or detectable. The Debian bug springs to mind here.

Or, more directly, a nation state could deliberately weaken your RNG.

Pad Transmission

The next problem is finding a secure way to transfer the pad. The pad will be longer than the message you wish to transmit, at least if you want to be able to detect alterations to your message. See below.

This immediately raises the question of what one hopes to gain by using the OTP. If you have a secure channel capable of transmitting a pad longer than the original message, why not just use this channel to transmit the message?

Given this logic, there is only really one use for the OTP, which is to time-shift a secure channel. For example, I might be able to meet my friend in the pub and give him a terabyte of pad but afterwards he might be abroad for two years.

Message Privacy

Assuming you've solved the problems of generation and transmission, next comes actually encrypting your message. This is the most straightforward piece of the whole exercise.

You just work through your message a word at a time and logically XOR that word with a corresponding one from the pad. No part of the pad may be re-used under any circumstances. It's best to have your program destroy the read section of the pad after completing the encryption operation.

Decryption on the other end is exactly the same process. Simply logically XOR the cipher-text with the pad to recover the plain-text. This works because XOR is its own inverse:

A XOR B XOR B = A

Message authenticity

One of the things that trips up amateurs is that encrypting your data doesn't means that nobody can undetectably alter the message in transit.

Suppose that an ATM used the OTP to encrypt its communications but no authentication. I have £0 in my bank account but I ask the ATM to give me £500. The bank replies with a single bit message which indicates whether the withdrawal is authorised or not: 1 for yes, 0 for no.

I know the bank is going to decline me so at precisely the right moment, I flip the bit before it gets to the machine. The machine spits out the £500.

You get around this problem by having a message authentication code (MAC). This is an authentication code you tack on the end of the message which acts as a secure checksum.

If I tried to flip the bit on a message with a MAC protecting it, the checksum would not longer verify and the system would know something funny is going on.

To authenticate OTP messages, you probably want to use a universal hash. This allows you to retain the security proof on both the hash and the cipher-text.

Universal hashes are a whole series of questions and answer in their own right so I'm just going to say that you should read around the subject.

Conclusion

The OTP is one of these ciphers that lot of amateurs gravitate towards because it's "perfectly" secure.

However, in reality we don't deal with perfection. We often don't have a secure channel with which to communicate a pad. We often don't have an RNG that has a failure rate of fractions of a billion or trillion. There are often cockups that result in pad being re-used.

For all of these reasons, competent cryptographers never recommend an OTP.


Which RSA keys are actually attacked In practice? I understand that it is important to check how hard it is to attack RSA keys, but I assume at some key size attackers would not even try. Real attacks are carried out by exploiting mistakes in the whole process, not the cryptography.
The maximum key size attempted would obviously depend on the value of the protected secrets, and the cost to the attacker. What key size would a rational attacker try to break, if they knew they could gain $1000 / a million dollars / a billion dollars / a trillion dollars?
(Some part of the motivation: On a recent thread it was said that if you choose two primes p, q for RSA and p=q, then this would be absolutely insecure. But if  a 2048 bit key is a square, would anyone actually bother checking this? BTW I think RSA wouldn’t “work” if p=q).
PS. The recommended link in the comment gives some answer. I would think that records set by academics don't represent what's possible, because it merely shows hardware improvements and from an academic standpoint it is quite boring. For government agencies, who would use it to detect secrets, 1,024 bit seems to be not 100% safe to protect a secret that is worth it. For a small time criminal, it would be safe.
But part of my question is: Where is the point where nobody will even try to crack it - with the result that some stupid mistake making a particular code insecure would never be detected, because nobody tries?

This question is based on a false premise, namely, that the difficulty of breaking cryptography (involving a given key type) depends only on the size of the key. This is not how cryptography is broken. The weak point in cryptography is usually flaws in the implementation.
For example, one way RSA can go wrong is if the key was not generated correctly. Cases of keys that were generated using a random generator that was not properly seeded are depressingly common. For example, Debian shipped a broken version of OpenSSL for two years which resulted in there being only a tiny number of possible SSH keys. Surveys of SSH and TLS public keys have shown that a small, but significant proportion of servers have keys that were generated with insufficient entropy or with a flawed process, resulting in keys that can be broken easily. (An RSA private key is determined by two (pseudo-)primes, and the public key is their product. If two private keys share a prime, it's trivial to spot this from the public keys $p \, q_1$ and $p \, q_2$.) Linux has had a steadfastly broken interface to random generation, historically giving the choice between an interface that blocks needlessly and one that is insecure in one specific but critical moment (just after the first boot of a system) (modern kernels have a good interface in the form of the getrandom system call, but because it's harder to use than the historical interfaces, a lot of software relies on the historical interfaces). In addition to the RNG problem, there is flawed key generation code out there, for example not using enough iterations when testing primality (which is a probabilistic test), or using computational shortcut that make the private key easier to calculate from the public key than brute force (such as generating primes that are close to each other, which can be faster, but is insecure).
A larger key size can help mitigate against a broken key generation process. For example, generating a larger key will request more material from the RNG and this can help if the RNG is not well-seeded at the beginning but receives additional entropy over time. Generating a larger key can also help if the code takes shortcuts, because it may compensate the loss of security from these shortcuts. But not all flaws can be mitigated that way. When the RNG is not seeded properly and only a small number of keys are possible at all (as in the Debian-OpenSSL case, or in the case of many embedded devices without a hardware RNG), no increase of the key size will help.
In addition to the key generation process, another source of weaknesses is the use of the key. Asymmetric (and symmetric) cryptography is prone to side channel attacks, where properties such as the timing of certain parts of the computation leaks information about the key, or about the data that the key is protecting. A larger key can help against some attacks, because many side channel attacks need to observe a large number of calculations in order to extract enough information to reveal the key or the data.
Asymmetric encryption is also prone to protocol attacks. Asymmetric decryption is tricky because it combines the private key with an input that cannot be trusted since it could have been produced by anyone. This can allow oracle attacks, where the attacker sends an invalid ciphertext, and based on the message or the timing of a decryption error, learns some information about the key. The general principle of this form of attack on RSA was published in 1998 by Bleichenbacher and was still a concrete problem 20 years later. Modern communication protocols avoid asymmetric decryption in favor of key establishment protocols where, rather than encrypting a session key with a symmetric key, both sides arrange to derive the same session key from different computations that give the same result. But RSA decryption is still used in the wild in TLS up to 1.2 (this is deprecated, but still used by “middleboxes” that intercept and filter TLS traffic in enterprise networks).

if a 2048 bit key is a square, would anyone actually bother checking this?

Well, yes, of course. It's very easy to check. It's also easy to factor the key if $p \approx q$, and it's one of the obvious things an attacker would try.

Where is the point where nobody will even try to crack it - with the result that some stupid mistake making a particular code insecure would never be detected, because nobody tries?

There is no such point. If you generate a key without a proper RNG, or if you store your key insecurely, or if you use an implementation that doesn't properly protect against applicable attacks such as side channel leaks and glitches, or if you use a flawed protocol, your key may be vulnerable no matter what its size is.
“Nobody will even try to crack it” is not a useful concept. It's based on the assumption that attackers are stupid and work in isolation. They aren't and they don't. Where there's a possible attack, all it takes is one expert to write a tool to perform a sophisticated attack, and sooner or later a conveniently packaged version of this tool will be available for free or for sale.


some of my confusions about DDH assumption The wiki defines the decisional Diffie–Hellman assumption as follows:
Decisional Diffie–Hellman assumption
Consider a (multiplicative) cyclic group $G$ of order $q$, and with generator $g$. The DDH assumption states that, given $g^a$ and $g^b$ for uniformly and independently chosen $a$,$b$ $\in \mathbb{Z}_q$, the value $g^{ab}$ "looks like" a random element in $G$.
This intuitive notion is formally stated by saying that the following two probability distributions are computationally indistinguishable (in the security parameter $q$):

$(g^a,g^b,g^{ab})$, where $a$ and $b$ are randomly and independently
chosen from $\mathbb{Z}_q$
$(g^a,g^b,g^c)$, where $a,b,c$ are randomly and independently chosen
from $\mathbb{Z}_q$.

some confusions about DDH assumption
my confusion doesn't lie in the group that hold the DDH but that does not hold the DDH. The Wiki says

Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb{Z}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the Legendre symbol of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element

poncho shows me how to do it. Next i will describe that in my understanding.
Given  $(g^a,g^b,g^{ab})$ and $(g^a,g^b,g^c)$, such that $a,b,c$ are are randomly and independently chosen from $\mathbb{Z}^*_p$. if $\left(\frac{g^a}{p}\right)=1\Rightarrow a\equiv0\pmod2$, and if $\left(\frac{g^a}{p}\right)=-1\Rightarrow a\equiv1\pmod2$ , so does $\left(\frac{g^b}{p}\right)$ and $\left(\frac{g^c}{p}\right)$. So there are one occasion that can be distinguished correctly : if $ab\neq c\pmod2$ then we can faithfully say that $g^{ab}\neq g^c$.
This is error-free as poncho said. But when $ab\equiv c\pmod2 $ happens, we can not distinguish $g^{ab}$ from $g^c$.That is to say, we can only partially distinguish $g^{ab}$ from $g^c$.
But in practical, does the DDH Oracle  really exist? if not, supposing the exist of DDH Oracle will mean nothing.  Or in other words, in the real word this Oracle is hard to realize  then  this kind of assumption will do nothing(this is only my personal thought)

A practical example
Next i want to use an example to illustrate my confusions.This protocol comes from here

The writer just say that  $\mathbb{G}=\langle g \rangle$(a cyclic group of order $q$) on which DDH problem can be efficiently solved. i guess that $q$ is prime. And i'm not sure whether the "on which DDH problem can be efficiently solved" refer to the method of  quadratic residue above. if so, there are many occasions that the DDH() cannot give a right answer. so i think the "on which DDH problem can be efficiently solved" does not have much meaning. i don't know if there exist other way to efficiently solve DDH problem, i really think that the DDH() cannot fully guarantee the answer's correctness in this example.
so who can help to clear these confusions?

For the Legendre symbol and DDH: when working modulo a prime $p$, you can have have a group where DDH (apparently) holds. Namely, suppose that there is a known prime $q$ which divides $p-1$, and $g$ has order exactly $q$. This is easy to achieve if you generate $q$ first, then look for a prime $p = qr + 1$ for some random values of $r$; then, to compute $g$, take a random $h$ modulo $p$ and compute $g = h^r$ (still modulo $p$)(if you end up with $g = 1$, try again, but probabilities are very low of this occurring). It can be shown that $g$ is a square modulo $p$, which implies that $\left(\frac{g^a}{p}\right) = 1$ for all $a$.

In fact, the Legendre symbol is just a special case of a more generic method. Suppose that $g$ has order $n$, and $k$ is a non-trivial prime divisor of $n$. Then, given $g^a$ for some unknown $a$ modulo $n$, you can compute $(g^a)^{n/k}$, which will be one of the $k$ values generated by $g^{n/k}$. This reduces DDH to a group of size $k$; if $k$ is small then DDH becomes easy. The method with the Legendre symbol really is the case $k = 2$.

By choosing $g$ to have a prime order $q$ exactly, this method is fully countered, and DDH is hard again.

For groups where DDH is easy, but CDH is hard: the method above is only partial: it makes DDH easy in some cases, in that it can detect some situations where a given triplet $(g^a,g^b,g^c)$ is not a DH triplet ($c \neq ab$), but not all. To have a group where DDH is invariably easy, but CDH still hard, you need some more mathematics. The only known really practical solution (so far) uses pairings on elliptic curves. This requires choosing curves with some specific characteristics.


How do mix networks work with server downtime? I am looking for an analysis of practical mix networks with server downtime.

For example, if a message is supposed to go from A -> B -> C -> D, what happens if B wants to send the message but C is offline temporarily?

This could be a stop-and-go mix network so holding onto a message longer is OK, but I am wondering whether there's any paper analyzing this sort of thing? For instance, how does it affect anonymity, how does B know when to retry sending it, etc?

Or what if C goes offline permanently, is the message lost? Is there a mix network protocol for resilience in this case?

It depends on your choice of mixnet, as to whether a mixnet is resilient in the case that C doesn't participate (for whatever reason, including system failures and adversarial behavior by C).

For onion routing, where the ciphertext is of the form

$enc(pk_A,enc(pk_B,enc(pk_C,enc(pk_D,m))))$,

the mixnet is not resilient, because $enc(pk_C,enc(pk_D,m))$ cannot be decrypted without participation of C.

By comparison, for a re-encryption mixnet, where the ciphertext is of the form

$enc(pk,m)$,

the mixnet works, since B can skip C and send directly to D. The resulting reduction in anonymity corresponds to reducing the number of mix nodes from four to three.


How do signatures or MACs achieve authenticity, integrity or non-repudiation？ Actually, I want to know whether there are explicit and formal definitions of the properties which are authenticity, integrity or non-repudiation.
It seems that the signatures and MACs can achieve the authenticity, integrity, non-repudiation and unforgeability. However, there is only an unforgeable experiment when we consider the security of signatures or MACs.
Q1: What about other three types of security experiments? Are there the formal definitions of the security experiments of the other three properties?
Q2: What are the relations among these four properties? (Anyway, how to prove the relation formally, if there are not a formal definitions?)
If the unforgeability implies the others which means that unforgeability is the strongest notion among these four properties, then I think I can regard this conclusion as the answer of Q1. If any pair of these four properties are separated, there must exist a scheme which only achieves any part of these four properties. (I know that a scheme which cannot achieve all these four properties is not secure. I just want to consider the existence of them in order to know the relation among these four properties.)

The 3 properties have commonly accepted meaning in Cryptography:

Authenticity: The message comes from the party associated with the verification key.
Integrity: The message had not been modified.
Non-repudiation: The signer cannot deny themselves signing the message.

We usually model the security against the weakest point of the signature/MAC - being forged; whereas other types of attacks such as key-recovery automatically implies the algorithm is insecure.

The unforgeability implies the other 3 (2 in case of MAC) properties, because the ability to forge a signature/MAC under a particular algorithm implies that

the message may come from someone capable of forging the signagure/MAC (authenticity),
capable of modifying a signed message (integrity), and
capable of signing messages against the wish of the holder of the private key (non-repudiation).


Taking $n-1$ bits from hash function will also be hash function? If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(x\right)$ is also collision resistant hash family?

Im thinking that $\mathcal{H}$ would not be collision resistant hash family but I cant find an exact counter example of $x \neq x'$ such that $W_{s}\left(x\right) = W_{s}\left(x'\right)$.
My guess was to prove using induction that we can deduce $k$ bits and still consided to be a collision resistant hash function, even if $k=n-1$ which will lead us to a function with image of 1 bit and that obviously wont be valid hash function.

If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(x\right)$ is also collision resistant hash family?

In general, no.

Let us assume that $\mathcal{H}'$ is a collision resistant hash family, and define $\mathcal{H}_k(x || b) = \mathcal{H}'_k(x) || b$, where $b$ is a single bit.

$\mathcal{H}$ is collision resistant (as a collision in $\mathcal{H}_k$ would imply a collision in $\mathcal{H}'_k$); however $\mathcal{W}$ is not, as $\mathcal{W}_k(00) = \mathcal{W}_k(01)$


Need help understanding public key format of Barreto-Naehrig signature I have a 256bit signature and a certificate with a public key to verify it. I had little information about the signature scheme used, but I know now that it's "ECBNwithSHA256". I have never come across these Barreto-Naehrig Curves until now.
My question to the community is: The certificate contains two point pairs (each 32 bytes) as the public key.

Can someone explain to me why the public key consists of 4 points here?
This is a Screenshot of the certificate:

It is common to define pairing-friendly curve such as  Barreto-Naehrig on sextic twists to implement efficient pairings (https://eprint.iacr.org/2012/232.pdf). for example, $E(\mathbb{F}_p): y^2 = x^3 + 2$ and sextic twist $E'(\mathbb{F}_{p^2}): x'^3 + \frac{2}{s} = x'^3 + 1 - u, where ,\mathbb{F}_{p^2} = \mathbb{F}_p [u]/(u^2 + 1), \mathbb{F}_{p^6} = \mathbb{F}_{p^2} [v]/(v^3 - (1+u)), \mathbb{F}_{p^{12}}=\mathbb{F}_{p^6} [w]/(w^2 - v), 1/s = 1/(1 + u)$
So the public key may be a point on a curve defined over an extended field and thus the coordinates will have multiple components. I didn't get into your screenshot in detail but I think it may be a point on the curve over $\mathbb{F}_p^2$ and thus the coordinates $(x,y)$ have 2 components each which explains why you have components of 32 bytes each.


How is the following different than RSA Signing of a document? If the goal is to demonstrate that you are who you say you are, I think the following will work: Bob wants to know that you are Amy. Bob encrypts a number using Amy's public key and then asks her what that number is. If Bob gets back the number, "Amy" at least had Amy's private key.

From what I have read, this is not what signing a document using RSA is. It is clear that it requires more emails to be exchanged; but is the fundamental idea different from Bob encrypting using Amy's public key and wanting to get back the correct decrypted message?

Two scenarios:

Alice sends a document to Bob that she has signed using her private key. Bob verifies the signature.
Alice sends a document to Bob. Bob encrypts a random message for Alice's public key. Alice decrypts it and sends it back to Bob. Bob verifies it's the same.

Both will only be possible if Alice has access to the private key, so you might think they are similar. However, the latter does not make any connection between the document and the authentication attempt. In fact, it allows a man-in-the-middle attack:

Eve intercepts a document meant for Bob, so Alice expects an encrypted message for decryption.
Eve sends another document to Bob, claiming to be Alice.
Bob encrypts a random message using Alice's public key and sends it to Eve.
Eve forwards it to Alice, who decrypts it and sends it back to Eve.
Eve can now send the decrypted message to Bob, convincing him she is Alice and that the document came from Alice.

In comparison, with signatures the document itself is signed. The signature cannot be transferred to a different document, or it will no longer verify. Moving it would require either breaking the asymmetric system to find the key or finding a hash collision.


Did non-military cryptography appear in the 50's and 60's only due to NSA leaks? I'm not talking about scytale, but encryption like RSA, DES, etc.

How exactly did civil cryptography evolve after World War II?

I won't answer your question up to every detail, as I would have to write a book to answer the pretty broad question to full length. But I'll give you some hints as it would be wrong to let you think that non-military cryptography has appeared in 50's and 60's only thanks to leaks from the NSA!

Before the 30's…

One of the earliest descriptions of encryption by substitution appears in the Kama-sutra, a text written in the 4th century AD by the Brahmin scholar Vatsyayana, but based on manuscripts dating back to the 4th century BC. The Kama-sutra recommends that women should study 64 arts, including "mlecchita-vikalpa" — the art of secret writing*, advocated in order to help women conceal the details of their liaisons.

All in all, "non-military cryptography" has been known to civilians for thousands of years!

Where "Modern" crypto came from…

As for "modern-day" encryption, I'll only add that in the 30's and 40's, things like the Enigma cryptographic machine series were available to the general public, but they were too expensive for the average working man. Even after WW2, most military cryptography still was not all too different from the substitution ciphers known from the past, which were - theoretically - also available to every civilian. As an example, you can look at the work of Claude Shannon, who worked for Bell Labs and not the military.

Shannon worked  at Bell Labs for several years. During his time there, he produced an article entitled “A mathematical theory of cryptography”. This article was written in 1945 and eventually was published in the Bell System Technical Journal in 1949. This is regarded to be the start of modern crypto… which is why Claude E. Shannon is considered by many to be the father of mathematical cryptography.

The (r)evolution of civilian modern crypto…

The cryptographic techniques and algorithms evolved in the 70's as computational power became available… and even "working class" civilians could afford computers. What leaked in those decades was nothing more than a hand full of different military cryptographic algorithms; but it's not as if there weren't any civilian cryptographic algorithms available at that time. As an example, you can look at the DES cipher you mention. DES was created by a research group at IBM, not the military.

Side-Note

Re-reading your question, I guess you don't know (or forgot) that it was not until the 1970s, when the US government started treating cryptographic algorithms and software as munitions and interfering with university research in cryptography, that cryptography was actually pretty "non-military"; especially from a research and development point of view. My answer to "Why are cryptography algorithms not exported to certain countries?" dives a bit more into this.

But generally it's a known fact that there has always been ample civil research and development of cryptographic algorithms and techniques and most military cryptography is based on and/or derived from such civilian research and development. An example of a modern crypto invention in the civilian area actually resulted in Bernstein v. US Department of Justice (which made it famous in the first place). Bernstein's "Snuffle" was not and never has been created, influenced, manipulated, or leaked by the NSA or the US government… nevertheless, if got hit hard by US legislation. So yes, there was influence by governments and their military… but they were not the ones who gave birth to modern civilian crypto. Shannon did that in '49 with his publication, and - just like thousands of years before - it's mostly civilians (especially academics and the likes) that invented and still invent modern crypto algorithms.

If you need more details, you should probably check Wikipedia's "History of cryptography" with a section called "Modern Cryptography". If that's not enough, maybe it's time to buy a book about crypto history. Wikipedia has a nice listing or related books at "Books on cryptography ~ History of cryptography".

Nota Bene

Last but not least, I would like to add that it should be clear that the NSA (since you explicitly mentioned them in the question) had no chance to influence crypto before November 4, 1952… as they were founded on that date.


Homomorphic (encrypted) comparison to an integer When working with an additive homomorphic encryption scheme (say Pallier's), is there an efficient way to get the encrypted  value of a comparison test to an integer value (I realise that an unencrypted comparison test would make the encryption scheme worthless)?

I know there are (rather costly in number of rounds and broadcast complexity) methods to compare two encrypted values, that is: given $Enc(x)$ and $Enc(y)$, obtain $Enc([x < y])$, which decodes to $1$ or $0$.

If we do not necessarily need $y$ to be private, but are instead willing to use a public integer value $d$ (presumably of the form $2^k$), are there any faster methods (in number of rounds) to get $Enc([x < d])$?

Edit 1: it is worth mentioning that, in this instance, $Enc(x)$ is itself obtained from homomorphic operations, so any method relying on having a binary decomposition of $Enc(x)$ would not be applicable (or more exactly: would require a costly pre-treatment protocol to binary-decompose the input)...

Edit 2: While I am definitely interested in hearing any generic answers to this problem (if they exist), my personal case can accommodate the following relaxations (by order of acceptability):

$y$ very small relative to the size of the modulo field (say, less than 3 bits).
$x$ small (say, less than 8 bits).
a secure comparison protocol not relying on pure homomorphic operations (e.g. requiring communication rounds).
if nothing better: testing for inequality ($Enc([x ≠ y])$)

I may have found an answer (welcoming any comment on whether I missed something) which works, given certain size restrictions on the input $x$ and $y$:

Say, party A has Enc(x) and Enc(y):

A flips a coin: b in {-1, 1}
A computes: $Enc(c) = (Enc(y) Enc(-x))^{b*r} Enc(-r') = Enc(b*r*(y-x)-r')$ where (r, r') are a pair of random obfuscating values such that:

$r' < r$
the distribution of the random variable $r(y-x)-r'$ does not reveal anything about $(y-x)$ (see Edit 2 below).
$log_2(n) > log_2(max(x,y)) + log_2(r) + 2$

A sends Enc(c) to the other party B
B sends back Enc(d) = Enc([c > 0])

If b = 1, Enc([y > x]) = Enc(d)
If b = -1, Enc([y > x]) = Enc(-d)Enc(1)

Am I missing an obvious flaw?

Edit: To avoid modulo problems, $c$ should obviously be smaller than n. Which should be guaranteed by enforcing the conditions on $r$, $r'$ listed above.

Also: negative values refer to the upper range of [0, n-1], as detailed in section 2 of this paper.

Edit 2: The main attack vector would be in the possibility to identify a specific distribution of $c' = r(y-x) - r'$, revealing information on $(y-x)$ (and particularly whether $x = y$). I initially blindly assumed (based on this paper) that $c'$ had to follow a uniform distribution, but this actually does not seem to be a direct requirement.

Section 3.3 of this paper notes that, for $x$ and $y$ in domain $\mathcal{D}_a = [l_a,h_a]$, if $r$ is picked in domain $\mathcal{D}_r = [1, (h_a-l_a)^2]$ and $r'$ from $[0, r]$ (both uniform), then the probability of accidentally revealing $a = b$ is $p \approx \frac{\ln h_r}{h_r}$. This is negligible for e.g. $h_r = 64$ ($p < 2^{-58}$), which still can fit the modulo limit, given a typically secure $n$ (e.g. 512 bits).

This can be made even more difficult by choosing a distribution at random to pick $r$ and $r'$ from.

Same paper discusses a (seemingly tighter) bound on $r, r'$ to prevent wraparound (haven't checked it yet, but it would not really affect the above).


Weakening of Paillier cryptosystem due to ciphertext equivalence and order in CryptDB The Paillier cryptosystem is probabilistic in nature and IND-CPA secure. By design given two ciphertexts one cannot distinguish whether decrypting those two ciphertexts will result in same or different plaintexts.

But in certain situations like Onion-layered encryption in CryptDB. There are other onions like DET and OPE that reveal whether two ciphertexts map to same underlying plaintext or whether the plaintexts are greater or less when compared to each other.

For example , in CryptDB the plaintext is encrypted using multiple schemes and stored separately. So two different plaintexts $m_1,m_2$, assuming both are numbers, would look in the tables as below

HOM Onion : Paillier_Enc($m_n,k_1$) = $c^h_n$ , $h$ denotes the homomorphic layer
DET Onion : AES_Enc($m_n, k_2$) = $c^d_n$, $d$ denotes the deterministic layer
OPE Onion : OPE_ENC($m_n, k_3$) = $c^o_n$, $o$ denotes the order preserving layer

Now although $c^h_1 , c^h_2$ do not reveal whether $m_1, m_2$ are equal because the Paillier scheme is probabilistic . There are other onion layers revealing whether the $m_1,m_2$ are same or less or greater to each other.

My hunch is these inferences from other layers weaken the Paillier cryptosystem's security guarantees, but I could not come up with a way to weaken them. So how can we take advantage of other onions leaking inferences (about equality, comparison) to break the Paillier system in some way?

Your hunch is wrong because of the definition of CPA security: Assume that some knowing some kind of relation between two plaintexts would give the attacker an advantage.

Now think of the INC-CPA game: Nothing stops the attacker from choosing exactly this kind of relationship. And if the scheme is IND-CPA secure, knowledge of such a relation does not break the scheme. As mikeazo pointed out: Even if you only use a message space of $\{0,1\}$, CPA security still ensures the attacker can not distinguish their encryptions.

The other aspect you hinted at: Under CPA security it is not possible to distinguish whether two ciphertexts encrypt the same plaintext: The attacker can encrypt $m_1$ and $m_2$ as often as he wishes. If there was a way to determine that one of the encryptions encrypts the same ciphertext as the challenge, he wins.


Hashing functions - How to define them? Let $\mathcal{G}$ be a cyclic additive group for an elliptic curve $E\, / \ \,\mathbb{F}_p$, and let $p, n$ be two large prime numbers (e.g., we can consider  $\texttt{secp160r1}$ with $p = 160$ bit and the reasonably even $n$ is $160 $ bit long).

I have read several papers in which hashing functions were defined, but I do not understand how the definitions were reached. Let me give you an example:

$H_1:\{0,1\}^* \times \mathcal{G} \times \mathcal{G} \rightarrow \mathbb{Z}_n^*$

$H_2:\{0,1\}^* \times \{0,1\}^* \times \mathcal{G} \times \mathcal{G} \times \mathcal{G} \times \mathcal{G} \rightarrow \mathbb{Z}_p^*$

My questions are:

Why do the authors multiply the value $\{0,1\}^*$ by $\mathcal{G}$ more than once ? One time is not enough?
Why, in the second function $H_2$, do they multiply the value $\{0,1\}^*$ two times with itself? What changes?
If I want to define a third hashing function $H_3$, do I need a third prime number or can I leverage $p$ or $n$ (in $H_1$ the output is in $\mathbb{Z}_n^*$, and in the second in $\mathbb{Z}_p^*$)?
What is in practice the difference between $H_1$ and $H_2$?
Supposing that $n = p = 160$ bit, may I estimate the output length for each hashing function? Is this long $160$ bit right (e.g., could be SHA-1)?
Why not simply define a hashing function as $H:\{0,1\}^* \rightarrow \{0,1\}^l$?

They are not. First of all, $\{0,1\}^*$ and $\mathcal{G}$ are not "values", they are sets. $\times$ does not mean multiplication, but the Cartesian product of those sets. Second of all, those are not definitions of functions. All that's specified there is the domain and range of the hash functions. Specifically $H_1$ maps tuples $(a,b,c)$, where $a\in\{0,1\}^*$ and $b,c\in\mathcal{G}$ to an element of $\mathbb{Z}_n^*$.
See above. $H_2$ maps tuples consisting of two elements of $\{0,1\}^*$ and four elements of $\mathcal{G}$ to an element of $\mathbb{Z}_p^*$.
You don't need any prime numbers to define a hash function. But also there are no definitions of hash function anywhere in your question.
They have a different domain. Meaning that they accept different inputs.
The output of those functions is not a bitstring. It's an element of $\mathbb{Z}_n^*$ and $\mathbb{Z}_p^*$ respectively. The values may be encoded as a bitstring, where the canonical encoding would indeed have length at most 160 bits.


Why are Jacobian Coordinates used? I couldn't find this explained in another question, but is there an actual reason as to why Jacobian coordinates are used for elliptic curves? Do they provide some sort of advantage in terms of performance? Or are they easier to use for security proofs?

Point addition in affine coordinates involves the computation of modular inverses for elements of the underlying finite field. Modular inversion can be done with the extended Euclidean algorithm, although its cost is around 100 times the cost of a single addition or multiplication in the finite field.

Point addition in projective and Jacobian coordinates, however, doesn't require to compute any modular inverse. Hence, the cost of adding two elliptic curve points in projective or Jacobian coordinates is much smaller than in affine representation.

The following is the result of a test I've just run for curve secp256k1, where 'a' means number of additions, 's' number of subtractions, and 'm' number of multiplications, and 'i' number of inversions:

## Addition in affine coordinates ##
{'a': 0, 's': 154, 'm': 299, 'i': 149}

## Addition in Jacobian coordinates ##
{'a': 1, 's': 5, 'm': 17, 'i': 0}

These numbers mean that, for this implementation (which is far from optimized, but serves as an example), addition in affine coordinates is approximately 20 times costlier than in Jacobian.


Rejection Sampling reasoning for Lattice Based Signatures I'm new to lattices.
According to Lattice Signatures and Bimodal Gaussians in the Rejection Sampling section.
In Schnorr, GQ you can simply commit to $y$, use it to hide a secret key $s$.
But this doesn't work in lattices. You need to hide the secret key with a small $y$. Turns out, a lot of old lattice-based signatures leaked a part of the secret keys. Instead, we must choose y from a narrow distribution and then perform rejection sampling so that $s$ is not leaked when we add $y$ to it.

Now:

What does there mean to be a narrow distribution?
What does it mean for $y$ to be small?
Why is this a problem in lattices specifically?

Narrow means that, with high probability, the ouput of the distribution is is small.
Small is meant in the sense of the Euclidean norm of a vector in the Euclidean space $\mathbb R^n$. More concretly, $v$ is informally said small to mean $\|v\| \leq B$ for some value $B > 0$ chosen large enough for a given scheme to work out, but small enough for the lattice problem SIS to remain hard.
It is not a problem outside lattice based crypto because in a finite group $G$, if $x \in G$ is uniform, so is $x+c$. We can't simply do that over an unbounded space such as $\mathbb R^n$.


Algorithm accepting every passphrase to fool unlegit user I'm looking for specific names and literature on crypto algorithms that accept every passphrase input by the user, in order to 'decrypt' - even with false passphrase - and present the unlegit user with a false plaintext. The unlegit user should not be able to determine whether the 'decrypted' text is real or fake - as it accepts every passphrase.

Of course using the legit passphrase reveals the legit plaintext.

I found two examples of what I mean:
The Fraunhofer Institut in Germany invented a smartphone password-manager app that uses this kind of technology. Its called iMobileSitter. And I think on Eurocrypt2014 a paper called 'Honey Encryption' with a  similar algorithm has been submitted.

I'm not sure of the exact status of the program, since there was some controversy surrounding it a few weeks ago, see: Is TrueCrypt not secure now and should I stop using it?. But the very popular program TrueCrypt, a program is typically used to encrypt stored files and drives, I believe has the property that you are asking about. Its called: Plausible Deniablility. So combine the concept of plausible deniablility with strong crypto and you have Deniable Encryption

A passage from the page on deniable encryption states:

  Normally ciphertexts decrypt to a single plaintext and hence once
  decrypted, the encryption user cannot claim that he encrypted a
  different message. Deniable encryption allows its users to decrypt the
  ciphertext to produce a different (innocuous but plausible) plaintext
  and insist that it is what they encrypted. The holder of the
  ciphertext will not have the means to differentiate between the true
  plaintext, and the bogus-claim plaintext.

How TrueCrypt implements this, is basically by allowing you to make hidden partitions on a hard drive, and have "fake" partitions to fool attackers.


How to find the inverse of f(x) in NTRU key generation? I work on a project that depends on the NTRU cryptosystem, but I don't know how to find the inverse of $f(x)$.

Please see the picture:

Please help me to understand this problem.

$\newcommand{\Z}{\mathbb{Z}}$This somewhat oblique notation $F_q(x) = f(x)^{-1} \pmod q$ means that $F_q$ is the inverse of a unit element $f$ in the quotient $(\Z/q\Z)[x]/(P)$ of the polynomial ring $(\Z/q\Z)[x]$ by the ideal generated by some monic irreducible polynomial $P$ with integer coefficients.  $P$ is a system parameter presumably defined in an earlier slide.  Given $P$ and $f$, you can compute $F_q$ with the extended Euclidean algorithm.

The notation is presumably chosen because we variously map the same polynomial expressions with integer coefficients of $P$, $f$, and $g$ into three different polynomial rings, $\Z[x]$, $(\Z/q\Z)[x]$, and $(\Z/p\Z)[x]$ at different times.  It wouldn't be quite right to say that $f$ is an element of $(\Z/q\Z)[x]/(P)$, because in the next sentence $f$ will be an element of $(\Z/p\Z)[x]/(P)$ instead.  Saying $a(x) = b(x) \pmod q$ means we are taking the base ring of the polynomials $a$ and $b$ to be $\Z/q\Z$ for that equation.


Can an encryption key be inferred by knowing the plaintext and the corresponding ciphertext? Thinking about validation methods for guaranteeing a proper key is used. Will keeping a dummy plaintext value and its corresponding ciphertext in plaintext code expose any risk?

Good thinking!
The good news is that, when you use authenticated encryption, there's no need to keep such "dummy" plaintext-ciphertext pair.
In a typical authenticated encryption, a tag is computed based on the key, the plaintext, and possibly additional data (e.g. AAD, Initialization Vector), so that upon decryption, the tag is verified for correctness. Typically, the tag is 128-bit as is the case with GCM-AES and ChaCha20-Poly1305.
Successful decryption of an authenticated ciphertext indicates that if the correct key had been used then the ciphertext along with other inputs to the encryption algorithm are correct and had not be modified by any man-in-the-middle.


What is wrong if you use a key in a Caesar cipher that is greater than 26? TL;DR- why can't we have a key cipher greater than 25 in the Caesar cipher?

Let's suppose the key is K = 30.
The message I want to send is "H E L L O W O R L D"

Now converting each letter to a number from 0-25, we get 7-4-11-11-14 22-14-17-11-3.

Adding 30, we get 37-34-41-41-44 52-44-47-41-33.
But as the cipher text ranges only from 0-25, we now have to use the modulo function on every letter by 25.

We end up getting 12-9-16-16-19 2-19-22-16-7

Now on receiving this message, all one has to do is subtract the key 30 from each number, add 25 and then convert back each number to its corresponding alphabet.

So why do we have to restrict the key-space of a caesar cipher to 0-25?

Basically the Caesar and Vigenére ciphers perform operations on groups. In this case the group consists of the values $\{0, 1, 2 ... 25\}$ in that particular order and the modular addition $+$. Now within a group it doesn't make sense to add a number outside of the group domain - in this case 0 to 25 - to the value.

So as we are using modular addition we can see that $12 + 30 \equiv 12 + 4 \mod 26$ as $42 \bmod 26 = 16$ and $16 \bmod 26 = 16$.

We can use this fact to call the values $0$ to $25$ representants because they actually just represent an infinite amount of integers: all integers which are the representant plus some multiple of $26$. So with this in mind $30$ and $4$ have the same representant $4$ (in theory you could use special notation to make the difference between numbers and representants for infinite amounts of numbers more clear but we will not do so for the sake of alignment with established standards).

So adding 30 only makes sense if we extend the group to at least 31 values. Within these ciphers that basically means extending the alphabet: the letters that get encrypted (or duplicating characters, to make it more difficult to analyze the resulting ciphertext).

You could accept $30$ as key, but it would not really extend the key space because $30$ would be fully equivalent (that's the $\equiv$ symbol) to the key value $4$. So the final key strength would still consist of 26 possible keys (about 4-something bits) as well.


Repeatable encryption for pseudonymisation Is there a good way to do repeatable (with the same result) encryption for pseudonymisation where the pseudonym can be decrypted?

I want to set up a system to allow multiple services to communicate about subjects without them being able to join their data together themselves. They would send their requests through a "middleman" service which would translate the IDs to enable communication between the services.

So for instance, a score service and a user info service where the score service could ask for the user's first name without having to know the actual id for this user.

Because I don't want to store a large lookup-table for each service in the middleman I would like to generate the pseudonyms on the fly. So far I've looked at some RSA (OAEP) and AES (CTR, GCM) algorithms. The problem with these (I believe) is that they add some random padding or require a unique initialisation vector (which is there to prevent information about the key to be leaked) which makes the encryption non-repeatable. (Data stays the same but the result changes for every time we encrypt)

The data would be something like secret:service_uuid:object_type:object_id to make these unique for each object-service pair.

A (maybe ignorant) solution I came up with was to use something like AES and create iv from the data (d) by doing something like this:

$iv = hash(d) \bmod m$

Where m is the max value for iv

But I'm not sure if this compromises the strength of the encryption algorithm.

Long story short, I have not been able to find any "standard" to solve this, and I have the feeling I might be introducing some vulnerabilities by forcing some algorithm to do something it wasn't designed to do. Does anyone know if there is a better way to do this?

AES with $\text{IV}$ created from the data $d$ by $\text{IV}=\operatorname{hash}(d)\bmod m$, where $m$ is the max value for $\text{IV}$

That seriously compromises confidentiality, and does does not provide authentication:

The $\text{IV}$ is typically in clear at the beginning of the cryptogram, and that allows someone without the key to test a guess of $d$, which is a total disaster for a login!
Someone without the key can prepare a cryptogram that will decipher (at least, to garbage, but that can still be damaging, causing denial of service or worse, see below).
If there is a test of acceptability of what's deciphered (e.g. a syntax check), that's ideal grounds for a padding oracle attack that might very well allow decryption without a guess (depending on details of the encryption, availability of a decryption oracle/server, test of acceptability and insight on its result an adversary gets thru side channels like error codes, network states, or timing).
Depending on AES mode and availability of valid cryptograms with known plaintext, someone without the key may be able to prepare cryptograms that will decipher to something under control of the attacker.

Making symmetric encryption deterministic (the academic name for "repeatable") is bound to allow a test that two messages are identical by comparing the ciphertexts, but all other drawbacks can and should be avoided.

A good option would be a Nonce-Misuse-Resistant Authenticated Encryption with a public fixed nounce, e.g. the key index (symmetric keys should be rotatable, and identified by key index for this purpose).

A modern such scheme is AEAD_AES_256_GCM_SIV of RFC 8452. We are straight in the designed-in usage: "encrypting two messages with the same nonce only discloses whether the messages were equal or not". The theory behind the scheme is described in Shay Gueron and Yehuda Lindell's GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte, in proceedings of CCS 2015.

If performance is not an issue, there are ways to obtain similar functionality from more available primitives, such as a hash and/or an encryption-only mode of operation. Edit the question stating available primitives if that's needed.


Can we build authenticated encryption using Feistel Networks? Most of the encryption modes of Feistel Networks especially the ones used to build fixed length block ciphers just provide confidentiality .

Can we build authenticated encryption using Feistel Networks ?

The simple way to build authenticated encryption using a Feistel Network is to build a Feistel based block cipher, then use one of the many modes of operation that turn a block cipher into an authenticated encryption scheme (eg CCM,OCB,GCM).

For a good survey on the subject of modes-of-operation I would recommend this paper by Rogaway. It does not cover the very most recent designs (such as those discussed at DIAC'13) but covers the more accepted methods in a reasonable amount of detail.


Knowledge of discrete log is needed in the proof of Cramer-Shoup public key scheme? In the proof of the Cramer-Shoup public key scheme [1], I understand that the adversary's view can be seen as equations such as $\log c = x_1 + w x_2, \log d = y_1 + w y_2$ and so on (equation 1 and 2 in [1]), where $\log = \log_{g_1}$ and $w = \log g_2$. Does this mean the adversary knows how to solve discrete log? If that's the case, why is it a reasonable assumption? Otherwise, how does the adversary know $\log c$, $\log d$ and $w$?

[1] https://link.springer.com/content/pdf/10.1007%2FBFb0055717.pdf

Of course, it doesn't mean that adversary knows how to solve discrete log.
We just wanted to say that adversary only knows that the point $P$ lies
somewhere on a plain $\cal{P}$ of such form.
We don't suppose that adversary knows actual parameters of the plane.

But it's enough for us to deduce that $\cal{P}$ intersects with another plane $\cal{H}$ (which also has a specific form, though we don't know exact parameters) only by a line, so this intersection is negligible (actually,
a probability for $P$ to lie exactly on the line is negligible).


How to verify the claim of entropy available made by Linux 4.5? The Linux kernel has an entropy source and it estimates its amount of bits in the device /proc/sys/kernel/random/entropy_avail.  How can I verify that this number makes sense?  I did the following experiment.  The system in question is:
# uname -rvmpio
4.15.0-1050-aws #52-Ubuntu SMP Thu Sep 12 19:56:00 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

The following program prints the number of bytes of information available in each second as claimed by the kernel.
$ while true; do cat /proc/sys/kernel/random/entropy_avail; sleep 1; done | awk ' { t += 1; s += $0; print "t =",t,"sum =",s/8, "avg =", s/t/8, "now =",$0/8 }'
t = 1 sum = 86.375 avg = 86.375 now = 86.375
t = 2 sum = 174.625 avg = 87.3125 now = 88.25
t = 3 sum = 175.875 avg = 58.625 now = 1.25
t = 4 sum = 179.75 avg = 44.9375 now = 3.875
t = 5 sum = 186 avg = 37.2 now = 6.25
t = 6 sum = 186.875 avg = 31.1458 now = 0.875
[...]

The following program consumes /dev/random as much as possible and estimates how many bytes of information is practically available at each second.
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
  int r, bs; char b[512];
  unsigned int t = 0, n, sum = 0;
  fcntl(0, F_SETFL, fcntl(0, F_GETFL) | O_NONBLOCK);
  while (1) {
    n = 0;
    while ( (bs = read(0, b, 512)) != -1) n += bs;
    t += 1; sum += n;
    printf("t = %3d, sum = %3d, avg = %.4f :: just read %d bytes\n",
           t, sum, (float) sum/t, n);
    sleep(1);
  }
}

Here's how to compile and run it:
$ make p
cc     p.c   -o p
$ ./p < /dev/random
t =   1, sum =  20, avg = 20.0000 :: just read 20 bytes
t =   2, sum =  20, avg = 10.0000 :: just read 0 bytes
t =   3, sum =  20, avg = 6.6667 :: just read 0 bytes
t =   4, sum =  26, avg = 6.5000 :: just read 6 bytes
t =   5, sum =  26, avg = 5.2000 :: just read 0 bytes
t =   6, sum =  26, avg = 4.3333 :: just read 0 bytes
t =   7, sum =  26, avg = 3.7143 :: just read 0 bytes
[...]

Keeping the file system in high activity (while true; do find /; done), we get a certain number of bits being produced at regular intervals.  Running p first to keep entropy production being consumed as much as possible and then checking out the estimate by the kernel, it seems these two numbers do not quite converge, but they are roughly close.  After 100 iterations, I get the following values:
$ while true; do cat /proc/sys/kernel/random/entropy_avail; sleep 1; done | awk ' { t += 1; s += $0; print "t =",t,"sum =",s/8, "avg =", s/t/8, "now =",$0/8 }'
[...]
t = 100 sum = 1534.12 avg = 15.3413 now = 7.625
t = 101 sum = 1537.88 avg = 15.2265 now = 3.75
^C

$ ./p < /dev/random
[...]
t = 100, sum = 2002, avg = 20.0200 :: just read 0 bytes
t = 101, sum = 2014, avg = 19.9406 :: just read 12 bytes
^C

It seems therefore that Linux 4.5 underestimates its amount of entropy --- assuming I'm the only consumer.  This assumption is probably false, but perhaps I am not too far from the truth.  My verification finds about 5 bytes over the estimate of the kernel.

You can't, and you're not the only consumer. The operating system rips you off. It uses true randomness to prevent attacks by shoving code into random places. And randomly sequencing it's network traffic. But here's the thing...

“We have to remember that what we observe is not nature in itself but nature exposed to our method of questioning.”

-Werner Heisenberg
and that's compounded with the concept of the observer effect.
Essentially what the kernel does is quantize various external events via a made up second order differential algorithm. There's a write up in Documentation and Analysis
of the Linux Random Number
Generator but essentially it comes down to temporal quantization of hardware events as :-

And so,

It seems therefore that Linux 4.5 underestimates its amount of entropy

Yes.  That's the conclusion of all of the academic works I've seen on /dev/random. It's essentially the least signification digit of system time when something happens. But, the problem is that it shouldn't take 160 PDF pages to convince us of randomness. My concept of Open Entropy dictates that it should be screaming right up in your face without funky science.
With delicacy, what's your real question?

Nothing in this post relates to Micro$oft operating systems.

If this is important to you, build your own entropy source. It's not difficult considering the 2nd law of thermodynamics. Get a diode.

There's a dangerous and hugely misunderstood  meme out there that suggests /dev/random = /dev/urandom without appreciating the role of time. $(\epsilon, \tau)$ and the left over hash lemma  is everything.


multi-theorem vs single-theorem for non-interactive zero knowledge I am trying to understand the definition of zero knowledge for non interactive zero knowledge (signature of knowledge). Sometimes I find multi-theorem zero knowledge, sometimes I find single-theorem. What's the difference ?

My main task is to show that a Zero Knowledge Signature of Knowledge which is zero knowledge (for one signature) is zero knowledge for several signatures. In other words, if you don't reveal anything by signing one message, you don't reveal anything if many people sign many documents with this ZKSoK.

In a zero-knowledge proof system, there are three main properties to be satisfied: completeness, soundness (knowledge soundness for zkpok), and zero-knowledge (or weaker notion such as witness indistinguishability).
one of soundness and zero-knowledge is computationally error-bounded, i.e. you can either than a (computational soundness + statistical zk) combo which is known as ZK Argument, OR a (statistical soundness + computational zk) combo which is referred as ZK Proof.
At the beginning of the protocol, there's usually a Setup step where proving keys and verification keys are generated based on the security parameter given. In NIZK, these proving keys and verification keys are part of the Common Reference String (CRS).
Depending on the construction, repetition of the protocol (i.e. run the protocol multiple times under the same proving and verification key) might hurt soundness or zero-knowledge. "hurt" as in the error bound just increase, making it prone to violation. For some proof system, repetition might violate the property and thus totally break the protocol.
single-theorem basically guarantee those three properties and their error bound for a single round.
multi-theorem basically mean reusing proving & verification keys from Setup for unbounded number of rounds/repetition/theorem without compromising the soundness or zk. (i.e. reuse CRS for many $x \in L$)


At what point can you you implement crypto algorithms? First off, this feels like it should be a common question, so I'm sorry if I've missed an older thread.

Note that in my question, I'm talking about "implementing AES" rather than "designing AES2" or something.

I am of course familiar with the saying that you should "never implement your own crypto" and I've recently also learned some about why, in terms of all the attacks and common mistakes, etc. However, I've never really liked that answer, because if no one ever implemented it, we would never have it. And since we do have it, someone must not have listened, and implemented it.

My question is: At what point is a person "allowed" to implement a crypto library? Be it for a new platform, a newly released algorithm, etc.

"Allowed" or "forbidden" are not the right terms; the Pope won't excommunicate you if you dare implement your own algorithms. The question is rather whether doing your own implementation is a smart move or not.

For learning, doing your own implementation is a good idea. It will teach you a lot on how the said algorithms work. A lot of details on how cryptographic algorithms are designed, in particular symmetric encryption and hash algorithms, come from implementation considerations -- the algorithm designer always tries to find the structure that will ensure the required security properties with the maximum efficiency (speed, code size... on a variety of architectures).

For "production", beware. Cryptographic algorithms, by design, are meant to process confidential elements (in particular keys, that concentrate a lot of secret in a few bits), so it is of the utmost importance that the implementation does not leak information. This is a lot harder than usually assumed. For instance, a very common and, I dare say, highly fashionable theme is about timing attacks through cache behaviours on software platforms (both the L1 cache for RAM access, and the in-CPU cache for jump prediction). This kind of attack can be used, at least conceptually, to extract keys from running systems, typically from another VM that runs on the same hardware (such attacks have been repeatedly demonstrated in lab conditions, so it seems plausible that they may be applicable in practice). Writing an AES or RSA implementation that is immune to cache timing attacks is possible, but it requires a lot of care, and very clear notions on how they work and how computers work. Even if you do not write assembly code, you must at least think about how the compiler for the language you are using will translate your code into assembly.

The bottom-line is that deploying your own implementations in the wild is rarely a good idea. Sometimes you have no choice, because (for instance) there is no available implementation for your target architecture and language, with a license compatible with what you want to do. This is not the common case, though.

Using the same libraries as everybody else means that whenever a nasty bug is found in your products, then your competitors have it too. From a business point of view, this is a good thing.

So you should really write your own cryptographic library... and not use it. If you can write a library, let two months pass, read it again, and not find anything wrong or suboptimal in it, then you are not trying hard enough.


How to establish if a string contains a message If you have a string S, then the string can be composed of four things:

cleartext
'random' data
encrypted data
compressed or otherwise non-encrypted, but modified, cleartext

If you want to see if the string is an encrypted message, (3), then you might construct a test for 'randomness', say the test is $T_0$. You'd then expect:

$T_0(a) \approx T_0(d)$ -- i.e. not interpreting a compression as an encryption because it is ordered
$T_0(b)$ $\not \approx$ $T_0(c)$ -- i.e. the message is detected

If the message is very well encrypted, then you'd expect:

$T_0(b) =  T_0(c)$ -- that is, the algorithm detects no patterns

Would that be correct?

I'd expect that a watermarked or steganographic image would be revealed as different from standard jpegs by a good $T_0$.

The randomness tests in 'diehard' and 'dieharder' look for specific types of pattern that would not be expected in strings of type (2). Would it not make more sense to structure a $T_0$ on known types of data, so, for example, an apparently normal image file that contained a message would stand out?

It will depend entirely on the specific encryption scheme. There is really no theoretical reason why a ciphertext should not be clearly identifiable as being a ciphertext and not a plaintext. In fact, take any encryption scheme and modify it so that the encryption algorithm works as before, only it appends to the ciphertext the string "THIS IS A CIPHERTEXT!", and modify the decryption algorithm to work as before only ignoring this string. For pretty much any reasonable encryption scheme this modified scheme will be (theoretically speaking) as secure as the original scheme.

Why is this? Because, when we evaluate the security of a scheme we assume that the adversary (i.e., the entity trying to break the scheme) knows what scheme he/she is breaking and is explicitly told what pieces of information are ciphertexts.


AES S-Box implementation: from a byte-by-byte to 2-bytes-by-2bytes? The S-Box in AES encryption is a byte substitution step. Is it possible to perform the substitution 2 bytes at a time, rather than 1 byte? What are the challenges/trade-offs involved?

First of all without any context going from a byte-by-byte substitution to a 2-bytes-by-2-bytes does not means anything as it is S-box implementation dependent.

I. Using Lookup tables (Boooooo!)

Example:
one could implement bit-by-bit $\neg$ as a lookup table:

neg[0] = 1
neg[1] = 0

And then go to a 2-bit-by-2-bit $\neg$ as such:

neg[00] = 11
neg[01] = 10
neg[10] = 01
neg[11] = 00

This will effectively compute the requested result but as you can already see the space required is stupidly huge as it increases by with the square of the width of the S-box...

In the other hand one could also implement the $\neg$ using the assembly instruction, which allows to process at least 8 bitwise $\neg$ at the same time !

In other word: FORGET ABOUT TABLE LOOKUPS.

II. Using Computations (Meh)

For AES it is the same, you can either use a Sbox[x] look up or you can compute that value using the formula provided in the specifications (requiring an inverse over $\operatorname{GF}(2)[X]$).

Also the advantage of such implementation is that you are less likely to be sensible to cache-timing attacks. You can then try to replicate these computations on multiple bytes at the same time.

III. Using Bit-slicing (Yeah!)

In order to go further than a 2-bytes-by-2-bytes substitution, you can have look at the AES hardware implementation. You will see gates and paths. You can replicate this circuit using normal instruction in a software.

in other word for a $\oplus$ gate:

     +-----+
x ---|     |
     | XOR |--- z
y ---|     |
     +-----+

can be seen as : $\texttt{0000000x} \oplus \texttt{0000000y} \to \texttt{0000000z}$

Wait this is actually worse! you are doing one bit per instruction, this is going to be super slow!

Well you probably noticed that you have 7 bits left empty. And because you want to process multiple S-box (bytes) in parallel, all the hardware operations on each bytes will be the same. So we can take a bit of each of the 8 bytes and compute the gate on them:

For 8 bytes:
$a = \texttt{a}_0\texttt{a}_1\texttt{a}_2\texttt{a}_3\texttt{a}_4\texttt{a}_5\texttt{a}_6\texttt{a}_7\\
b =\texttt{b}_0\texttt{b}_1\texttt{b}_2\texttt{b}_3\texttt{b}_4\texttt{b}_5\texttt{b}_6\texttt{b}_7\\
c = \texttt{c}_0\texttt{c}_1\texttt{c}_2\texttt{c}_3\texttt{c}_4\texttt{c}_5\texttt{c}_6\texttt{c}_7\\
d = \texttt{d}_0\texttt{d}_1\texttt{d}_2\texttt{d}_3\texttt{d}_4\texttt{d}_5\texttt{d}_6\texttt{d}_7\\
e = \texttt{e}_0\texttt{e}_1\texttt{e}_2\texttt{e}_3\texttt{e}_4\texttt{e}_5\texttt{e}_6\texttt{e}_7\\
f = \texttt{f}_0\texttt{f}_1\texttt{f}_2\texttt{f}_3\texttt{f}_4\texttt{f}_5\texttt{f}_6\texttt{f}_7\\
g = \texttt{g}_0\texttt{g}_1\texttt{g}_2\texttt{g}_3\texttt{g}_4\texttt{g}_5\texttt{g}_6\texttt{g}_7\\
h = \texttt{h}_0\texttt{h}_1\texttt{h}_2\texttt{h}_3\texttt{h}_4\texttt{h}_5\texttt{h}_6\texttt{h}_7$

We can construct the following 8 bytes:

$bit_0 = \texttt{a}_0\texttt{b}_0\texttt{c}_0\texttt{d}_0\texttt{e}_0\texttt{f}_0\texttt{g}_0\texttt{h}_0\\
bit_1 = \texttt{a}_1\texttt{b}_1\texttt{c}_1\texttt{d}_1\texttt{e}_1\texttt{f}_1\texttt{g}_1\texttt{h}_1\\
bit_2 = \texttt{a}_2\texttt{b}_2\texttt{c}_2\texttt{d}_2\texttt{e}_2\texttt{f}_2\texttt{g}_2\texttt{h}_2\\
bit_3 = \texttt{a}_3\texttt{b}_3\texttt{c}_3\texttt{d}_3\texttt{e}_3\texttt{f}_3\texttt{g}_3\texttt{h}_3\\
bit_4 = \texttt{a}_4\texttt{b}_4\texttt{c}_4\texttt{d}_4\texttt{e}_4\texttt{f}_4\texttt{g}_4\texttt{h}_4\\
bit_5 = \texttt{a}_5\texttt{b}_5\texttt{c}_5\texttt{d}_5\texttt{e}_5\texttt{f}_5\texttt{g}_5\texttt{h}_5\\
bit_6 = \texttt{a}_6\texttt{b}_6\texttt{c}_6\texttt{d}_6\texttt{e}_6\texttt{f}_6\texttt{g}_6\texttt{h}_6\\
bit_7 = \texttt{a}_7\texttt{b}_7\texttt{c}_7\texttt{d}_7\texttt{e}_7\texttt{f}_7\texttt{g}_7\texttt{h}_7\\$

Notice that each byte $bit_\alpha$ contains only a the $\alpha$ bit of $a,b,c,d,e,f,g,h$.

Then we can replicate our gates operations as seen above on these $bit_\alpha$. Once the computations are done, all we need to do is rearrange back the bits in their respective bytes.

Remark: By doing so and extending this technique one can compute 8, 32, 64 or 128 AES S-box at the same time!

This technique is called bit-slicing.

Those are the 3 mains way to implement AES (a bit more to read here).

Now for your second question:

  What are the challenges/trade-offs involved?

Those are: Memory/Rom Space, Time of execution, complexity of implementation (meaning that it is also easy to screw up...)


algebraic attacks for mixed operations (mod 2 and mod 256) If a cipher has mixed operations, e.g $\oplus$ (addition mod $2$), and addition modulo $2^8$. How we we going to express them mathematically? Thanks in advance!

There is of course but because of carry bits there will be data-dependent "nonlinear" terms. If I do it for 2 bits you can get the idea. It gets unwieldy but you can easily write code to do it for longer bitlengths. The list below is an XOR table expressed as integers:

$$
\begin{array}{c|ccc}
\oplus & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 1 & 2 & 3 \\
1 & 1 & \color{red}0 & 3 & \color{red}2 \\
2 & 2 & 3 & 0 & 1 \\
3 & 3 & \color{red}2 & 1 & \color{red}0 \\
\end{array}
$$

while the table below is addition mod 4:
$$
\begin{array}{c|ccc}
+ & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 1 & 2 & 3 \\
1 & 1 & \color{green}2 & 3 & \color{green}0 \\
2 & 2 & 3 & 0 & 1 \\
3 & 3 & \color{green}0 & 1 & \color{green}2 \\
\end{array}
$$

Note that there are exactly 4 positions (in general for $n$ bits there will be $2^{n-1}+2^{n-2}+\cdots$ such positions) where the two operations differ, so relatively worse as $n$ increases) where the two differ. Can we express these positions in terms of integer properties?

The answer is: Let $x,y \in \mathbb{Z}_4,$ considered as an additive group. Then  the XOR operation on $x,y$ can be defined as

$$
x \oplus y = \begin{cases}
x + y + 2 ~(\text{mod } 4) &
\text{if }   x \equiv 1 ~(\text{mod } 2)
\text{ and } y \equiv 1 ~(\text{mod } 2) \\
x + y ~(\text{mod } 4) & \text{otherwise}.
\end{cases}
$$

The full answer has to do with the highest powers of $2$ dividing the two numbers within $\mathbb{Z}_{2^n},$ i.e., the subring and ideal structure.


Is it possible to decrypt the 2nd byte of AES-256-CFB-8 ciphertext without decrypting the 1st byte? I am stuck with AES-CFB decryption.

Assume I encrypted plaintext helloworld (10 bytes) using AES-CFB.

Now I want to decrypt the second byte e individually, that is I don't want to decrypt the first bytes or any other bytes except the second one.

Is it possible to do that without decrypting the first byte?

I did my fair share of research and even tried several practical approaches to find an answer myself, but somehow I’m stuck.

In case it helps answering my question, here’s what my latest attempt looks like (think of it as “pseudo-code” as I’m definitely not asking an off-topic question related to the code itself):

char *key = "whatever";
char *data = "helloworld";
unsigned char out_cipher[10], out_plain[10];
unsigned char iv_enc[AES_BLOCK_SIZE], iv_dec[AES_BLOCK_SIZE];
RAND_bytes(iv_enc, AES_BLOCK_SIZE);
memcpy(iv_dec, iv_enc, AES_BLOCK_SIZE);
AES_KEY enc_key, dec_key;
AES_set_encrypt_key(key, 256, &enc_key);
AES_set_encrypt_key(key, 256, &dec_key);
AES_cfb8_encrypt(data, out_cipher, 10, &enc_key, iv_enc, &num, AES_ENCRYPT);
AES_cfb8_encrypt(out_cipher + 1, out_plain + 1, 1, &dec_key, &out_cipher[0], &num, AES_DECRYPT);

But even trying to approach this programmatically didn’t help me grasp this. Sure, I managed to retrieve an answer. Yet, it was clearly wrong because the 2nd byte of the decrypted plaintext differs from the original plaintext.

As I’ve now run out of ideas on how to find the answer to my question, I decided to ask here hoping someone can enlighten me if it is possible to decrypt the 2nd byte of an AES-CFB ciphertext without decrypting the 1st byte? Or maybe am I missing something else?

Yes, you can do this.  If you want to know how to do it (as opposed to just blindly copying a code snipped written by someone else and hoping it'll work), you'll need to understand a little bit about how CFB mode encryption works.

First of all, CFB is a block cipher mode of operation.  That is, it's a recipe for taking a block cipher like AES, which can only encrypt 16-byte blocks into other 16-byte blocks, and using it to securely encrypt (and decrypt) arbitrary streams of bytes.

Why do we even need a "mode of operation" like CFB?  Why can't we just split the message into 16-byte blocks and encrypt each of them with AES?  Well, yes we can, but such an encryption scheme, known as "ECB mode", turns out to not be as secure as we'd like.  So, instead, we use slightly more complicated schemes like CBC, CFB, OFB or CTR, all of which can be proven to provide full semantic security when used properly.*

This causes a bit of terminology confusion sometimes.  When we speak of "encrypting something with AES", in the context of describing a mode of operation, we mean using the raw AES block cipher to transform a 16-byte input block into a 16-byte output.  (Your crypto library might have a separate API for this, or it might simply expose it as "ECB mode".)  However, the words "encrypt" and "decrypt" are also used for the entire process of applying e.g. CFB mode encryption to the entire message.  This gets particularly confusing when you realize that CFB decryption still uses AES encryption!

Second, there are actually several different CFB modes!  The most common (and efficient) one, which is illustrated in the image included in several earlier answers, is called the "full-block" CFB mode, and works like this (assuming we're using AES as the block cipher):

To encrypt the first 16 bytes of the message, take the 16-byte IV, feed it into AES, and XOR the resulting 16-byte block with the first 16 message bytes to produce the first 16 bytes of ciphertext.  (If the message is shorter than 16 bytes, just truncate the AES output to match its length.)
To encrypt the next 16 bytes of the message, take the 16-byte ciphertext (i.e. the AES output XORed with the message) that we just produced in the previous step, feed it into AES, and XOR it with the 16 message bytes that we want to encrypt to produce another 16 bytes of ciphertext.
Repeat the same process for every subsequent block of 16 message bytes, every time using the previous 16 bytes of ciphertext as the AES input, until you reach the end of the message.  Again, if the last message block is less than the full 16 bytes long, truncate the AES output to match its length.

However, what you seem to be using, based on your code, is the variant of CFB mode that encrypts a single byte at a time, sometimes called CFB-8 (because a byte has 8 bits; full-block CFB using AES would be CFB-128, and there's even a CFB-1 variant that encrypts a single bit at a time).

This CFB-8 mode works exactly the same as the full-block CFB mode, except that you always truncate the AES output to just one byte and XOR it with just one byte of the message to produce a single byte of ciphertext.  (You still always take the previous 16 bytes of ciphertext, prefixed with the IV for the first 16 message bytes, as the AES input.)  That is to say, CFB-8 encryption works like this:

To encrypt the first byte of the message, take the 16-byte IV, feed it into AES, and XOR the first byte of the AES output with the first byte of the message to produce the first byte of ciphertext.  (The remaining 15 bytes of AES output are just thrown away!)
To encrypt the second byte of the message, take the last 15 bytes of the IV plus the first byte of ciphertext that we just produced and, just like before, feed them into AES, take the first byte of the output, and XOR it with the second message byte to produce the second ciphertext byte.
To encrypt the third byte of the message, take the last 14 bytes of the IV, plus the two bytes of ciphertext that we've just produced, feed them into AES and XOR the first byte of the output with the third message byte, just like above, etc.

(Why would you want to use this CFB-8 mode, given that it's about 16 times slower than full-block CFB?  Well, unless you really want to be able to start decrypting the ciphertext at any byte, you really don't — that's the only real advantage it offers over full-block CFB mode.)

In both cases, CFB decryption is just the inverse of this process: to decrypt a (16-byte or 1-byte, depending on the CFB variant used) block of ciphertext, you take the previous 16 bytes of ciphertext (again, with the IV treated as a prefix of the ciphertext for the first 16 bytes), feed them through AES (in the same direction as for encryption!), and XOR the result with the following block (or byte) of ciphertext that you want to decrypt.

Now, while CFB encryption needs to be done sequentially from the start of the message, because you need to encrypt the previous block / byte of the message in order to know the 16 bytes of ciphertext needed for encrypting the next block / byte, CFB decryption can be done in any order (or even in parallel!) because the entire ciphertext is already known.

It turns out that you can, in fact, do this even if your crypto library doesn't give you access to the raw AES block cipher.  The crucial observation here is that, for CFB mode, the IV is really just treated as prefix of the ciphertext that is used to get the encryption / decryption process started.

Thus, to decrypt a CFB ciphertext starting from the $n$-th block / byte, you just take the previous 16 bytes of the ciphertext (prefixed with the actual IV) and pass them to your crypto library as the IV for CFB decryption.

For example, using your CFB-8 "pseudocode" as a basis, you could decrypt a message starting from the $n$-th byte like this:

// key setup
char *key = "whatever";
AES_KEY aes_key;
AES_set_encrypt_key(key, 256, &aes_key);

// encrypt message using CFB-8, prepend IV to ciphertext
unsigned char *in_plain = "helloworld";
const int enc_len = 10;
unsigned char iv_enc[AES_BLOCK_SIZE];
RAND_bytes(iv_enc, AES_BLOCK_SIZE);
unsigned char ciphertext[AES_BLOCK_SIZE + enc_len];
memcpy(ciphertext, iv_enc, AES_BLOCK_SIZE);
unsigned char *out_cipher = ciphertext + AES_BLOCK_SIZE;
AES_cfb8_encrypt(in_plain, out_cipher, enc_len, &aes_key, iv_enc, &num, AES_ENCRYPT);

// decrypt dec_len message bytes starting from byte dec_start of ciphertext
const int dec_start = 1, dec_len = 1;
unsigned char out_plain[dec_len];
unsigned char iv_dec[AES_BLOCK_SIZE];
memcpy(iv_dec, ciphertext + dec_start, AES_BLOCK_SIZE);
unsigned char *in_cipher = ciphertext + dec_start + AES_BLOCK_SIZE;
AES_cfb8_encrypt(in_cipher, out_plain, dec_len, &aes_key, iv_dec, &num, AES_DECRYPT);

Note that I'm using a single ciphertext buffer to store both the IV and the ciphertext, and just passing a pointer into that buffer to the encryption / decryption API.  (I do make a copy of the IV, since apparently the OpenSSL API this is based on modifies the IV string in place.)  In a real application, this ciphertext buffer is what you'd send to the recipient after encryption.  For CFB mode, this is a natural arrangement, and allows the IV for decryption to be obtained simply by taking a pointer to AES_BLOCK_SIZE = 16 bytes before the start of the ciphertext portion we wish to decrypt.

Essentially the same code should work for full-block CFB, too, except that you need to ensure that the starting offset dec_start is an integer multiple of the AES block size, so that decryption starts correctly at a block boundary.

*) Basically, semantic security means that an eavesdropper who can see all your encrypted messages (but cannot modify them or feed you fake messages, and does not know the encryption key) cannot learn anything about the plaintext messages except their length.  Note that none of the "classical" encryption modes, including CFB, offer sufficient protection against active attackers who may try to modify or forge messages; for that you need an authenticated encryption mode.