A signature algorithm should - in general - be thought to contain the hashing method as parameter. Take for instance RSA / PSS. RSA / PSS includes the  EMSA-PSS-ENCODE operation. Here the hash function to use is an option to the algorith.

Step 2 is:

  Let mHash = Hash(M), an octet string of length hLen.

where M is the message to be signed.

"Or do I need to hash the plaintext to provide message integrity?" is therefore a question that is non-sensical for most signature definitions. RSA has deprecated modes that directly sign a message (with message recovery) but those are generally not used. ECDSA is also defined for use with a hash function and EC crypto cannot easily "encrypt the message" with the private key for signature generation.

As you have found out, Signature dsa = Signature.getInstance("SHA256withECDSA"); uses SHA-256 as an option to ECDSA. The hashing will then be performed internally.

Sometimes hash value or intermediate hash value is used as input for signature generation. This can be useful when the device that performs the private key generation is limited in hashing bandwith. E.g. for a smart card you may not want to send all the data to the smart card - sending just the hash is much more efficient.


Yes, you are in the ballpark with your assumptions.

  I will store the encryptedKey with the encrypted data, but can I use the same key for all rows or do I need to generate a new one for each one?

No you can use the same key.

  How does the AAD factor into this? Do I need to store it? Does it need to be unique per row?

If you don't need AAD then you don't need to supply it. AAD means "additional authenticated data", i.e. any data you also want to be authenticated together with the ciphertext, which you want to keep in plaintext.

  Do I need to generate a new nonce for each row of data? Can I store it together with the data?

Yes to both.

Notes on the implementation:

GCMParameterSpec spec = new GCMParameterSpec(16 * 8, nonce);

You should not use "magic literals". Instead use something like Cipher.getBlockSize() * Byte.SIZE. You would of course need to define the cipher earlier. Same goes for the number 12, use a constant e.g. GCM_DEFAULT_NONCE_SIZE_BYTES.

byte[] aad = "Whatever I like".getBytes();
byte[] cipherText = cipher.doFinal(data.getBytes());

You need to specify an explicit encoding here. StandardCharsets.UTF_8 is popular, and not without reason.

Cipher cipher = Cipher.getInstance("AES/GCM/NoPadding", "BC");

Oracles provider also contains GCM, and that may perform much better than the Bouncy Castle one (which will always be programmed in Java). In general, don't specify a provider unless you really need to (and then you may want to make it configurable).


In ECDSA one randomly selects the private key $d_A$ from interval $[1,n-1]$, where the $n$ is the order of the Elliptic curve with $n-1$ non-trivial points, and with the point at infinity, $\mathcal O$ as the trivial point.

$n = \texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}$ that is 64 bytes, or as an integer

$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337$

one should prefer $S = \operatorname{Hash}(f(0)) \pmod n$ so that all the information mixed before the modulus. Actually, one can still use the original number, however, if the number is bigger than the order, it generates unnecessary bigger calculations, when this step is performed

$$s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$$

Note that the $p$ is used to represent the elements of the curve and an easy observation is that it limits the number of points of any curve $\leq p^2$. The Hasse theorem gives a tighter relation;

$$|n-(p+1)|\leq 2{\sqrt  {p}}$$


Mathematics behind the paper "how to leak a secret" for ring signature

From the paper, $E$ is a cipher, i.e., $E_k$ is a permutation. That is, given a secret key $k$, one can compute both the encryption $y=E_k(x)$ (for any $x$) and the decryption $x=E^{-1}_k(y)$ (for any $y$). Therefore, if you know $z$ and all but one $y_i$, you can pick a $v$ (which equals $z$ in the context of ring signature) and get the missing $y_s$ by computing the XOR of $s-1$ $E_k$ encryptions starting from "inside" of the $E(E(...))$ expression and $r-s$ $E_k^{-1}$ decryptions starting from "outside". For instance, if $r=3$ and $s=2$, then $y_2=E_k(y_1\oplus v)\oplus E^{-1}_k(E^{-1}_k(z)\oplus y_3)$.


Can HKDF be instantiated with HMAC-SWIFFT?

The reasoning is wrong: the whole point of the paper is to establish a definition for secure general-purpose KDFs.

In definition 7 of the paper, it is defined that a KDF is secure, if it can withstand distinguishing game from an adversary with capability to query the KDF oracle - that's what something linear like SWIFFT cannot provide.

As for the quoted text in OP, it just means the author is proving his ideas using as few and as straightforwardly useful assumptions as possible, it did not imply what I thought it implied in OP.


How to XOR two hexa numbers by hand fast

If you are lucky, the definition of "simple calculator" may include all non-graphic calculators. In that case, you can use a Casio FX-115ES Plus, which includes hexadecimal and octal base modes, and has an XOR operator. It can operate on groups of octets up to 32 bits.

If you are not that lucky, the XOR table is your best friend. Depending on how many calculations you need to perform, it may very well be faster to create one on a scratch sheet during the exam. You may even be allowed to bring one with you.

I had a requirement for an XOR table to perform quick calculations on a printed code book for cryptographically strong communication over a public voice channel. It also had to be done quickly without the use of a computer or any electronic device, and had to fit on a small 4x6 sheet in the space under the ciphertext.

I came up with several methods to condense the table and still have it usable. If you are clever and resourceful, the knowledge of how to create the condensed versions can allow you to very quickly perform many XOR calculations. There is a recursive pattern to the hexadecimal XOR table which can be exploited, the table above is color coded to show this pattern, which extends down to the individual characters. Here are the condensed tables:

While the above table takes up less space, it has the same amount of characters, and thus takes about the same amount of time to create. A simple rule is required to select the correct characters.

The next level now takes both half the space of the previous, as well as half the characters. The rule is more complex, but a few minutes of practice makes it almost as fast to use as the full table. Even the rule can be simplified with XOR, the result will be correct if the XOR of the rule selections is 1.

The final level is once again half the space and half the characters (almost) as the previous, while requiring an additional rule to get the job done. If you remember the recursive structure and the basic layout of this table, you can recreate it in under a minute with a pen and paper.

Start with the inner column header, first nibble; 0 1 2 3 4 5 6 7
Then add the 2nd nibble, which is the first nibble + 8; 8 9 A B C D E F
The outer column header is the inner column header with the halves flipped
The inner row header is the first half of the inner col header
The outer row header is the first half of the outer col header
Then you fill in the table with the recursive structure, built from the inner column header.
Creating the double compressed table omits the outer headers but uses a full row header.

A single example on the triple table:

25 XOR B6
2 X B = [2a] X [3b] (1 2 2) = 9
Because 2 is the 1st nibble and B is the 2nd, we use the 2nd nibble of [19]
5 X 6 = [5d] x [6e] (1 1 1) = 3
Because 5 is the 1st nibble and 6 is the 1st, we use the 1st nibble of [3b]
Therefore 25 XOR B6 = 93


What is the difference between H(M) and H3(M, s, IDA)?

I'll take the (previous version of the) question as: how to implement a secure hash function $H3$ with 3 arguments, from one hash function $H$ with 1 argument, all with argument(s) in $\{0,1\}^*$.

Note: For a concrete $H$ with the destination set $\mathbb Z_p^*$ thought in the question, we could use SHA3-512 followed by a suitable function; for example, $x\to H(x)=g^{\operatorname{SHA3-512}(x)}$ where $g$ is a generator of $\mathbb Z_p^*$. That $H$ is collision-resistant to $\min\big(512,\log_2\varphi(p)\big)/2$ bits (where $\varphi$ is Euler's totient function); and first and second preimage resistant to $\min\big(512,\log_2\varphi(p)\big)$ bits. Further, it is secure in the Random Oracle Model for suitable choice of $p$.

The construction $H3(M,S,I)=H(\;M\;\|\;S\;\|\;I\;)$ where $\|$ stands for concatenation of bitstrings is such that usual security properties of $H$ (including collision-resistance and security in the Random Oracle Model) demonstrably apply to $H3$, if at most one of $M$, $S$, $I$ is of variable size.

Otherwise it is not secure in general: exhibiting a collision is trivial; for example, $H3(\text{01},\text{0101},\text{0101})=H3(\text{0101},\text{0101},\text{01})$. However, with the middle parameters $S$ random, secret, and non-malleable (as presumably in the question), there is no spectacularly practical attack.

A secure construction for variable-size inputs is $H3\big(M,S,I\big)=H\big(\;E(M)\;\|\;E(S)\;\|\;I\;\big)$, where $E$ is a prefix-free function on $\{0,1\}^*$ ; that is, such that
$$\forall X\in \{0,1\}^*,\forall Y\in \{0,1\}^*,\forall Z\in \{0,1\}^*,E(X)=E(Y)\|Z\implies X=Y$$
Examples of suitable prefix-free constructions for $E(X)$:

prefix each bit in $X$ with a $\text{0}$ bit, then append a final $\text{1}$.
prefix $X$ of length $b$ bits with $b+1$ encoded in big-endian binary (thus with $\lceil\log_2(b+1)\rceil$ bits starting with a $\text{1}$ bit), then prefix that with $\lceil\log_2(b+1)\rceil-1$ bits at $\text{0}$.
the encoding of bitstrings in ASN.1 DER then re-encoded into a bitstring (e.g. using big-endian conventions for internal consistency).


Advanced Encryption Standard Algorithm Secret Key

One very important thing you are missing is the idea behind AddRoundKey and the Key Schedule.

Each round, there is a new round-key. The round key is derived from the main key. So, say you have a 128-bit block (AES) and a 256-bit key. The internal state is 128-bits and the round key is 128-bits. The specification states that for this configuration, there will be 14 rounds. Since the round-key changes for each round, it is easy to see that all 256-bits of the main key will be used over the 14 rounds.

To see exactly how all 256-bits of the main key are used, you'll have to dive into the details of the key schedule.


Why is pseudorandom OTP (P-OTP) IND-CPA insecure

The game you stated is not the IND-CPA game, it is the IND-EAV game, where the adversary is given only the challenge ciphertext and is asked to guess the message being encrypted. In the IND-CPA game,the adversary is given access to an encryption oracle that can encrypt arbitrary messages of his choice.

The main reason why P-OTP can not be CPA-secure is because it is deterministic, that is, if you encrypt the same plaintext twice you'll get the same ciphertext. In general, any scheme with this property can not be CPA-secure, can you figure out why?

On the other hand, PRF+OTP is not deterministic: it refreshes each encryption with a random value $r$. This key difference makes the scheme CPA-secure, the proof can be found in any basic book like Katz' Modern Cryptography (Thm 3.31 in the 2nd edition), but the basic idea is that if the value $r$ is not repeated in the oracle's queries, then the attacker get no information about the message being encrypted (so you have perfect secrecy in this case, just like in the OTP), and the probability that this does not occurre is small enough.


In pairwise key hierarchy there are two root keys: pre-shared key (PSK) and Authentication, Authorization, and Accounting Key (AAAK). From these two keys pairwise master key (PMK) is derived. In the case of PSK, PMK is equal to PSK. In other case, PMK is obtained by taking the first 256 bits of AAAK. Now, to the question about generating pairwise transient key (PTK).

PTK is generated from PMK by using pseudorandom function (PRF) which is based on HMAC-SHA-1. The formula will be: PTK=PRF(PMK, X, an||stn||amac||stmac). Where X is the parameter indicating the length of PTK. Note that, in CCMP X=384 bits, whereas in TKIP X=512 bits.

Unfortunately, I'll not be able to answer your second question. If nobody else will reply, I'll do it later. The good reference is this document IEEE802.11i-2004


How to sequence SHA256 block circuit to obtain hash of a message comprising multiple 512 blocks?

One can't use the circuit exactly as given.

To build a two-blocks SHA-256, the second round must be fed as input both the second 512-bit (padded) block, and the 256-bit output by the first round. The final hash is then the 256-bit output of the second round.

For the first round, and in the circuit given, the only variable inputs are the 512-bit first block; the other 256 input bits are always set to a constant defined by SHA-256, equal to 0x6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19, and thus these 256 input bits are missing in the equations given.

I guess you'll have to rewrite (or get from another source) the equations of a SHA-256 round from the definition, and then check that when the 256-bit input from the previous round is set to the right constant, your work is equivalent to the equations given.


Which algorithm has better performance (HMAC, UMAC, and Poly1305)?

First of all, HMAC—with any particular hash function, say HMAC-SHA256—is a different type of thing from UMAC and Poly1305.  So it would be misleading to compare them directly.

HMAC-SHA256 is a pseudorandom function family, or PRF, with long inputs and short outputs, meaning a keyed family of functions $H_k\colon \{0,1\}^* \to \{0,1\}^{256}$ such that if the 256-bit key $k$ is uniformly distributed, then $H_k$ appears to be uniformly distributed among all functions $F\colon \{0,1\}^* \to \{0,1\}^{256}$.  You can use this to authenticate messages by using $t = H_k(m)$ as an authentication tag, because an adversary not knowing $k$ can't guess $H_k(m)$ much better than an adversary not knowing $F$ can guess $F(m)$, which in turn they have a $2^{-256}$ chance of guessing in one try.

UMAC and Poly1305 are one-time authenticators.  You can use a key $k$ once to authenticate a single message $m$ by using $t = \operatorname{Poly1305}_k(m)$ as an authentication tag.  If you ever reveal $\operatorname{Poly1305}_k(m)$ and $\operatorname{Poly1305}_k(m')$ where $m \ne m'$, an adversary can trivially compute $k$ and forge authentication tags on any message of their choice.  But you can extend these to work on many messages, each with a distinct sequence number or noncolliding random token $n$ called a nonce, by composing them with a PRF, and instead using, e.g., $t = \operatorname{Poly1305}_{k_n}(m)$, where $k_n = \operatorname{HMAC-SHA256}_k(n)$.  You must never reuse the same $(k, n)$ pair with two different messages.

For more on message authentication codes, one-time authenticators, HMACs, and pseudorandom function families, an earlier question has several good answers.

Typically, these days, Poly1305 is used in a predefined composition called NaCl crypto_secretbox_xsalsa20poly1305 or one of libsodium's variants of it, which uses the PRF XSalsa20 both to derive the one-time keys $k_n$ and as a stream cipher to derive one-time pads for encrypting a message, at the same time.  This authenticated encryption composition, crypto_secretbox_xsalsa20poly1305, is much faster on pretty much any CPU than any authenticated encryption involving HMAC.  (Possible exception: Maybe on a tiny microcontroller you will have hardware support for HMAC-SHA256, but not for XSalsa20 or Poly1305.)

Does that mean HMAC-SHA256 is useless?  No.  You don't always have a message sequence number in a conversation.  For example, if you are distributing a bearer token in a mostly stateless web application, in order to use Poly1305 as an authenticator you would have to include a ${\geq}192$-bit randomly chosen nonce as an input to a PRF to select the key, which together with the 128-bit Poly1305 output would cost 320 bits of space for an authenticator tag, while for essentially the same security (for short messages and low volumes of data) you could use the 128-bit truncation of HMAC-SHA256 instead, or BLAKE2s-128, or KMAC128-128.


If you can live with security against passive adversaries here is how you could do that: Denote the inputs of Alice and Bob $x$ and $y$ respectively. Bob generates public- and private-key for the FHE scheme. He sends the public key to Alice a long with an encryption of his input. Alice encrypts her own input and computes an encryption of $g(x,y)$ using the homomorphic properties of the FHE scheme (i.e., using the eval algorithm). Alice then sends this encryption to Bob, who decrypts and now has the intended output.

Note that if you assume active adversaries this breaks down because you have no guarantee that Alice will compute the agreed upon function.

Edit:

You would need to make sure that the ciphertext Alice sends to Bob does not reveal more information about Alices input than $g(x,y)$. As Ricky points out in the comment this may require some additional properties of the FHE scheme. One way to ensure this (as Ricky points out) is to require the FHE scheme to be circuit private. This means that an encryption of $g(x,y)$ obtained using the eval algorithm is indistinguishable from a fresh encryption of $g(x,y)$, i.e., an encryption obtained by directly encrypting the result $g(x,y)$.


Is there an easy way to calculate "d" in the RSA algorithm?

The easiest way which is widely known to calculate a modular inverse is finding the smallest $k\in\mathbb N$ such that the following expression is an integral integer:

$$\frac{1+k\cdot \varphi}{e}$$

If this is an integral integer, it is the inverse of $e$ modulo $\varphi$ and thus $d$ and you'll find it with at most $e$ tries.

The issue obviously know is that the run-time of this will grow linearly with the size of $e$, as opposed to the extended euclidean algorithm (EEA) which will run in time proportional to (a power of) the logarithm of $e$, which will especially be much faster than the above method when $e$ is chosen as large as the modulus. If you want to see examples and how-tos on the algorithm, Wikipedia is your friend as usual.


The way in which the stego key is used depends on the type of media and algorithm used for hiding data. For example, in image steganography the stego key is used to select the pixels where the data will be hidden. An attacker without the key does not know what pixels he have to read.

Note that before hiding data is usual to encrypt the message so a crypto key is also needed.

On the other hand, the mechanism used to exchange a key using steganography is known as Public-Key Steganography. Check the following reference:

https://www.cs.cmu.edu/~biglou/pubkeystego.pdf

A simple option is to use public key cryptography hiding the message encrypted with the public key into the image (we do this without stego key, so that anyone can extract it).
An attacker that extracts the message will not be able to tell whether the data extracted is a cipher text or random noise. Only the one with the private key will be able to read the message.


Key Exchange & key Distribution in symmetric key cryptography

I think the difference between key exchange and key distribution can be very subtle, but it probably comes down to the former being an active way of "dealing" keys, while the latter is something that can be more passive.

I think a few examples may make this more clear.

Key exchange

Alice and Bob want to communicate over a private channel. They both know each other's public keys ($PK_A$ and $PK_B$), and Alice sends Bob a message, a content encryption key, which she encrypted using Bob's public key.

Bob recovers this key by decrypting it using his private key, tied to $PK_B$.

Alice and Bob now have a common content encryption key, which they exchanged.

Key agreement

Not really covered by your question, but mentioned by @SEJPM to be relevant, key agreement is very much like key exchange, except that the key as such never crossed the channel.

This for example happens in Diffie-Hellman key agreement, where both parties have (publically) agreed to use a generator $g$ and a modulus $p$. Alice and Bob respectively choose secret integers $a$ and $b$, and they exchange values $A = g^a \mod p$ and $B=g^b \mod p$. Both Alice and Bob can then calculate the same common key (they agreed upon a key) $K \equiv A^b \mod p \equiv B^a \mod p = g^{ab} \mod p$, which they can use (after using a key derivation function) for a symmetric cipher.

N.b., the difference between key agreement and key exchange might be vague, up to the point that the terms are used interchangeably.

Key distribution

Key distribution deals with the problem that if $N$ parties want to securely communicate with each other, without any other party eavesdropping on the conversation, $\frac{N\cdot(N-1)}{2}$ keys are to be distributed.

This is, for example, a problem in the key distribution in wireless sensor networks, or the Web of Trust in PGP.

For example in PGP, all participants have a public key, which they can use in a fitting key agreement/key exchange protocol to establish a private channel with another participant.

In wireless sensor networks, depending on the expected number of nodes, it is sometimes opted to pre-distribute (hence key-distribution) a list of symmetric keys.

Key distribution is thus more of solving a many-to-many problem, while key agreement and key exchange both cover the one-to-one problem.


What is the difference between MACTripleDES and TripleDES?

Triple DES is a block cipher.  (Specifically, it's a variant of the old DES block cipher with better security, but several times lower performance.)  You can use it to encrypt small blocks of data (64 bits = 8 bytes, for Triple DES), but what it's really useful for is as a building block for other cryptographic schemes, such as stream encryption or message authentication codes (MACs).

MACTripleDES is, apparently, a class in the Microsoft .NET framework that provides some kind of a MAC using Triple DES.  The documentation doesn't actually seem to say which MAC construction it uses, but this answer on SO implies that it's classic CBC-MAC.

Note that raw CBC-MAC is not, by itself, secure for variable-length messages.  To make it secure, you need to use one of the techniques described in the linked Wikipedia article (prepending the length to the message, encrypting the output with a different key, or using a separate MAC key for each message length), or use a more modern MAC algorithm like CMAC instead.  (You may also wish to consider using a more modern cipher with a larger key and block size and better performance than Triple DES, such AES.)


How to break CBC cipher with partly known plaintext?

$\mathrm{Enc}_k$ always transforms the same block value to the same block value. Since blocks are only one byte long, there are only 256 different block values. So you can build a table of those from the parts of the plaintext that you know. Once you've built that table, you can use it in the reverse direction to calculate $\mathrm{Dec}_k$.

$$
\begin{array}{l|l}
x & \mathrm{Enc}_k(x) \\ \hline
0 & \_ \\
1 & \_ \\
\vdots \\
255 & \_ \\
\end{array}
$$

Knowing $M_1$, the equation $C_1 = \mathrm{Enc}_k(M_1 \oplus C_0)$ gives you one entry in the table. More generally, whenever you know the value $M_i$, the equation $C_{i+1} = \mathrm{Enc}_k(M_{i+1} \oplus C_i)$ gives you one entry in the table. Some positions may call $\mathrm{Enc}_k$ on the same input as another position, so it may take more than 256 known bytes in the plaintext, but with a few hundred bytes of known plaintext the probability of missing entries decreases rapidly¹ since the inputs for different values of $i$ are essentially random.

If there are missing values in the table, you can narrow things down in two ways. First, since $\mathrm{Enc}_k$ is a permutation, all the values in the second column are distinct. Second, all the $M_i$ are probably printable characters, which limits the possibilities. Within the scope of the exercise, I'd expect that if there are any blanks, they're easy to fill in with a little hand-driven calculation.

The core of the problem is the 8-bit block. An 8-bit block is far, far too short. In the real world, older block ciphers such as DES and ((X)X)TEA have 64-bit blocks, and modern block ciphers have 128-bit blocks. Even with a 64-bit block, such a table attack is unlikely to give any useful results (the table would require 128 EiB of sttorage, and you'd need roughly that amount of guessable plaintext with a known ciphertext to build it). 64-bit blocks are vulnerable to a sparse version of this attack where you hope that $\mathrm{Enc}_k$ has been called twice on the same input, and this reveals something about the message (if $C_i = C_j$ then $M_i \oplus C_{i-1} = M_j \oplus C_{j-1}$, which reveals the value of $M_i \oplus M_j$, and in particular reveals $M_j$ if you know $M_i$). And you only need about $2^{32}$ blocks of message to have a decent chance of a repeated block value (birthday bound), which makes this attack practical (most famously as Sweet32).

CBC itself with a block cipher with a decent-size block and with a random IV is secure even against chosen-plaintext attacks (IND-CPA). However, it is not at all secure against adaptative chosen-plaintext attacks, where the attacker can submit some plaintext to encrypt after seeing the previous portion of the ciphertext.

   In the adaptative case, I know $C_i$ and am allowed to submit $M_{i+1}$ which lets me learn $C_{i+1} = \mathrm{Enc}_k(M_{i+1} \oplus C_i)$. So I choose $M_{i+1} = C_i \oplus x$ and this way I can learn $\mathrm{Enc}_k(x)$ for an arbitrary $x$. If I've guessed a plausible value for $M_j$ for some $j$, this lets me verify this guess by testing whether $C_{i+1} = C_j$.

CBC as used in practice is not secure in general because it requires padding, since CBC can only encrypt a whole number of blocks. Padding is vulnerable to padding oracle attacks in scenarios where the attacker can submit chosen ciphertext. This is why CBC is deprecated, especially for communication. (It can be ok for storage where the adversary might be able to see ciphertext, e.g. from leaked backups, but has no way to inject ciphertext.)

¹  Unless $\mathrm{Enc}_k$ has some correlation with $M$.


For part a) of your question: In this case 2 would be the order of 187 in the multiplicative group modulo 1457. This means you could retrieve the factors of 1457 using the formula gcd($187^{2/2}-1$, 1457) and gcd($187^{2/2}+1$, 1457).

Having the factors of 1457, you can compute $\phi$ with ease.

@fgrieu: The calculation is taken from the non-quantum part of Shor's Algorithm. Basically it's the same as what you mentioned in the comments of the question. Thanks for pointing out my mistake. I mixed up some numbers in my gcd calculation...


Verifying signature of plaintext using encrypted message only

What you want is a "signature-friendly" encryption scheme, where one can verify a signature on an encrypted message. We can define it as follows:

KeyGen: generate keys $(\mathsf{pk},\mathsf{sk})$
Encrypt: given $\mathsf{pk}$, a message $m$, and a signature $s$, output a ciphertext $c$
Decrypt: given $\mathsf{sk}$, and a ciphertext $c$, output a plaintext $m$
Verify: given $\mathsf{pk}$, a ciphertext $c$, and a signature $s$, output a bit $b$

With the following (informal) guarantees: (KeyGen,Encrypt,Decrypt) is one-way (as pointed out by SEJPM in the comments to the question, the scheme cannot be IND-CPA secure), encryption/decryption work correctly, and Verify($\mathsf{pk},c,s$) outputs 1 if and only if Check(Decrypt($c,\mathsf{sk}$),$s)=1$, where Check is the signature verification algorithm.

We can build such an encryption scheme in a natural way, starting from any encryption scheme, any signature scheme, and a non-interactive zero-knowledge (NIZK) proof system. A NIZK proof system for a language $L$ works as follows:

Setup: generate a common reference string crs
Prove: given a word $x$ and a witness $w$ for $x\in L$ (and the crs), output a proof $\pi$ of $x\in L$
Verify: given a word $x$ and a proof $\pi$ (and the crs), output a bit

with the following guarantees: if the prover is honest (and $x\in L$), Verify outputs 1, if $x\notin L$, no prover can construct a proof $\pi$ accepted by Verify, and the proof leaks no information about $w$ (slightly more formally, the proof can be simulated without $w$).

Let $E$ denote some arbitrary encryption scheme, and $S$ denote some arbitrary signature scheme. Consider a NIZK proof system for the language $L$ of triples $(\mathsf{pk},c,s)$ such that $c$ is an encryption with $\mathsf{pk}$ (under $E$) of a message $m$ satisfying Check$(m,s)=1$ (where Check is the signature verification algorithm of $S$). The witness for $(\mathsf{pk},c,s)\in L$ is the pair $(m,r)$ such that $c=$Encrypt$(\mathsf{pk},m;r)$ and Check$(m,s)=1$.

KeyGen: generates keys $(\mathsf{pk},\mathsf{sk})$ for $E$, and a common reference string crs for the NIZK proof system. The public key is $(\mathsf{pk},$crs$)$ an the secret key is $\mathsf{sk}$.
Encrypt: given $(\mathsf{pk}$,crs$)$, a message $m$, and a signature $s$, check that Check$(m,s)=1$; output $\bot$ if this is not the case. Else, compute an encryption $c$ of $m$ under $E$ with $\mathsf{pk}$ (with a random coin $r$), and a proof $\pi$ of $(\mathsf{pk},c,s)\in L$, using witness $(m,r)$. Output the ciphertext $(c,\pi)$.
Decrypt: given a ciphertext $(c,\pi)$ and $\mathsf{sk}$, output the decryption of $c$ under $E$ with $\mathsf{sk}$.
Verify: given the public key $(\mathsf{pk}$,crs$)$, a ciphertext $(c,\pi)$, and a signature $s$, output NIZK.Verify(crs,$(\mathsf{pk},c,s), \pi$).

The security properties of the above scheme follow immediately from those of $E$ and from the zero-knowledge property of the NIZK proof system, and the signature verification property follows from the soundness of the NIZK proof system.

The above scheme is a somewhat generic template; to get an efficient construction, one must carefully choose the underlying primitives, with proof-friendly encryption scheme and signature scheme. To obtain better efficiency, it would probably be wise to use an interactive zero-knowledge proof, and to make it non-interactive in the random oracle model using the Fiat-Shamir transform. It requires some work, but it should be feasible to make this quite efficient with appropriate choice of the underlying primitives.


How is the EAX-mode used in EAP-PSK (RFC 4764)?

In RFC 4764, the ciphertext does not include the authentication tag created by EAX (which is treated separately); you can see this in figure 1, where they show the ciphertext (of length L) and the tag separately.

In contrast, the test vectors do include the authentication tag, and that additional length make the ciphertexts look longer.


Yes, what you have is enough to recover p in both cases.

In the first case you just need to write the proper equation to be then solved thanks to Coppersmith method to find small roots of univariate polynomial.
As explained by Alexander May in pages 40 and 41 of his thesis what you ask is always doable if the unknown bits are consecutive (and you have at least $\frac{n}{4}$ known bits).

You just need to write the correct polynomial and let Coppersmith's method find the solution. The preconditions to using Coppersmith's method are:

$f_p(x)=0 \pmod p$ at the point we want to evaluate (i.e., for the middle bits).
$f_p(x)$ is monic (i.e., the leading coefficient of $f$ is 1).

First, let's start writing $p$ in terms of $x$. Let $MID(p)$ represent the middle bits of $p$. So $p = MSB(p) + MID(p) · 2^{n/8} + LSB(p)$**. Now let's rewrite this as a function of $x$. Let $g_p(x) = MSB(p) + x · 2^{n/8} + LSB(p)$. We have to make this function monic. To do this, we can multiply $g_p(x)$ by $(2^{n/8})^{-1} \mod N$. We can't do it $\mod p$ since we don't know how to compute inverses $\mod p$ as $p$ is unknown. Ok, so let's rewrite our functions,

$$
f_p(x) =g_p(x)(2^{n/8})^{-1} \mod N = x + MSB(p)\cdot (2^{n/8})^{-1} + x + LSB(p) (2^{n/8})^{-1}
$$

Now all that's left before computing Coppersmith's method is to check that $f_p(MID(p))=0 \mod p$.

$$
f(x)=MID(p)+MSB(p)(2^{n/8})^{-1}+LSB(p)(2^{n/8})^{-1}=p(2^{n/8})^{-1}
$$

Note that this can be rewritten as: $pC$, and any number multiplied by $p$ in $\mod p$ is $0 \mod p$ i.e., $pC = 0 \mod p$.

I successfully tested a solution for the problem you described using sage, the solution is available here.

In the second case, as poncho pointed out, it is trivial to recover the $LSB(p)$ knowing the $LSB(q)$, just note that: $LSB(p) = N * LSB(q)^{-1}\bmod{2^{n/8}}  $

In case your unknown bits of p are not consecutive, then it's not so easy and you probably will need more bits: see this paper by Herrmann and May that basically states that $log(2)n \approx 0.7n $ bits of $p$ are always enough to solve the equation but the complexity is exponential in the number of different not consecutive unknown bit blocks.

** I left the notation in terms of MSB(p) to be consistent with the first author for this answer, but I think showing that the preconditions for applying that Coppersmith hold is easier when we think of the MSB(p) as the bit values shifted by some $2^{n/k}$ where $k$ is some constant. This notation can be seen in referring to the middle bits $MID(p) \cdot (2^{n/8})$.


Standard deviation of gaussian noise in FHEW scheme

Apologies for seeing this question just now. For your first question, well, there seems to be a typo: I should have written $\|s\|^2 \leq n/2$, and then we have $\sqrt{(\|s\|^2 +1) /12 }  = \sqrt{251/12} \approx 4.57$.

Now, we take 2 ciphertext with LWE error of std-deviation $\beta$, and sum them. Assuming independence the std-dev of the sum of the errors is $\sqrt 2 \beta$. For correctness, we need this sum of errors to be less than $q/8$ (Here, to save every last bit, we relax the naive condition stated in Lemma 7, and directly bound the sum $q/8 + |e_0 + e_1|$ by $q/4$ rather than bounding $e_0$ and $e_1$).

answer to comment on decreasing error via swapping KeySwitch and $\textsf{HomNAND}$

Just for the sake of this explanation, let me lie about the actual noise propagation, and assume that each operation HN and KS just add a constant to the quantity of noise, denoted $h$ and $k$.

The ``easy to describe scheme'' does $\textsf{HomNAND}(KS(X_1), KS(X_2))$, which leads to an error of the form $(x_1 + k) + (x_2 + k) + h = x_1 + x_2 + h + 2k$.

The ``better but less easy to describe scheme'' does $KS(\textsf{HomNAND}(X1, X_2)) $which leads to and error $(x_1+x_2+h) + k$. That is one ks less.

It turns out that even with the actual formula, we also gain a little bit on the final error with this trick.


Is it hard to recover $p$ from $k \phi(p)$?

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?"  It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of possibilities; we will consider it success if that attacker can create such a list with the correct value on it somewhere.

The answer would depend on how big $k$ (and $p-1$) is (and, how big the product is).  If either is small (say, no more than 100 or 200 bits), or alternately smooth (that is, consists of prime factors that are small), then ECM would be able to pull out $k$ (or $p-1$), giving the attacker a good guess.  In addition, if both have large factors, but the product is sufficiently small, then NFS would be able to factor the product.  However, if both have large primes as factors, then it is unlikely to be feasible to recover $p$.

However, the above assumes that the attacker has no further information about either $p$ or $k$; if he (for example) also knows the value $pq$ (for a large prime $q$), then it is easy for him to derive $p$; he selects a random value $a$, and computes $gcd( pq, a^{k\phi(p)}-1 \bmod pq )$; with high probability, that's $p$ (assuming $k$ is unrelated to $q$; if the value of $k$ is (say) a multiple of $q-1$, then there are other ways to recover $p$ and $q$.


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

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

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

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


Multiplication instead of Key Derivation Function?

Is it a risk to replace the use of a pbkdf function with a multiplication of the form S=J**K, creating a big number and only use the bits we need to exchange the only message that conversation needs using a xor operation between S and the message?

One concern I would have would be a possible bias in the bits of $S$; at the very least, the lsbit of $S$ would be 0 with probability 0.75; if you use that to xor with the message, that would mean that the attacker would learn some probabilistic information about that bit.

In addition, if you encrypt the message without doing any sort of integrity protection, that means that the attacker can modify the encrypted message (for example, by flipping bits within the ciphertext) which would yield predictable changes in the decryption of the modified message.

I would suggest that you stick with conventional wisdom when implementing your system; for example, you might want to use:

$$S = \operatorname{SHA-256}( J \mathbin\| K )$$

(possibly along with nonces that are exchanged along with the DH negotiation), and then use $S$ as a key to AES-GCM, which encrypts the actual message.


Prove the size of a message in a succinct way

If the commitment is additively homomorphic then there are methods of doing this. They relate more to the numeric range, but these are essentially equivalent. First, it is possible to use the proofs of non-negativity of Helga Lipmaa in On Diophantine Complexity and Statistical Zero-Knowledge Arguments. These prove maximum by using the additive homomorphic property to subtract the minimum value, and then have the prover prove that the result is non-negative. Simpler solutions (some a bit weaker) appear in Efficient Proofs that a Committed Number Lies in an Interval. I don't remember if these can be made non-interactive using Fiat-Shamir, but I think that they can (and they are enough for you to start doing your own research into it).


Why do we use groups, rings and fields in cryptography?

Kindly, let me know what was the actual problem which leads us to use groups in cyptogrpahy?

Well, we use groups and other similar mathematical constructs because:

We found there are problems that appeared to be difficult to solve with those groups

We found ways to translate the difficulty of solving those problems into the cryptographical strength of some object (such as an RSA public key encryption, or a signature), that is, you can't break the cryptographical object (e.g. decrypt the encrypted ciphertext without the key) unless you can solve the hard problem.

The second part is crucial; we know problems that are much harder to solve than the ones we use in cryptography; however we don't know how to exploit those.
That's pretty much the answer; the answer to "why do we use groups" is pretty much the same as Willy Sutton supposedly gave to the question "why do you rob banks" - "because that's where the money is" - that is, we do it because it provides the cryptographical security we're looking for.

I believe if I don't know "why" then everything is useless.

Then you're in trouble with cryptography - one of the things we do not know is why these hard problems are actually hard (if, in fact, they are) - the most we know is that a number of fairly bright people have tried to do a number of rather clever tricks to solve them, and none of them worked.


How can finding a collision help an attacker with tampering messages with HMAC

From that same document:

  In any case the minimal recommended length for K is L bytes (as the hash output length).

So as long as the key is fully randomized, i.e. a cryptographically strong key, the time for brute forcing is at least the same or higher than the time finding a collision. If your key is indeed smaller or not fully randomized, then brute forcing attacks may indeed apply.

If you can find a collision, then you could possibly replace the message. But the hash would still be dependent on the key, so you should see this as a strict lower bound. An attacker would still not break HMAC by only finding a collision (otherwise HMAC with MD5 would be broken by now).

For instance, Wikipedia mentions:

  The cryptographic strength of the HMAC depends upon the size of the secret key that is used. The most common attack against HMACs is brute force to uncover the secret key. HMACs are substantially less affected by collisions than their underlying hashing algorithms alone.Therefore, HMAC-MD5 does not suffer from the same weaknesses that have been found in MD5.


Mathematically / statistically "safe" way to differentiate between crypto and random blob?

If anything can distinguish a blob of random data from an encryption of some (known) data (other than any intentionally added data formats, like a header or a length difference), the encryption algorithm is called broken.
(This is one of the variants of the ciphertext  indistinguishability criterion for ciphers.)

As there are several encryption algorithms which seem to fulfill this criterion, this means in reverse, no, you can't prove that some self-created blob of random data is really random.

A possible solution would be to have some third party generate the random data for you, and sign a confirmation that it is random. I'm not sure that there is such a service – while random.org offers random numbers (or bytes), I don't see something which can certify those.
(One idea would be to store a transcript of the TLS connection by which you downloaded it, but that can also be faked.)

You can download pregenerated files from random.org – assuming random.org isn't part of your conspiracy, this should be good enough to prove you don't have encrypted data there. (But it would also be utterly useless to carry them around in your USB drive, other than to annoy the border guards.)

Another thing to keep in mind: Even if you have real random data with you (which you might previously have shared with someone else), you (or your partner) can later use this to encrypt plaintext (using a one-time-pad) to be sent over the Internet. So allowing you to bring random data into the country just opens the way for you to use encryption later.


Look at the rest of the code around it. The hash value gets used twice: once to feed back into the pool and once as an output. Ideally those two would be independent, but the requirement is that an attacker who sees the output is not be able to tell what went into the pool.

Another option would be to halve the hash, throw half of it back in and the other half out. However, in that case the data being fed back would be just 80 bits - short enough for a brute force attack without knowing the output. Hence the comment earlier in the file: "By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash."

So basically the XOR is used as a cheap one way function. Is it any better than taking just the first half and throwing both back in the pool? SHA-1 would have to be pretty broken for that to make any difference.

Then again, this code to fold in half is actually from a time when using SHA-1 was an option and MD5 the default (early-mid 90s, not sure exactly when). So distrusting the hash was not nearly as paranoid as it seems today. Later patches have left it in because it's "harmless".


What is the relationship between a NIZK protocol and a digital signature scheme?

Recall that in strong existential unforgeability for
digital signatures, we want it to be the case that even after seeing many signatures under different instances, it should still not be possible to create a new signature unless you know the secret key (equivalently witness in a NIZK).

So, one can use a NIZK to design a digital signature (of knowledge), but the underlying NIZK needs to provide a more stronger version of soundness (a standard NIZK only provides soundness) that technically is known as simulation-sound extractability. Intuitively, simulation-sound extractability in NIZKs is equivalent to concept of strong existential unforgeability. More precisely, simulation-sound extractability implies that it is only possible to prove instances to which you know a witness, even when you have already seen a number of simulated proofs (signatures).

To sum up, a digital signature of knowledge can be designed using a NIZK that guarantees simulation-sound extractability.


Is it safe to distribute different portions of the same data encrypted with different AES keys?

We assume that Bob knows B and Enc(K1, ABC) but doesn't know K1, A or C. Then the only information Bob can learn about ABC is the length of AC (not even the length of A and C individually). If Bob knows Enc(K1, M), Bob can't even tell whether B is a substring of M. This is assuming that Enc is any sensible symmetric cipher, including AES-CBC (with a random IV), AES-CTR (with a initial counter value that doesn't overlap any counter value used for another input with the same key), AES-GCM (with a non-repeated nonce), AES-CCM (with a non-repeated nonce), etc.

AES itself is a permutation on 128-bit blocks, not a way to encrypt a message. involves some xor operations internally, but this is not a xor between the message and something else. There is no simple arithmetic relation involving related inputs and related outputs, otherwise we'd consider it to be completely broken. Given AES_Enc(K, A) and AES_Enc(K, B) where A and B are 128-bit strings, the only thing you can deduce about A and B is whether they're equal or not (A = B if and only if AES_Enc(K, A) = AES_Enc(K, B)).

There are ways to encrypt a message that involve xoring the message with a keystream which is produced using AES as a building block: ciphertext = plaintext ⊕ keystream. AES-CTR is a relatively simple one, where the keystream is built by encrypting successive values. Suppose you have the encryption of two messages with the same key:

ciphertext1 = plaintext1 ⊕ keystream1
ciphertext2 = plaintext2 ⊕ keystream2

keystream1 and keystream2 are indistinguishable from random to someone who doesn't know the key. Therefore ciphertext1 and ciphertext2 are also indistinguishable from random. Any relationship between the plaintexts is completely hidden by this random data, and not visible as a relationship between the ciphertexts.

Badly used modes of operation, for example using a non-random IV, can cause keystream1 and keystream2 to be related in some way. But that's due to badly using the encryption mechanism. The standard mechanisms themselves don't have such weaknesses.

Note that this assumes that Bob doesn't know the key. If Bob knows some part of K1, all bets are off. Never reveal part of a secret key.


The reason I was taught why poly-time is the conventional way to define "efficient" algorithms is that it's the smallest notion closed under various forms of composition.

If we have an algorithm for deciding whether some input is in some language and we let $N$ be the length of the input, then we'd like to call all the following operations efficient:

Returning "yes" or "no" all the time costs one (or constant) time.
Reading the input costs $N$ time.
Calling one efficient algorithm taking time $A(N)$, then passing the result through an efficient algorithm taking time $B(N)$ gives a total time of $A(N) + B(N)$, so our class of "efficient running times" should be closed under addition.
If an algorithm taking $A(N)$ time on its own is efficient, and you have an algorithm with $A(N)$ steps where each step is a call to another efficient algorithm taking $B(N)$ time, then you end up with $A(N)B(N)$ time, so "efficiency" should be closed under multiplication.

Plug all that together and you get "polynomial in $N$" as the smallest possible "efficiency notion" - which does not of course exclude other, larger notions such as the ones mentioned above.

This is not so much a cryptography as a general complexity theory/theoretical CS point, which cryptographers have borrowed for their notions of security.


Can two rc4 encoded messages be XORed and decrypted if encrypted with the same key?

No.  The key is not used to encrypt the message.  RC4 is a stream cipher.  The key is utilized to generate a one-time pad to encrypt the message.  This is what you have actually done:

E1 = RC4(M1,K) = M1 XOR PAD(k)
E2 = RC4(M2,K) = M2 XOR PAD(k)

E1 XOR E2 => M1 XOR M2

Ergo, RC4 keys are safe for single time use.  You need to concatenate a nonce to the key for multiple use.


How to find the right additive polynomial in inverse affine transformation in AES

The Affine Transformation for AES Sbox is given by

Let M b the 8x8 binary matrix and C be the affine additive constant then

B = M x A xor C --------------- (1)

The straight forward reverse to this transformation is

A = M-1 * ( B xor C ) --------------- (2)

Where as the inverse of Affine Transformation is given as

Let D be the additive constant used in above inverse affine transformation then

A = ( M-1 x B ) xor D --------------- (3)

Place value of B from (1) in (3)

A = ( ( M-1 x (M x A xor C ) ) xor D

A = ( ( M-1 x M x A) xor ( M-1 x C ) ) xor D

Multiplying M with M-1 will be Identity, thus

A = A xor (M-1 x C) xor D

this implies

D = M-1 x C

and thats how the additive constant in inverse affine transformation have been calculated.

in fact it is


Your XOR equations are wrong.
You wrote:

    1110
XOR 0000
  = 0001

But it's not how the XOR works. 1 xor 0 = 1, and in your example it somehow turns into 0 wich is an error. Reference the xor table: https://en.wikipedia.org/wiki/Exclusive_or

So, the correct answer for S1(x1) XOR S1(x2) is:

    1110
XOR 0000
  = 1110

and for x1 xor x2:

    0000000
XOR 0000001
  = 0000001


This started as a comment to CodeinChaos's answer, but did not fit. I'm trying to regurgitate, in layman's terms, my understanding of the consequences on $\operatorname{SHA-256d}$ of the paper he quotes: Yevgeniy Dodis, Thomas Ristenpart, John Steinberger, Stefano Tessaro: To Hash or Not to Hash Again? (In) differentiability Results for H2 and HMAC, in proceedings of Crypto 2012.

This paper does NOT imply that we could determine with sizable advantage over a random choice whether a black box with $256$-bit input and output is a Random Oracle, or implements $\operatorname{SHA-256d}$, using $2^{64}$ queries to that black box, without knowing the initialization value used by $\operatorname{SHA-256}$ (we assume it is replaced by a random $256$-bit value), and using much less computational work than necessary to break $\operatorname{SHA-256}$ with sizable probability. In other words, $\operatorname{SHA-256d}$ remains a secure Pseudo Random Function in that standard definition of the term. That's proven by the standard argument: a distinguisher (in that definition) able to break $\operatorname{SHA-256d}$ can be turned into one able to break $\operatorname{SHA-256}$ with only twice as much queries.

Nevertheless, the paper shows that we can devise protocols involving a hash where using $\operatorname{SHA-256}$ is safe; but using $\operatorname{SHA-256d}$ is entirely unsafe (with negligible effort, not $2^{64}$). An example is this protocol designed to provide mutual proof that each party has made some minimum number of evaluations of some $256$-bit hash function $H$ (note: Alice performs the odd steps, and the next even step is performed by Bob with roles reversed):

Alice draws a random $256$-bit $A_0$ and sends it to Bob, together with the minimum number $k_A\in[2^8..2^{18}]$ of evaluations of $H$ that she wants Bob to perform;
Bob draws a random $256$-bit $B_0$ and sends it to Alice, together with the minimum number $k_B\in[2^8..2^{18}]$ of evaluations of $H$ that he wants Alice to perform;
Alice sets $\hat B_0$ and $\hat k_B$ to what she got at step 2., and terminates the protocol with failure if $\hat k_B>2^{18}$;
Bob sets $\hat A_0$ and $\hat k_A$ to what he got at step 1., and terminates the protocol with failure if $\hat k_A>2^{18}$;
Alice repeats for $j=1\dots\max(k_A,\hat k_B)$:

If $A_{j-1}=B_0$, terminate the protocol with failure;
compute $A_j=H(A_{j-1})$;
compute $\hat B_j=H(\hat B_{j-1})$;

Bob repeats for $j=1\dots\max(k_B,\hat k_A)$:

If $B_{j-1}=A_0$, terminate the protocol with failure;
compute $B_j=H(B_{j-1})$;
compute $\hat A_j=H(\hat A_{j-1})$;

Alice sends $\hat B_{\hat k_B}$ to Bob;
Bob sends $\hat A_{\hat k_A}$ to Alice;
If what Alice got at step 8. is different from $A_{k_A}$, she terminates the protocol with failure; else she declares success;
If what Bob got at step 7. is different from $B_{k_B}$, he terminates the protocol with failure; else he declares success.

When $H$ is $\operatorname{SHA-256}$, this protocol is safe for both Alice and Bob. However if $H$ is $\operatorname{SHA-256d}$, defined as $x\mapsto \operatorname{SHA-256}(\operatorname{SHA-256}(x))$, there is a simple "mirror" attack for Bob:

at step 2., Bob computes and sends $B_0=\operatorname{SHA-256}(A_0)$ and $k_B=k_A-1$ where $A_0$ and $k_A$ is what he got at step 1.; this will pass the test performed by Alice at step 3.; and pass the tests she performs at step 5., with about the same negligible odds of failure as if Bob had chosen $B_0$ at random;
at step 8., Bob computes and sends $\operatorname{SHA-256}(\hat B_{\hat k_B})$ where $\hat B_{\hat k_B}$ is what he got at step 7.; this will always pass the test Alice performs at step 9.!!

This strategy allows Bob to apparently perform his duties with computational effort about a single evaluation of $\operatorname{SHA-256d}$, by circumventing the tests performed by Alice at step 5., which intend was to prevent Bob from choosing $B_0$ as one of the $A_j$ so that most of his work could in fact be done by Alice.

The paper (and the above example, which is inspired from the paper) implies that with a definition of indifferentiability from a Random Oracle sufficiently strong to support a security proof of certain protocols (in particular: mutual proof-of-work protocols) under the assumption that a hash used by this protocol is secure, indifferentiability of $H^2:x\mapsto H^2(x)=H(H(x))$ does not follow from indifferentiability of $H$.

That shows in particular that the definition of a practically secure hash as a random public member of a Pseudo-Random Function Familly characterized by: "even a computationally unbounded adversary can not distinguish, with constant positive advantage over a random choice, if a black box with $n$-bit output implements a random member of the family, or a RO, with a number of queries to the black box polynomial in $n$" (or: "asymptotically less than the birthday bound $O(n^{1/2})$" ) is NOT a measure of security suitable for proving practical security of such protocols.

The paper proceeds to show that $\bar H(x)=H(H'(x))$ where $H'$ is a variant of $H$, is indifferentiable from RO, assuming $H$ and $H'$ are, under a definition of indifferentiability suitable for that goal.

One way of seeing this is that the composition of two random members of a PRFF is secure, but the composition of twice the same random member is not secure w.r.t. an adversary with access to an oracle implementing that random member, which is unavoidable in practice.

Update: although BitCoin involves proof-of-work using a hash, and $\operatorname{SHA-256d}$, I would be extremely surprised if there was some devastating attack due to the use of that hash.


Is it possible to create an easy to use encryption/decryption method that will never be comprimised?

If the key is:

generated with an unpredictable truly random uniform generator (not a pseudo-random generator);
as long as the data to encrypt;
used for only one message ever;

then this is the One-Time Pad model, and you can encrypt data by a simple bitwise XOR (no need for an explicit function, just XOR).

Otherwise, there is no solution which resists attackers with infinite computational abilities. Shannon's thesis is all about that.


Detect desynchronization in HOTP authentication

From RFC 4226:

  7.4.  Resynchronization of the Counter

  Although the server's counter value is only incremented after a
  successful HOTP authentication, the counter on the token is
  incremented every time a new HOTP is requested by the user.  Because
  of this, the counter values on the server and on the token might be
  out of synchronization.

  We RECOMMEND setting a look-ahead parameter s on the server, which
  defines the size of the look-ahead window.  In a nutshell, the server
  can recalculate the next s HOTP-server values, and check them against
  the received HOTP client.

  Synchronization of counters in this scenario simply requires the
  server to calculate the next HOTP values and determine if there is a
  match.  Optionally, the system MAY require the user to send a
  sequence of (say, 2, 3) HOTP values for resynchronization purpose,
  since forging a sequence of consecutive HOTP values is even more
  difficult than guessing a single HOTP value.

  The upper bound set by the parameter s ensures the server does not
  go    on checking HOTP values forever (causing a denial-of-service
  attack)    and also restricts the space of possible solutions for an
  attacker    trying to manufacture HOTP values. s SHOULD be set as low
  as    possible, while still ensuring that usability is not impacted.


Padding
You cannot fill the remaining blocks with the null bytes unless

The message has a fixed size that doesn't require sending file sizes.
The file size is sent over the channel.
The message doesn't contain null-bytes.

In the general, the padding must be unambiguous. 10..0 padding can be fine.

if data is 1234567890000000
now the data is 123456789 or 1234567890 or 12345678900 or..

if you use 10..0 then with the data 1234567890001000
it will be clear that the data is 123456789000

You can use PKCS#7 padding for ECB and CBC mode. PKCS#7 supports modes have block sizes larger than 64-bit block up to 255. The previous one, PKCS#5 padding had support up to 64-bit block size that was fine for DES.
In PKCS#7 padding, the remaining bytes count is padded as a byte value. For example;
123456789ABCDEF1     here consider the integers as bytes like 1 = 0x01
123456789ABCDE22
123456789ABCD333

Then the removal of padding bytes result in
123456789ABCDEF
123456789ABCDE
123456789ABCD

If the last block is full an additional block is filled with 1F
0123456789ABCDEF next block is full of `1F`s

The known padding methods are not limited to the above methods see more in Wikipedia: Padding_(cryptography).
For the complete difference between PKCS#5 and PKCS#7 see this canonical question What is the difference between PKCS#5 padding and PKCS#7 padding

CBC padding Oracle attack
For CBC mode operation, if padding oracle is applicable then the server can act like a decryption oracle. This attack academically first published  in 2002 by Serge Vaudenay. Although the servers are patched there are attacks based on the downgrade like Lucky13 and Poodle. Keep your servers on the secure level! TLS 1.3 has huge clean ups and it has no more CBC mode of operation. The TLS 1.3 encryption modes with their IDs;

{0x13,0x01} - TLS_AES_256_GCM_SHA384
{0x13,0x02} - TLS_CHACHA20_POLY1305_SHA256
{0x13,0x03} - TLS_AES_128_GCM_SHA256
{0x13,0x04} - TLS_AES_128_CCM_8_SHA256
{0x13,0x05} - TLS_AES_128_CCM_SHA256

One can see how the padding oracle attacks work in these answers and remember if applicable the attacker can decrypt all of the message not only the padded part.

If there is no such padding oracle attack then it is secure. Example the data stored as data-at-rest.

Padless modes
It is better to use a mode like CTR and OFB modes that don't require padding at all. They can work with arbitrary byte sizes.
Forget ECB
Don't use ECB which is insecure leaks patterns, it is not a probabilistic encryption, not even secure against KPA attacks on multi-block messages. Some even don't call it as a mode of operation.
Modern Modes
The all above modes are also called archaic mode of operation and they can have at most CPA. In modern Cryptography, we use and suggest to use Authenticated Encryption (AE) (AEAD: AE with associated data) modes like AES-GCM and ChaCha20-Poly1305 which can have IND-CCA2. These will provide you Confidentiality, Integrity, and Authentication, all in one. And remember, never use a key-IV pair again in these modes. If you want only leak about the same message is sent nothing more then use a misuse-resistant mode like SIV. AES-GCM-SIV will be the future.
There is a new mode
Daence: Salsa20 and ChaCha in Deterministic Authenticated Encryption with no noNCEnse as of 2020 by Taylor R Campbell

We present Daence, a deterministic authenticated cipher based on a pseudorandom function family and a universal hash family, similar to SIV. We recommend instances with Salsa20 or ChaCha, and Poly1305, for high performance, high security, and easy deployment.

This mode uses the Associated Data (AD) to eliminate the case that even the same message is sent under the same key-IV pair if the AD is different than the ciphertext messages will be different up to some probability.


Why does a broken hash function undermine an HMAC?

Actually, HMAC might still be secure for a hash function that is broken (with respect to the requirements of a cryptographic hash function, such as primary preimage resistance, secondary preimage resistance and collision resistance), but it must not be too badly broken. If you read the original paper, you see that the authors assume things such as the hash function being "weakly collision resistant", or more precisely that the inner hash function is collision resistant only to adversaries that see the hash value only after it being hashed again with a different secret key.

Also, since HMAC, contrary to NMAC, doesn't use two independent keys, but a single key that is combined with two different pads using XOR, additional assumption about the pseudo randomness of the hash function are made.

I believe MD4 does not even meet these weaker assumptions, and that is why HMAC-MD4 is considered to be broken, while e.g. HMAC-MD5 is not (yet).


First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references).

So we could simply do something like this:

while k >= m:
  k = k-m

$m$ could be public or secret shared.

This will be fairly slow if $k$ is large and $m$ is small. As poncho points out, someone learning $k\bmod{m}$ and the number of iterations of the loop will be able to recover $k$.

This could be mitigated by always running the loop the same number of times and using $t= (k>=m)$ (where $t$ takes on $0$ or $1$ accordingly) then doing $k=k-(t)m$. This has obvious limitations so it will depend on the situation as to whether or not this will be acceptable (note that we can upper bound the number of iterations if both $m$ and the order of the field used in Shamir are known).

There are more specialized protocols that would be faster and may solve the problem poncho pointed out.


Why is the lite version of Cramer-Shoup not IND-CCA2 secure?

CS-lite has the same homomorphic properties as ElGamal. In particular, compontentwise product of $\textsf{Enc}(pk,m_1)$ and $\textsf{Enc}(pk,m_2)$ is a valid encryption of $m_1 m_2$ (and hence will decrypt properly):

$$(g_1^r, g_2^r, A^r m_1, B^r) \cdot (g_1^s, g_2^s, A^s m_2, B^s) = (g_1^{r+s}, g_2^{r+s}, A^{r+s} (m_1m_2), B^{r+s})$$

So a simple CCA2 attack is to request $\textsf{Enc}(pk,m)$ for an unknown $m$, multiply this ciphertext by a fresh encryption of 1, and ask the decryption oracle to decrypt the result (revealing $m$).


tweakable block cipher and ideal block cipher

I'll write down the definitions for tweakable block ciphers and ideal block ciphers, and hopefully the distinction becomes more clear.

A tweakable block cipher is a function $E:\mathsf{K}\times\mathsf{T}\times\mathsf{X}\to\mathsf{X}$, where $\mathsf{K}$ is the set of keys, $\mathsf{T}$ the set of tweaks, and $\mathsf{X}$ the inputs. In particular, it should be the case that if you fix a key $K\in\mathsf{K}$ and tweak $T\in\mathsf{T}$, that $E(K,T,\cdot)$ is a permutation over $\mathsf{X}$. A regular block cipher is just a tweakable block cipher with only one tweak.

With a tweakable block cipher, you generate the key as you normally would with a block cipher, but now you're given access to a family of permutations via the tweak input, instead of just one permutation as with regular block ciphers. So $E(K,T_1,\cdot)$ and $E(K,T_2,\cdot)$ should give you access to different permutations. In fact, the security requirement of a tweakable block cipher says that each of those permutations $E(K,T_1,\cdot)$, $E(K,T_2,\cdot)$, $\ldots$, should 'look' independent of each other, and behave like ideal permutations (an ideal permutation is one which is generated uniformly at random from the set of all permutations over $\mathsf{X}$).

Now an ideal block cipher is a mathematical object. It has the same syntax as regular block ciphers, namely it takes a key and gives you an ideal permutation per key, but there is no tweak input. In some sense you could consider ideal block ciphers to be a tweakable analogue to ideal permutations, since now you're given a family of ideal permutations to access. And in fact, in the security definition for tweakable block ciphers, you will be comparing your tweakable block cipher to a family of permutations. Therefore, in some sense you could say that a tweakable block cipher gives you the same functionality as an ideal block cipher, but the biggest difference is that a tweakable block cipher needs a uniformly generated key in order for it to work properly, whereas an ideal block cipher does not: it is an ideal mathematical object.


No. The construction is not secure!

The security property of MAC says that, every poly-time adversary who has access to a MAC oracle (the oracle outputs MAC on input message) cannot come up with a MAC on a message of his choice (without querying the oracle) with non-negligible probability. In your construction, suppose you know that $G(x) = G(x')$ for some known values $x, x'$. Then an adversary can query for MAC on $m_1 || x$ (for any message $m_1$) and then obtain MAC for $m_1 || x'$.

Note: It's easy to construct a PRG $G$ such that $G(x) = G(x')$. Take any PRG $G'$ and pick any two values $x,x'$. Construct $G$ as follows. $G(y) = G'(y)$ if $y \neq x$. $G(y) = G'(x')$ if $y = x$. Note that $G$ is a PRG if $G'$ is a PRG.


Can we use fixed Beaver's multiplication triples many times?

If you reuse the same multiplication triples, then you leak information about the secret shared values that you multiply.

Let's recall how the multiplication works in Beaver's protocol for secure evaluation of arithmetic circuits. Protocols like the ones from the SPDZ family follow Beaver's blueprint and "just" add some additional magic on top for getting active security. Let's focus on the simple approach of Beaver, since you will already run into problems there, when you reuse multiplication triples:

Assume you have a secret shared values $[x]$ and $[y]$, where the notation $[x]$ means that $x = \sum^n_{i=1}x_i$ and party $P_i$ has share $x_i$.
Let $[a],[b],[c]$ with $c = a \cdot b$ be a secret shared multiplication triple.

To multiply $[x]$ and $[y]$ you compute $[z]$, where $z = x \cdot y$, as follows:

Each party computes $$[d] := [x] - [a] = [x-a]$$ and publishes its share thereof (thus revealing $d$)
Each party computes $$[e] := [y] - [b] = [y-b]$$ and publishes its share thereof (thus revealing $e$)
All parties locally compute $$[z] = [c] + [x]\cdot e + [y] \cdot d - e \cdot d$$ (Note that when we want to add or subtract a public value like $e \cdot d$ to a secret shared value, then only one of the parties adds the public value to its shares.)

Now if you were to reuse the same multiplication triple $[a],[b],[c]$ in another multiplication of some other secret values $[u]$ and $[v]$, then you would reveal $$d' = u - a$$ and $$e' = v - b$$

From this information, a honest-but-curious party could now compute
$$ d - d' = (x-a) - (u-a) = x - u$$
This is clearly bad, since it directly reveals the difference between two secret values $x$ and $u$. The same, with $e$ and $e'$, obviously also works to compute the difference $y - v$.

For this reason it is crucial for the security of the protocol that you use every multiplication triple at most once!


Is calculating a hash code for a large file in parallel less secure than doing it sequentially?

If you want to use Skein (one of the SHA-3 candidates) anyway: it has a "mode of operation" (configuration variant) for tree hashing, which works just like your method 2.

It does this internally of the operation, as multiple calls of UBI on the individual blocks. This is described in section 3.5.6 of the Skein specification paper (version 1.3).

You will need a leaf-size of 1 MB (so, Y_l = 14, for the 512-bit variant, 15 for 256, 13 for 1024) and a maximum tree height Y_m = 2 for your application. (The image shows an example with Y_m >= 3.)

The paper does not really include any cryptographic analysis of the tree hashing mode, but the fact that it is included (and even mentioned as a possible use for password hashing) seems to mean that the authors consider it at least as save as the "standard" sequential mode. (It is also not mentioned at all in the proof paper.)

On a more theoretical level:
Most ways of finding collisions in hash functions rely on finding a collision in the underlying compression function f : S × M -> S (which maps a previous state together with a block of data to the new state).

A collision here is one of these:

a pair of messages and a state such that f(s, m1) = f(s, m2)
a pair of two states, a message block, so that f(s1, m) = f(s2, m)
a pair of messages and a pair of states such that f(s1, m1) = f(s2, m2).

The first one is the easiest one to exploit - simply modify one block of your message, and let all the other blocks same.

To use the other ones, we additionally need a preimage attack on the compression function for the previous blocks, which is usually thought to be even more complicated.

If we have a collision of this first type, we can exploit it in the tree version just as well as in the sequential version, namely on the lowest level. For creating collisions on the higher levels, we again need preimage attacks on the lower levels.

So, as long as the hash function (and its compression function) is preimage resistant, the tree version has not more collision weak points than the "long stream" one.


Can I use HKDF to improve security of HMAC used with weak hash function?

First of all: accelerating PBKDF by using a faster hash doesn't make sense; an attacker is likely to receive the same speedup.

On 64 bit machines SHA-512 or one of the 384, 256 or 224 derivatives is likely to be faster than SHA-256. So you might be able to increase security and have a faster hash algorithm.

MD4 should probably not be used for anything anymore, including HMAC. MD5 is still considered secure for key derivation, but I personally would not feel comfortable using it for anything.

If you are not worried about forgeries you could simply go for a checksum over the ciphertext and a check value of some kind to see if the password is correct. I'm wondering though if the consequences of not protecting against forgeries is fully understood (e.g. with regards to padding oracle attacks). It may well be that failing to protect against forgeries allows attacks on the cipher or cipher mode of operation.

Currently I would go for PBKDF2, bcrypt or even scrypt, then perform HKDF-Extract to obtain an encryption key. For the KDF functions I would use SHA-512. Then I would use AES-GCM for authenticated encryption. Many processors will be able to accelerate AES-GCM fine, may it ever come to that.  Possibly I would use another KDF extract to create a different key that I would just use to check if the password entered was correct (in my opinion the work factor of the PBKDF should protect the key, not the size of the ciphertext as that may be small).

Alternatively you could use a NaCl compatible library such as libsodium, which has been optimized for security and speed.


Is randomsound for increasing entropy pool not doing what it is supposed to do?

Ah ... I see. I am not a C/C++-expert.

So the union in injector "projects"ints on bitfield and vice versa. That is, the start of ints and bitfield in memory is the same. Writing on bitfield automatically writes on ints.

See http://www.wachtler.de/ck/8_7_struct_union.html (in german).

So everything is fine.


Why is prime number size important for RSA security?

In RSA with modulus $n$, the legitimate user's cost to encrypt a message is $(\log_2 n) (\log_2 \log_2 n)^{1 + o(1)}$ bit operations, with the best public exponent $e = 3$; and to decrypt a message (if you know the secret exponent) is $(\log_2 n) (\log_2 \log_2 n)^{2 + o(1)}$ bit operations.  This is most assuredly not exponential in $n$ or even in the size $\log_2 n$ of $n$, and it is quite fast in concrete terms—to measure how fast it is, you can run openssl speed rsa4096 in the privacy of your own living room!  You can also consult the SUPERCOP benchmarks for measurements on a wide variety of computers to see the concrete speeds.

What about the attacker's cost to decrypt in RSA without knowing the private key?

If $n = pq$ for $p < q$, the cost of the elliptic curve method of factorization (ECM) is $L^{\sqrt{2} + o(1)}$ where $L = e^{(\log p)^{1/2} (\log \log p)^{1/2}}$.  This is the best-known classical method of factoring that depends on the size of a factor, so the factors must be chosen large enough to put this out of reach.  This is neither a polynomial function, nor an exponential function, but somewhere in the middle: $e^{(\log p)^\alpha (\log \log p)^{1 - \alpha}}$ is polynomial in $\log p$ when $\alpha = 0$ and exponential in $\log p$ when $\alpha = 1$, but here $\alpha = 1/2$.  But, of course, what is really interesting is not the asymptotic growth curves of attack costs, but the concrete attack costs for specific parameter sizes.  Based on experimental evidence of ECM performance[1], to make sure that the cost is near $2^{128}$ we can set $p \approx 2^{1024}$ for a ‘128-bit security level’.

There are other methods of factoring:

The number field sieve (NFS) costs about $L^{1.704\dots + o(1)}$ per key in a large batch attack[2], where $L = e^{(\log n)^{1/3} (\log \log n)^{2/3}}$.  Note that this cost depends on the size of $n$ rather than on the size of its factor $p$.  For a 128-bit security level, we need to set $n \approx 3584$.

If we had a large quantum computer:

Shor's algorithm costs about $(\log_2 n)^{2 + o(1)}$ qubit operations.  If large quantum computers ever became feasible, then for a >100-bit security level, we would need $n \approx 2^{2^{43}}$, i.e. a terabyte modulus[3].
Grover-optimized ECM costs about $L^{1 + o(1)}$ where $L = e^{(\log p)^{1/2} (\log \log p)^{1/2}}$, which requires us to use somewhat larger primes.  If large quantum computers ever became feasible, then for a >100-bit security level, we would need $p \approx 2^{2048}$, though cryptographers recommend $p \approx 2^{4096}$ until quantum computing is better understood[3].

(Combining the attack costs of Shor and Grover-ECM, it is cheapest for the legitimate user if we use multi-prime RSA with $n = p_1 p_2 \cdots p_\ell$ where $p_i \approx 2^{4096}$ and $\ell \approx 2^{32}$, i.e. four billion factors.)


How did someone discover N, order of G for SECP256k1?

I understand that (N-1) is the total number of valid points on the
  curve

Actually no. $N$ is the number of points on the curve, $N-1$ is the number of non-trivial points, where the point at infinity $\mathcal O$ is the trivial point (because it is essentially the $0$ for curves).

  Could someone please explain, in simple and easy terms, how the
  creators did (or should have) derived the N, order of G for SECP256k1?

First, let's assume we already know the order of the curve, ie the number of points on it. Let's call this number $n$. It turns out that for secp256k1 $n$ is a prime. Now we know by Lagrange's Theorem the order of any subgroup (like the subgroup generated by $G$) of secp256k1 must divide $n$, so either have $1$ or $n$ elements. But the only element that generates a subgroup with one element is $\mathcal O$ (because $\mathcal O+\mathcal O=\mathcal O$) and thus $G$ must have order $n$.

But how do we find the order of the curve? It turns out that mathematicians have already solved this problem and found an algorithm to efficiently count the number of points on a curve without actually visiting every single one, it's called Schoof's algorithm. Now the details of this algorithm are very complex and thus I won't go into them here. If you really want to know, you can read the linked article and the references given at the bottom of the page.


PBKDF2 output size vs internal hashing algorithm

My question is, do these two sizes need to match?

Well, officially no, the output of PBKDF2 is only limited by the following definition from PKCS#5:

dkLen      intended length in octets of the derived
           key, a positive integer, at most
           (2^32 - 1) * hLen

There hLen is the length of the internal hash algorithm.

PBKDF1 is actually limited to hLen - unless you are using the horrible Microsoft implementation which is simply completely insecure and unspecified for anything over hLen of output.

It is however strongly recommended to keep to hLen as output. The reason for this is not that the output is somehow dependent. The problem is that the whole work factor (parameterized by the iteration count) is repeated for each additional block that is required. The problem with this is that attackers do often not need to perform all these additional operations to verify correctness of the input while brute forcing or performing a dictionary attack. So additional output put you at a disadvantage over an attacker.

Try to keep to SHA-512 and a maximum output size of 512 bits or use an additional function such as HKDF to increase the amount of output (or use the KDF multiple times to derive multiple keys/secret values).

  Why is AES even used to generate the final key, and not just a SHA hash of the derived key?

This is a misconception on your part. AES may take the output of PBKDF2 to be an AES key. No AES key operations are however performed within PBKDF2 (AES has a block size of 128 so expecting 256 bytes of output would be strange anyway).

Directly converting the output to a key means that the user doesn't have to "manually" an AES key type from the output of the KDF. This is more secure as the bytes do not have to be copied into the resulting key - and the original bytes don't need to be destroyed (zeroed) either.

In case of hardware crypto the output of the KDF may be kept in the device as well (instead of first copying it to memory of the host device), although this is usually not an issue for PBKDF2 as password handling is usually not performed in specialized hardware.


Fooling Proof-of-Storage Protocols. What's the difference with Length-Extension attack?

Why would the server try to "fool" the client?

The server could be paid by the client on the basis of terabyte⋅day stored (that's the pricing model of Amazon S3), but only pretending to store, to make easy money.

The goal of a proof-of-storage protocol is to repel crooks from the remote storage business, and reassure the client that the data is safe, without actually restoring backups (which is expensive, at least due to communication costs, and because there might be an access fee beyond that). Also, checking data returned from the server requires the client to have a way to distinguish that the data is genuine, which requires either the genuine data (expensive, and partially negating the benefits of delegating storage), or some precautions taken at a moment when the genuine data was available. Notice that a rogue server could be successful at guessing which segment of the genuine data will be asked as a test, and/or could use sophisticated algorithms to generate plausible missing data from actually available data; and even make checksums in recognized archive formats (gz, zip..) check OK.

More insidious: the server's operator could pretend to keep data on two storage medium in two different locations, but actually use one, and generate fake data in the rare case of a bad block on the sole hard disk with the data. That roughly halves energy, space, and investment costs, thus makes profits skyrocket, and is hard to prove remotely. Regular use of a proof-of-storage protocol will at least catch the most greedy implementations of that fraud (but not those using some RAID5 on a single site).

  How is that different from a length extension attack?

A pure length-extension attacks computes a new hash $H'=\mathcal H(M\mathbin\|C)$ given $H=\mathcal H(M)$ and $C$; while the modified length-extension attack outlined replaces $H$ with a slightly larger amount of information: the internal state of $\mathcal H$ slightly before finalization of the computation leading to $H$. This allows that modified attack to work for any $C$, while for most hashes a pure length-extension attack works only for some very particular $C$ (in the case of SHA-256: starting with a precise string of at least 65 bits uniquely dependent on the length of $M$).

Thus the pure length-extension attack is not enough to foul the would-be proof-of-storage protocol proposed, but a modified length-extension attack is.


This is a common misunderstanding of zero knowledge. In order to prove something in zero knowledge (in fact, in order to prove anything in a way that is non-trivial), there must a well defined statement. See https://crypto.stackexchange.com/a/60633/25354 for an explanation of this.

Note that in your context, it is always true that there exists some $b$ such that $a<b$ (over the integers). Thus, without having some commitment or encryption of $b$ before the proof starts, this is trivially always true.


The two most popular ways I am aware of are Shamir secret sharing and additive secret sharing. I'll explain both.

Additive Secret Sharing
I'll start with additive as it is conceptually simpler (but also more limited). I'll also use bitwise addition modulo 2 as the addition operation (i.e., XOR), but know that that isn't the only option. You could use real, no-kidding addition in a finite field (say $\mathbb{Z}_p$ for a prime $p$).

Say I have a key $k$ and a plaintext $p$. I encrypt to get $c=E(p,k)$. Now I distribute $c$ to $n$ friends. I also generate random bitstrings of the same length as $k$, $s_1,\dots,s_{n-1}$. I also set $s_n=k\oplus s_1\oplus\dots\oplus s_{n-1}$. I send $s_i$ to friend $i$. Note that $k=s_1\oplus\dots\oplus s_{n}$. Thus, if all $n$ friends get together, they can reconstruct $k$ and decrypt $c$. If any group of up to $n-1$ of my friends get together they can not reconstruct $k$ and they learn no additional information about $k$ that they didn't already have.

Shamir Secret Sharing
Shamir secret sharing is more complicated, but more powerful. In SSS, I can generate the shares such that any $t+1$ out of $n$ of my friends can get together to reconstruct $k$. Any group of at most size $t$ learns nothing about $k$. It is based on the idea of polynomial interpolation. For example, in school we learned that it takes 2 points to uniquely identify a line. If you only have one point, there are infinitely many lines that could touch that point. If you have 2 points, there is only 1 line. So, what if we encoded the secret $k$ into the line (for example, the y intercept). Then I can distribute different points on that line (excluding the y intercept) to all my friends. Any 1 of them by themselves, cannot figure out the y intercept. But, 2 of them together can reconstruct the line and figure out the y intercept and recover $k$.

SSS uses this idea. Fix a field, say $\mathbb{Z}_p$. Construct the following polynomial:
$f(x)=k+r_1x+r_2x^2+\dots+r_tx^t$ where $r_1,\dots,r_t$ are random field elements. Notice that $f(0)=k$. Send $f(1)$ to one friend, $f(2)$ to another, and so on.

It turns out that any $t+1$ of your friends can then come together and, using lagrangian interpolation, compute $f(0)=k$ to recover the secret $k$. Any group of size at most $t$, however, learns nothing about $k$.


Are Barreto-Naehrig Curves suitable for pairing-based cryptography?

You can, with the right parameter sizes (384-bit prime instead of the older 256-bit).

Pairings can be attacked in two fronts: the elliptic curve or the extension finite field. The security of the pairing will be the the one that is easiest to break.

Previously, a BN curve using an elliptic curve over a 256-bit prime provided 128 bits of security; it was the "perfect" case since the elliptic curve provided 128 bits and the extension field also provided 128 bits.

After Extended Tower Number Field Sieve:
A New Complexity for the Medium Prime Case, things changed in the extension field case, and it's hard to give a concrete estimate since the paper handles asymptotics and we'd need to have concrete implementations to have more accuracy. But the paper estimates that the prime size must be doubled (i.e. from 256 bits to 512 for 128 bits of security). Aurore Guillevic estimates that it should be changed to 448 or 512 bits. However, further analysis in Challenges with Assessing the Impact of NFS Advances on the
Security of Pairing-based Cryptography, indicate that 384 bits should be enough.

So, if you use $p$ with 384 bits, you should be fine, but the performance won't be very good. In this case, the elliptic curve provides 192 bits of security while the extension field provides 128 bits, and we're stuck with the smaller value.

As an example, Zcash chooses the BLS12 pairing for the 128-bit security level since, due its structure, it is a 256-bit group (instead of a 384-bit group in BN) which makes some things faster. The underlying prime is the same size, though (384 bits).


A mathematically elegant and rather simple way of hashing are the parity bits of a Hamming code, as small changes in the data will yield different parity bits. You can weakly hash 4-bit strings to 3-bit strings with the standard (7,4) Hamming code, but the general Hamming code construction has high enough rate that you can hash longer strings (say, 26 bits to 5 bits) with a very simple algorithm and give them a hint by showing how to break the (7,4) hash.

Actually, it does sound like a fun homework assignment to find a string of length $2^{20} - 21$ that hashes to a particular $20$ bit string using a $(2^{20}-1, 2^{20}-21)$ Hamming code

Of course there are better "real hashes", but you didn't want that, right? :)


Threshold decryption in multi-key homomorphic encryption

Everything you write looks correct. However, you may be expecting the distributed decryption protocol to have a security property that it does not (and was not intended to, and really cannot in your example) have.

Specifically, the Mukherjee-Wichs paper you linked defines security to say (roughly) that, given the evaluated ciphertext, its underlying plaintext, and the secret keys for all but one of the parties, we can statistically simulate that party’s partial decryption. This corresponds to all but one of the parties being semi-honest, and protecting the privacy of the remaining honest party’s input (as far as is possible).

In your example, the evaluation function just sums the three inputs. Because all but one of the parties is semi-honest, the adversary knows all their inputs. It is also entitled to the output sum of all the parties’ inputs. This means it can trivially compute the honest party’s input! So, there is actually no “security violation” arising from the fact that the decryption protocol implicitly reveals the honest party’s input, because that input is implicitly revealed by the function itself.

If you consider a different evaluation function that doesn’t implicitly reveal the honest party’s input, then I think you should see why the “smudging” noise works as intended.


Plain RSA with $3$ primes, find all integers $x$ so that $x$ is equal to $y$ when $y= e_K(x) = x^{b} \bmod n$

If I understand correctly, you are looking for the integers $x$ such that, for all $b$, $x^b \equiv x \pmod n$.

You almost have it!  You've correctly identified $x = 0$ and $x = 1$ as solutions.  If you had a solution $x$, what can you say about $x_i := x \bmod p_i$ for each $p_i$—how are $x_i$ and ${x_i}^b$ related modulo $p_i$?  Can you use the solutions $x = 0$ or $x = 1$ modulo $n$ as inspirations to find solutions modulo $p_i$ and recombine them into solutions modulo $n$?


Padding Oracle Attack CBC Mode: If the set of characters of plaintext is known, then can you speed up the process

I will assume you generally understand the mechanics of the padding oracle attack. Say we have some ciphertext block $c_i = c_{i-1} \oplus E(k,m_i)$ and we want to find the last byte of $m_i$. Let $b$ denote the last byte of $m_i$, which we are trying to find.
Consider ciphertexts of the form $(c_{i-1} \oplus \texttt{00} \cdots \texttt{00} g,c_i)$, where $g$ is a single byte. Such a ciphertext decrypts to $m_i$, except the last byte has been changed from $b$ to $b \oplus g$. When the server decrypts, it sees a string that ends in byte $b \oplus g$ --- does this string have valid padding? In most cases, it has valid padding only when $b \oplus g = \texttt{01}$ (lets assume that $m_i$ doesn't end in $\cdots \texttt{02}\,b$ or $\cdots \texttt{0303}\,b$, etc). When the server tells us which choice of $g$ leads to valid padding, we can solve for $b = \texttt{01} \oplus g$.
If you know that $b$ is one of only 26 possible values, then there are only 26 possible values of $g$ that you need to try -- compared to the general case where you have to try all 256 choices of byte $g$. I only mentioned the case of finding the last byte of the plaintext, but the same logic applies for any byte.


Is there a public-key cryptography method that enables public keys to be much smaller than private keys?

Yes. Hash based signature schemes are a prime example. The private/secret key of a Merkle tree is the whole list of leaves, while the public key is the root hash.

In practice the leaves are not usually all stored, but derived from a shorter key. Even then it may be useful to store e.g. $O(h)$ hashes to accelerate signing, where $h$ is the tree height. With CMSS (pdf) $T$ levels of trees are generated and the signer stores the verification keys for the active tree at each level, which is about $T$ times as much data as the public key.


A Cramer-Shoup public key has the form:

  $B = g_1^{b_1} g_2^{b_2}; \quad C = g_1^{c_1} g_2^{c_2}; \quad D = g_1^{d_1} g_2^{d_2}$

and an encryption of $m$ has the form:

  $g_1^r, ~ g_2^r, ~ m B^r, ~ (CD^\mu)^r$

where $\mu$ is a hash of the first 3 components.

CCA security proof breaks down:

In the CCA security proof, you observe that if you know the private key then you can generate the challenge ciphertext as a function of $g_1^r$ and $g_2^r$ (mirroring how the receiver would actually decrypt), which gives:

  $g_1^r, ~ g_2^r, ~ m [(g_1^r)^{b_1} (g_2^r)^{b_2}], ~ [ (g_1^r)^{c_1 + d_1 \mu} (g_2^r)^{c_2 + d_2 \mu} ]$

Then the first step of the proof is to replace $g_1^r, g_2^r$ with $g_1^{r_1}, g_2^{r_2}$ with $r_1, r_2$ random. This change is indistinguishable by DDH, but not if the discrete log of $g_2$ with respect to $g_1$ is known, as in your case. The rest of the proof follows from an information-theoretic argument.

Explicit CCA attack unclear:

Even though the proof seems to break down, I'm having trouble demonstrating an explicit attack on CCA security. You can definitely break the hybrids of  the CCA security proof without even consulting the decryption oracle. But we know the scheme remains CPA-secure (see below), so this it's possible that there's a problem only in the proof while the scheme remains CCA secure (though I doubt that).

CPA security maintained:

Even if you give the adversary everything but $b_1$ -- including the discrete log of $g_2$ with respect to $g_1$ -- you can still argue that the scheme is CPA secure. That's because we still have $r, b_1$ chosen uniformly, so $g_1^{r b_1}$ is pseudorandom given $g_1^r$, $g_1^{b_1}$. In particular, the third ciphertext component (the only one that involves the plaintext) is pseudorandom.


What are other good attack examples that use the hash collision?

Collisions are a generic tool in many attacks beyond hashes. Examples:

Attack of double encryption $C=E_{(K_1,K_2)}(P)=E_{K_2}(E_{K_1}(P))$ given a few (say 2) plaintext/ciphertext pairs $(P_i,C_i)$, which basically finds a collision between $F(K_1)=(E_{K_1}(P_1),E_{K_1}(P_2))$ and $G(K_2)=(D_{K_2}(C_1),D_{K_2}(C_2))$.
Discrete logarithm, in Baby-Step/Giant-Step and it-s memory-lean variant Pollard's rho. Basically these solve $x[G]=A$ in some group (noted additively) with generator $G$ by finding a collision between $y[G]$ and $z[G]+A$ with $y$ and $z$ from disjoint sets, then get $x=y-z$ modulo the group order.
Integer factorization, using a different Pollard's rho.

The reduction of the effort from $O(n)$ to $O(\sqrt n)$ characteristic of collision search, combined with the possibility of parallel collision search on independent machines with little memory*, is what makes these methods attractive. For 1, and 2 in the case of a generic group, this is the best known method.

* See Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.


What is the difference between CSPRNG and PRNG?

"PRNG" means "Pseudorandom Number Generator" which means that a sequence of numbers (bits, bytes...) is produced from an algorithm which looks random, but is in fact deterministic (the sequence is generated from some unknown internal state), hence pseudorandom.

Such pseudorandomness can be cryptographically secure, or not. It is cryptographically secure if nobody can reliably distinguish the output from true randomness, even if the PRNG algorithm is perfectly known (but not its internal state). A non-cryptographically secure PRNG would fool basic statistical tests but can be distinguished from true randomness by an intelligent attacker.

For instance, consider the following generator:

There is an internal state s which is a sequence of 20 bytes.
The generator produces a long sequence of bytes by 20-byte chunks.
To produce the next chunk, the algorithm is: output s, then set s to SHA-1(s).

This PRNG will be very good statistically, but it is trivial to distinguish from true randomness: just take two consecutive 20-byte chunks in the output, and see if the second is the result of SHA-1 over the first. This is not a cryptographically secure PRNG.

Of course, every CSPRNG is a PRNG, but not every PRNG is a CSPRNG. Some non-CS PRNG like the Mersenne twister can achieve quite high a performance and be adequate in non-cryptographic situations where there is no intelligent attacker to defeat (e.g. physics simulations). Although there also are some known high-performance CSPRNG (e.g. these stream ciphers), a non-CS PRNG may give an edge in contexts where the lack of cryptographic security is not an issue.


Does the double-hash H(H(x)) have greater collision probability than H(x)?

I'm not sure what the question here is, but obviously applying the hash function twice can never decrease the number/probability of collision as all collisions in the first invocation are maintained.

However if H is collision free( a permutation as opposed to a random function) doubling will not cause any more collision it will remain collision free. So we see the number of collision does not strictly increase.

For a PRF, the number of collision does clearly increase, this is one reason why when we iteratively hash passwords in for key derivation we mix in the input again every round and not simply hash calculate $H^n(salt || pass)$

If you look at the structure of a function you will see several cycles and threads(trees) leading into these cycles:

The cycles do not generate more collisions when doubled. Each thread meeting a cycle contributes one collision, If All the threads are of length 1 no more collisions are added when applying twice in any other case the number of collisions increases.