Can I use NaCl's scalar multiplication functions for Diffie Hellman Key Agreement? I want to create some software that performs diffie hellman group key agreement but I don't want to reinvent the wheel even if I know how it's done. So I came accross the NaCl library, especially the scalar_mult functions.

As far I know you can perform Diffie Hellman key agreement on elliptic curves therefore, my thought is if I combine it with crypto_box ones for key generation, I can do a Diffie Hellman Key agreement.

My Idea is (described in some sort of pseudocode) shown in the following image:

Would you recommend it as shown above?

Yes.

The DH function is $$\operatorname{X25519}(n, p) := x\bigl([\operatorname{clamp}(n)] x^{-1}(\operatorname{decode}(p))\bigr)$$ with scalar multiplication $[\alpha]P$ on the curve $y^2 = x^3 + 486662 x^2 + x$ over the prime field $\operatorname F_{2^{255} - 19}$, where $n$ is 32-byte string representing a private key, and $p$ is a 32-byte string representing a public key.

Here $\operatorname{decode}(p)$ maps a 32-byte string into an element of $\mathbb F_{2^{255} - 19}$, and $\operatorname{clamp}(n)$ maps a uniform random 32-byte string into a uniform random integer in $\{2^{254}, 2^{254} + 8, 2^{254} + 16, \dots, 2^{255} - 8\}$—that is, an integer multiple of 8 between $2^{254}$ and $2^{255} - 1$.

As a DH function, this has the property that $\operatorname{X25519}(n, \operatorname{X25519}(m, \underline 9)) = \operatorname{X25519}(m, \operatorname{X25519}(n, \underline 9))$, where $\underline 9$ is the encoding of the standard base point, whose $x$ coordinate is 9, which means that both parties will arrive at the same shared secret.

The security contract requires that that you must hash the shared secret: use $H(\operatorname{X25519}(n, p))$.  Specifically, the security conjecture is that even if you reveal $\operatorname{X25519}(n, \underline 9)$ and $p \mapsto H(\operatorname{X25519}(n, p))$ for any $p$ of an attacker's choice, then the attacker must spend ${\sim}2^{128}$ bit operations to find any shared secret.  The security contract also requires that you never use $n$ for any purpose except the two crypto_scalarmult functions:

crypto_scalarmult_base(p, n) sets $p$ to the public key $\operatorname{X25519}(n, \underline 9)$.  You may publish $p$.
crypto_scalarmult(q, n, p) sets $q$ to the unhashed shared secret $\operatorname{X25519}(n, p)$, the secret shared between the private key $n$ and the public key $p$.  You must hash $q$ before using it.


Selective and existential unforgability of signature schemes I understand that one can define EUF-CMA of a signature scheme is terms of a game where the adversary is allowed to query signatures on messages of his choosing, and at the end of the game he must output a pair (m, s) such that s is a valid signature of m, and m has not been queried before. My questions are the following:

How does one select selective unforgability under chosen message attack in terms of a game?
Are there examples of signatures which are SUF-CMA, but not EUF-CMA?

1) In the selective unforgeability game (often also denoted universal unforgeability), the adversary is given the public key and a target message for which it needs to produce a forgery (instead of giving the adversary only the public key and letting the adversary choose the target message).

2) No, any scheme that is EUF-CMA is also SUF-CMA (this is easy to show; build an EUF-CMA adversary from any SUF-CMA one by simply running the SUF one on an arbitrarily chosen message).


How to deduce enigma settings given a partial plaintext? Assuming some large block of text is encrypted with an enigma machine and I only know a small subset of letters before and after encryption, how do I go about figuring out the enigma settings from this point?

According to "Applied Cryptanalysis", the theoretical keyspace of Enigma is approximately $2^{366}$, but due to practical limitations, Enigma as used by the Germans only had a keyspace of approximately $2^{77}$. Given the power of some of the clouds out there (with GPUs and all), I bet you could do a brute-force attack of the 77-bit key space in a reasonable amount of time. Deep Crack could brute-force the 56-bit key space of DES in about 4.5 days. I'd think we could do much better than that today.

If you had a machine 100 times faster than Deep Crack, it would take about 265 years to do the brute force. If you had a thousand of these machines (not unrealistic given cloud computing), you could brute force it in 96 days (10000 machines would make it 9.6 days).

Since you are given a partial plaintext, however, I would think you could even do much better. Cryptanalysts during the war were able to do much better than brute force because of a protocol failure. The people enciphering messages would encrypt a session key with the daily key. They repeated the session key due to transmission errors. This allowed cryptanalysts to do statistical analysis once they had multiple messages captured from the same day. Without additional information from the OP though, it is unclear whether similar protocol weaknesses could be exploited.


Why using AES in ECB (Electronic Code Book) mode a bad idea? Why using AES in ECB (Electronic Code Book) mode a bad idea? is CTR mode better? Given only these two can be used for parallelization.

ECB is bad because identical plaintext blocks result in identical ciphertext blocks. Encrypted data is therefore not pseudo-random.

This is how Tux looks like after ECB encryption:

CTR mode doesn't have this problem. Data encrypted with CTR mode is pseudo-random and doesn't show any pattern. So CTR is much better.

CBC and CFB can also decrypt parallel, but not encrypt.


Cryptography survey as an undergrad Is cryptography so specialized that taking a survey class is a waste of time?
I'm not the type of person who can do logs in my head or has a deep mathematical aptitude, but cryptography is certainly very interesting. But I wonder if I'll scratch the surface and realize quite quickly that there are very few who can participate in the greater conversations.

No, I think a general understanding of what a cipher, hash, signature, MAC and a few other of these concepts will make it much easier to understand what cryptography is about.

It's like some knowledge about cars can be very helpful, even if you don't get to be a mechanic. Especially understanding a bit about certificates and PKI is pretty useful, as it is the underlying authentication structure for the internet (especially TLS and therefore HTTPS).

We may be a bit biased here. You can get by pretty well without knowing cryptography. Then again, you won't need a lot of mathematics unless you presume you're going to build cryptographic algorithms or perform cryptographic analysis.


How safe are Libsodium Crypto Boxes? I am currently working on a huge PHP project and we are seriously considering to use the Libsodium PHP library in it.

My question is related to the "sodium crypto box" functionality. We would use this functionality to implement public key authenticated encryption. We would generate keypairs using the "sodium crypto box keypair" function, nonces using the "sodium crypto box noncebytes" function, and seal/open the crypto boxes through the "sodium crypto box" and "sodium crypto box open" functions.

My question is basically "how safe is this"?

Public keys will be public, so our concern is that someone might be able to generate a correctly sealed box by "cracking" somehow the secret key of the sender, or to open a sealed box by cracking the SK of the receiver. These keys are 64-digit hexadecimal strings. Is my assumption correct that this means that there are 16^64?

If yes, this would mean that brute forcing all possible combinations at a rate of 1 million tries per second would take 3.6717430630808 * 10^63 years? Or are there more "efficient" attacks?

On the official Libsodium website I found the following algorithm details with respect to the functions we want to use:

  Key exchange: X25519
  Encryption: XSalsa20 stream cipher
  Authentication: Poly1305 MAC

Can someone try to explain me what this means ? Is following interpretation correct:

X25519: This is the keypair generation algorithm?
XSalsa20: This is the encryption algorithm?
Poly1305: This is the nonce generation algorithm?

You can think of crypto_box_curve25519xsalsa20poly1305 as some composition of X25519, a key agreement scheme; XSalsa20, a symmetric-key stream cipher; and Poly1305, a one-time polynomial evaluation message authentication code.  But that's not the best way to think about it when you're engineering something out of it—partly because there are many ways you could compose those, but mainly because it doesn't help you to figure out how it fits into your application.

Instead, you should think of it as a contract, with obligations on your part and security services on the part of crypto_box_curve25519xsalsa20poly1305:

Your obligations to crypto_box_curve25519xsalsa20poly1305.

(a) You must generate a secret key uniformly at random.

(b) You must choose a distinct nonce for every public key and message you use that secret key with.  You may generate them uniformly at random if you like.
Security provided by crypto_box_curve25519xsalsa20poly1305, even in the face of an adversary who can intercept every box on the wire and persuade the legitimate users to create boxes for arbitrary messages of their choice adaptively.

(a) Anyone who does not know one of the two secrets keys for a sender and receiver cannot open boxes whose contents did not already know.

(b) Anyone who does not know one of the two secret keys for a sender and receiver cannot forge a box not created by the sender or receiver.

crypto_box_curve25519xsalsa20poly1305 does not provide third-party verifiability, also known in some circles as nonrepudiation: if Alice sends a box to Bob, Bob can't cryptographically persuade Charlie that Alice sent him that message without also demonstrating to Charlie the ability to forge Alice$\rightarrow$Bob messages.

This is spelled out in slightly more academic detail in the NaCl crypto_box documentation under ‘Security model’.

Attack costs.
crypto_box_curve25519xsalsa20poly1305 is designed to target a ‘128-bit security level’, which means that the area*time cost—area on a silicon die times amount of time you spend powering it—of the best known attacks is around that of $2^{128}$ bit operations, which is more than we can imagine anyone ever carrying out.

The secret keys of crypto_box_curve25519xsalsa20poly1305 are indeed 256 bits long, but there is enough mathematical structure in X25519 to admit an attack cheaper than simply enumerating and trying all possible secret keys—so much cheaper that the best you can hope to get for an elliptic curve over a field of 256 bits is a 128-bit security level.  You can find highly technical references about these attacks at SafeCurves under ‘ECDLP security’.

The secret keys of crypto_secretbox_xsalsa20poly1305, an operation out of which crypto_box_curve25519xsalsa20poly1305 is built, are also 256 bits long, but the nature of the kind of object that a secretbox is allows multi-target attacks, where the best known area*time cost of breaking at least one of a set of $n$ target $k$-bit keys with nonnegligible probability is significantly less than $2^k$.  Using a 256-bit key for crypto_secretbox guarantees that even for an unimaginably large set of $2^{128}$ targets, the best known area*time cost of breaking at least one of those targets with nonnegligible probability still exceeds that of $2^{128}$ bit operations.


What is the importance of the $r$ and $c$ values for the Sponge Construction? What is the importance of the $r$ and $c$ values?

Keccak[r=1600,c=0] is stated on a calculator on the Keccak website to be a checksum. But I figured if c=0, then there's only one possible output?

If C is 128, is there only 2^64 possible outputs, despite have infinite output length and an infinite number of inputs?

Keccak is Sponge-based hash function:

[Image taken from the official sponge page]

It has a large internal state, and iterates this with a permutation (that for theoretical proofs we model as an ideal permutation).

The total state of Keccak is $s=r+c$ bits.  Because the user can only ever read from or input data into the $r$-section of this (the 'rate component of the state'), a user cannot directly modify the capacity component of the state.  It turns out that the security of the construction boils down to avoiding internal collision on the capacity component (which is $c$-bits wide). That is, we require that the capacity component of the state never takes the same values twice and due to the birthday bound, this happens after around $2^{c/2}$ blocks.

So, for provable security, we need $c$ to be suitably large. However, the input and output is always at rate $r$.


fully homomorphic encryption (FHE) Please, I would like to find some hints or solution to my following problem, I would appreciate your assistance to walk with me throughout the solution

Given fully homomorphic encryption (FHE) scheme(gen, enc, dec, eval), design
a secure computation protocol so that two players, Alice and Bob, can jointly and securely
evaluate a function $g : \{0, 1\}^ k \times \{0, 1\}^k \rightarrow \{0, 1\}^k$
Here, both Alice and Bob provide inputs
but only Bob learns the output

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

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

Edit:

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


Is it possible to break a hash-based block cipher? Let's define the following block cipher:

$C_n = M_n \oplus H(k + n)$ where $C_n$ is the nth block of ciphertext, $M_n$ is the nth block of plaintext, $H$ is a cryptographic hash function, and $k$ is the secret key.

Decryption can be performed trivially, by computing $M_n = C_n \oplus H(k + n)$.

Assuming a proper mode of operation, such as CBC, how would we go about attacking such a scheme? Is this scheme provably as secure as $H$ is?

This is not a "block cipher" because a block cipher is a key-dependent permutation of the space of blocks of a given size. Here, you handle data by blocks, but the "encryption" part is done by XORing with a value $H(k+n)$ which depends on the key $k$ and on the "block number" $n$. So you do not have one permutation (for a given key), but a lot of them.

Correspondingly, it is unclear what "CBC" would look like with such a beast. If you imagine it as this:

$$ C_0 = M_0 \oplus IV \oplus H(k+0) $$
$$ C_n = M_n \oplus C_{n-1} \oplus H(k+n) $$

then this is unfortunately hopelessly weak if you encrypt two distinct messages with the same key, even if you use distinct IV -- because the XORs with $IV$ and $C_{n-1}$ can be trivially cancelled by anybody ($x\oplus y \oplus y = x$ for all $x$ and $y$) and you end up with the infamous "two times pad".

As @PaŭloEbermann says, your cipher propose is a stream cipher: it is XORing with a key-dependent pseudo-random stream, generated from the key $k$ but independent of the plaintext. Here, the pseudo-random number generator is built from a hash function. There are several ways to do that, not all being good, because some well-known hash function (MD5 and the whole SHA family) suffer from something known as the length extension attack. The "safe" way to build a PRNG out of a hash function is to use HMAC, and that is called HMAC_DRBG. It is a NIST standard. The same standard defines Hash_DRBG, which is faster (and similar to your proposal) but potentially weaker because it relies on some ill-defined properties of the underlying hash function.

Of course, an IV should be added, and not with a kind-of-CBC, as explained above. Rather, replace your key $k$ with $IV||k$ (concatenation of the IV and the key). There again, subtle weaknesses may lurk.

Either way, building a (stream) cipher out of a hash function is possible, but it requires care, and often offers rather poor performance. Indeed, hash functions are fast at processing lots of input data. Here, you want it to produce lots of output data -- and for that, hash functions are not very fast. Even with SHA-1 and Hash_DRBG, the resulting cipher would be slower than a common AES.


Behavior of AES-CTR with 128-bit nonce and possible overflow If I feed 128 bits of randomness into AES-CTR as its IV / nonce / initial counter, what will happen if I feed in a random 128-bit integer that overflows and wraps around?

I've written a test for this and found that at least some CTR implementations do the expected thing and wrap the entire uint128 around, but is it possible to guarantee this? Are there common implementations that will fail or do different and thus incompatible things here?

I guess what I'm asking is whether this is portable or not.

NIST SP 800-38A ("Recommendation for Block Cipher Modes of Operation Methods and Techniques "), Appendix B states that "The standard incrementing function takes
[x]m and returns [x+1 mod 2^m]" (my formatting, they used typesetting to show exponents).  Section B.1 goes into more detail about recommendations for the CTR mode incrementing function.

Regarding standards and compliance (which usually force portability), I couldn't really say.  And even if it was standardized to be done that way, that doesn't mean there aren't non-compliant implementations, and it doesn't mean all implementations are bug-free.

So, I guess my best answer to you is that while most implementations probably do that (wrap around like an unsigned number), and you can test it with different platforms, I don't think you can count on it, and I don't think you can scream if a vendor /changes/ this later to behave differently.  I'm not sure there is anything worded strongly enough that you can point to that would back up a complaint.

Edited to add:  The NIST document is interesting reading.  For recommendations on the incrementing function, (here I'm paraphrasing / summarizing), it basically says the incrementing function needn't necessarily increment w/ wrap, it simply must provide all 2^n unique values for an n-bit counter.  So for example, an LFSR or LCG could also be used.


Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known? Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any two hybrids $H_i$ and $H_{i + 1}$ can only be efficiently distinguished with probability $2^{-\lambda}$. So, by iterating through all the hybrids, it seems to me that the probability that $H_1$ and $H_n$ can be efficiently distinguished is bounded by $(p(\lambda) - 1) \cdot 2^{-\lambda}$ using union bound. Asymptotically, this probability is negligible in $\lambda$.
My question is that, when $n = p(\lambda)$ is polynomially bounded with respect to $\lambda$ but not known, it seems impossible to choose a reasonable $\lambda$ such that $(p(\lambda) - 1) \cdot 2^{-\lambda}$ is sufficiently small (e.g., $< 2^{-40}$). I think that the same issue may exist as well when it comes to some computational security parameter $\kappa$. It would be appreciated if someone could give me any hint on this question. Many thanks.

a function "polynomially bounded" means there exists $d\in \mathbb{N}$ such taht
$f(\lambda)\leq \lambda^d$ asymptotically.
You don't have to know $f$, but if you want to bound the advantage of your adversary asymptotically, you have to know a such $d$ which verifies this inequality.
If you don't, then you can't deduce anything. But in general, if you look the proof in details what is $n$, and why it has been claimed polynomially bounded, it's easy to find a such $d$, such that $n\leq \lambda^d$ asymptotically.


Fermat's factorization method on weak RSA modulus Given a public key for RSA, I have extracted the modulus which looks like this:

Public-Key: (2049 bit)
Modulus:
    01:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:02:19:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:
    f8:45
Exponent: 65537 (0x10001)

I have successfully factorized the modulus using Fermat's factorization method. This method is fast when the prime factors are close to the square root of the modulus.

My question is, how can you tell that this modulus has its prime factors close to its square root?

Thank you

In general, it is not sizably easier to tell from an RSA modulus that Fermat factorization will succeeds, than it is to perform such factorization.

However here, it is visually easy to notice the long sequence of 00 and ff in the modulus. That translates into noticing that the modulus to factor is $2^{2048}+\mathtt{21a}_h\cdot2^{1024}-\mathtt{107bb}_h$, or equivalently $2^{2048}+538\cdot2^{1024}-67515$.

Per comment: the number is 257-byte, with the left 01:00:00:00:, thus just over $2^{2048}$. Cutting where the long ff:ff:ff: starts, the right fragment has 128 bytes, thus has a value just shy of $2^{1024}$, and the :00:00:00:02:19:on its left contributes for an additional $\mathtt{219}_h\cdot2^{1024}$, totaling near $\mathtt{21a}_h\cdot2^{1024}$. The correction to subtract is one more than the bitwise complement of the right fragment :ff:ff:ff:fe:f8:45.
In other words, the modulus is $2^{2048}+\left(\mathtt{0000000219}_h+1\right)\cdot2^{1024}-(\overline{\mathtt{fffffffef845}_h}+1)$.

That $2^{2048}+538\cdot2^{1024}-67515$ suggests to try if the modulus could be $(2^{1024}+a)(2^{1024}+b)$ for integers $a$ and $b$ of small absolute value, that is if the system $a+b=538\text{ and }a\cdot b=-67515$ has an integer solution. We can

Solve the second degree equation $x^2+538x-67515=0$ which roots will be $a$ and $b$, and check these are integers. We get roots are $-\dfrac{538}2\pm\sqrt{\left(\dfrac{538}2\right)^2+67515}$, which indeed are integers $643$ and $-105$, and that gives us the factorization as $(2^{1024}+643)(2^{1024}-105)$.
Or factor $67515=3\cdot5\cdot7\cdot643$, which invites to try $a=643$ and $b=-3\cdot5\cdot7=-105$, with indeed $a+b=538$.

Notice the above factorization method works only because the hex fragments in the middle and in the right of the modulus given have a highly specific property: $\left(\dfrac{\mathtt{0000000219}_h+1}2\right)^2+\overline{\mathtt{fffffffef845}_h}+1$ is the square of an integer. Otherwise that method leads nowhere, and it is likely Fermat fails too.

Fermat factorization works on the given moduli because it is of the form $(2^{1024}+a)(2^{1024}+b)$ with $a$ and $b$ small integers, thus the product of two close integers. Fermat works for many 2049-bit integers not of this form, but still only a negligibly tiny fraction of 2049-bit integers.


Simple proof that shows AES is not a uniform permutation on any n-bit string? Is there a simple proof that shows AES is not a uniform permutation on any $n$-bit string?

Since I'm just starting with crypto, I'd like to see a simple yet elegant proof for the said property. Thanks!

There is no uniform permutation; there is a permutation uniformly chosen from the set of all possible permutations over $Z_2^{128}$.

It is evident that AES is not a uniformly chosen permutation, since its permutation is fixed for any key.

One can consider a family $\{AES_K\}$  of AES permutations under all possible keys $K$. Even if the key is chosen uniformly, the resulting permutation is not uniformly chosen, as not every permutation is an AES permutation with some key. This comes from a simple counting argument: there are $2^{128}$ 128-bit keys and thus $2^{128}$ AES-128 permutations, but the total number of bijections over $Z_2^{128}$ is
$$
(2^{128})! \approx \frac{2^{128\cdot  2^{128}}}{e^{2^{128}}} \approx 2^{2^{133.5}}.
$$


Can 2 bit commitment protocols be secure when sent together with the same bit Suppose I have 2 bit commitment schemes, C1 and C2 which are computationally hiding.Suppose I commit the same bit using both and send them to an adversary who knows that the same bit was committed. Is the scheme still computationally hiding, or are there counterexamples?

It is certainly safe for any commitment scheme we would want to use.  However, I believe that we can make a stronger statement; we can show that if there is such a method, then either C1 or C2 is not computationally hiding.

Suppose we have an oracle $\theta( C_1^x, C_2^y )$ that would take a commitment in C1 to the bit $x$ and a commitment in C2 to the bit $y$, and if those two commitments were to the same bit ($x=y$), it would output that common value; if they were to different bits, then the behavior is unspecified.

Then, suppose we were given a commitment $C_1^b$ in scheme C1 to a bit $b$.  When we could do is generate two commitments in C2, namely $C_2^0$ and $C_2^1$, and evaluate both $\theta(C_1^b, C_2^0)$ and $\theta(C_1^b, C_2^1)$.  Now, if $b=0$, we know that $\theta(C_1^b, C_2^0)$ must evaluate to zero (by the definition of the oracle); and so if the behavior of $\theta(C_1^b, C_2^1)$ was anything other than evaluating to one with high probability, we would be able to deduce that $b=0$.  Similarly, if $b=1$, then we see that $\theta(C_1^b, C_2^0)$ must evaluate to zero with high probability.

Hence, for C1 to be hiding, we must have $\theta(C_1^b, C_2^x) = x$ almost all the time.

This gives us a computationally efficient method to evaluate C2 commitments, that is, C2 is not hiding.


Meaning of the $m$ power of a modular world A cryptosystem is defined by a 5 tuple $(P,C,K,E,D)$=(plain text, cipher text, key, encryption function, decryption function)

So, my question is with the definition given for permutation cipher, which is stated
"If $m$ be a +ve integer, and let $P=C=(Z_{26})^m$ and let K consists of all the permutation of $\{1,\ldots,m\}$, for a key, $\pi$, we define:
$$e_π(x_1,\ldots,x_m)=(x_{π(1)},\ldots,x_{π(m)})$$
$$d_π(y_1,\ldots,y_m)=(y_{π(1)}^{-1},\ldots,y_{π(m)}^{-1})$$

What I don't understand is, what does $(Z_{26})^m$ mean?

The notation $(Z_{26})^m$ means the $m$-fold cartesian product of $Z_{26}$.  This is a set whose elements are all tuples of length $m$ with components in $Z_{26}$.  For example, $(Z_2)^2$ means the set of tuples (0,0), (0,1), (1,0), (1,1), where $Z_2$ alone is taken to mean the set of integers modulo 2, i.e. 0 or 1.  In this context, you can read $(Z_{26})^m$ as the set of strings that are $m$ English letters long.

(Beware: Sometimes $Z$ means the center of a group, not the integers, so I prefer to write the unambiguous $\mathbb Z$.  Sometimes $Z_p$ or $\mathbb Z_p$ means the $p$-adic integers, so I prefer to write $\mathbb Z/p\mathbb Z$ which is the unambiguous quotient of $\mathbb Z$ by the ideal $p\mathbb Z$, i.e. the integers modulo $p$.  But in this case context suggests that $Z_{26}$ means the set of integers modulo 26, corresponding to the English alphabet.)


Can gnupg master key decrypt something encrypted with subkey? When creating gpg subkeys, the master key signs and certifies that a subkey belongs to that master. That's ok, but, can master key decrypt something encrypted by a subkey? I guess no, but I want to be 100% sure. Am I right or I misunderstood?

No, the master private key cannot decrypt anything encrypted by a subordinate public key. Otherwise, it would mean that the master keypair is the same as the subordinate keypair.


What is Identity-Based Encryption (IBE) and why is it "better"? Most CS/Math undergrads run into the well-known RSA cryptosystem at some point.  But about 10 years ago Boneh and Franklin introduced a practical Identity-Based Encryption system (IBE) that has excited much of the research community and produced a huge flood of follow-up work.

What is IBE exactly and in what way does it improve over conventional public-key systems like RSA?

Conventional public-key cryptosystems require key distribution: in order to encrypt a message destined to Bob, you must know Bob's public key with enough certainty (an attacker could try to substitute his own key there). Various systems have been designed for that, e.g. certificates. In practice, key distribution proves complex.

With IBE, the name (email address) of Bob is his public key, so it is already distributed. To understand it, imagine the following model: there is a trusted central service, to which you send the email; the central service forwards it to Bob, and all communications are encrypted. This is how encrypted communications worked before the invention of RSA, so it is an old model. It has two drawbacks:

the central service must be trusted (it has the power to read all emails);
the central service must have oversized optic fibers and thousands of processors because every message goes through it.

IBE uses high-level mathematics to remove the second issue. With IBE, the "central service" must exist, but it needs not be "online"; its real-time action is replaced with a mathematical pairing.

Another, more mathematical way to say it, is that with IBE, a central authority has a key pair. The central authority can compute the private key corresponding to a given "public key", where public keys can be just any sequence of bits, e.g. email addresses. You cannot do that with RSA: RSA public keys have a strong internal mathematical structure. With IBE users key pairs, not so. The counterpart of that property is that the central authority public key must be involved in the encryption and decryption processes. In a full-fledged IBE system, users obtain their own private key from the central authority; afterwards, no need to talk to the central authority.

Voltage Security sells IBE-based products (Dan Boneh is one of the founders of that company). The practical point of IBE is to "avoid" certificates. See Voltages pages to get some descriptions of IBE; also, the Boneh-Franklin article is a good source of information. Details on the actual computation of Weil and Tate pairings are intricate; Ben Lynn's thesis is a good starting point.


What if the p and q used in keys generation of Pailler cryptosystem are composite? I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$.

Assuming that a keypair  is generated with $p$ and $q$ that are coprime and that $pq$ is coprime with $(p - 1)(q - 1)$, but either $p$ or $q$ is composite, I'm wondering what security issues afflict such a key.

For example I wonder if, when $p$ is prime but $q$ is composite (so that $q = xy$ with $x$ and $y$ primes), there exists multiple public keys that can encrypt/decrypt a message.

Moreover, I'm wondering how it impacts $g$ and $r$ selection, and if the encryption function is still additively homomorphic. For example, with proper primes, one can use $r$ calculation to prove the sender of an encrypted message his control over the private key without sending the encrypted value over the channel. But is this still true for any $r$ if $p$ or $q$ are not truly primes?

Finally, which kind of cryptographic attacks are excluded by proper prime selection?

For starters: Paillier and RSA are based on very similar assumptions, and both systems would be broken immediately by an algorithm to factor large composites. Additionally, knowing $\phi(n)$ or $\lambda(n)$ is quite essential to both systems, because the trapdoor for decryption is based on that.

As you can see, the relation to RSA is quite close, and thus the following topics on this site are very relevant:

RSA with probable primes
RSA with composite numbers

Now let's translate that to Paillier:

First off, in most cases if you use $q-1$ and $q$ is not prime, then the entire encryption/decryption will not work, because actually $\lambda(q)\neq p-1$ (with the Carmichael function $\lambda$). This means, that $D(E(x)) = x$ with the encryption $E$ and decryption $D$ is a primality test itself for both primes $p$ and $q$.

But let's assume, that you happen to find numbers $p$ and $q$ with $n = pq=abc$, where $a,b,c> 1$. In the key generation process you calculate $\lambda = lcm(p-1, q-1)$, which is just the Carmichael function for a proper $n=pq$. In order for the normal encryption/decryption to work, the following would have to hold: $lcm(p-1,q-1) = k \cdot lcm(\lambda(a),\lambda(b),\lambda(c))$ for some $k$, where actually $\lambda(n)=lcm(\lambda(a),\lambda(b),\lambda(c))$ is the real order of the multiplicative group (for any odd prime number $x: \lambda(x) = x-1$).

Now I suggest a closer look at Paillier's original paper, e.g. in section 3 the proof that $E_g(x,y)=g^xy^n \mod n^2$ is a bijection if  the order of $g$ is a multiple of $n$. This still holds, even if $n$ has actually more than two prime factors. Similarly, $S_n = \{u < n^2 | u = 1 \mod n\}$ is still a multiplicative subgroup regardless of the prime factors of $n$ and the function $L(u)$ is still well-defined.

Now, let's estimate what the "too large order" effects. Basically, this is similar to RSA, where you can calculate $d$ modulo $\phi(n)$ or modulo $\lambda(n)$: If you use the bigger group where the order is actually less, you get a different $d$ but it works just the same. This is the same in Paillier: $\lambda$ might be a larger number, but it will work regardless (assuming the previously stated assumption is met)

Considering your other questions: The choice of $g$ is not affected by a wrong $\lambda$, especially if using the simplified version with $g=n+1$. The role of $r$ is this: In the decryption you first exponentiate it by $\lambda$, and $r^{n\lambda} = 1$ for any $r$. This is also true, if we our $\lambda$ is a multiple of the real multiplicative group order. A possible problem could arise if $r$ is a zero divisor, but even with multiple large prime factors in $n$ this is negligible. (not sure about this one right now)

About the homomorphic property: Assuming the encryption/decryption still works, this property also still holds. There is no reason why it shouldn't.

And finally about the attacks: Well, this is the same as for RSA, where we still don't know any more efficient attack than just factoring the modulus. And what we know from RSA: With a bigger number of prime factors, some algorithms become faster, e.g. when they scale with the size of the smallest prime factor. Some algorithms scale with the length of the modulus. For some more information about that, I suggest reading the answers to the previously mentioned crypto-SE questions.

As a final note: Just because large prime numbers have a negligible chance of being composite, this doesn't mean you actually have to consider this as a possible weakness: There are plenty of methods of proving or disproving primality and you can get to arbitrary confidence levels (e.g. $1 - 2^{-80}$ is quite common), and they are sufficiently fast. Prime generation itself can be done with a negligible rate of error. And if you think of the Fermat test and Carmichael numbers right now: There are other methods without such curiosities.


Who's talking to who encryption - does this concept work? With all the NSA stuff in the news, I've been thinking about how to ensure the "who's talking to who" is just as private as the contents of the messages. I had an idea on the subject, about which I've got two questions: the first, does this concept work (i.e. meet its stated objectives); and if so, what services employ this technique.

The problem: how to ensure that the "who" is just as private as the "what" of communication

The idea:

There exists a voluntary network of nodes that all have public key
encryption systems, and published public keys.
The sender sends a message to the first intermediate node, encrypted with that
intermediate node's public key.
The first intermediate node decrypts the message, which contains the second intermediate node's address and a payload that's encrypted with the second intermediate node's public key. The first intermediate note sends the payload to the
second intermediate node.
The second intermediate node decrypts the message, which contains the
third intermediate node's address and a payload that's encrypted with
the third intermediate node's public key. The second intermediate
note sends the payload to the third intermediate node.
The third intermediate node decrypts the message, which contains the
final recipients node's address and a payload that's encrypted with
the final recipients's public key. The third intermediate note sends
the payload to the final recipient.
The final recipient decrypts the message.

Key points about this system:

the sender needs the public keys of all intermediate nodes (a published database would be needed of addresses and public keys)
I was originally thinking of this in respect of email, but it should work with any communication, e.g. snail mail, IP packets, etc
on a computer it should be fairly easy to automate the multiple layers of encryption
the number of nodes can be manually selected, or selected at random
the nodes themselves should be selected at random
the communication could contain multiple next-hop nodes with a priority order, in case nodes fail. The nodes could provide an acknowledgement message back to the node they received communication from
the messages could potentially be randomly padded to ensure that the reducing size of the message over time (as address headers are removed) does not give a clue to the communication direction
random communication could be added to the network to further confuse snoopers
to prove the source of the correspondence to the sender, the sender and recipient would  need to pre-agree a secret that the sender would include in the message. Alternatively, the entire system could be set up such that each node gives a unique secret to each other node encrypted using that node's public key. This would establish encrypted relationships by default, without the need for pre-agreeing, and wouldn't allow anyone to infer relationships from the establishment of the original secret

Challenges:

as the network scales, the database of addresses and public keys
becomes potentially too large
if the secret sharing mentioned in the
key points is employed, the number of secrets each node would need to
hold could get prohibitively large if the network gets large

Like @StephenTouset said

  You appear to be reinventing the concept of onion routing.

For a practical example, check the Tor Project (based on the Onion Routing program) which enables online anonymity and directs internet traffic through a worldwide network consisting of thousands of relays to conceal a user's location… which would cover most of what you need.

But there are other implementations out there too; most of them handling encrypted, anonymous data (voice, text, binary) transfers using random node allocations and bridging.

Besides that, it is worth diving into mixnets too.

For more, the anonymity bibliography might come handy as an orientation for further research.


Forgery Attack Against RSA Digital Signature I have been reading about attacks against RSA Digital Signature in a book

  The attacker chooses the signature first and then computes the
  message. As a consequence, he cannot control the semantics of the
  message x

why the attacker can't control the message??
Let's say that e=115 ,n=11021 and the attacker want to send the message 3
Can't he just search for a value x in the space n such that x^e=3??

And what if Oscar send to Alice his public key instead of bob's   ?? How dose the RSA Digital Signature protect against such an attack??

why the attacker can't control the message??

Well, if he could control the message, that is, given the value $x^e \bmod N$, find $x$, well, he just solved the RSA problem, and we believe that he can't do that, or at least, he can't do that in any modulus that we expect is secure.  Yes, you can do a brute force search over a $N$ as small as 11021; that indicates that such an $N$ is too small to be used for RSA.

  And what if Oscar send to Alice his public key instead of bob's ?? How does the RSA Digital Signature protect against such an attack??

If Oscar sends his public key to Alice, and Alice does accept it as Bob's key, then yes, Oscar will be able to sign any message, and Alice will mistakenly believe it came from Bob (because it was signed using what she thought was Bob's key).

How does RSA protect against this?  Answer: it doesn't; that's a problem that RSA assumes that is protected against by some higher level protocol.

The issue is "how do we bind a public key, which is a bunch of bits, to an identity in way that we can trust".  There are a number of ways to address this.

One such way (which is fairly common in practice) are certificates; we have a message that states "Bob's key is [public key], as attested by Trent", and that message is signed by Trent.  If Alice trusts Trent, then Bob (or Oscar) could send that certificate to Alice, and she can validate what the certificate says (because she trusts Trent).  Oscar cannot generate a certificate with his key and Bob's identity, because Trent will not issue such a certificate (and Oscar can't fake Trent's signature on something he can generate).

There are other ways of solving this as well; that you solve it is obviously crucial.


Why does CBC-MAC need prefix-free inputs to be a good PRF? In the FFX spec, there is a note about using CBC-MAC as the round function.

  Security notes. The round function F is constructed in such a way that the set of inputs on
  which the CBC-MAC is invoked is preﬁx-free. (A set of strings is preﬁx-free if for any distinct x, y
  in the set, x is not a preﬁx of y.) The CBC-MAC is known to be a good PRF when it is invoked
  on a set of preﬁx-free inputs, assuming AES is a good PRP [23].

Why is it important that the input be prefix-free? The citation is for Erez Petrank and Charles Rackoff, ‘CBC MAC for Real-Time Data Sources’, Journal of Cryptology 13(3), 2000, pp. 315–338 (paywall-free, tech report, preprint).

Because CBC-MAC with inputs that are not prefix free is weak against existential forgery, meaning it is not a "secure" MAC.  More precisely, CBC-MAC is easily distinguishable from a random function (i.e. not a PRF) when the input domain is not prefix-free.  This is because an adversary can request the CBC-MAC of messages $M_0$ and $M_1$, and then xor the MAC for $M_0$ with the first block of $M_1$, and thereby trivially construct another message, $M_2$ (such that $M_2 = M_0||\overline{M_1}$, where $\overline{M_1}$ is $M_1$ with the first block altered).  $M_2$ will have the same MAC as $M_1$, which is a collision that should be very hard to find for a PRF.  Note that $M_0$ is a prefix of $M_2$.

CBC-MAC can be made secure by either i) only using it for fixed-length messages (because no message of length $l$ can be a prefix of any other message of length $l$), or ii) always prepending $L_m$, the length of the message, to the message and using CBC-MAC on the string $L_m || M$.


Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5? I've studied that the Bleichenbacher's CCA attack on PKCS#1 v1.5. is a base to many versions of attacks in the area.

I'm trying to understand that attack, but every explanation I saw starts with the technical details, without giving some overview, so it's hard to follow...

Can you explain it in a simple words before giving the little details?

When encrypting something with RSA, using PKCS#1 v1.5, the data that is to be encrypted is first padded, then the padded value is converted into an integer, and the RSA modular exponentiation (with the public exponent) is applied. Upon decryption, the modular exponentiation (with the private exponent) is applied, and then the padding is removed. The core of Bleichenbacher's attack relies on an oracle: the attack works if there is some system, somewhere, which can tell, given a sequence of bytes of the length of an encrypted message, whether decryption would yield something which has the proper padding format or not.

An example would be a SSL/TLS server. In the initial handshake, at some point, the client is supposed to generate a random key (the "pre-master secret"), encrypt it with the server's public key, and send it. The server decrypts the value, obtains the pre-master secret, and then compute from that pre-master secret the keys used for symmetric encryption of the rest of the connection. Using the standard for guidance, the client sends a ClientKeyExchange (which contains the encrypted pre-master secret), then a ChangeCipherSpec, then Finished; this last message is encrypted with the derived symmetric key and its contents are verified by the server.

If the client sends a random sequence of bytes of the right length to the server instead of a properly encrypted pre-master secret, then the server will, most of the time, respond with an error message telling "I tried to decrypt your ClientKeyExchange contents, but this failed, there was not a proper padding in it". However, by pure chance, it may happen that the random string, after applying the modular exponentiation, yields something which really looks like a pre-master secret with correct padding. In that case, the server will not complain about the ClientKeyExchange, but about the Finished message, which will be incorrectly encrypted.

This is the information the attacker wants: whether the sequence of bytes he sent would, upon decryption, look properly padded or not.

Let's see with a bit more technical details. In RSA, let $n$ be the public modulus. Let $M$ be a message to encrypt with $n$ (in the case of SSL, $M$ is the pre-master secret, of length 48 bytes). The PKCS#1 v1.5 padding, for encryption, consists in adding some bytes to the left, so that the total length after padding is equal to that of $n$. For instance, if the server's public key is a 2048-bit RSA key, then $n$ has length 256 bytes, so the padded $M$ should also have length 256 bytes.

A properly padded message $M$ has the following format:

0x00 0x02 [some non-zero bytes] 0x00 [here goes M]

so the sequence of bytes will begin with a byte of value 0, then a byte of value 2, then some bytes which should have random values (but not zero), then a byte of value 0, then $M$ itself. The number of non-zero bytes is adjusted so that the total length is equal to the length of $n$. Upon decryption, the server will look at the first two bytes, and require them to be equal to 0x00 and 0x02, in that order. Then it will scan for the next byte of value 0, thus skipping over all the random non-zero bytes. This way, the padding can be unambiguously removed.

It follows that if the client sends a random string of bytes, then it has probability roughly between $2^{-15}$ and $2^{-17}$ to follow the PKCS#1 padding format (that's the probability that the first two bytes are 0x00 0x02, and that there is at least one byte of value 0 afterwards; exact probability depends on the length and value of $n$).

The attack scenario is the following:

There is a SSL server, which will send distinct error messages depending on whether a proper PKCS#1 padding was found or not. Alternatively, the two cases could be distinguished through some other information leak (e.g. the server takes longer to respond if the padding was correct).
The attacker eavesdropped on a connection, and would like to decrypt it. He observed the ClientKeyExchange, so he saw an encrypted message $c$. He knows that $c = m^e \pmod n$ where $e$ is the public exponent, and $m$ is the padded pre-master secret for that connection. He wants to recover $m$, or at least the pre-master secret which is contained in $m$, because that will allow him to compute the symmetric keys used for the connection.

Then the attacker will initiate many connections to the server. For each connection, the attacker generates a value $s$ and sends, as ClientKeyExchange, a value $c' = cs^e \pmod n$. The server decrypts that, and obtains $m' = (cs^e)^d \pmod n$ ($d$ is the private exponent), which is equal to $ms \pmod n$. Most of the time, this $ms$ value will not be properly padded (it will not begin with 0x00 0x02 or will not contain an extra 0x00). However, with a low but non-negligible probability (once every 30000 to 130000 attempts, roughly), luck will have it that the $ms \pmod n$ value looks padded. If that is the case, then the server's behaviour will inform the attacker of that fact. The attacker then learns that, for this value $s$ (the attacker knows it, since he chose it), then $ms \pmod n$ is in a specific range (the range of integers which begin with 0x00 0x02 when encoded in bytes using big-endian convention).

The rest of the attack is trying again, with carefully chosen random values $s$. Each time the server responds with "that was a proper PKCS#1 padding", this gives some information which helps the attacker narrow his guesses on $m$. After a few million connections in all, the attacker learned enough to pinpoint the exact $m$, yielding the pre-master secret.

See the original article for details; once you know how the RSA padding works, the rest is just maths, which are not too hard.

To prevent this attack, SSL servers do not inform the client about padding woes. If decryption fails because of a bad padding, then the server continues with a random pre-master secret (the true failure will then occur when processing the Finished message).

One may note that the specific weakness of the PKCS#1 v1.5 padding (for encryption) is that it is not very redundant; the random bytes are, indeed, random, without any specifically enforced value. This is what allows a sequence of random bytes to be "properly padded" with a small but not negligible probability. Newer versions of PKCS#1 describe a new padding type, called OAEP, which uses hash function to add a lot of internal redundancy, which makes it extremely improbable that a random string matches the padding format. This prevents Bleichenbacher's attack. Unfortunately, SSL still uses PKCS#1 v1.5.


Is OCB with short MAC malleable? At the beginning of OCB's white paper [pdf], OCB is compared to other modes, and non-malleability is one of the properties advertised.

At the end of the paper, it is mentioned the MAC length can be chosen by users according to their needs.

Was long MACs assumed in the claim of non-malleability, or is the property still holding with short/no MACs ?

The answer to your question is contained in the Authenticity bound (Theorem 5.1).  This is because Authenticity implies non-malleability (see e.g. http://eprint.iacr.org/2011/092.pdf).  Note that only one term in the bound refers to the length of the tag (referred to by the variable $\tau$):

$$\mathbf{Adv}_{OCB}^{auth}[\mathrm{Perm}(n), \tau] (A) \leq \dfrac{1.5\overline{\sigma}^2}{2^n}+\dfrac{1}{2^{\tau}},$$

where $\overline{\sigma} = \sigma + 2q + 5c + 11$, such that $q$ is the number of chosen plaintext queries of aggregate length $\sigma$ blocks, and $c$ is the total length in blocks of the attempted forgery.

As you can see, the length of the tag only matters for the last term.  So if the tag is 128 bits then the last term adds $\frac{1}{2^{128}}$ to the total Adversarial advantage.  But if the tag is truncated to only 32 bits then the advantage will increase by $\frac{1}{2^{32}}$, which is about 1 in 4 billion.  Depending on your risk tolerance and threat model, the latter increase in Adversarial advantage might be acceptably small in exchange for the space savings of shorter tags.


BGW Multiplication: How does it work? I could not understand how multiplication is carried out in the BGW protocol for 3 parties. Reference: https://crypto.stanford.edu/pbc/notes/crypto/bgw.html

I've understood that in multiplication, we calculate r(x) = p(x)q(x) but this means that r(x) is a polynomial of degree 2t. How is this polynomial redistributed in the circuit to get an O(n^2) complexity in multiplication over BGW protocol?

Note that p(x) and q(x) are both polynomials of degree t and as I am taking the case of semi-honest adversaries, t < n/2.

We can use the notation of the source document, except I will say we are trying to compute $ab = c$ (for $a,b,c\in\mathbb{F}_p$), so I can use $x$ as a variable when discussing polynomials.

Let $a_1,\dots, a_n$ and $b_1,\dots, b_n$ be $t$-out-of-$n$ secret sharings of $a, b$.
Recall this means that they're computed by taking random $t$-degree polynomials:
$$A(x) = \sum_{i = 0}^t \alpha_i x^i,\quad B(x) = \sum_{i = 0}^t\beta_i x^i$$
Where $A(0) = a, B(0) = b$ (so random subject to this condition).
The shares are then created by evaluating the polynomials on the points $\{1,2,\dots,n\}$.
In particular:
$$\forall i \in\{1,\dots,n\} : a_i = A(i),\quad b_i = B(i)$$
Now we want to compute the product.
The polynomial $C(x) = A(x)B(x)$ has the right constant term (as $C(0) = A(0)B(0) = ab$), but is too high of degree (as you mention).
Moreover the "shares" of $C(i)$ can be computed locally, as $C(i) = A(i)B(i) = a_ib_i$.

But $C(x)$ is degree $2t$ (as you mention). We want to find some other polynomial $\mathcal{C}(x)$ such that:

$\mathcal{C}(0) = C(0) = ab$
$\mathcal{C}(x)$ is degree $t$
Computing $\mathcal{C}(i)$ isn't "too expensive" (in communication) if you already know $A(i)$ and $B(i)$

What will we do then? The idea is to utilize that there are two different ways of representing degree $t$ polynomials:

Through their $t+1$ coefficients (this is the "obvious") way
Through the evaulation of them on (at least) $t+1$ distinct points

Either of these is enough information to uniquely reconstruct the polynomial.
The surprising thing is that you can convert from one to the other using a linear operation.

To see how we might establish this, recall that for an $n\times n$ matrix $D$ and vector $\vec{v} = (v_1,\dots, v_n)$, we have that:
$$(D\vec{v})_i = \sum_{k = 0}^{n-1}D_{i, k} v_k
$$

Note that this is similar to the expression:
$$A(x) = \sum_{i = 0}^t \alpha_i x^i$$
If we fix evaluation points $\{1,\dots, n\}$, then we have in fact that:
$$A(i) = \sum_{k = 0}^t \alpha_k i^k$$
This suggests setting $D_{i, k} = i^k$ and $v_k = \alpha_k$.
This is precisely what we'll do, by defining the Vandermonde matrix (with respect to the aforementioned evaluation points):
$$V = \begin{pmatrix}
1^0 & 1^1 & \dots & 1^{n-1}\\
2^0 & 2^1 & \dots & 2^{n-1} \\
\vdots && \ddots & \vdots\\
n^0 & n^1 & \dots & n^{n-1}
\end{pmatrix}$$
Note that:
$$V\begin{pmatrix}\alpha_0\\\vdots\\\alpha_{n-1}\end{pmatrix}
=\begin{pmatrix}
\sum_{k = 0}^{n-1} \alpha_i 1^i\\
\sum_{k = 0}^{n-1} \alpha_i 2^i\\
\vdots\\
\sum_{k = 0}^{n-1} \alpha_i n^i\\
\end{pmatrix} = \begin{pmatrix}A(1)\\
A(2)\\
\vdots\\
A(n)
\end{pmatrix} = \begin{pmatrix}a_1\\
a_2\\
\vdots\\
a_n
\end{pmatrix}
$$
So the Vandermonde Matrix precisely maps the "coefficient representation" of a polynomial to its "evaluation representation".
This ends up being extremely closely related to the Fourier transform. The Discrete Fourier Transform can be written as a Vandermonde Matrix, and the Fast Fourier Transform can be explained that it's Vandermonde Matrix is Toeplitz (and in fact circulant), so admits especially efficient representations and matrix/vector multiplications, but this is an ahistorical aside.

So, we have an (invertible) matrix that maps an $n$-dimensional "coefficient vector" representation of a polynomial to an $n$-dimensional "evaluation vector" representation of a polynomial.
For the moment, don't worry about how all of the people move around all the shares --- just make sure you understand how to do the computation.

We start with the "evaluation vector" representation $C(i) = A(i)B(i)$ for $i\in\{1,\dots,n\}$, which we can write as $\vec c = (c_1,\dots, c_n)$.
We convert this to the "coefficient vector" representation via $V^{-1}\vec{c}$.
This gives the coefficients of the polynomial $C(x) = A(x)B(x)$ as a vector.
While there are $n$ coefficients, as discussed before this polynomial (uniquely determined from $\vec{c}$) is of degree $2t$, so the higher-order coefficients are 0.

We can convert this to a degree $t$ polynomial via truncation.
Let:
$$P = \begin{pmatrix} I_{t+1} & 0\\
0 & 0\end{pmatrix}$$
Be an $n\times n$ block matrix, where $I_{t+1}$ is the $(t+1)\times (t+1)$ identity matrix.
Then $PV^{-1}\vec{c}$ will "drop" higher order coefficients, leaving a degree $t$ polynomial.
Importantly, it doesn't touch the constant term (so $\mathcal{C}(0) = C(0) = ab$ is preserved).

All that's left is to convert back to shares, so to convert from the "coefficient representation" to the "evaluation representation", again by using $V$.
Thus $VPV^{-1}\vec{c}$ will output the shares (of a degree $t$ polynomial) that you want.
Moreover, $VPV^{-1}$ can be precomputed by all participants in the protocol (it's just some $n\times n$ matrix. I could probably even write it out here, but won't).

This reduces the problem of multiplying shares to the problem of "computing a linear equation" of shares, which your source also discusses (at this link).
As this is getting long I'll leave the answer here, but if you don't understand the linear case I encourage you to ask a new question about it.


SHA-256 security for initial 32 bits I have concerns regarding truncated SHA-256 hashes in an application I am building at the moment:

Nomenclature

secret - the full 256-bit SHA-256 result of hashing 16 random bytes
public - a unique identifier for an object.
hash - the output of SHA-256(secret || - || public)
prefix - the first 8 characters (32-bit) of hex encoded hash.

Scenario

secret is generated once and remains constant throughout the lifecycle of the scenario.It is not known to the attacker

Identifiers for all objects (publics) are known to the attacker.

prefix will be the base for further computation and information retrieval for a given object.
The first 4 bytes (32 bit) of hash have to be sufficient for that.

It is important that a potential attacker cannot generate a valid prefix for a given public.

Concerns

The attacker's utopia is to find secret so they can generate a valid hash for every object.
This is unrealistic to brute force (computation would take forever).

However, because only the first 32 bit of hash matter, is there a mechanic / cryptographic attribute, that makes it feasible for the attacker to guess / compute a valid secret that would allow them to generate prefix values for given publics?

Example

secret = 'af8b81c94d68...' (256-bit)
public = '123456'
hash = 'fe13c815ab44...' (256-bit)
prefix = hash[0...8] = 'fe13c815'

Can the attacker guess secret such that they would end up with a valid prefix?

Can the attacker use that guessed, validated secret and compute prefix values for different publics?

Can the attacker guess secret such that they would end up with a valid prefix?
Can the attacker use that guessed, validated secret and compute prefix values for different publics?

You don't need a collision attack here. You need the pre-image attack that given a hash value $h$ one needs to find an $x$ such that $h = \operatorname{SHA-256}(x)$. Note that the attacker doesn't need to find the original value, any value that has the required has value will be a success for the pre-image attack and there can be more than one value or none in the range $[0..2^{256}]$. We expect that some will have none due to the collisions.
The 16 bytes hex string makes 128-bit and that is beyond the search for anyone. Therefore looking for the original value will be beyond any attacker since there is no known successful pre-image attack better than searching for SHA-256.
Since you trimmed the result, the pre-image resistance now requires around the 32-bit search to find one. The attacker will look for a candidate secret so that
$$\operatorname{SHA-256}(\operatorname{SHA-256}(\text{candidate secret}) \mathbin\|\text{-} \mathbin\| \text{public})$$ will produce valid output.
Once a successful candidate is found, unlikely to be the original since it was the output of SHA-256, the system will accept this a valid input. The attacker only needs to look for the first 32-bit of a 224-bit where they can set the rest bits to zero.
$$\text{candidate secret} = \overbrace{\texttt{0x00000000 to 0xFFFFFFFF}}^{32 \;bits}\;\overbrace{\texttt{0x00000...0}}^{224 \;bits}$$
That search is quite double if you consider some of the top machines

Summit can reach $\approx 2^{63}$ SHA-1 hashes around one hour, $\approx 2^{72}$ hashes in one year.
Titan can reach $\approx 2^{63}$ SHA-1 hashes around two hours, $\approx 2^{71}$ hashes in one year.
Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019.

The advice: keep the result at least 16 bytes if you don't fear a possible future quantum attack. Otherwise one needs to double size for Grover's attack and triple size for Brassard et.al's attack. Of course, it is not clear how one can prepare the sequential evaluation without a magnificent delay that can cause an invisibility.


How do ZK-STARKs, ZK-SNARKs, and Bulletproofs compare in size and speed for range proofs? How do ZK-STARKs, ZK-SNARKs and Bulletproofs compare in size and speed for range proofs? The general behavior is depicted in this chart. But do those numbers scale linearly to the proof and verification times listed on dalek-cryptography's bulletproofs page, that has a 64-bit range proof taking 7.3ms and verification taking 1ms?  That is, would generating and verifying a ZK-STARK of a 64-bit range proof take microseconds?

The paper in this address provides some more precise evaluations of various ZK proof techniques, including zk-STARKs, zk-SNARKs and Bullet proofs.

The have evaluation for a proof of membership for a Merkle tree with different number of leaves.


What changed in PKCS#1 v2.2, and why? PKCS#1 is one of the most used (de-facto) standard for real-world use of RSA.

That's for good reasons: PKCS#1 is well thought, versatile, understandable, has been relatively stable for over two decades, and remains practically secure in its original form, contrary to some other standardized uses¹ of RSA. The major upgrade to PKCS#1, from v1 to v2, circa 1998, introduced OAEP encryption with stronger security argument, and improved protection against timing and padding oracle attacks of a decryption device. V2.1 introduced PSS signature and multi-prime RSA.

PKCS#1² was updated from v2.1³ to v2.2⁴ in October 2012, and published by February 2013. Changes include:

incorporation of erratas (last updated in 2005) to PKCS#1 v2.1 (last updated in 2002);
additional hashes of the SHA-2 family, including SHA-512/256, SHA-224, and SHA-512/224;
corresponding algorithm identifiers;
corresponding test hex constants;
availability only in PDF format with permission to copy disabled (but who automatically compares to test hex constants anyway?);
updated legalese on the text (which remains worthless if taken literally, as it is of the form "permission to copy is granted if" followed by a condition that is false independently of what the copier does);
in the ASN Module:

PKCS-1 was changed to PKCS-1v2-2 and pkcs-1(1) was changed to pkcs-1v2-2(2);
in the IMPORTS (..) FROM NIST-SHA2 section, modules(0) sha2(1) was changed to hashAlgs(2).

What's the meaning, purposes and consequences of these changes in the ASN Module?

Are there any other technical changes? Is yes, which, and what's their meaning, purposes and consequences?

¹ The ISO/IEC 9796[-1] signature scheme was withdrawn for lack of security under chosen-message attack. The first scheme in ISO/IEC 9796-2 lives with a mild weakness under such condition. That's fixed with scheme 2, which is essentially  PSS-R, and scheme 3 which is a variant functionally substitutable to the broken scheme 1.

² Archive page of the website for RSA Laboratories.

³ Copy as published by RSA Security Inc. Public-Key Cryptography Standards.

⁴ Copy as published by EMC Corporation Public-Key Cryptography Standards.

It's merely an update to align the hashing algorithms. There are in fact no real "consequences" which might have any negative impact as the v2.1 schemes are still supported. The positive impact is the alignment with FIPS 180-4.
To quote the revision history at page 59 of "PKCS #1 v2.2: RSA Cryptography Standard":

Version 2.2 updates the list of allowed hashing algorithms to align them with FIPS 180-4, therefore adding SHA-224, SHA-512/224 and SHA-512/256.
The following substantive changes were made:
— Object identifiers for sha224WithRSAEncryption, sha512-224WithRSAEncryption and sha512-256WithRSAEncryption were added.
This version continues to support the schemes in version 2.1


FEAL-4 Linear Cryptanalysis - Prevention currently, I prepare for an exam about cryptanalysis. In class, we talked about linear cryptanalysis for FEAL-4. We constructed four linear equations, extended them to equations for three rounds and then applied a Brut Force search in order to find the keys of every round.

My question is as follows: How can I prevent such an attack?

My idea: I think, it is necessary to replace the S-Boxes of FEAL with 'better' S-Boxes? Such that, it is not possible to find relationships between input and output bits of the S-boxes (and therefore, also for the whole F-Function). But how does such an 'good' S-Box look like?

By convention:

LC = Linear Cryptanalysis
DC = Differential Cryptanalysis

There are multiple ways to increase the security of a block cipher.

The first one (and usually applied) is to increase the number of rounds. In the case of FEAL, they switched from 4 to 8 rounds and then to X rounds. Therefore you would have to extend the equations for 7+ rounds before starting your brute force attack (see table below from Handbook of applied Crypto, note that the time indicated is not correct anymore due to the book being written in 1996...)

+---------------+------------------------+----------------+-----------------+
|               |                        |                |                 |
|  Attack       |    Data complexity     |   storage      |  procesing      |
|  Method       |                        | complexity     |  complexity     |
|               | known   |  chosen      |                |                 |
+---------------------------------------------------------------------------+
|   FEAL-4-LC   |   5     |              |    30K bytes   |   6 minutes     |
|   FEAL-6-LC   |  100    |              |   100K bytes   |  40 minutes     |
|   FEAL-8-LC   |  2^24   |              |                |  10 minutes     |
|   FEAL-8-DC   |         | 2^7  pairs   |  280K bytes    |   2 minutes     |
|   FEAL-16-DC  |         | 2^29 pairs   |                | 2^30 operations |
|   FEAL-24-DC  |         | 2^45 pairs   |                | 2^46 operations |
|   FEAL-32-DC  |         | 2^66 pairs   |                | 2^67 operations |
+---------------+---------+--------------+----------------+-----------------+

In the case of Linear cryptanalysis, the linear equations/approximations used to break the cipher holds with a certain probability. You just have to make sure that this probability stays low.

It has been shown by Joan Daemen and Vincent Rijmen in The Design of Rijndael: AES, chapter 7 that LC and DC share similarities by the Walsh-Hadamard transform. Increasing the DC resistance of an algorithm also increases the LC resistance.

The idea is therefore to find a good S-box, you need to prove that the Differentials don't go over a certain probability (the lower the better). In the case of Rinjdael (AES), they use a $8$ bit S-box. Therefore the table of the differentials has $2^8 = 256$ rows and columns. By analyzing such table, they made sure that no differential probabilities goes over $\frac{4}{256}$.

The bigger the S-box, the harder the differentials will be to exploit. However, it is also required from the designer to prove the security of his algorithm. So increasing the size of the S-box also make the proof harder. This is the reason why the $\chi$ function of keccak is similar to a 5 bit s-box.

Smaller S-box implies higher probabilities right ? Therefore, we add a diffusion layer. The goal is to propagate the differences and make them harder to track. There you have two kind of strategies: weak alignment or strong alignment... But that is getting too far.

I would suggest to have a look at this presentation Two ways of building round functions for block ciphers by J. Daemen.


Encrypted hash vs hashed encryption Problem

Is there any combination of hash and encryption algorithms with show the following properties:

File $\rightarrow$ Hash $\rightarrow$ Encrypt $==$ Hash $\leftarrow$ Encrypt $\leftarrow$ File

So a combination of hashing and encryption which can be applied in arbitrary order so that it leads to the same result.

Use case

I want to add optional encryption to an existing file synchronisation service. Currently only trusted nodes exist, which store data unencrypted. They use the file hash as an identifier.

My idea is, to add untrusted nodes which store the data encrypted. Only the trusted nodes have the key.

In order to detect changes, hash values are compared. Since the data only exists in encrypted form on untrusted clients, they can only compute the hash of encrypted files. On trusted clients, data exists unencrypted and has a hash of the unencrypted version stored along. Now it would be far easier to just encrypt the hash on the fly instead of encrypting the whole file and computing the hash of it.

Don't overlook the extension in my edit!

Edit (2019-03-26)

I noticed that I should clarify some things about the use case:

Two equal files do not exist in our application since they are deduplicated!
We split files into equally sized blocks. So in this example all files have the same length!
There are multiple nodes. For simplicity let's look at the case where we have 2 trusted ($N_{t1}$, $N_{t2}$) and 1 untrusted node ($N_u$). They are all in sync at an arbitrary point in time. Now node $N_{t1}$ creates a new file, encrypts it and synchronizes it with $N_u$. Now $N_{t2}$ comes back online and wants to determine which files have changed.

Further, I want to respond to Ilmari Karonen's answer (also too long for a comment):

  The case $m_1 = m_2$ does not exist (see my clarification above).

  We use relatively small blocks (128KB). So plaintext-guessing-attacks are an issue?

  I thought about something like your first scheme already (please correct me if there is a structural difference):
  I could just store the hash of the unencrypted file (which is our current file identifier) $H(m)$ together with the encrypted file $E_K(m)$. This would allow offline key-guessing attacks though:
  1. Try to decrypt the ciphertext $E_K(m)$ with different keys $K_i$:
     $E^{-1}_{K_i}(E_K(m)))=m_i$
  2. Hash the result $H(m_i)$
  3. Check if this is equal to the stored hash $H(m_i)\stackrel{?}{=}H(m)$
     If so, we found the plaintext :/
  When the used keys are long enough, this shouldn't be a problem. But with increasing computing power, it is only a question of time until this can be cracked.

  Is your third scheme different from what I try to avoid (see use case): In order to calculate $H_K(m)$, I need to encrypt and hash the plaintext ($H(E_K(m))$). This needs a lot of computational power for big directories. Alternatively, I could compute it once and save it. This would decrease data efficiency significantly. Nevertheless, if it is considered secure, I guess it is the best we have since I don't want to compromise on security.

  Your second scheme seems interesting, although I didn't understand it completely yet (I will have to check the links you posted). Do you think this scheme is more promising with the clarified use case than the third scheme?

What you want does not exists with any secure encryption scheme and collision resistant hash function.

Any encryption scheme that is at least CPA secure¹ cannot be deterministic. Therefore not only can the equality you ask for not hold, it's even true that for $c_1 = \mathsf{Enc}(k,H(m))$ and $c_2 = \mathsf{Enc}(k,H(m))$, it holds with overwhelming probability that
$c_1\neq c_2$. similarly, $h_1\neq h_2$ with overwhelming probability for $h_1 = H(\mathsf{Enc}(k,m))$ and $h_2 = H(\mathsf{Enc}(k,m))$, since the encryption scheme is secure and the hash function is collision resistant.

Furthermore, due to a secure encryption scheme being probabilistic, ist must also be expanding. I.e., for $c = \mathsf{Enc}(k,m)$ it holds that $|c|>|m|$.

Since a hash function compresses inputs to a fixed length, it must therefore hold that $$|\mathsf{Enc}(k,H(m))| > |H(\mathsf{Enc}(k,m))|$$
and thus by extension necessarily that
$$\mathsf{Enc}(k,H(m))\neq H(\mathsf{Enc}(k,m))$$
even if you would try to somehow correlate the randomness used in the two encryptions.

¹This is the absolute bare minimum of what we consider a secure encryption scheme in most cases. As Maarten points out in the comments there are some narrowly defined use-cases in which weaker notions of security may be acceptable.


Possibility of Man-in-the-Middle on X3DH I'm reading about the security of the Signal protocol (used in WhatsApp) and in particular, the X3DH part used to establish authentication, all papers seem to gloss over Man in the Middle attacks.  Is it possible or not to MitM between users and the server?  Seems easy on the server.

This is "covered" by section 4.1 of the X3DH spec:

  Before or after an X3DH key agreement, the parties may compare their identity public keys $IK_A$ and $IK_B$ through some authenticated channel. For example, they may compare public key fingerprints manually, or by scanning a QR code. Methods for doing this are outside the scope of this document.

Signal and WhatsApp both support verifying identities through QR codes, and provide a warning (optional in WhatsApp) if the other party's identity public key changes. That would stop MITM attacks, or make them detectable, though in practice almost no one does the verification.

Also note that the connection between the app and server is TLS-protected, so any MITM attack would need to be carried out by compromising the server itself.


How are initialization vectors used in TLS 1.1? From my understanding, TLS 1.0 can use CBC to encrypt data. To do so, it creates one initialization vector (IV), and then uses the previous ciphertext block as the IV for the next record. I made this diagram to depict my understanding about TLS 1.0:

In the diagram above, the red arrow opens up TLS 1.0 to the BEAST attack. As of TLS 1.1, this seems to be fixed by creating explicit IVs:

  [CBCATT] describes a chosen plaintext attack on TLS that depends on
  knowing the IV for a record.  Previous versions of TLS [TLS1.0] used
  the CBC residue of the previous record as the IV and therefore enabled
  this attack. This version uses an explicit IV in order to protect
  against this attack.

  - RFC 4346

My question is: When and where exactly are these explicit IVs created? Are they created for each message like so (both messages are still being sent within the same stream like above)?:

Or do we now have explicit IVs for each record?:

... or is it neither of these?

I'm relatively unexperienced with all this so please forgive me if this is a silly question.

You might be somewhat confused by the term 'record'.

In TLS, a data to be encrypted is divided into a series of fragments; each fragment is encrypted as a record, with each record being encrypted and integrity protected independently [1].  Such a record can hold up to 16kbytes of data. This 'record' is standard TLS terminology and is what you are referring to as a 'message'.  If you use a block cipher, then the amount of data that is processed by that block cipher at a time is referred to as a 'block' (not a 'record'), and in TLS, we generally don't talk about it that much, as there is generally little need to deal with the lower levels of how the crypto is done.

In TLS, each record is encrypted separately.  If you use TLS 1.1 and CBC mode, when you encrypt a record, you pick an unpredictable IV, and then use that IV to CBC-mode encrypt all the data (and the HMAC of the data).  You use CBC-mode in the standard way, and so CBC mode uses the IV the encrypt the first block (16 bytes for AES), and then uses resulting initial 16 bytes of ciphertext to encrypt the second block, and so on.  It's just like TLS 1.0 CBC mode, except instead of using the previous ciphertext as the next IV, you use the value that appears immediately before the ciphertext.  Hence, your first diagram is more accurate.

[1]: In addition, TLS sometimes sends messages between the encryptor and decryptor, to do the original negotiation, or to do rekeys.  This data is also sent within records.


How secure is encrypting with self-hash I don't have much knowledge about cryptography beyond using libraries for it. So just wanted to understand if the following two cases differ sufficiently in security or is it just psychological:

Say I have a plain text T and I use the following scheme to encrypt:

Take SHA512(T) = H(T)
Use any good symmetric encryption scheme to encrypt T with H(T).
Result cipher text = C
Keep H(T) safely secret.

How secure is cipher text C in the wild now ? (I can do (1) a few times if it adds anything - so instead of H(T) use H(H(H(T))) etc. - you get the idea).

How would this compare with using an encryption key unrelated to T ? Since H(T) shouldn't be reversible how much more does an unrelated key  add to the security ?

These scheme doesn't really make sense in its current form:

The key depends on the message. That means, it can not be chosen before the message is chosen. And it is't independent of other parts.
How does the recipient receive that key? Or does he learn that from a separate communication channel, after the message (and thus the key) has been chosen? In that case: Why was not the message transmitted instead of the key?

A usual statement is "the key is drawn at random" - and implicitly you can add there " statistically independent from anything else". The reason for this is simple: If a value is calculated based on some other value, then it can be quite difficult to prove that this calculated value does not reveal anything about the original one. Therefore, we just chose a new random value without any dependencies on anything else.

Then, the security of cryptsystems is mostly analyzed with the assumption of a random key. Based on that assumption, statements about security can only be applied if the assumption holds. Having a message-dependent key is far from being random, especially with a deterministic function like a common hash function: If you assume that there are only a very limited amount of possible messages, then there are only a limited amount of possible keys. This makes the assumption invalid. So even if the scheme was known to be secure for random keys, this might not be secure at all.

  How would this compare with using an encryption key unrelated to T ? Since H(T) shouldn't be reversible how much more does an unrelated key add to the security ?

Well, no security statement can't be made about your scheme in general. You did not describe what kind of messages you have, how easy they are to guess or just in general, how much entropy you actually got. At worst, this could be completely insecure (example: there are only messages "yes" and "no", everyone can just go through the "encryption" and detect which ciphertext matches which plaintext). At best, you are lucky that the attacker didn't guess your plaintext.

So what is the advantage from a random key? It is huge, because you actually get something where security has been analyzed by lots of people over many years. In cryptography, it is really easy to get things wrong and not even notice it. Also, there is usually no leeway in the definitions unless explicltly stated. If something requires a uniform random key, then both parts are necessary - if you use a key which isn't random (including independence of other things) or isn't chosen uniformly, none of the previous security analysis might apply any more.


Implementation of modular arithmetic? In FIPS 186-3 appendix D.2 "implementation of Modular Arithmetic", they show shortcuts for solving
$$B = A \mod m$$

for select Curves.

How would you go about determining a valid short cuts for the various curves?
If I wanted to practice on using a small finite field (e.g. 23, 31) because it's something that could be solved by hand. And I wanted to use one of the mentioned shortcuts, how would I go about deriving it?

These prime numbers are called Solinas primes (because they were described by Jerome Solinas). The article details how they are found and how optimization works for them.

As a brief summary, consider a prime:
$$p = \sum_{i=0}^{k} b_i 2^{iw} $$
where each $b_i$ is either $0$, $1$ or $-1$, and $w$ is your "word size" (typically $w = 32$ or $64$ will yield the best results on usual computers). You also want $b_0 \neq 0$ ($p$ must be prime, so in particular it must be odd) and $b_k = 1$: the prime value is close to $2^{wk}$. To make things even easier to implement, make sure that $p$ is slightly below $2^{wk}$ rather than slightly higher, meaning that the highest non-zero $b_i$ (for $i < k$) has value $-1$.

With such a prime, modular reduction is easy because, modulo $p$, you have:
$$ 2^{wk} = \sum_{i=0}^{k-1} -b_i 2^{iw} \pmod p $$
from which you can infer:
$$ -x 2^{w(k+j)} = \sum_{i=0}^{k-1} b_i x 2^{w(i+j)} \pmod p $$
for all integers $x$ and $j$. Therefore, if you have a $n$-word value $X$ (with $n > k$):
$$ X = \sum_{i=0}^{n-1} x_i 2^{wi} \mathrm{\ \ \ \ \ \ where\ } 0 \leq x_i < 2^w $$
then you can compute the value $X'$:
$$ X' = X - x_{n-1} 2^{w(n-1)} + \sum_{i=0}^{k-1} b_i x_{n-1} 2^{w(n-1-k+i)} $$
This addition is easily computed because all the $b_i$ are $0$, $1$ or $-1$, so this amounts to adding or subtracting word $x_{n-1}$ to some other, lower words. With the relation above, you have $X' = X \pmod p$. But $X'$ now consists of $n-1$ words. So, with a few addition and subtractions, you have removed one word from your problem. Iterate.

Whether Solinas primes really give that much an advantage over a random prime (with Montgomery multiplication) is disputed. It depends on the implementation architecture. It has also been argued that choosing $p = 2^m - z$ for a small $z$ yields more efficient computations. As for all performance things, there is no absolute answer; it must be tried and measured, and any new language, compiler, processor version or architecture can change the answers.


Bulk encryption with Triple Blowfish Blowfish has a large key setup penalty, except is fast once it gets rolling.  I believe that before AES optimizations became commonplace, it was faster than AES after the initial key setup.  It's top speed once it gets rolling is good for bulk encryption, except it has a 64 bit block size.  Would the following address the block size limitation in terms of bulk encryption?
You encrypt the first 64 bit block with all three keys.
You then take the first key and grab the next block starting at bit 33 to 97.  After that you encrypt blocks 98-162, 163-227, etc., progressing 64 bits at a time after the initial half-step.
You then transpose the bytes of the intermediate ciphertext 128 bits at a time across the entire hard drive, specifically mixing across the two 64-bit blocks.  You could use a static byte level transposition, odd byes in one block and even bytes in the other.  I'm looking into other ideas, such as a matrix, except for now I'm still at a static or possible key-based columnar transposition for now.
You then take the second key and grab the next block starting at bit 17 to 81.  After that you encrypt blocks 82-146, 147-211, etc.
You then transpose the bytes of the intermediate ciphertext 128 bits at a time, specifically mixing across the 2 64-bit blocks.
You then take the third key and grab the next block starting at bit 9 to 73.  After that you encrypt blocks 74-138, 139-203, etc., progress 64 bits at a time.
Does the key staggering complicate the MITM attack?  I'm trying for triple 256 Blowfish with defense against the 64 bit block size and possibly even defense against the MITM attack.

My understanding is that the cipher's encryption:

Performs a fixed public reversible transformation of the first 128 bytes of plaintext.
Enciphers the first 8 bytes $[B_0…B_7]$ with $K_1$, $K_2$, then $K_3$
Enciphers bytes $[B_{4+8i}…B_{11+8i}]$ with $K_1$
Enciphers bytes $[B_{2+8i}…B_{9+8i}]$ with $K_2$
Enciphers bytes $[B_{1+8i}…B_{8+8i}]$ with $K_3$

The index $i\ge0$ grows as large as necessary to cover the whole plaintext (something untold takes care of the end).
Consider what happens when one enciphers the all-zero plaintext. Step 1 leaves that unchanged. Step 2 causes irregularities in the first 8 bytes. Step 3 extends that to the first 8+4=12 bytes. Step 4 extends that to the first 12+6=18 bytes.  Step 4 extends that to the first 18+7=25 bytes. But starting from byte 25 in the output of step 5, there's a key-dependent pattern that repeats every 8 bytes.
More generally, for any repeating 8-byte pattern in plaintext, there's a matching 8-byte pattern in the ciphertext (after the first 128+4+6+7=145 bytes or so).
I conclude that the proposed construction does not fully "address the block size limitation in terms of bulk encryption". It does increase diffusion, thought.

I advocate against step 1. It does make the first byte of ciphertext dependent on more input bytes, but any fixed public reversible transformation of plaintext demonstrably has no cryptographic value under Chosen Plaintext Attack (as in the above), or under any Known Plaintext Attack working with random plaintext.
It's possible to make a 128-bit block cipher out of a 64-bit one. Assuming some safe operating mode like GCM, CTR, CBC, OFB, CFB on top of that, a simple such 128-bit block cipher construction that I would trust to have security up to $2^{48}$ bytes encrypted (rather than $2^{31}$ for Blowfish or $2^{64}$ for AES) uses 6 keys, assumed independent. In a Blowfish context, we could prefix a common key with 6 different 4-byte haphazard public constants. Starting from a 128-bit plaintext $[B_0…B_{15}]$:

encipher $[B_0…B_7]$ with $K_1$, $[B_8…B_{15}]$ with $K_2$.
encipher $[B_4…B_{11}]$ with $K_3$, $[B_{12}…B_{15}]\mathbin\|[B_0…B_3]$ with $K_4$.
encipher $[B_0…B_7]$ with $K_5$, $[B_8…B_{15}]$ with $K_6$.


Does the One Time Pad rely on confusion or diffusion? From what I could research, XORing a random key adds confusion.

But I do not undertand the rationale for that classification. Shannon's confusion is supposed to obscure the relationship between the ciphertext and key, but the OTP clearly does not do this: unlike many other ciphers, if one has one plaintext and corresponding ciphertext, then there is a trivial relationship between the latter and the key...

Furthermore, what seems to me that OTP actually does is to rely (only) on diffusion: it makes the redundancy of the plaintext harder to notice, but it does not "get rid" (lacking a better expression) of it. In fact, if one obtains two cryptograms enciphered with the same key, one can then obtain the XOR of the corresponding plaintext messages, which must contain some patterns related to the structure of the original messages. (*)

In sum, I'd say the OTP is based on diffusion, and is secure only because of the sui generis requirement that the key be used exactly once. Where am I going wrong?

(*) - Otherwise one could not use the two time pad to recover the original plaintexts.

The One-Time Pad employs neither confusion nor diffusion, as defined by Shannon:

  "Two methods (other than recourse to ideal systems) suggest themselves for frustrating a statistical analysis. These we may call the methods of diffusion and confusion. In the method of diffusion the statistical structure of $M$ which leads to its redundancy is “dissipated” into long range statistics—i.e., into statistical structure involving long combinations of letters in the cryptogram. [...] The method of confusion is to make the relation between the simple statistics of $E$ and the simple description of $K$ a very complex and involved one."

(It's worth noting that, to really understand these definitions, you should read the full paper in detail.  In particular, the earlier definition of a "strongly ideal cipher" that the text alludes to is kind of nontrivial, and not something commonly encountered in modern cryptography.)

In the one-time pad, each ciphertext symbol depends on exactly one message symbol and one key symbol.  Thus, there is no diffusion, in the sense used by Shannon, since the relationship between the message $M$ and the ciphertext $E$ is trivial, nor can there be any confusion, since the relationship between the key $K$ and the ciphertext $E$ is equally trivial.

Instead, the perfect secrecy of the one-time pad follows from the fact that the use of a random one-time key masks any redundancy in the plaintext: without knowledge of the key, the ciphertext is statistically independent of the plaintext, and thus no ciphertext statistics can reveal any information about the message.  (Such statistics can reveal information about the key, if the attacker can guess some of the plaintext; but since the key is never reused, this makes no difference.)

It should be noted that this does not contradict Shannon's statements in any way: the section where the terms "confusion" and "diffusion" are defined is explicitly concerned only with non-ideal (in the sense defined earlier) ciphers using keys of bounded length.  The one-time pad is not such a cipher, and so the statistical analysis techniques that confusion and diffusion are supposed to prevent do not (necessarily) apply to it.  Furthermore, Shannon never claims that confusion and diffusion would be the only ways to protect a cipher from statistical analysis; merely that they are two obvious and general ways to (attempt to) do so.


find $a$ and $k$ for a given el gamal cryptosystem I am given this question:

Suppose Alice is using the ElGamal Signature scheme with parameters

$p = 31847$, $\alpha = 5$, and $\beta = 25703$

Assuming that we have received signed messages

$(x_1,(\gamma_1,\space \delta_1)) = (8990, (23972,\space 31396))$

and

$(x_2,(\gamma_2,\space \delta_2)) = (31415,(23972,\space 20481))$

determine integers $k$ and $a$ that Alice has used without solving any instance of discrete logarithm problem.

I also know from my lecture slides that the following equations are true

$\beta = a^\alpha \bmod p$
$\gamma = a^k \bmod p$
$a\gamma + k\delta = x \bmod p-1$

Since the question specifies not to use the discrete log problem, we can only use equation 3

so we have a system of two equations:

$a\gamma_1 + k\delta_1 = x_1 \bmod p-1 \rightarrow a(23972) + k(31396) = 8890 \bmod (31846)$
$a\gamma_2 + k\delta_2 = x_2 \bmod p-1 \rightarrow a(23972) + k(20481) = 31415 \bmod (31846)$

solving for $k$ is simple enough, just take 1. - 2. as equation 3. below:

$k(10915) = -22425 \bmod(31846) = 9421 \bmod(31846)$

and solve for $k$:

$k = 1165 \bmod(31846)$

Now here's where I'm getting stuck, by plugging in $k$ to equation 2. we get:

$a(23972) + (1165)(20481) = 31415 \bmod 31846 \rightarrow a(23972) = (23704) \bmod 31846$

but we can't isolate $a$ because the $\text{gcd}(23972, 31846) > 1$ so there is no inverse of $23972 \bmod 31846$

note plugging $k$ into equation 3. gets a similar result.

This question is from my textbook so it should be solvable, but the math  is telling me that it's not solvable.

Could someone please explain if there is some work around to finding $a$ when it is multiplied by a non-invertable number?

I found the answer after getting a hint from my professor

basically if we have an equation in to form

$$m*x = (m*y) mod (m*z)$$
we can factor out m such that:
$$x = (y) mod (z)$$

but...
the only caveat is that there are m solutions for x:
$$
x, x+z, x+2*z, ..., x+(m-1)z = (m*y) mod (m*z)
$$
using this we can solve the equation in the question $$a(23972)=(23704) mod (31846)$$
even though 23972 is not invertable mod 31846.

start by factoring out 2 from everything
$$2a(11986) = 2(11852) mod 2(15923)$$

this gives:
$$
a(11986) = 11852 mod 15923
$$

solving for a:
$$
a = (11852)(11986)^{-1} mod 15923 = (11852)(182) mod 15923 = 7459 mod 15923
$$
now the multiple solution part:

where  $$m = 2$$ and $$z = 15923$$ in our case

a = 7459 mod mz and 7459 + z mod mz

so $$a = (7459) mod (31846), (23382) mod (31846)$$
and $$k = (1162) mod (31846)$$


Finding the IV values for SHA-256 I should start by saying this question has little to no practical application. It is purely recreational. I am not trying to solve a specific problem, beyond "I wonder…"

If I had an initial input (say 64 bytes long, all in hex) and I had a desired output, is there an efficient way (read: not brute force) to find IV values that would give the desired output, after 64 rounds?

In other words, accepting that SHA-256 has no backdoor, how would I find IVs that did create a backdoor?

No, there is no known way to achieve what's asked.

SHA-256 is a Merkle-Damgård hash using a compression function built per the Davies-Meyer construction. Assuming the known input fits 55 bytes (that is, can be expressed as at most 110 hex characters, which either matches the question, or is close to that), it is padded into a single 512-bit block $B$. What's asked amounts to finding 256-bit $I$ with $E_B(I)\boxplus I=H$ where $E$ is a 64-round 256-bit block cipher having 512-bit key $B$, $H$ is the 256-bit desired output, and $\boxplus$ is 256-bit addition without carry across 32-bit boundaries. For an idealized cipher, there's demonstrably nothing better than brute force to solve this problem, and we do not know a significantly better method for the particular cipher used in SHA-256.

For larger input, what's asked seems to require breaking that same problem except for a different (or a few different) values of $H$ obtained by breaking the second and possibly later round(s), thus is likely not much easier (rather, slightly harder). And provably, if we could break the multi-rounds problem in general, that would allow to break the one-round problem with about the same work.


Is the EdDSA signature scheme provable security? The EdDSA signature scheme is a deterministic scheme. So could it be proven provable security in Random oracle model?

EdDSA is Schnorr signatures over the Edwards curve, with an additional twist that it is made deterministic. The basic Schnorr scheme can be proven secure under the discrete log assumption in the random oracle model. Furthermore, any probabilistic signature scheme can be made deterministic by applying a PRF (with a key that is part of the private key) to the message in order to derive the randomness used. This is essentially what EdDSA does. Thus, yes, it is provably secure in the random oracle model, assuming that the discrete log problem is hard in that group.


Is 50% of bits changed in every round always gives 50% of changed bits in the end? Let's say we have a cipher with such property, that every round change 50% of bits in every block in average. Is it obvious or it means that after few rounds we will get exactly 50% changed bits?
If I think about it, it looks like it doesn't have to be like that. Next round can delete some changes from previous round and so on. In the end we we can get a different number of bits changed, even if each round changes exactly 50% of the bits.
Am I right? If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed? Can it be proven somehow or usually we have to rely on statistical tests?

If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed?

Well, obviously one can construct artificial examples where this doesn't happen; the most obvious (and trivial) being if round 1 and round 2 are inverses of each other (that is, round 1 followed by round 2 gives you the original plaintext); even if both rounds were individually ideal, we still don't get the avalanche effect after two rounds (even though we had it after one).
Symmetric ciphers are generally don't have enough structure to allow us to construct proofs that this doesn't happen (and adding structure generally makes the cipher weaker, not stronger; adversaries can also take advantage of structure); we generally have to rely on plausibility arguments.