MD5: Existence of invariant (fixed point)

It is not known a practical method to find a 128-bit $B$ such that $\operatorname{MD5}(B)=B$. Argument: that's essentially a first-preimage attack against a variant of MD5 defined as $H(B)=\operatorname{MD5}(B)\oplus B$ restricted to $\{0,1\}^{128}$ input space, for the all-zero result; and MD5, as well as (conjecturally) that hash variant, is still strong as far as preimage attacks go.

Moreover, if we model MD5 as a random function (a natural model), the probability that there is a solution is $1-(1-2^{-128})^{(2^{128})}\ \approx\ 1-1/e\ \approx\ 63.2\%$. That leaves us far from sure that there exists a solution: odds are about 12/7.


If you had to implement the BGN Cryptosystem, how would you do it?

Here's a paper showing how to realize the BGN cryptosystem with a prime order group.  You could implement the cryptosystem with PBC or one of the other paring libs.

"Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups"
David Mandell Freeman
Eurocrypt 2010

http://theory.stanford.edu/~dfreeman/papers/subgroups.pdf
http://theory.stanford.edu/~dfreeman/talks/eurocrypt10.pdf

Have a look at slide 13 of the talk — the BGN example looks fairly simple.  The following slide suggests that prime-order BGN will be more efficient at higher security levels too.

This is probably how I would implement it.


Hybrid encryption with RSA and AES versus spliting into multiple RSA messages?

The question has several aspects:

it asked (initially) about any security issue in breaking a piece of data into separately RSA-encrypted chunks;
it asks what's the weak link in the security chain when doing hybrid encryption with a 256-bit AES key transfered enciphered using 2048-bit RSA;
it asks how much slower 2048-bit RSA would be for bulk encryption, compared to AES-256;
it (formerly) outlined a protocol where a public key is RSA-enciphered (causing the Plaintext is too long error); that protocol turned out to be unsafe not protect the confidentiality of data enciphered with that public key, basically because that public key was sent enciphered, rather than signed.

On the first aspect: if the goal of encryption is limited to protecting the confidentiality of some data (which is the only goal assigned to encryption in its modern definition), and RSA encryption is done properly (that is, with random padding), then there is no security issue, only performance and message size issues.

However the protocol formerly outlined used RSA encryption for other purposes than encryption. So maybe breaking the encrypted material into chunks worsens things; like, multiple cryptograms can be reordered by an adversary.

When doing hybrid encryption with 2048-bit RSA used to transfer a 256-bit AES key, the weak link is, from an academic point of view, the 2048-bit RSA key. According to the multiple sources considered by this well-respected website on key length, 2048-bit RSA is somwhat less secure than a block cipher with a 128-bit key, which itself is (theoretically) $2^{128}$ times less secure than a block cipher with a 256-bit key. Two levels of explanations to that:

Qualitative: in RSA, an adversary is given a lot of information about the key (the whole public modulus); whereas in AES, the key is assumed secret, being exposed to the adversary only through the complex layers of the cipher.
Quantitative: factoring $N$ is known to require less than $\exp\Big(\big(\sqrt[3]{\frac{64}{9}}+o(1)\big)\cdot(\ln N)^{\frac1 3}\cdot(\ln\ln N)^{\frac2 3}\Big)$ operations, and plugging $N\approx2^{2048}$ into that, ignoring the $o(1)$ term, gives less than $2^{117}$.

But reality is, the true weak link (beyond using a bad protocol) is the ability to keep undisclosed the secret material involved (e.g. the secret AES key and the private RSA key). Many things conspire to make this hard, both for RSA and AES, including implementation goofs, side channels, and NSA-planted backdoors.

How much slower RSA-2048 is compared to AES-256 depends on many things:

Is the cost of key generation to be considered? That is the case in the protocol formerly described, where a 2048-bit RSA key is generated for each user connection, and used only a few times per session, unquestionably making RSA key generation the performance bottleneck: generating an RSA key is much slower than using it, and can be like $2^{20\pm12}$ times more costly than AES-256 key generation or encryption (methods used for RSA key generation vary widely, and what we should include on the AES-256 side is unclear).
What is the hardware? If there is hardware for AES, but not for RSA, which is common on many modern CPUs, AES-256 encipher and decipher bulk data like $2^{20\pm 8}$ times faster than bulk RSA can. Even with hardware for RSA but not AES, like on this Smart Card with ARM Cortex M3 CPU, RSA is slower than AES is.
What is the software? Poorly written software can slow anything without limit. It is very common that two deployed implementations of a cryptographic algorithm differ in performance by a factor of $2^4$ on the same hardware.
Are we considering RSA encryption or decryption, and in the former case what's the public exponent? With $e=3$ and simple implementations, RSA-2048 decryption is $2^{10\pm1}$ times slower than encryption is; make that $2^{7\pm1}$ for $e=65537$.
The size of what's encrypted: AES's speed advantage is least when the data enciphered exactly fits the capacity of the RSA encryption scheme.

On the last aspect (now no longer part of the question):

Whatever exactly the protocol outlined was and aimed at, it was bound to be vulnerable to a Man-in-the-Middle attack during the "upload" of the "uniquely already known (user) public key"; a sure sign is that the client starts without any credential.
The protocol included an explicit step of encrypting something designated as "public key" (see end of step 4 in the protocol); this is a tale-tale sign of a design error.
Even if that "public key" was not made public, the confidentiality of commands normally sent enciphered by the user using that key (in step 5 of the protocol) was not ensured, for an adversary could inject another public key to be used instead.
In some most common uses of RSA for signature, an unknown public key is easy to infer from a few signatures;  keeping that public key confidential during its transfer does not prevent its later disclosure when and if it is used for signatures (as alluded in comments but not in the former description of the protocol).


it is possible to use quantum algorithm search (Grover's algorithm) for new searching strategies for differential and linear attacks

Grover's algorithm is a probabilistic quantum algorithm that finds (with high probability) the unique input to a black box function that produces a particular output value, using
$$
O({\sqrt  {N}})
$$ evaluations of the function, where the fuction has domain of size $N$.
is the size of the function's domain.

Keeping in mind the fact that the spedup is only quadratic, unlike Shor's algorithm which provides exponential speedups on a different problem,  it can be applied to any search problem over a finite domain.

The normally suggested countermeasure to this algorithm in the symmetric crypto setting is quite mild: symmetric key lengths can be doubled to compensate for the risk.

Edit: For multiobject search for $\ell$ objects, Boyer et. al. in 1 proved the following theorem, which as pointed out by @poncho in the comments, is a bit counterintuitive.

Theorem: (paraphrased) Assume that $\ell/N$ is small. Then
any search algorithm for $\ell$ objects, in the form of [grover search]
takes on average $O(\sqrt{N/\ell})$ iterations in order to be successful with positive probability $>1/2$
independent of $N$ and $\ell.$

M. Boyer, G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, Fortsch. Phys. 46 (1998), 493–506. See related paper on arXiv here


Tentative answer to my own question. Please criticize!

All variables in capital are one 128-bit word, with $w=7$. Parameters are as in the question, and $k-4\le n\le128$.
I use an auxiliary arbitrary public permutation $\large\mathscr P$ of one word; a simplistic one is constructed using Addition-Rotation-Xor. A function evaluation goes:

set $D$ to the function's input
memory setup: repeat for $C$ from $2^{k-w}-1$ down to $0$

write $D$ to memory at address $C$

set $A$ to zero.
main loop: repeat for $C$ from $2^n-1$ down to $0$

set $A$ to $A\oplus{\large\mathscr P}(D\oplus C)$
read $R$ from memory at address $A\bmod2^{k-w}$
write $D$ to memory at same address
set $D$ to $D\oplus{\large\mathscr P}(R\oplus C)$

output $D$.

Some rationale of the design:

Address of the next memory location used depends, thru two nested invocations $\large\mathscr P$ and depending on chronology thanks to $C$, on the value previously read $R$, and will-be result $D$.
The main loop has reversible effect on the combination of memory, $A$ and $D$; hence the input-to-output entropy loss can be estimated as at most 0.8272… bits.
Mixing of counter $C$ makes getting into a short cycle unconceivable.
The average number of accesses to each memory cell is at least 8.

Permutation $\large\mathscr P$ is:

set $X$ to the function's input
repeat for $t$ each of the six constants 3, 5, 7, 13, 23, 43

set $X$ to $3\big(X\oplus(X\operatorname{\lll}t)\big)\bmod2^{128}$ where $\lll$ is left rotation on 128 bits

output $X$.

Note following comment: this is a toy/simplistic permutation, not to be reused outside the present context of deep iteration, and was not the focus of the answer. There are far less rounds than necessary for complete propagation of a bit difference; but in the context, two invocations (thus twice more rounds) are nested from $R$ to $A$. Zero is a stationary point, since the only constants are rotation counts (hastily obtained by starting from 3, doubling, and rounding down to the next prime).
Tentative test vector: for ${\large\mathscr P}\big({\large\mathscr P}(1)\big)$ I get 0x5be8f27af383369a91de3e614e6650dd.


If you have three rounds and the encryption in the first round has no effect, then the left side of the third round is

$$ L_3 = R_0~\oplus~F(L_0 \oplus R_0, K_2) $$

and when you exchange the left and right side of the initial block

$$ L_3' = L_0~\oplus~F(R_0 \oplus L_0, K_2) = L_0~\oplus~F(L_0 \oplus R_0, K_2) $$

So

$$ L_3~\oplus~L_3' = R_0~\oplus~L_0 $$

This property lets you distinguish the output of the Feistel network from random.


detect the RSA public key from encrypted text

Maybe, but this approach depends on the distribution of the public key sizes.
Suppose that cm is the encrypted message, and ni is the modulus for customer i.

If cm >= ni, then customer i cannot be the recipient of this particular message.
if cm is significantly smaller then ni (16-32 bits or so, depending on how certain you want to be) then it is possible (but unlikely) to have been sent to customer i.

So if there is a variety of key sizes, this may allow you to narrow down the list of possible senders. For example, if customer X has a 4096-bit key and all the others have 3072-bit keys, identifying messages from customer X would be easy.
On the other hand, if everyone has a 3072-bit key, you may be able to narrow the list of senders down some, but you would still have a fairly large list remaining.
One possible countermeasure is to add random high-order padding bits to the message to make the padded message larger than any modulus. In other words, if the largest modulus is (decimal) 1000000, then 1234 might become 9351234, while 12345 might become 7412345.  Each recipient can remove high-order bits until the message is smaller than their modulus, then try decrypting the message.


SHA-1: number of possible inputs, number of possible outputs, how many inputs have the same output,

From Wikipedia I read SHA-1 function produces an output of 160 bits and expects a max message size of $2^{64}-1$ bits. Is that right?

Yup, looks right.

  If I order all possible inputs I would produce approx. $2^{2^{64}}$ different bit array inputs, right?

Yes. The number of possible inputs is the sum of the number of possible $l$-bit strings for $l$ from $0$ to $2^{64}-1$:

$$\sum_{l=0}^{2^{64}-1} 2^l \;=\; 2^{2^{64}} - 1$$

  If the bit array has less than $2^{64}-1$ elements it is like receiving 0's for the rest (or maybe start receiving 0's until...)?

Actually, SHA-1's padding is designed to prevent this from occurring. If $\text{SHA-1}$ is to be a secure cryptographic hash function, it shouldn't be possible to come up with any two messages $m_1$, $m_2$ such that $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$ (i.e. a hash collision). If it were true that $\text{SHA-1}(m) = \text{SHA-1}(m \| 0)$ ($\|$ is concatenation), that would violate this requirement.

  If $2^{2^{64}}$ is the whole universe it looks like almost the whole universe is inside each bucket (hash output).

That's a good intuition.  $2^{160}$ is a huge number, but $2^{2^{64}}$ is beyond astronomical (it's estimated that there are fewer than $2^{266}$ atoms in the visible universe).  This is what makes cryptographic hash functions so interesting.  We know that there is an incredibly astronomically massive number of colliding input pairs, but we just can't find any (or at least, we can't with a good hash function: SHA-1 is broken, and someone has most likely already found a collision).

  Does it mean that if I take randomly two different inputs of the set of $2^{2^{64}}$ elements the probability that they belong to the same bucket is very high?

If a bucket means a given hash output, then no, the probability is quite low. Let's assume that SHA-1 was a strong, unbroken hash function. Choose one input from the set of $2^{2^{64}}-1$, call it $m_1$, and let $h_1 = \text{SHA-1}(m_1)$. Note that $h_1$ is one of $2^{160}$ possible values. Now choose at random the second input, call it $m_2$, and let $h_2 = \text{SHA-1}(m_2)$. The probability that $h_2$ ended up being the same value as $h_1$ is $1/2^{160}$.

This explanation might better match your intuition: The $2^{2^{64}}-1$ possible inputs are divided into $2^{160}$ equal-sized buckets (approximately equal-sized, at least). All of these buckets are massive, but there are so many buckets that the probability of choosing two values in the same bucket is still quite low.


Calculate shared key having A public Key and B private Key (Diffie Hellman)

$\text{B}_\text{private}$ is $\text{b}$ and $\text{B}_\text{public}$ is $\text{g}^\text{b} \bmod p$.

So $\text{B}$ can compute $(\text{A}_\text{public})^b \bmod p = \text{g}^{\text{ab}} \bmod p$


Are Authenticated Encryption ciphersuites supported in legacy TLS versions older than TLS 1.2?

Pretty sure AES GCM is only defined for TLS 1.2.  If you look at RFC 5288, it's titled "AES Galois Counter Mode (GCM) Cipher Suites for TLS" and it only defines suites for TLS 1.2:

  The following cipher suites use the new authenticated encryption
     modes defined in TLS 1.2 with AES in Galois Counter Mode (GCM)

Later on it says

  These cipher suites make use of the authenticated encryption with
     additional data defined in TLS 1.2 [RFC5246].  They MUST NOT be
     negotiated in older versions of TLS.  Clients MUST NOT offer these
     cipher suites if they do not offer TLS 1.2 or later.  Servers that
     select an earlier version of TLS MUST NOT select one of these cipher
     suites.

While this doesn't mean that a different, particularly a later, RFC couldn't have defined them, I can't see why one would have done so.


Showing that $2^{N-1}\equiv1\pmod N$ when $N=2^p-1$ for prime $p$

a) $2^p \equiv 1 \mod N$ because $2^p = N + 1$. When you reduce $\mod N$ (take the remainder when dividing by $N$),  you are left with 1.

b) $N - 1 = 2^p - 2$

By Fermat's little theorem, $2^p \equiv 2 \mod p$:

$2^p - 2 \equiv 2 - 2 \equiv 0 \mod p$

c)

From a) we know that $2^p \equiv 1 \mod N$

From b) we know that $N - 1 \equiv 0\mod p$, therefore $N-1$ is a multiple of $p$.

Let $N-1 = kp$ for some integer $k$

$2^{N-1} = 2^{kp}$

$(2^p)^{k} \equiv 1^k \equiv 1 \mod N$


Using a non cryptographic PRNG for randomized algorithms

In fact, on a recent enough x86 CPU (I mean 2011 or later, so not exactly bleeding edge), there are AES opcodes that, as their name say, help implement the AES block cipher with hardwired dedicated operations. They are really fast. Thus, a PRNG that simply runs AES in CTR mode (encryption of successive values of a counter) will:

be cryptographically secure; and:
be blindingly fast, actually more so than most non-cryptographic PRNG.

We are talking here about several gigabytes per second. This should be adequate, and even negligible, for most purposes.

If your platform of choice does not have such an hardware implementation of AES, then there still are good cryptographic options, in particular the stream ciphers from the eSTREAM projects.

As an aside, there are several variants of Quicksort, and are not necessarily randomized. The randomized versions of Quicksort try to avoid the tricky cases where the performance degrades from the average O(n log n) to O(n2). Presumably, if there is an attacker, then the attacker will try to force the input to hit that kind of bad situation, as a denial-of-service attack. If you use a non-secure PRNG, then the attacker may indeed analyse the timing information to predict the PRNG output and thus defeat the countermeasure. Enforcing a delay might work only if the delay is such that the sorting is always below the threshold, which means that you made it so that your Quicksort is always slow. In other words, you defeat DoS by attackers by DoS-ing yourself harder. This is hardly a nice situation.

A fast, cryptographically secure PRNG will avoid such situations nicely, and if that PRNG is properly implemented, then its cost will be negligible with regards to the cost of sorting. Alternatively, you might consider other sorting algorithms that have guaranteed O(n log n) performance even in the worst case, in particular Mergesort and Heapsort (Mergesort is usually faster than Quicksort, but requires an extra RAM buffer; Heapsort is a bit slower but in run in guaranteed fixed RAM, contrary to Quicksort).


Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is, $x$ and $y$ with $x\neq y$ and $H(H(x))=H(H(y))$.
Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

$H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
$H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.

What could suffer is the output distribution of $H\circ H$ as opposed to $H$, that is, even if $H$ is uniformly distributed on the set of all bit strings $\{0,1\}^\ast$, the distribution of $H\circ H$ may be arbitrarily bad. For instance, when $H$ is not bijective on its image (which is the usual case), there are always hash values that are not in $H\circ H$'s image while others may have lots of preimages. However, this doesn't break collision resistance in the cryptographic sense, as outlined above.


About DH-EKE and ECDHE_PSK (PSK versus Pasword)

Assuming you're actually asking wether there is a difference for TLS in between a (high-entropy) pre-shared key (PSK) and a (low-entropy) pre-shared password, the short answer is:

No.

The long answer, however is a bit more complicated.
By itself the TLS-PSK ciphersuites don't differentiate between different degrees of entropy. However there are a few TLS-SRP ciphersuites, using the secure remote password protocol - a password-authenticated key-exchange (PAKE) protocol. They actually have some nice properties which only get interesting if you can assume the PSKs to be low entropy.

  Does entropy matter for TLS-PSK?

Yes it does.
If you're using the TLS_PSK_... ciphersuites you actually use the PSK as a basis for your session key meaning that this key is susceptible to off-line brute-force attacks. However it looks like you want to use TLS_ECDHE_PSK_... ciphersuites, which are much harder to attack. You can't derive the session key without breaking the ECDH key-exchange and knowing the PSK. So there's no trivial passive attack to obtain the transmitted contents after the handshake was done. However active attacks are very well possible, as you can install yourself as a man-in-the-middle (standard attack on DH) and try to impersonate the other client by trying out the different possible values for the PSK. This is infeasible if the PSK is high-entropy but very well possible if the PSK has low entropy.


I don't understand the definition of monotonic access structures

It's for $B,C \in 2^{\{P_1, P_2, ..., P_n\}}$

So, take $B = \{1,2\} \in \mathbb{A}$ as in your example. $\forall C \in 2^{\{1,2,3,4\}}$ such that $B \subset C$, $C$ must be in $\mathbb{A}$.

Possible values of $C$ are $\{1, 2\}$, $\{1, 2, 3\}$, $\{1,2,4\}$, and $\{1,2,3,4\}$. As you can see not all of them are in $\mathbb{A}$.

The idea is that if any set has access, all sets that contain it must also have access.


Are there use cases where a signature itself needs to be signed?

In a nutshell there are two main uses cases for signing an existing signature:

validation: the signature of another person (ex: a superior) is
required to give effect to a primary signature. The second signature
covers the content, the first signature and potentially additional
data added by the second signer.
witness / notary: a second person signs only the first signature, to
vouch that the person applying the first signature is indeed the right one.
Contrary to the previous case, the content is not covered by the second signature, because the second signer does not commit to it.


Understanding the wide trail design strategy

Given the importance of the wide-trail strategy in modern symmetric-key cryptography, this question really deserves an answer (and a much better score). Since nobody else has tried, I'll give a brief summary and some context. Hopefully this will help you understand the paper by Daemen and Rijmen (paywal-free preprint) better.

Since the (public) discovery of differential and linear cryptanalysis, an active research area within symmetric-key cryptography has been dedicated to bounding the probability of differentials and the correlation of linear approximations in practical constructions. The goal of this line of work is to prove (or heuristically argue) the security of a construction against linear and differential cryptanalysis. The most successful approach to this end is the wide-trail strategy.

Differential and Linear Cryptanalysis

This is not the right place to explain differential and linear cryptanalysis (you can find introductions elsewhere), but some notation has to be introduced for the remainder of this post. Recall that differential cryptanalysis studies the propagation of differences $\Delta_0 \to \Delta_r$. Such differentials have an associated probability that I shall denote by $p(\Delta_0, \Delta_r)$. Linear cryptanalysis considers linear approximations which are described by a pair of masks $(u_0, u_r)$. They have an associated correlation $c(u_0, u_r)$, which is twice the bias.

In practice, one does not find differentials but rather differential characteristics, i.e. sequences of input and output differences of parts of the cipher that are easier to understand (typically, the round functon). So a differential characteristic may be defined as a tuple $(\Delta_0, \Delta_1 \ldots, \Delta_r)$. Similarly, one has linear trails in linear cryptanalysis and these are sequences of input and output masks $(u_0, u_1, \ldots, u_r)$.
In some cases, the probability of a differential and the correlation of a linear approximation can be estimated as follows:

$$p(\Delta_0, \Delta_r) \approx \prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i)$$
$$c(u_0, u_r) \approx \prod_{i = 1}^r c(u_{i-1}, u_i),$$

where the choice of intermediate differences/masks is understood to be the optimal one.

I must stress again that these are approximations, and in many cases these are not valid. For example, it is clear that one often needs to take into account multiple characteristics or trails. In fact, there is an entire branch of research dedicated to refining the above estimates in both the differential and linear settings. I will not go in to these matters as they are (mostly) outside of the scope of your question.

In the remainder of this post, I will focus on heuristic security arguments that are based on showing that all characteristics have small probability, and all trails have a small correlation. I will also not really discuss how small "small" should be (this is based on cost estimates of differential/linear attacks).

Bounds on Characteristics and Trails

From here on, assume we are dealing with an SPN (but the argument will apply to several other constructions too). Suppose the round function consists of a nonlinear S-box layer, a linear layer and a key addition.

Suppose the nonlinear layer consists of $m$ S-boxes which are applied in parallel. The S-boxes have some maximum differential probability $p_{max}$ and a maximum absolute correlation $c_{max}$. By this I mean the maximum over all non-zero input differences and non-zero masks. This is important because a zero input difference always yields a zero output difference and similarly for linear approximations (assume we are dealing with permutations).

So clearly, we have the upper bounds

$$\prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i) \le (p_{max})^{n_D}$$
$$\left|\prod_{i = 1}^r c(u_{i-1}, u_i)\right| \le (c_{max})^{n_L}.$$

Here, the number $n_D$ is equal to the number of S-boxes in the characteristic with non-zero input difference. We call this differentially active S-boxes.
Similarly, $n_L$ is the number of linearly active S-boxes in the trail.

Role of the Nonlinear Layer

A lot of early work focused on the choice of the nonlinear layer. That is, one attempts to minimize the quantities  $p_{max}$ and $c_{max}$. Of course, one still needs to have some sort of bound on $n_D$ and $n_L$, but that is not the main concern in this line of work. For example, this 1995 paper by Nyberg and Knudsen (paywall-free preprint) uses a DES-like structure and then discusses how to choose the nonlinear function to minimize $p_{max}$. Do note that their security argument is stronger than what I describe here, as they consider (in more modern terminology) the EDP (expected differential probability) rather than individual characteristics.

Because efficiency tends to impose limits  on the size of the S-boxes that can be used in a construction, $p_{max}$ and $c_{max}$ cannot be made very small. The natural conclusion is that we need to increase $n_D$ and $n_L$ somehow. This will be the role of the linear layer.

Role of the Linear Layer

Recall that the S-box layer consists of $m$ S-boxes which are applied in parallel. So it makes sense to split the differences and masks into $m$ parts: $\Delta_i = \Delta_i^{(1)} \| \Delta_i^{(2)} \| \cdots \| \Delta_i^{(m)}$ and $u_i = u_i^{(1)} \| u_i^{(2)} \| \cdots \| u_i^{(m)}$. Let us denote the number of nonzero $\Delta^{(j)}$ in $\Delta = \Delta^{(1)} \| \cdots \| \Delta^{(m)}$ by $\mathrm{wt}(\Delta)$ and likewise for $\mathrm{wt}(u)$.

The set of $j$ such that $\Delta^{(j)} \neq 0$ is often called the activity pattern of $\Delta$. One has a similar definition for masks.

The number of active S-boxes $n_D$ and $n_L$ in a characteristic/trail can then be expressed as
$$n_D = \sum_{i = 0}^{r-1} \mathrm{wt}(\Delta_i),$$
$$n_L = \sum_{i = 1}^r \mathrm{wt}(u_i).$$

Remember that one wants to maximize $n_D$ and $n_L$, so the weights $\mathrm{wt}(\Delta_i)$ and $\mathrm{wt}(\Delta_i)$ should be made large.
This can be done using the linear layer, because the linear layer restricts which transitions $\Delta_i \to \Delta_{i + 1}$ and $u_i \to u_{i + 1}$ are possible. That is, if the S-box layer has differential $\Delta_i \to \Delta_i^\ast$ with nonzero probability, then $\Delta_{i + 1} = L(\Delta_i^\ast)$ for a linear layer $L$. Without the DDT of the S-boxes, we don't really know what $\Delta_i^\ast$ is, but we do know that it has the same activity pattern and in particular the same weight. So we can optimize $L$ independently of the S-boxes by maximizing the quantity

$$\mathcal B_D(L) = \min_{\Delta \neq 0} [\mathrm{wt}(\Delta) + \mathrm{wt}(L(\Delta))]$$

This quantity, called the branch number, was introduced by Daemen in  his PhD thesis. Later, $\mathcal B_D$ was called the differential branch number in contrast with the linear branch number defined below.

Similar ideas apply for linear cryptanalysis: the linear layer restricts which mask activity pattern transitions are possible. If $L$ is invertible (let's assume this for simplicity), then $u_{i + 1} = L^{-\top}(u_i)$ where $\top$ denotes the transpose. Hence, the linear branch number for an invertible $L$ is defined as
$$ \mathcal B_L(L) = \mathcal B_D(L^{-\top}) = \mathcal B_D{(L^\top)}.$$
Note that one can also define the linear branch number of a noninvertible map.

So we want to maximize $\mathcal B_D$ and $\mathcal B_L$. In his PhD thesis, Rijmen related the branch number to coding theory. I will not go into details here, but this leads to the use of MDS codes to obtain $L$. The first cipher to use these ideas was probably SHARK by Rijmen et al. In practice, the entire linear layer $L$ is usually not an MDS matrix. Instead, one combines a column-wise MDS linear layer with a cellwise permutation that ensures diffusion between columns.

Wide trail strategy

The wide trail strategy is the design strategy that you get when you combine the ideas above (I have made several simplifications though.) Quoting from the paper:

  The reasoning above suggests two possible mechanisms to eliminate
  low-weight trails:

  Choose S-boxes with high minimum differential and correlation weight.
  Design the round transformation such a way that there are no relevant trails with low bundle weight.

The first part is the role of the S-boxes, the second part relates to the linear layer (in principle one can also consider nonlinear diffusion layers, but this goes out of scope). An important difference between the wide trail strategy and earlier/other approaches (for example Nyberg and Knudsen) is the emphasis on the linear layer:

  Instead  of  spending  most  of  the  resources  on  large  S-boxes,
  the  wide  trail strategy aims at designing the round
  transformation(s) such that there are no  trails  with  a  low  bundle
  weight.  In  ciphers  designed  by  the  wide  trail strategy, a
  relatively large amount of resources is spent in the linear step to
  provide high multiple-round diffusion.

An immediate bound on the probability of characteristics over two rounds of such a cipher is $(p_{max})^{\mathcal B_D}$ and the absolute correlation of 2-round trails is upper bounded by $(c_{max})^{\mathcal B_L}$. Better bounds can usually be obtained for 4 rounds (here the effect of the cellwise permutation becomes relevant). I will not go into the details.

The wide-trail strategy led to the block ciphers SHARK, Square and ultimately Rijndael (which became the AES). After the AES competition, many other ciphers where designed based on (or at least inspired by) the wide-trail approach.

Beyond Wide Trails

Despite the length of this post, I have only described the very basics.

New techniques (e.g. based on SAT and MILP solvers) have been developed to compute the number of active S-boxes. Research has not ended, but it's really not feasible to try and give an overview of developments here.

Bounding characteristics and trails is not enough, because it only leads to heuristic security arguments. One can for instance try to compute the MEDP (maximum expected differential probability) and MELP (maximum expected linear potential) for a block cipher. Such calculations typically rely on the assumption that round keys are independent.
There are examples of designs that were broken (using linear/differential attacks) despite good heuristic arguments for their security against these attacks.


request for data to test deterministic ecdsa signature algorithm for secp256k1


Using exponential Elgamal as the encryption function,

Define the list of candidates: e.g., Alice, Bob, Carol
Voters submit an encryption of their vote: e.g., to voter for Alice: $v=\langle\mathsf{Enc}(1),\mathsf{Enc}(0),\mathsf{Enc}(0)\rangle$
Use an OR-proof (Fig 2) to show each ciphertext encrypts a 0 or a 1: e.g., $\langle \pi_1, \pi_2, \pi_3 \rangle$
Under encryption, add up the ciphertexts in the vote: e.g., $v_t=\mathsf{Enc}(1)\cdot\mathsf{Enc}(0)\cdot\mathsf{Enc}(0)=\mathsf{Enc}(1+0+0)=\mathsf{Enc}(1)$
Use the same OR-proof to show $v_t$ encrypts a 0 or a 1 (a 0 means the voter abstained)
Submit $\langle v, \pi_1, \pi_2, \pi_3, v_t, \pi_t \rangle$

Anyone can check the validity of $\pi_1, \pi_2, \pi_3$. Anyone can add up $v$ to see it is $v_t$. Anyone can check $\pi_t$.

The election officials take $v$ from everyone, add them up element-wise. Then the results are decrypted (usually with a shared key) using a protocol that proves it was decrypted correctly (see same paper for how to do this).


What are easy yet fool proof ways of ensuring that AES encryption algorithm works like it should and no bugs/developer mistakes have sneaked in?

For this kind of problem, the cryptographic algorithm/protocol designers, usually, presents test vectors for their designs. You can find some of them in books, too.

In your case, AES is standardized by NIST on May 26, 2002, and they provide test vectors in Appendix F of NIST 800-38A for various mode of encryption.

Before the standardization on November 26, 2001, the NIST FIPS 197 document provided
 example vectors in Appendix C. This is a more detailed vector for each round instead of just input and output.

input: cipher input
start: state at start of round[r]
s_box: state after SubBytes()
s_row: state after ShiftRows()
m_col: state after MixColumns()
k_sch: key schedule value for round[r]
output: cipher output


Using key derived using HKDF or NIST sp800-108 with AES-CCM/GCM

... the derived keying material shall not be used as a key stream for a stream cipher

Using the derived keying material as a key for AES-GCM is not the same as using the derived keying material as a key stream.

The quote means "don't xor the key material with the plaintext" as your entire encryption process.

AES-GCM does not xor the key with the plaintext. It uses it as the key for AES to generate a key stream, which is completely secure.


Summary of definitions of cryptographic variables and operands

I haven't seen a cheat sheet for anything cryptography-specific but most, if not all, you can find in a math symbols cheat sheet. For example Wikipedia math symbols list also lists the XOR function.


How do i manage encryption keys with a cloud provider?

One approach to doing this is using end-to-end encryption, where the provider never has access to the keys. A system that uses proxy re-encryption (PRE) can allow each user to have her own keys, but admins can manage a group that represents the users for your company, so it is not necessary to re-encrypt all the files the company can access every time a new user is added or a user is removed.

A paper that describes this in detail is available here (this directs through my company's website to the ACM digital library - sorry for the extra hop, but it avoids the need to have ACM Digital Library access to get the paper). In summary, proxy re-encryption is a scheme originally designed to allow the delegation of encryption from one person to another. PRE schemes are based on public key cryptography, and they allow someone (the delegator) who has her own private key plus the public key of another person (the delegatee) to compute a re-encryption key. This key will allow ciphertexts encrypted to the delegator to be re-encrypted or transformed so that they can be decrypted using the delegatee's private key. This process does not allow the proxy or individual doing the transformation to decrypt the ciphertext.

If the delegator is an abstract entity that represents your company, and system administrators control access to that entity's private key, they can generate re-encryption keys to different users within the company. Revoking access is achieved by removing the re-encryption key between the company and an individual user.


Why does Laravel only support AES-256-CBC?

I see two reasons:

The addition of good libraries/modes is quite recent (Libsodium is only available since 7.2+ and AES-XXX-GCM with 7.1+).
Encrypted messages in Laravel don't have a version marker that would allow more than one scheme to coexist on a given installation. It mean that a given site must stick with one encryption scheme / key or all the existing encrypted messages will become unreadable. It makes upgrading encryption in Laravel quite hard.

...and since the current scheme (AES-256-CBC + HMAC-256) is fairly competent, Taylor is sticking with it.


In ECC scalar multiplication, how do `add(Q, Q)` exceptions occur?

In ECC scalar multiplication, how do add(Q, Q) exceptions occur?

Probability that it occurs when performing multiplication for large random $k$ (allowed to exceed $l$) and $P$ a generator is $\mathcal O\left(\dfrac{\log(k)}l\right)$ for a random $n$-bit curve, thus negligible when using actual curve parameters. Thus it can occur only when fed incorrect parameters; the cryptosystem or hardware is under attack; or using toy-size parameters making the crytosystem insecure.

  So add(Q, Q) can indeed not occur. □

I see no gap in the question's proof, now that it is explicitly stated that $P$ is on the curve, thus itself has prime order $l$.

  Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

No for correct execution (including, no induced fault attack) and parameters: $P$ on the curve of prime order $l$, $P\ne\infty$, $0\le k<l$.


Applying Trapdoor Function directly to plaintext

An eavesdropper could easily test any candidate message to determine

whether or that candidate message was the plaintext message.

def test_candidate_message_(pk,c,candidate):
 if c == F(pk,candidate):
  return True
 else:
  return False


Combining keys after key expansion: is it secure?

Well, yes.

The output of the cryptographic hash functions is indistinguishable from random - although not perfectly secure. So if you have $c = \operatorname{H}(K_1) \oplus \operatorname{H}(K_2) \oplus p$ then the result should be dependent on both keys, and you would almost have doubled the key size. This is similar to use two iterations of a block cipher and XOR them together. The XOR function itself should not leak any information about the hash values themselves.

There are however (quite) a few practicalities:

hash algorithms are sometimes not designed to be resistant to side channel attacks, and hashing keys may leak information about the keys themselves;
if the keys themselves are not very secure - e.g. relatively short or non-random - then having a hash could be used to distinguish the valid key values;
key reuse, as in a one time pad, is obviously catastrophical to security.

Using a key derivation function KDF such as HKDF over the concatenation of both key a values and then a trusted cipher would of be a much better way of accomplishing the same level of security, although I would imagine that the scheme in the question is more efficient on restricted platforms. Obviously a cipher has the advantage to be able to encrypt almost any amount of data instead of being restricted to the output size of the hash.

Finally, if the keys are already fully secure, they could be directly used in a one time pad. If the keys are passwords then a password based KDF should be used instead to strengthen the key material before it is used.


This is actually an RSA decryption problem, not a discrete log problem.

In this case, $$g = y^{x^{-1} \bmod \phi(N)} \pmod N$$

If you have the factorization $N = pq$, where $p, q$ are both prime, this is essentially:

$$g = y^{x^{-1} \bmod (p-1)(q-1)} \bmod N$$

You can compute $x^{-1} \bmod (p-1)(q-1)$ (or, what would work equally well, $x^{-1} \bmod \text{lcm}((p-1)(q-1))$), using the Extended Euclidean Algorithm for computing multiplicative inverses.


Elliptic Curve Cryptography Encryption Results

It has to be this way.

First, if it was deterministic, you could trivially break the encryption. Say the encrypted message was a response to "which candidate for President do you vote for". An attacker would simply need to encrypt each candidate's name and see the response that matched the encrypted data.

Second, if it was the same length as the encrypted data, you'd have at least two problems. First, short messages could be trivially brute forced. For example, if the output were only two bytes (for any input) you could encrypt messages until you got a match. Second, there's an obvious pigeonhole problem for messages of any length. You can't encrypt all possible X byte messages into an X byte output unless the relationship is one-to-one, which requires it to be deterministic which fails for the reasons I explained above.

I'm not specifically familiar with jecc, but the usual way to use ECC for encryption (IES) involves two random steps. First, the data to be encrypted is encrypted with a random symmetric key. Second, a random public/private ECC key pair is used in the encryption of the symmetric key. This explains both the indeterminism and the length.


What are the required security properties for salts?

512 bits is overkill for even global uniqueness. 256 bits should be enough, with a good random number generator: even if every person on earth generated one every nanosecond, it would take a million million years to reach the birthday bound.

However, I agree that global uniqueness is a good idea. If anyone anywhere uses the same salt and password hash (or other salt-using algorithm), an attacker could theoretically attack those in less time than otherwise.

If you had a unique application-specific pepper (additional salt that is shared by all users), you could safely use salts that are only locally unique, for example outputs from a counter. This might in some cases be useful for saving space.


You can do this slightly better with an additional $\mathcal{0}(2^{56})$ memory and with $\mathcal{0}(2^{56})$ time.

You can notice that the relation $c \leftarrow E_{k_1}(E_{k_2}(m))$ can be rewritten as $D_{k_1}(c) = E_{k_2}(m)$ (just apply the decrypt function on both sides.

First step consists in the generation of every pair $(k_2, E_{k_2}(m))$ and storing them in table (preferably a hash-table for fast lookups).

Having a table with all the pairs $k_2, E_{k_2}(m)$ you can now try all values for $k_1 = 0,2^{56}$ and apply the decrypt function $D_{k_1}$ on the ciphertext received initally. If the value $D_{k_1}(c)$ exists in your precomputed table then you have found the other key $k_2$ which was used to encrypt the original plaintext.

This method also stands by the name of meet-in-the-middle attack.


Is it possible to encrypt a message's destination as well as its content?

Any peer to peer mesh network would be sufficient.  If peers pass messages on to other peers then no peer can no for certain which peer a message is intended for.  It would be possible to determine (with some degree of confidence) the source of the message.

The real difficulty is handling all the other problems.  How do you deal with malicious nodes, denial of service attacks, and who pays for the network as peers are anonymous.  That is just the tip of the iceberg.

As a real world example the Bitcoin network uses similar system for connecting peers and passing messages.  Transactions are simply messages shared peer to peer in an adhoc fashion (your node tells all your peers who tells all their peers who tells are their peer .... and the recipient is one of them).  Bitcoin solves a lot of those "bad node" problems because the messages (transactions) have a cost in term of fees taken out of the transaction.  They are low but they do prevent things like some attacker just creating a bunch of nodes and telling them to make a trillion messages to cripple the network.


A permutation on a set is a bijection from the set to itself; thus $\sigma$ is a (bijective) map from $P$ to itself, not from $p(P)$ to itself (though it does induce a map from $p(P)$ to itself in a natural manner).

Also, if $f$ is a map from $A$ to $B$ and $X$ is a subset of $A$, then $f(X) = \{f(x), x \in X\}$. This is completely standard notation.

For a collection $\Lambda$ of subsets of $P$, $\sigma(\Lambda) = \{\sigma(A), A \in \Lambda\}$ is the collection of subsets of $P$ which is obtained by applying $\sigma$ to all the elements of $\Lambda$.

Example: $P = \{1,2,\dots,8\}$, $\Omega = \{\{1,2\},\dots,\{7,8\}\}$. Then $\Lambda = \{\{1,2,3,4\},\{5,6,7,8\}\}$ is $\Omega$-partite since clearly every permutation of $P$ that fixes each $P_i$ also fixes each element of $\Lambda$, so in fact we even have $\sigma(A) = A$ for all $A$. On the other hand, $\Lambda' = \{\{1,2,3\},\{4,5,6\},\{7,8\}\}$ is not; for instance $\sigma = (34)$ yields $\sigma(\Lambda') = \{\{1,2,4\},\{3,5,6\},\{7,8\}\} \ne \Lambda'$.


How bad would it be to reuse the random blinding factor in a scheme like Paillier?

The first obvious objection is that it would do a lousy job of blinding values; if you reuse the blinding factor, then it would be practical to correlate the blinded values with their original ones (and the entire point of blinding values is to prevent anyone from doing so).

Suppose we had two original encrypted values $c$, $d$, and the corresponded blinded versions $x = c \cdot r_1^n$ and $y = d \cdot r_2^n$.  Knowing nothing else, it would be infeasible to decide whether $x$ is a blinded copy of $c$, or a blinded copy of $d$.

However, if $r_1 = r_2 = r$, we can check if $c \cdot y = d \cdot x$.  If $x$ is a blinded version of $c$, and $y$ is a blinded version of $d$, then this check gives us $c \cdot d \cdot r^n = d \cdot c \cdot r^n$, or in other words, equality holds.

In addition, you ask:

  Since multiplication by $s$ "should" be large-enough to trigger a modulo wrap-around, it seems like successive $s^i$ values would not give any information about any of the previous $s^k,k<i$ (and thus preserve the security of all ciphertexts). Is this correct?

That is also not correct.  Given $c \cdot s^2$ and $c \cdot s$, the attacker can recover $c$ by computing:

$$(c \cdot s^2)^{-1} \cdot (c \cdot s)^2 = c$$

$(c \cdot s^2)^{-1}$ is the inverse of $c \cdot s^2$ modulo $n^2$, it can be computed as long as $c \cdot s^2$ is relatively prime to $n^2$


Keys and mixed encoding - security implications

You only have $6$ bits of entropy in $8$ bits of your output - in general that does not fullfill the requirements for a cryptohraphic key of being drawn uniformly random over the full range. In general, this can potentially be desastorous: You have no security guarantees, because no security proof applies any more. In the worst case such a bias in the key can completely break the system - without anyone noticing.

In a general setting however, you should also notice that those $256$ bit output of the CSPRNG are not $256$ bit any more if you encode it as Base64 and decode as ASCII. It should be $344$ bit output, and that doesn't fit any more, if a $256$ bit key is expected.

In your specific case with HMAC it is probably fine - because HMAC is equipped to handle different keylengths: The first thing HMAC does is to transform the key into the correct length. If the key is too short, it is padded, if it's too long the hash function is used on the key. You have $256$ btis of entropy in a longer string, so this should be fine.

But please note: It is unusual that an cryptographic function is equipped to handle variable keylengths, this is a lucky catch. While it should work in this case, in general it is a really bad idea to neglect the assumptions about the key. The term key implies often, that it is drawn uniformly from a specific range and considered in binary format.


Why the exponent is a power of 2 in Ring-LWE?

As @Raoul722 pointed out the polynomial should be irreducible.

One should also add the fact that in the original Ring-LWE article security proofs hold by sampling the error with a spherical distribution and the poly $f=x^{2^n}+1$.

In How (Not) to Instantiate Ring-LWE, from Invulnerability instantiations subsection it's specified that you could in fact select any number field and still be a hard problem but then you have to change the error distribution.

To answer your question, the reason is just to make proofs easier.


ZKP: Proving knowledge of a variable length hash preimage

(I'm writing this all with Bulletproofs in the back of my head)

Variable length inputs

As far as I know, it's not possible to achieve literal variable/secret-length inputs, except if I'm allowed to tweak your definition a bit. If you would allow input lengths up to a certain amount $n_{max}$, then you can vary the length below it. To achieve this, you can for example always commit to $n_{max}$ inputs, where you set the first $n$ inputs to your real inputs $v_1,\dots,v_n$, and the last $n_{max} - n$ to a semantically meaningless input. Then your proof protocol can be:

$$ \bigvee_{i=1}^{n_{max}} \text{statement when length = }i\text{ using } \{v_1,\dots,v_i\} $$

I.e., you write a proof that is the disjunction of the statements for proofs of length $i$. Of course, this makes your statement more complex, but a system like Bulletproofs compresses it well. You would need $n_{max}-1$ additional multipliers for the disjunction, thus if your statement for length $i$ needs $\text{poly}(i)$ multipliers, the total statement length would be something like $$\mathcal{O}(\log(n_{max}\cdot \text{poly}(n_{max}))) = \mathcal{O}(\log(n_{max}) + \log(\text{poly}(n_{max}))),$$ which gives you a constant overhead.

Constant-size commitments

Contrary to popular believe, Bulletproof witnesses don't necessarily need to be input commitments. The Bulletproofs paper actually does two main things to the original 2016 protocol of Bootle et al: reduce the complexity of the inner-product argument, and add support for Pedersen commitments. The latter just means that you don't have to implement Pedersen commitments inside the circuit (which would hurt the performance a lot). So, the way to avoid chunking and committing, is to avoid committing completely. After all, you could see your hash as a (imperfectly hiding) commitment already.

If you want to see how this works inside the main Bulletproofs equation ($W_L\cdot\vec a_L + W_R\cdot \vec a_R + W_O\cdot \vec a_O = W_V\cdot \vec v + \vec c$), notice that $\vec v$ is not the whole witness; $\vec a_L, \vec a_R \text{ and } \vec a_O$ are also part of the witness.

If you want an example of how this could work in practice, have a look at the excellent Rust-implementation of Bulletproofs arithmetic circuits. Their r1cs-integrated-range-proof test for example, decomposes a witness number in 64 different bit-variables, constrains the bits and only then binds it to the commitment. You could perfectly modify that code to bind the bits to a hash input gadget, and constrain the output of the hash gadget to your hash value.

This all of course requires knowledge of the input length, but the trick from above can then be used to hide the length up to a certain bound.

I hope this helps your case!


Understanding Montgomery's parameterization of elliptic curves

Write $(x_i, y_i) = (X_i : Y_i : Z_i)$, so that $x_i = X_i/Z_i$ and $y_i = X_i/Z_i$, where $Z_i \ne 0$ is arbitrary.  (If you are not familiar with projective coordinates or you like visuals, see an illustration of projective coordinates on a real elliptic curve.)

Let's take the doubling formula for example, where $(x_3, y_3) = (x_1, y_1) + (x_1, y_1) = [2](x_1, y_1)$:

\begin{equation*}
  4 x_1 x_3 ({x_1}^2 + A x_1 + 1) = ({x_1}^2 - 1)^2 \tag{p. 261, second display}
\end{equation*}

so that

\begin{equation*}
  x_3 = \frac{({x_1}^2 - 1)^2}{4 x_1 ({x_1}^2 + A x_1 + 1)},
\end{equation*}

which in projective coordinates is

\begin{align*}
  \frac{X_3}{Z_3}
   &= \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2}
           {4 \frac{X_1}{Z_1}
              \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\
   &= \frac{{Z_1}^4}{{Z_1}^4}
      \cdot
      \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2}
           {4 \frac{X_1}{Z_1}
              \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\
   &= \frac{\bigl({Z_1}^2\bigr)^2 \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2}
           {4 X_1 Z_1 {Z_1}^2
            \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\
   &= \frac{\bigl({X_1}^2 - {Z_1}^2\bigr)^2}
           {4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr)}.
\end{align*}

From this, we can read off the numerator and denominator:

\begin{equation*}
  X_3 = \bigl({X_1}^2 - {Z_1}^2\bigr)^2
  \qquad\text{and}\qquad
  Z_3 = 4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr).
\end{equation*}

Obviously, we can multiply both of them by the same arbitrary nonzero factor too, but there's no need here.

For the addition formula that is not doubling, you're trying to write $[m + n]P = [m]P + [n]P$ in terms of $X$ and $Z$ coordinates for $[m]P$, $[n]P$, and $[m - n]P = [m]P - [n]P$.  That is, you have $x_1 = x([m]P)$, $x_2 = x([n]P)$, and $x_4 = x([m - n]P)$, and you're trying to find $x_3 = x([m + n]P)$.  Use the top equation on p. 261, $$x_3 x_4 (x_1 - x_2)^2 = (x_1 x_2 - 1)^2,$$ and again write it out in terms of $x_i = X_i/Z_i$.

The last part is a matter of tidying to reduce the number of distinct intermediate quantities, e.g. using the observation that

\begin{multline*}
  {X_1}^2 + A X_1 Z_1 + {Z_1}^2
   = {X_1}^2 - 2 X_1 Z_1 + {Z_1}^2 + 2 X_1 Z_1 + (A/4) 4 X_1 Z_1 \\
   = (X_1 - Z_1)^2 + \frac{A + 2}{4} 4 X_1 Z_1
\end{multline*}

to write the whole doubling formula in terms of $X_1 \pm Z_1$ for a total cost of 4A + 2S + 3M.


What are the strenghts and weaknesses of Whirlpool Hashing Algorithm

This far there are no known significant cryptographic weaknesses in Whirlpool hash algorithm.

The biggest practical concern would appear to be:

Whirlpool performance is lower than many other hash functions (see e.g., http://www.cryptopp.com/benchmarks.html)

Because of this speed issue, something like SHA-512 often gets more use.


Does the signatures generated by a revoked member before revocation remains valid in VLR group signatures

I think it depends on the implementation of the scheme. A naive implementation might do what you've described and invalidate every previous signature of the revoked member.

However, the scheme proposed here: http://www.scitepress.org/Papers/2012/40175/40175.pdf takes a respective time $period$ into account.

Here the verification algorithm is defined as:

$Verify(gpk, j, RL_{j}, m , \sigma)$:

  This  algorithm,  run  by  a verifier takes as input a message $m$,  its signature $\sigma$, a  period $j$,  the  corresponding  Revocation  List $RL_{j}$ and the public parameters $gpk$.  It checks if the message has been signed by an unrevoked group member, without revealing the signer’s identity.  The possible outputs are valid and invalid.

As you can see, the verification check depends on a certain time period here. In this case, all signatures in previous periods would remain valid. This is especially useful because it enables to unrevoke members in a later period without having to generate a new key for that user.

So to answer your question: I think it depends on the implementation.


Yes, I believe you can argue statistical indistinguishability here. But, note that this is a weaker property than the typical one-time-pad which is perfectly secure, because XOR is mathematical magic (incurring no $\mathsf{negl}(\lambda)$-sized statistical offsets as below..).

High-level idea: If $N$ is sufficiently large with respect to $p$ --- i.e. if $N \ge \Omega(p\cdot\lambda^{\omega(1)})$ --- then random samples of size $\approx N$ will statistically swallow any "$p$-bounded" distribution (random samples of size $\approx p$).

[[Let $\lambda$ be the security parameter. For now, I'll ignore the factorization of $p$ vs $N$ for this..]]

Here's some fun with statistical distance between distributions:

A distribution $\chi$ is $(B,\epsilon)$-bounded if the probability of sampling a value larger than $B$ is unlikely; i.e. $$\Pr_{x\leftarrow\chi}[|x| > B] < \epsilon.$$

(Aside: Actually, my discussion here also assumes that the bound $B$ in $B$-bounded distributions is "chosen as small as feasible" for a given distribution; i.e. $B$ should be "tight" for $\chi$ asymptotically.)

A distribution $\widetilde{\chi}$ is $(B,\epsilon)$-swallowing if for all $y\in [-B, B]$ (respectively, $y\in [0, B]$), it holds that $\widetilde{\chi}$ and $y + \widetilde{\chi}$ are within $\epsilon$ statistical distance.

It turns out that the ("truncated," resp. "rounded") Gaussian distribution satisfies the property described above; namely, any $\left(B\cdot\lambda^{\omega(1)}, \epsilon\right)$-bounded distribution $\chi$ is also a $\left(B, \epsilon+\mathsf{negl}(\lambda)\right)$-swallowing distribution as well. (Gaussians just happen to often have "nice" geometric properties like this.)

For example: If $\chi$ is $(B, \mathsf{negl}(\lambda))$-bounded, and if $\widetilde{\chi}$ is $(B\cdot\lambda^{\omega(1)}, \mathsf{negl}(\lambda))$-bounded, and we sample $x\leftarrow\chi$ and $\widetilde{x}\leftarrow\widetilde{\chi},$ then we have:
$$
\widetilde{x} + x \stackrel{\rm stat}{\approx} \widetilde{x}
$$

In general, many "natural" distributions will exhibit this "swallowing" property. The Uniform distribution over (ranges of) integers is well-defined by a bound $B$ (or $p,$ or $N$), and swallows all 'small, uniformly random integers' w.h.p. whenever there is a superpoly gap in magnitude.

Note that you need to "sample & add-in" a fresh, i.i.d. "swallowing term" to each new message, for each time you use this kind of argument.. As far as going beyond truncuated Gaussians or bounded ranges of integers: Use your judgment! =) The distributions (certainly) must hit the same (say..) subgroups to use this argument, etc.

..finally, note there's no need to bother with statistical swallowing if the desired security property is a (standalone) One-Time Pad! Just using the standard OTP will be more efficient (fewer bits sampled in order to blind messages; i.e. less randomness needs to be securely/safely generated/shared). Moreover, the standard OTP will achieve stronger than just statistical indistinguishability.


Why not send the identity in the encrypted message?

You can of course add a trusted path requirement to Trent (the trusted key distribution center) on the top of the given protocol. This is however not a requirement for the scheme itself.

Trent, as trusted third party serving multiple users, of course needs to know who to communicate to. So the identity cannot be encrypted with the public key of Alice or Bob.

As you can see the information between Alice and Bob is encrypted. This is no problem as both just use their own key to decrypt the messages between them.

That all said, there seem to be multiple attacks on the scheme - this seems to be one of them. The problem of not establishing a trusted path to the KDC could be a big improvement on the protocol. Just to remind you: only use this protocol for study, not for real life implementations.

Please understand that these protocols are building blocks for creating secure systems. You need to understand exactly what kind of security is provided by the scheme to use it for building a secure system. Anonimity of Alice and Bob when talking to the KDC is clearly not part of the security provided by this protocol.


Can this AES encryption operation be described as being Homomorphic operation?

No, it cannot. The idea is that homomorphic operations take place on the ciphertext, not on the plaintext. This is clearly described by the Wikipedia article on homomorphic encryption.

You can do limited homomorphic operations on AES ciphertext. For instance, if you perform CTR (counter) mode encryption then you can XOR one or more bits, and the result will be that, after decryption, the plaintext will also have those same bits flipped. So here the operation takes place on the ciphertext but it has the same effect on the plaintext without affecting the confidentiality of the message.

In general however homomorphic encryption will be performed on forms of encryption based on mathematical operations, such as modular exponentiation used for raw RSA. As the encryption/decryption operation itself are mathematical constructs it is easier to perform operations on the ciphertext that have the same effect on the plaintext, such as multiplication (the first example in the Wikipedia page).

Full homomorphic encryption, where you can do an unlimited amount of operations on the ciphertext, remains elusive.

Your question could also be read that you simply try to learn things from the ciphertext. Now unless you perform deterministic encryption you should not learn anything from the ciphertext except its length. If you would learn anything from properly encrypted and randomised ciphertext (i.e. with a proper IV) then the cipher would be broken.

So that would mean that your scheme is broken. You would still not perform homomorphic encryption as:

learning things from the ciphertext is exactly what (homomorphic) encryption tries to avoid and;
as you don't alter the ciphertext no morphing is actually performed.

So whichever way you look at it, no, this has nothing to do with homomorphic encryption.


Hash or encryption function for challenge-response protocol?

You need to first understand the security properties you are trying to achieve. Possible security goals:

It shouldn't be possible to answer convincingly if you don't know the secret
If you do know the secret and provide a response, an eavesdropper shouldn't be able to extract the secret from seeing the challenge and response
The challenger shouldn't be able to craft a challenge in such a way that it would leak information about the secret
An eavesdropper shouldn't be able to replay responses later and have them accepted

There may be other properties too.

Once you have a list of properties, you have to figure out why these properties hold. The reason should be things like "if the adversary could do that, they could also break the encryption" or "find collisions in a hash function."

How you choose to use a hash or an encryption function is based on the security properties you need and which primitive provides the correct notion of security. Hashing and encryption is not interchangeable. They provide very different properties.

There isn't anything we can say about the relative merits of hashing vs. encryption that applies universally to all challenge-response protocols. It is specific to the exact protocol and what properties you want from it. If you need more help, you could provide the two competing protocols and ask for help with (in a new question) evaluating their relative merits.


This question is only relevant if you choose $p,q$ in a non-standard way.  The standard way to choose $p,q$ is to choose them as two independent random $k/2$-bit numbers.  If you do it the standard way, the question is not relevant (the probability that $|p-q|$ is too small is negligible -- and is dominated by the chances of other kinds of failures).

This question would be relevant if you were choosing $p,q$ in some funny way that had an unusually high probability of making $|p-q|$ be unusually small.  Yes, you can quantify how much easier this makes factoring.  For instance, the Fermat factoring method works as follows: for $a=\lceil \sqrt{n} \rceil, \lceil \sqrt{n} \rceil+1, \lceil \sqrt{n} \rceil+2,\dots$, it checks whether $n/a^2$ is a perfect square; if so, it has factored $n$.

We can analyze the running time of Fermat's method.  Let $\epsilon=(p/\sqrt{n}) - 1$, so that $p=\sqrt{n}(1+\epsilon)$ and $q=\sqrt{n}/(1+\epsilon)=\sqrt{n}(1-\epsilon+\epsilon^2-\cdots)$.  Fermat's method succeeds when $a=(p+q)/2=\sqrt{n}(1+\epsilon^2/2-\cdots)$.  In other words, it requires $\approx \sqrt{n} \epsilon^2/2$ iterations.  So, if you want this to take at least $2^{100}$ time, you need $\sqrt{n} \epsilon^2/2 \ge 2^{100}$, or equivalently, $\epsilon \ge 2^{50.5}/n^{1/4}$.  Since $|p-q| \approx 2\sqrt{n}\epsilon$, this means we need $|p-q| \ge 2^{51.5} n^{1/4} = 2^{51.5} 2^{k/4}$.

In other words, if you want Fermat factoring to take at least $2^{100}$ time, you need $\Delta$ to be at least $2^{51.5} 2^{k/4}$.  For a detailed derivation, see

Cryptanalysis of RSA with small prime difference, Benne de Weger, Applicable Algebra in Engineering, Communication and Computing (AAECC) vol 13 no 1 pp.17-28, 2002.  See Section 3 (much of the rest is not relevant and addresses a different question).

See also the following paper, which says that $n$ can be factored in polynomial time if $|p-q| \le 2^{k/3}$:

The Fermat factorization method revisited, Robert Erra and Christophe Grenier, eprint 2009/318, July 23, 2009.

For instance, the paper gives an example of a 1024-bit RSA modulus ($k=1024$).  It says that if $p$ and $q$ are identical in their 171 most significant bits, then you can factor $n$.  You can compare this to the requirement in the DSS standard, if you like.

But again, the right way to make this attack infeasible is to choose $p,q$ independently at random (as is the standard method).  And if you choose $p,q$ in the proper way, the threat is rendered infeasible, and you don't need to worry about the size of $|p-q|$.  For example, if you want a 2048-bit RSA key, choose a random 1024-bit key $p$, and then choose a 1024-bit key $q$.  Don't worry about their difference; the mathematics say that they will have a sufficiently large difference.

I hope that this answers your question sufficiently.

I see that the DSS standard does contain the requirement that you mention.  I think it is ill-considered, or perhaps not there for the reason you might think it is.  It is true that if you chose a RSA modulus by picking $p$ and $q$ in some crazy way that made it likely $|p-q|$ would be small, then RSA would be insecure (there are factoring methods that can be used to factor $n$ in this circumstance).  However, in that case the problem there would not be that you chose $p,q$ with a small difference: the problem would be that you failed to generate $p,q$ independently at random.  So, don't do that.  As long as you do generate $p,q$ properly, you don't need to separately check any condition on $|p-q|$; if $p,q$ are chosen randomly and independently at random, the chances that $|p-q|$ is too small is negligible (less than the chance of getting struck by lightning several times in a row, less than the chance of someone factoring your RSA modulus, etc.).

Why does the DSS contain this recommendation?  I don't know.  I think the recommendation is misguided and unnecessary.

Bottom line: the best answer to your question is to un-ask the question, as it contains some implicit assumptions that are not valid.


Can a block cipher with fixed point permutations be a good PRP?

Short answer
As Maeher said, the adversary cannot recognize which points are reprogrammed or distinguish $\widetilde E$ from $E$, given oracle access to $\widetilde E$ (or $E$). This is because the adversary who detects such points can also be used to break the PRP security of $E$ by finding the key $K$.
Formal proof
It suffices to prove that no efficient algorithm can distinguish $E$ from $\widetilde E$ via oracle access. That is, we will prove that for any efficient $A$ with $q$ query to the oracle such that
$$
|\Pr_{K}[A^{E(K,\cdot)}()=1] - \Pr_K[A^{\widetilde E(K,\cdot)}() =1]|=\epsilon, \label{1}\tag{1}
$$
it holds that $\epsilon$ is negligibly small.
To measure the advantage in a different term, first note that a difference in the oracle access to $E$ and $\widetilde E$ only happens if the adversary query $(K,K)$ or $(K,X)$ for $X=E^{-1}(K,K)$ to the oracle. Otherwise, both oracles work exactly the same and there is no chance to figure out the difference. Let's say the above event by $\rm Bad$. Then it holds that
$$
\epsilon \le \Pr_K[A^{E(K,\cdot)}()=1|{\rm Bad}] \le \Pr_K[A^{E(K,\cdot)}()|{\rm Bad}].\label{2}\tag{2}
$$
Note that whether the oracle is $E$ or $\widetilde E$ doesn't make any difference. We choose $E$ here.
What is the probability of $\rm Bad$? We define a new adversary $B$ having oracle access to $E$ to find the key of PRP as follows.

Choose a random $1 \le i \le q$.
Run $A$ with the given oracle right before $i$-th query. Let the input of $i$-th query by $X$ and with probability, $1/2$ do either

output $X$, or
query $X$ to the oracle and output the answer $E(K,X)$.

Suppose that in the $i$-th query the $\rm Bad$ event occurs. If the first case of $\rm Bad$ occurs, i.e. $A$ queries $K$ to the oracle, then $B$ outputs $K$ with probability $\epsilon/2q$ by the first action (output $X$ directly).
On the other hand, if $A$ queries $E^{-1}(K,K)$, the second action outputs $E(K,E^{-1}(K,K))=K$ that also has probability $\epsilon/2q$.
Overall, the algorithm $B$ outputs $K$ with probability $\epsilon/2q$.
However, the PRP security of $E$ says that this probability is negligibly small. This implies $\epsilon$ is small as well since $q$ is polynomially bounded (given that $A$ is efficient). Thus no efficient algorithm can distinguish $E$ from $\widetilde E$ via oracle access, and since $E$ is PRP, $\widetilde E$ is a PRP as well, which is as we desired.


Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" (with sufficiently powerful conditions on $m$). These kinds of questions are known to be difficult, and we simply do not know of an efficient way of answering them for general composites of unknown factorization.

Reformulating the problem geometrically does not appear to be helpful in this case (for instance, you need to know $p + q$ to know the side length of the square, and, of course, if you know $pq= N$ and $p + q$ then you can already factor $N$ efficiently without further techniques necessary).

As an aside, it is striking that we should not be able to answer questions about the behaviour of a simple function over the integers like $f(x) = x^2 \bmod{N}$, but recall that modular arithmetic is intrinsically linear: two integers $x$ and $y$ are congruent modulo $N$ if and only if $x - y = kn$ for some integer $k$. If you come from a programming background, it is a bit like mixing addition/multiplication and XOR/OR/AND in your algorithms - as long as you stick to one or the other, math it easy (standard algebra for the first, boolean logic/De Morgan's laws and so on for the other) and you can easily rearrange things around and so on, but as soon as you use both, even the simplest functions become very hard to understand and work with (a fact often used in symmetric cryptography). As an another example, mixing continuous functions like $\sin(x)$ with discrete functions like $\lfloor x \rfloor$. Same with mixing modular arithmetic and nonlinear functions like squaring. We do know how to work with these - to some extent - modulo primes or prime powers, a surprising result of number theory (for instance, it is easy to take square roots modulo a prime), and the Chinese remainder theorem [which, by the way, essentially borrows ideas from linear algebra] lets us extend these results to any integer whose factorization is known. But if the factorization is not known, there does not appear to be an easy shortcut in the general case (yet, of course, it is not proven that none exist).

As a result it is not surprising that most* of the current most efficient general purpose factorization algorithms use linear algebra techniques at their core to find a factorization of $N$ - it's about the only thing we can do if we know nothing about $N$ or it doesn't have any special structure (for instance, a prime factor with a smooth multiplicative order over some group that's easy to compute in, e.g. integers/elliptic curve). This is not to say that these algorithms are trivial. The fastest one (the number field sieve) uses powerful and nontrivial results from the theory of finite fields, but still builds on the same structural framework as the quadratic sieve and other sieving algorithms.

* The ECM algorithm is kind of in a class of its own, since it can be considered general purpose, yet uses group-theoretic ideas to find factors of $N$ while remaining rather competitive up to a certain input size - if you are interested in integer factorization, it is well worth your time to read all you can about this algorithm, and its predecessors the $p - 1$ and $p + 1$ algorithms (which are all conceptually similar but approach the problem in different and insightful directions)


What makes SHA-2 and SHA-3 have security levels half their output hash length?

You can't say SHA-2 has a security level of half its hash length without any given context.  128 bit against what type of attack?  What is the attacker trying to do?  Perform a collision? Ok yes it has 128 bit against collisions. Perform a preimage? Nope it has 256 bit security against preimage attacks.

Any algorithm is considered n bit strength if the expected number of operations for the average case is 2^n.  For unbroken cryptographic hashes the strength is 2^(n/2) against collisions and 2^n against preimages.  Collisions are simply "easier" than preimage attacks due to the birthday problem.  They take less operations so you need a larger search space (digest length) to achieve the same level of security.

So the statement that SHA-256 has 128 bit security is incomplete and it ignores the fact that collisions are not always relevant.  Against many type of scenarios a collision is of no value.  An example where collisions are not a threat would be hashed passwords.  For an attacker to break a specific password they need to find a preimage of the password hash.  In that application SHA-256 has 256 bit security because collisions present no security risk(i.e. attacker determines abc and xyz both hash 1234 and that doesn't match any password hash).  It doesn't help that the word collision is used in common language to scenarios which refer to a preimage.  Also keep in mind there are two types of preimage attacks and once algorithms become partially compromised they may have differing levels of security depending on if it is a first or second preimage attack.  Of course once an algorithm is compromised you should look to migrate to a more secure algorithm but that distinction could be relevant in some situations.


How to solve cipher encrypted with Vigenère + Columnar Transposition?

Obviously such a combination of ciphers is stronger than any of these two ciphers alone.

The Vigenere cipher provides "confusion", while the transposition cipher provides "diffusion". These are terms used by C. Shannon, refer to http://en.wikipedia.org/wiki/Confusion_and_diffusion.

Modern ciphers like AES are making use of diffusion and confusion as well. But - besides additional other operations - here several rounds are applied.

I think applying these two encryption methods (vigenere & transposition) to a plain text only once will still be a rather weak encryption (at least compared to AES).

In the following I provide some of my thoughts. I haven't verified them, so I cannot guarantee that everything described below works as expected. :-)

Some thoughts of how to attack such an encryption: Evolutionary algorithms (http://en.wikipedia.org/wiki/Evolutionary_algorithm) are one way to break transposition ciphers (btw, EAs can be used to break Vigenere ciphers as well). One variant of such an algorithm is called genetic algorithm (http://en.wikipedia.org/wiki/Genetic_algorithm). Investigations in this area have been done, e.g. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.4358&rep=rep1&type=pdf.

One main function within a genetic algorithm (GA) is called fitness function. Once a key has been chosen the given cipher text is decrypted using this key and the resulting clear text is passed to the fitness function (http://en.wikipedia.org/wiki/Fitness_function). The fitness function returns a measure how close the result comes to an optimum solution.

In case simple transposition ciphers are to be solved the fitness function determines how close the clear text comes to the English language.

Now if a clear text is encrypted by the Vigenere cipher, and the resulting Vigenere cipher text is encrypted using the transposition cipher then the resulting cipher text can be attacked by treating it as a "simple" transposition cipher. The difference is now that the fitness function must return a measure how probable it is that the resulting clear text is a Vigenere cipher.

Vigenere ciphers have certain characteristics, e.g. an autocorrelation will show periodic maxima (http://www.cryptool-online.org/index.php?option=com_content&view=article&id=90&Itemid=107&lang=en). Thus it should not be a problem writing a fitness function which distinguishes a Vigenere cipher from a random sequence of characters.

Once the transposition cipher is solved solving the Vigenere cipher is rather straight forward.

Implementing a fitness function checking for the Vigenere cipher will probably be slower than a corresponding function checking for English text. Thus I expect that breaking the cipher "Vigenere & transposition" will require much more processing time than breaking any of these ciphers alone.

There is still an open question: How to find the key length for the transposition cipher? One possible way might be to apply an autocorrelation to the cipher text. I would expect to see maxima at multiples of the least common multiple of the Vigenere key length and the transposition key length. This should at least limit the potential key lengths to try.


How to attack this authentication protocol from "Cryptography: An introduction"

If the attacker M is impersonating both A and S, then he obviously doesn't have to bother sending the third message in the protocol to himself.  Thus, the protocol reduces to:

M(A) → B: A, Na
B → M(S): B, {A, Na, Tb}Kbs, Nb
M(A) → B: {A, Kab, Tb}Kbs, {Nb}Kab

where M(A) and M(S) denote M impersonating A and S respectively.

By itself, this is not a successful attack: while M can pick any valid Kab he wants, he generally cannot obtain the corresponding ciphertext {A, Kab, Tb}Kbs to send to B.  However, if the formats for Kab and Na are compatible, such that M can choose Kab equal to Na, and if B does not check for this possibility, then M can simply replay the ciphertext {A, Na, Tb}Kbs he received from B in the second step, leading to the attack:

M(A) → B: A, Na=Kab
B → M(S): B, {A, Na=Kab, Tb}Kbs, Nb
M(A) → B: {A, Na=Kab, Tb}Kbs, {Nb}Na=Kab

Other attack methods may exist if the encryption scheme denoted by the curly braces is malleable, but the attack described above will work even if it's not.


PKCS#7 signed data structure in signed PDF document

The actual data can be omitted from a SignedData encapContentInfo; see current CMS RFC which is not materially changed from earlier versions. The RFC calls this "external signature"; IME it is also called "detached signature" or "clear-sign[ing,ed]", and is widely used. For example S/MIME signed messages usually are a multipart containing the plaintext data and separately (the encoding of) a no-data/external/detached signature on that plaintext; this allows the text part to be handled by a non-SMIME-aware or even non-MIME-aware program (only without signature verification).


Protecting Ed448 against DPA and fault attacks

The, common, assumption used in that paper is that an attacker can DPA a fixed secret when it's mixed with known (to the attacker) and varying data.

The proposed solution was to add random after the key to fill the SHA-512 block size.

By doing this:

the first SHA-512 computation processes the fixed secret and varying but unknown data, so the attacker can't perform DPA.
After the first block, the result is the intermediate hash value which is unknown and varying (from message to message), so it can't be recovered through DPA when processing subsequent blocks.

Side note: if we would have padded the key with zeros instead of random, we would have mixed the fixed key with known but fixed data. The attacker in this case is not able to DPA the key. However she can DPA the intermediate hash value after the first block, which is secret and now fixed and will get mixed with the known and varying message.

Your proposed solution SHAKE256(dom4(prehash, context) || b || Z || PH(M), 114) with Z random data would work if you carefully select the size of Z and assuming the attacker can't control the context.

If the attacker control the context then she can choose varying context that together will the key (b) will completely fill the SHAKE256 block, so no random is used in that computation and DPA can be performed.

If the attacker can't control the context then you just have to make sure that Z is not too small and fills the block.

For example, given the block size of SHAKE256 of 136 bytes, if len(dom4(prehash, context) || b)=134, due to a large context, then 2 bytes for Z won't be enough and you will need to select a Z of 138 bytes (2 to fill the current block and 136 for another full block).

Update:
Please be aware that the generation of r is one way to side-channel attack EdDSA, but it's not the only one. The scalar multiplication should be protected as well from single trace attacks (technically not DPA) and the computation of $S = (r + k * s)$ could be targeted by DPA as $s$ is fixed and unknown and $k$ is varying and known.


Implementing AES in C++: 4x4 Array of unint8_t, or 4x1 array of uint32_t?

One way to see it is the following: RAM is slow. Modern processors can do several operations in a single clock cycles. However, a RAM access, such as retrieving data from an array based on a computed index, has inherent latencies and concurrencies issues; in the best of cases, you can do one memory access per cycle, and the result is not available for computations until at least one or two cycles later (even if all the data is in L1 cache).

Therefore, generically, it is best to do as little array accesses as possible. Which means grabbing from each array access as much data as possible, such as a full 32-bit word instead of just one byte.

The trouble with generic comments like the one above is that they are, well, generic. Performance issues depend a lot on the involved architectures, the operational constraints, and what you want to achieve; there are several metrics of performance, such as bandwidth, latency, code size, energy consumption... So, really, you have to try. However, most people (including myself) who have tried to implement AES on 32-bit processors (like a PC or an ARM CPU) with at least a few kilobytes of L1 cache, and no hard limit on code size, have found the "32-bit word" structure to be the best -- unless you aim for an implementation which resists to cache timing attacks, in which case you have to do things quite differently, without any array at all.

To investigate the ins and outs of AES software implementation, you could do worse than perusing Brian Gladman's site which is kind of a reference on the subject.


Negligible function defined as product of polynomial and a negligible function

Since $f_1$ is negligible, it is smaller than the inverse of any polynomial, for all sufficiently large $n$. In particular, given any polynomial $q$, it is smaller than $1/p_1q$.


Need for secure hash function for a bloom filter

Are there other attack vectors?

This will very much depend on the application and how the attacker interacts with the bloom filter.

Let's say you are using a bloom filter to whitelist applications that are allowed to run on your system. The system computes a hash of an application before it is executed and checks it against the bloom filter. If it is in the whitelisted "set", then then application runs. If not, then the application is terminated.

Users can submit applications to the system administrator to have them whitelisted. The administrator does some manual analysis of the application before adding it to the whitelist to ensure it is good software (let's just pretend that the administrator can do this with complete accuracy).

The administrator can set the size of the bloom filter and the number of hashes to get an arbitrarily low false positive rate.

If a non-cryptographic hash function is used, e.g., CRC32. It is not unreasonable to assume that the probabilistic analysis that the administrator uses to determine the parameters of the bloom filter are incorrect.

This could manifest itself in a few particular ways.

If the attacker cannot get a benign application of his choosing approved but does know some number of already approved applications, the attacker can likely construct a malicious application that will be guaranteed to be in the set.
If the attacker can get a benign application approved, it is not unreasonable to assume that an attacker could come up with 2 programs, 1 benign and 1 malicious that would have the same hash values. By getting the benign one in the set, the malicious one is now also in the set.

Both of these scenarios would be much harder (i.e., computationally infeasible) if a cryptographically secure hash function is used, as opposed to a non-cryptographic function (like CRC32).


You need an authentic channel from Alice to Bob to get a secret channel from Bob to Alice. This assumption is missing in a), so anyone in control of the communication channel can play man in the middle on any protocol.

As long you don't have a secret channel from Alice to Bob or an authentic channel from Bob to Alice, Alice will never (= for any protocol) be sure who is sending her the secret messages.

See U. Maurer, P. Schmid, A calculus for secure channel establishment in open networks, ESORICS' 94, LNCS 875, pp 175-192.


There is no such thing as "as secure as AES" when it comes to encryption. This sounds weird, but let me explain. AES is a block cipher. As block cipher it always uses deterministic permutation of the bits in the plain text block. And as it is deterministic it always encrypts the same plaintext block to the same ciphertext block.

It is therefore not IND_CPA secure when used as a cipher. In other words, you can clearly see that the same plaintext encrypts to the same ciphertext; you can therefore distinguish plaintext blocks by looking at the ciphertext blocks. AES is a secure block cipher, it is not a secure cipher by itself.

Now if you would add padding bits then you would still not accomplish IND_CPA security. Padding schemes for block ciphers - such as PKCS#7 padding - are generally deterministic. So that's not going to work in the general case.

CTR mode encryption is considered a secure mode of operation for block ciphers with a block size of 128 bit or more. CTR mode however requires a nonce to operate. So you would either have to generate one and store it with your ciphertext or you would have to use some out-of-band means to generate a nonce (e.g. a number stored elsewhere in a database). This is a good option if you can store some 128 bits of output: simply store a 64 bit randomly generated nonce and 64 bits of ciphertext (which you may have to extend to 128 bits for many API's by right-padding with zero's).

CTR mode doesn't add any integrity protection, so you might want to add this by using an authenticated (AEAD) cipher. This will however add more bits for the authentication tag to the output.

With 64 bits of plaintext it becomes very tempting to simply encrypt with a 64 bit block cipher. This won't provide IND_CPA security, but you may not care if identical plaintext blocks can be distinguished. You could also take a look at Format Preserving Encryption. Triple DES would still be an option for this; in practice it will likely offer as much security as a 128 bit cipher.

Maybe it's a good idea to use public key encryption. This would for instance be the case if you don't want the decryption key exposed during encryption.

I've answered this in the general sense. But you can see that there are many unknowns to us. This is why the question "Is there any other scheme that i can use to encrypt 64 bit data and is as secure as AES." is bunk.

Encryption is not a goal; providing security for your data is. And without a clear definition of your goals, use cases, requirements and threat models any answer may be wrong.

Note that all schemes have limits on how many 64 bit blocks may be encrypted with a single key.


The relationship between a private and public key?

We'll assume RSA rather than elliptic curve, just because it's simpler.

A key consists of a modulus and an exponent. Both the public and private key use the same modulus, what differs is the exponent. To encrypt (or decrypt) you take your message, raise it to the power of the exponent, divide the modulus, and the remainder is your encrypted (or decrypted) answer.

How to generate your key

You start with two random prime numbers ("p" and "q"), if you have a 2048-bit key, then P and Q are both 1024 bits long. You multiply them together; that's your "modulus" -- the unique part of your public key. The other part of your public key (the "exponent") doesn't need to be unique, but it should be prime; most people just use 65537 because it's safe enough, and it makes your implementation fast.

Now let's figure out the corresponding private key. All you need to do is find the modulo multiplicative inverse of your public exponent with respect to (p-1) times (q-1). The math is simple, but not important here; it's just a simple calculation. That result you get, that's your private exponent; that's the "secret" part about your private key. You're done with P and Q now, throw 'em away.

So encrypt/decrypt a value: raise the value to either your public exponent or private exponent, divide by your modulus (same modulus for both keys) and the remainder is your answer.

Now let's try to attack it

I have the public key (which consists of the number 65537 as well as the modulus (P * Q) and what I'm trying to figure out is the number derived from (P-1) * (Q-1). If I knew what P and Q were, that would be dead-simple. But I don't. Instead, I know what P * Q is.

This is why people say that breaking RSA just boils down to factoring large numbers. Because if I could factor P * Q into P and Q, then I could re-derive the private key.

How are the keys related

The link between the two is this multiplicative inverse thing; it's like how 2 is linked to 1/2 and 13 is linked to 1/13. One can undo the other. Except that the relationship only exists in this finite field defined by the modulus. This is that wrap-around math world which is a lot like dealing with time on a clock -- where 10 plus 3 is 1 instead of 13 (because the clock only goes up to 12).

So to calculate that inverse relationship directly from the public key, you'd end up having to try to compute it over and over, with 1 trip around the clock, two trips, three, and so on until you got an answer that works. This turns out taking more time than the factoring challenge, so everybody just sticks to factoring.

This post contains mild technical inaccuracies mostly for brevity and simplicity. Feel free to leave a comment if you're the type of person who likes to argue on the Internet for fake points, but you will likely be summarily ignored.


GMW protocol says that A and B can locally compute $c_i = a_i \oplus b_i$ and the result should be same for both.

I highlighted the part that is incorrect. They started with secret shares of $a=0$ and secret shares of $b=1$. Now they have secret shares of the XOR $c= a \oplus b =1$.

Only if the secret value $c$ is zero will their shares be the same (and of course, they have no way of knowing whether this is the case). In your example $c=1$ so their shares will be opposite.

Basically, you can see that $c_1$ and $c_2$ are valid secret shares of $a \oplus b$ since:
$$
  c_1 \oplus c_2 = (a_1 \oplus b_1) \oplus (a_2 \oplus b_2) = (a_1 \oplus a_2) \oplus (b_1 \oplus b_2) = a \oplus b
$$


RSA Proof - Is Z(n) closed under multiplication

$Z_n=\{0,\ldots,n-1\}$ is not a multiplicative group (I assume that this is what you mean by closed under multiplication in this context, see below) because it contains the zero (this element is not invertible) and furthermore if $n$ is not prime, all elements that are not co-prime to $n$ also have no multiplicative inverse. $Z_n^*$ are the elements from $1$ to $n-1$ that are co-prime to $n$ and thus all invertible and thus this set forms a group under multiplication (modulo $n$).

To expand on the "closed under multiplication": The set $\{0,\ldots,n-1\}$ is indeed closed under multiplication modulo $n$ meaning that whenever you multiply two elements modulo $n$ the result will be in this set. However, this is not sufficient to form a multiplicative group (you require an identity, inverses and to show the associativity of the group law).


What does "crypto_box" actually mean in libsodium and NaCl?

What does "cryptobox" mean in Libsodium and NaCl? In general, and in specific case, what does "box" do?

cryptobox or correctly crypto_box is just box. box_easy calls secretbox with the shared key between the sender and receiver, unique per direction. box_seal calls box_easy with a random sender secret key and prepends the ciphertext with its corresponding public key. secretbox does the symmetric authenticated encryption.

crypto_box_easy(ciphertext, MESSAGE, MESSAGE_LEN, nonce,
                    bob_publickey, alice_secretkey)
crypto_box_seal(ciphertext, MESSAGE, MESSAGE_LEN, recipient_pk);
crypto_secretbox_easy(ciphertext, MESSAGE, MESSAGE_LEN, nonce, key);

  I know that libsodium is authenticated encryption, but gpg is not. "Box" makes me think the encryption and signing are somehow sealed and protected.

Both secretbox and GPG/PGP use authenticated encryption. box (deniably) authenticates the sender without a signature. box uses Diffie-Hellman to derive a key which requires either of the sender or receiver's secret key to compute. Consequently, if an adversary steals Alice' key, they may impersonate Bob to Alice; this attack is known as Key Compromise Impersonation.

PGP is vulnerable to a related attack by using sign-then-encrypt. I.e. If Alice signs a message and encrypts it for Bob, Bob may decrypt it and encrypt it for Carol. When Carol decrypts the message, she may believe Alice sent her the message, because Alice did, in fact, sign it.

Libsodium's box is better than PGP's sign-then-encrypt but we can do even better when both parties can send messages to the other. I.e Triple-DH used in Signal (ignore the prekey extension). Edit: Although I'd rather avoid signatures, I should have included this. Signatures may be combined appropriately by signing the (message, recipient public key) tuple; such that signature validation with the incorrect recipient fails to verify.


Commit and prove as a general trick for malicious security

No, zero-knowledge proofs are not only a trick to prove security: essentially all protocols where zero-knowledge proofs are used would be insecure against malicious adversaries if zero-knowledge proofs are removed, or replaced by "decommitments" as you suggest.

Let me illustrate this on a simple example. Suppose that Alice and Bob have respective inputs $x$ and $y$, which are $n$-bit string. Suppose also that Bob wants to obtain the Hamming distance between $x$ and $y$. For example, Bob could be a server which stores a fingerprint, and it should grant some access rights only to the user which has this fingerprint; hence, the goal of the protocol is to check that Alice's fingerprint is correct (in which case it will be close to $y$ - not necessarily equal due to imperfect measures), but without leaking $x$ or $y$.

A simple solution to the above is as follow: Bob encrypts each bit $y_1, \cdots, y_n$ using, say, the ElGamal encryption scheme "in the exponent" (i.e., an encryption of $y_i$ is of the form $(g^{r}, h^rg^{y_i})$), and sends these $n$ ciphertext to Alice. Now, Alice can homomorphically compute an encryption of the Hamming distance between $x$ and $y$, using the fact that $\mathsf{HD}(x,y) = \sum_{i=1}^n x_i + y_i - 2x_iy_i$, and send back this ciphertext to Bob, who decrypts it and gets $\mathsf{HD}(x,y)$.

Suppose now that Bob is malicious. In this case, he could for example cheat as follow: instead of encrypting $(y_1, \cdots, y_n)$, he encrypts $2, 4, \cdots, 2^n$. It is easy to see that doing so allow him to recover the entire $x$ when decrypting the final ciphertext. To prevent this attack, the natural solution is to use a zero-knowledge proof. With the general commit-and-prove strategy, it would look as follow: Bob commits to $y_1, \cdots, y_n$, proves in zero-knowledge that each commitment commit to the same value that the one encrypted in the corresponding ElGamal ciphertext, and proves in zero-knowledge that each committed value is a bit (i.e., that each $y_i$ satisfies $y_i(1-y_i) = 0$). This guarantees that Bob cannot perform the attack I mentioned. In the proof, this will allow the simulator to indeed extract the $y_i$, but also guarantees that they are bits, and are the value encrypted in the ciphertexts.

Now, if we were simply opening the commitments, all security would break down. Specifically, either Bob commits to the correct $y_i$; but then, when decommitting, he reveals all his private input $y$ to Alice. Or Bob commits incorrect values; but then, Alice has no way to check anything about the encrypted value simply from seeing opening to these incorrect values.


Just thinking out loud here:

Take a picture of the contents of a box.
Put these pictures in a safe.
Ship box and safe together, lock with key of sender.
Receiver unlocks safe, compares pictures with contents of box.

The safe and keys are already common for symmetric encryption too.