How to properly sign and verify using DSA? Can anyone spot my mistake? The question that I am trying to answer is as follows:

10.14. The parameters of DSA are given by p = 59,q = 29,α = 3, and Bob’s private key is d = 23. Show the process of signing (Bob) and verification (Alice) for following hash values h(x) and ephemeral keys kE:

h(x) = 17,kE = 25
h(x) = 2,kE = 13
h(x) = 21,kE = 8

I managed to figure out part 1 correctly and then modeled the other two parts after part 1, but the problem is that both part 2 and part 3 came out to be invalid in the verification stage, and I am pretty sure that they were supposed to be valid. Here is my work:

h(x) = 17,kE = 25

Generation(Bob):

Chooses values p=59, q=29, α=3, d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)
Actual signature generation:
compute hash message of h(x)= 17
1. choose enphemeral key kE = 25
2. r=(α^kE mod p) = 3^25 mod 59 = 51 mod 59
3. s= (h(x)+d*r)*α= (17+23*51)*3= 3,570 mod 59= 30 mod 59

sends (x,(r,s))= (x,(51, 30))

Verification(Alice):

1. w= r^(-1) mod q = 51^(-1) mod 29= 22^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
    29= 22(1)+7
    22= 7(3)+1
    -----------
    1= 22+ 7(-3)            //Set equal to 1
      = 22+ (29+22(-1))(-3) //Substitute
      =29(-3)+ 22(4)        //Distribute
     22^(-1) mod 29 = 4 mod 29
2. u1= w*h(x) mod q = 4*17 = 68 mod 29 = 10 mod 29
3. u2= w*r mod q = 4*51= 204 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
    = (3^(10)*45^(1)) mod 59) mod 29
    = (59,049*45 mod 59)mod 29
    =(2,657,205 mod 59)mod 29
    =  22 mod 29
5. v=22,
r mod q= 51 mod 29 = 22 mod 29
v = r mod q → Valid signature

h(x) = 2,kE = 13

Generation(Bob):

Chooses values p=59, q=29, α=3. d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)

Actual signature generation
compute hash message of h(x)= 2
1. choose enphemeral key kE = 13
2. r=(α^(kE) mod p) = 3^(13) mod 59 = 1,594,323 mod 59 = 25 mod 59
3. s= (h(x)+d*r)*α= (2+23*25)*3= 1,731 mod 59= 20 mod 59
sends (x,(r,s))= (x,(25, 20))

Verification(Alice):

1. w= r^(-1) mod q = 25^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
    29= 25(1)+4
    25= 4(6)+1
    --------------------
    1= 25+ 4(-6)             //Set equal to 1
      = 25+ (29+25(-1))(-6)  //Substitute
      =29(-6)+ 25(7)         //Distribute
     25^(-1) mod 29 = 7 mod 29
2. u1= w*h(x) mod q = 7*2 = 14 mod 29
3. u2= w*r mod q = 7*25= 175 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
    = (3^(14)*45^(1) mod 59) mod 29
    = (4,782,969*45 mod 59)mod 29
    =(215,233,605 mod 59)mod 29
    =  12 mod 29
5. v=12, r mod q= 25 mod 29
v ≠ r mod q → Invalid signature

h(x) = 21,kE = 8

Generation(Bob):

Chooses values p=59, q=29, α=3. d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)

Actual signature generation
compute hash message of h(x)= 21
1. choose enphemeral key kE = 8
2. r=(α^(kE) mod p) = 3^(8) mod 59 = 6,561 mod 59 = 12 mod 59
3. s= (h(x)+d*r)*α= (21+23*12)*3= 891 mod 59= 6 mod 59
sends (x,(r,s))= (x,(12, 6))

Verification(Alice):

1. w= r-1 mod q = 12^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
    29= 12(2)+5
    12= 5(2)+2
    5= 2(2)+1
    ------------------
    1= 5+2(-2)                  //Set equal to 1
      = 5+(12+5(-2))(-2)        //Substitute
      =12(-2)+ 5(5)             //Distribute
      = 12(-2)+(29+12(-2))(5)   //Substitute
      =29(5)+ 12(-12)           //Distribute
     12^(-1) mod 29 =-12 mod 29
    w= 17 mod 29
2. u1= w*h(x) mod q = 17*21 = 357 mod 29= 9 mod 29
3. u2= w*r mod q = 17*12= 204 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
    = (3^(9)*45^(1) mod 59) mod 29
    = (19,683*45 mod 59)mod 29
    =(885,735 mod 59)mod 29
    =  27 mod 29
5. v=27, r mod q= 12 mod 29
v ≠ r mod q → Invalid signature

I have no idea what I did wrong. I checked my answers several times, so if someone could point out the mistake that I made that I cannot see, I would appreciate it!

Keeping your notation, signature generation in DSA is the following:

$r = (\alpha^{kE} \bmod p) \bmod q$
$s = kEinv \times (h(x) + d\times r) \bmod q$

where $kEinv$ is the modular inverse of $kE$ modulo $q$.

But you actually did was using the formula $s= (h(x)+d\times r) \times \alpha \bmod q$, and you forgot to reduce $r$ modulo $q$. You can take a look at the wikipedia page.


Do asymmetric signatures require constant-time verification? To avoid a timing attack, HMAC signatures are usually compared in constant-time (every byte is compared, and the results aggregated).

Is the same necessary for asymmetric signature algorithms such as ECDSA or RSA?

Towards the security of the signature scheme, no precaution against timing attack is necessary when verifying an asymmetric signature. That's because there is no secret involved, thus no information leak to fear.

However it can happen that the message, or the signature itself, is intended to be secret; a leak by timing dependency (during computation of the hash of the message, during verification of message padding..) could compromise this (not the security of the signature mechanism). Except for intentionally leaky implementation of signature verification, the leak would most likely be only of few bits, and thus not to fear for the signature. However sometime any small message leak is important; and repeated leaks on related messages could in the end leak a lot of information about what's common in the messages.


Multiple-parties signature schemes please let me know if there's any digital signature scheme for the following problem. Thanks in advance!

I want to have a token that's somehow signed (or granted) by multiple
3rd parties for a certain document. The token then can be used to
access resources managed by the parties.
3rd parties just need to use their private keys to validate the token

I find the Wiki article about Multisignature, but really I don't know how to apply it into my case.

Generate the token as a random number. Have each of the parties sign the token independently. Each will provide one signature on the token. Concatenate all the signatures into a big string. That string can then be sent when resources are requested. Each party can verify that its own signature exists in the string.


To find nonlinear invariant of S box I read a paper about a nonlinear invariant attack that is Y.Todo et. al's "Nonlinear Invariant Attack: Practical Attack on Full SCREAM, iSCREAM, and Midori64"

In this paper's Appendix A., they said that

  Then, by Gaussian elimination like computation, we compute matrix $M'=[M_1'\|M_2']. $ If rows of $M_2'$ are $[0,0,...,0]$ or $[1,0,0,...,0]$, the corresponding row of $M_1'$is the basis of $U(S)$

I wonder why that is the basis of $U(S)$.

In my thinking corresponding row of $M_1'$ such that the row of $M_2'$ are $[1,0,0,...,0]$ or $[0,1,0,0,...,0]$ or $...$ or $[0,0,0,...,0,1]$ is the basis of $U(S)$.

Can you show me why "If rows of $M_2'$ are $[0,0,...,0]$ or $[1,0,0,...,0]$, the corresponding row of $M_1'$ is the basis of $U(S)$" is right.

Keep this fact.

By linear algebra, we can know that $M'_{1} \times M=M'_{2}$.

Let $\beta _i$ be a row of $M'_{1}$ which is correspond to $M'_2$ 's $[0,\ldots,0]$ row

and let  $\beta_i=[\beta_{0,i},\beta_{1,i},\ldots,\beta_{2^n-1,i}]$

Then we can know that $\beta_{i} \times M=[0,\ldots,0] $ by above fact.

So, if we define $b_i(x)=\beta_{0,i}x^0 \oplus \beta_{1,i}x^1 \oplus \cdot\cdot\cdot \oplus \beta_{2^n-1,i}x^{2^n-1}$.

Then,

\begin{align}
b_i(x)\oplus b_i(S(x))= & \bigoplus_{u\in\mathbb{F}_2^n}\beta_{u,i}\big(x^u \oplus S(x)^u\big)\\
= & \bigoplus_{u\in\mathbb{F}_2^n} \beta_{u,i}\big(\bigoplus_{v\in\mathbb{F}_2^n} \lambda_{u,v}x^v \big)\\
= & \bigoplus_{u\in\mathbb{F}_2^n}\big(\bigoplus_{v\in\mathbb{F}_2^n}\beta_{u,i}\lambda_{u,v}\big)x^v\\
=& 0
\end{align}

We can apply this formula similarly to the case of $[1,0,\ldots,0]$.


Exactly how slow is asymmetric encryption? I'm currently doing a project on RSA, and have just come across this website.

https://www.namecheap.com/support/knowledgebase/article.aspx/798/67/what-is-an-rsa-key-used-for

On here, it says that

  Since encrypted data transmission takes too much time in case of asymmetric encryption, this kind of encryption is used for a secure symmetric key exchange that is used for actual transmitted data encryption and decryption.

Now I was not aware that this was the case, so my question is, does this mean that asymmetric encryption is relatively slow compared to symmetric encryption, or is it impractically slow to be implemented in things like SSL?

Also, out of curiosity, exactly how much slower is it in terms of a time value?

Update:

Another question, why do the primes have to be far apart? I guess since the numbers used are so big they are far apart anyway, but is this a prerequisite for RSA, or just a fact that holds due to the size of the numbers?

Thanks

Yes, asymmetric encryption is slow compared to symmetric encryption.

With symmetric ciphers, encryption and decryption speed can be several gigabytes per seconds on a common PC core; see these benchmarks.

With RSA encryption, on comparable hardware, we are talking tens of thousands encryptions per second, and only few hundreds of decryption per seconds, for common key sizes, and small messages (like 1 bit to 250 bytes, way enough for a session keys and authenticators); see these benchmarks.

Pure asymmetric encryption would often be like 3 to 5 decimal orders of magnitude slower than symmetric encryption is. That's the main reason why in practice, when enciphering messages that could be over what fits the capacity of a single asymmetric encryption, we use hybrid encryption.


Is FIPS 140-2's "Continuous random number generator test" practical? Section 4.9.2 of FIPS PUB 140-2 specifies, amongst other things, a "Continuous random number generator test."  Here are the relavant bits:

  If each call to a[n] RNG produces blocks of n bits (where n > 15), [...] Each subsequent generation of an n-bit block shall be compared with the previously generated block. The test shall fail if any two compared n-bit blocks are equal.
  If each call to a[n] RNG produces fewer than 16 bits, [...] (for some n > 15) [...] Each subsequent generation of n bits shall be compared with the
  previously generated n bits. The test fails if any two compared n-bit sequences are equal.

Isn't (n > 15) too small?

I am concerned about their choice of 16 being the minimum for 'n'.  At 16-bits, one would expect to see the test fail, inappropriately, about every 64,000 iterations.  That is rather frequent!  Even an 'n' of 32 will lead to noticeable false positives if the RNG is being used very frequently.

In my specific case, I have a 32-bit TRNG, and would much rather stretch 'n' to 64 to prevent false positives.

Thoughts?

This requirement is a part of the general "continuous tests", and as such it's primary purpose is to detect "flatline" failures (if you can torture that analogy into making sense). Remember that FIPS-140 was originally written with hardware implementations in mind, so the approaches they take for testing sometimes seem odd for software since hardware failures tend to be different from software failures.

I don't think there's a problem, though. You could choose $n = 16$ and potentially have statistical problems, but you don't have to pick something that small. Build your construction to output the size block that you want it to. Eg, modern constructions like CTR_DRBG from SP800-90 output 16 bytes at a time, which is well outside statistical concern.

Also, you're probably not certifying a TRNG, since there are no non-deterministic RNGs that can be certified.


Equal length of primes in paillier cryptosystem In the key generation step of paillier cryptosystem ,

In order to satisfy  $\gcd(pq,(p-1)(q-1))=1$ , we can take equal length primes.

Instead of taking(length as parameter to generate $p,q$) equal length primes , is there any time efficient method to generate $p,q$ that assures
$pq,(p-1)(q-1)$ are relatively prime ? Or is it mandatory to take equal length primes for efficient implementation .

Just out of curiosity I want to know whether there are any public-key cryptosystems in which primes of equal length are mandatory. If there is , please list names of few of them.

Some work :

Let $p,q$ be the primes such that $p<q$.

Then $p\not|(p-1)$ and $q\not|(q-1)$

Since $p<q$ , $q\not|(p-1)$

So , the only chance to violate the condition $\gcd(pq,(p-1)(q-1))=1$ is $p|(q-1)$

More generally largest prime number minus one does not consists of smallest prime number as a prime factor .

How to ensure this without taking equal length primes ?

In your question, you already pointed out, that the necessary condition is

  More generally largest prime minus one does not consists of smallest prime as a prime factor

therefore, it is sufficient to just check if $p$ divides $q-1$ by computing division. You can just verify this condition during the key generation. I don't know of a more efficient way, anyway, it should be efficient enough for key generation. The main drawback for efficiency would occur if you repeatedly generate unsuitalbe keys, but the probability of that would depend on the length difference you allow for the two primes.

However, in general I think that the security of the scheme depends on the size of the smallest prime, however, the efficiency depends on the size of the obtained modulus $N = pq$, therefore it is probably reasonable to just use equal size primes for the best security and efficiency. Hence, I would guess that the main reason for noting that this property can be ensured by taking equal length primes, is to make sure that no additional work is required to check this during key generation.

I can not point out any schemes that definitely require equal length primes.


Endless PRNG from PRNG with specific stretch? Every definition of pseudorandom generator that I've seen says it takes n-bit strings and gives poly(n)-bit strings.

Is there a proof that if there is such a pseudorandom generator then there is a pseudorandom generator that takes n-bit seeds and repeatedly outputs bits on request?

Things I would be curious about that are not essential to the answer:

Could it be made random access? (ie, one can efficiently find what its m-th output will be)
Could it be made so that a state compromise would not give useful information about earlier outputs?

Most PRNG constructions can generate arbitrarily long pseudo-random bit sequences (or at least, can quite easily extended to do such).

Of course, a limited internal state size means that there will be some point from where the sequence repeats itself. (We can make the size that large that this will not occur in practice.)

A simple way to have a seekable PRNG would be to apply a message authentication code on seek and seed:

$$ R_{\operatorname{seek}} = MAC(\operatorname{seed}, \operatorname{seek}) $$

The seed should be on the key position here.

In this case, the internal state (the seed) will stay constant, i.e. a random output sequence will be repeatable by providing the same (sequence of) seek(s) again. As the seek can get (almost) arbitrarily long, you will have an (almost) endless sequence.

(Of course, if using a counter as the seek value, the counter's size must be included in the PRNG's state size, so a limited size state does not allow an endless non-repeating sequence.)

A non-recoverable PRNG is build by applying some one-way function on the internal state in each round of operation, additionally to generating the output (with another one-way function) from the state. So, given two one-way functions $f_1$ and $f_2$ and previous state $S_{\text{old}}$, we do

$$ R = f_1(S_{\text{old}}) $$
   $$ S_{\text{new}} = f_2(S_{\text{old}}) $$

and output $R$.

This PRNG will cycle as soon as $f_1^n(S_0)$ reaches a cycle. For a random function on a $n$-bit state, after an expected number of around $2^{n/2}$ steps a cycle of expected size $2^{n/2}$  will be reached.

You can combine both ideas if you don't need that seeks are commutative (i.e. that $seek(a); seek(b)$ gives the same output as $seek(b); seek(a)$.


Avalanche effect in DES I couldn't understand the avalanche effect in DES. Could someone explain how avalanche effect happens in DES

First of all, the avalanche effect is a desirable effect: it means that a very small change in the input will lead to a very big change in the output.

A security algorithm that doesn't provide this avalanche effect can lead to an easy statistical analysis: if the change of one bit from the input leads to the change of only one bit of the output, then it's easy to guess / try to find the input: just change one bit of it and verify if it was the right one.

How it works in DES: if you take a look at the DES, you'll see that it has 16 rounds and 2 permutations. The real thing happens in the rounds: for each round, the input bits are used to look up for bits that will be used as the output (the S-box). take a look at this presentation, for example. With the shifts that are made at each round, it means that the "index bits" (the ones used to do the table look up) come from the "data bits" from the previous round.

Changing a single bit in the input will cause more bits to be changed in the following rounds. Slide 6.41 of the above presentation shows how many bits will change at each round.


Protecting authorship of a message I posted a similar question but I see that I did it incorrectly. For this reason I post it again hoping not to cause any problem.

I have the following situation:
Alice often sends funny jokes to Bob. She does not care about the confidentiality of these messages but wants to get credit for the jokes to prevent Bob from claiming authorship of or modifying them. How can public-key cryptography achieve this?

I have provided the following answer but I need feedback from an expert:
It is clear that we are talking about an ideal situation because Bob can create a new message and type each joke entirely. However, we can do the following taking in consideration some restrictions for Bob.

If confidentiality is not important then it is not necessary to encrypt the messages. What Alice can do is to include a text at the end of each joke stating she is the author, for example, “Alice is the author of this joke”. After that, Alice digitally signs each message with her private key producing a hash of the message and sends it to Bob along with her public key. When Bob sends a joke to Carol, he sends Alice’s original message including Alice's signature and Alice's public key. This way, if Bob modifies the message, the digital signature will not be successfully validated by Carol because there will be a different result of the hash meaning that the original message suffered a change in some way.

I will very much appreciate your comments.

Public key cryptography per-ce cannot protect the authorship. In your example, e.g., Bob could re-type Alice' joke, sign it with his own valid key, and claim that he thought about it before Alice sent him the joke.

A possible solution could be to use a trusted escrow: Any party who invents a joke and wants to hold title to it has to send the joke to the trusted escrow before telling the joke to anyone else. The escrow timestamps the joke and signs the timestamped joke with their private key.

Now if Carrol receives the same joke from both Alice and Bob, who both claim title to it, and Carrol wants to know who is the real author, then she goes as follows:

Ask both Alice and Bob to send the joke as was originally signed by the trusted escrow.
If one of them fails to provide a signed joke then we assume that she/he is an imposer.
If both send a signed joke then Carrol will:

a. Verify with the trusted escrow's public keys that both signatures are valid.

b. Compare the time stamps.

We formally define the author of the joke as the one whose timestamp is the earliest.


Can RSA with padding detect all errors in ciphertext? I'm new in cryptography and there are a couple of things that i'm not sure if i understand correctly.

First, when using padding (PKCS or OAEP), if the chiphertext has errors in transmission we'll we always get an error at the decyption process? Will it detect all errors, or is there a possibility that a certain combination of errors will result in a decryption but with a false result in plaintext?

Second, if no padding is used, (i believe it is called vanilla rsa?) and there are errors on the ciphertext, then the decryption will work any time but will give wrong results instead of the original encrypted plaintext?

Finally with padding or not, with no errors on ciphertext and by using a wrong private key will we get an error in decryption or just a false decrypted plaintext?

First, when using padding (PKCS or OAEP), if the chiphertext has
  errors in transmission we'll we always get an error at the decyption
  process?

Yes, with extremely high probability. This is basically a chosen ciphertext attack and RSA-OAEP is fully immune to them, so the odds that you won't detect this attack (a.k.a. "error") are extremely low (below $2^{-128}$).

  Will it detect all errors, or is there a possibility that a certain
  combination of errors will result in a decryption but with a false
  result in plaintext?

This is possible but extremely unlikely, again due to the IND-CCA2 security of RSA-OAEP.

  Second, if no padding is used, (i believe it is called vanilla rsa?)
  and there are errors on the ciphertext, then the decryption will work
  any time but will give wrong results instead of the original encrypted
  plaintext?

Sometimes it's called "textbook RSA", "plain RSA" or "unpadded RSA".
If you follow the textbook RSA description, any errors will change the value of the ciphertext, resulting in a different number being decoded, resulting in an (unrelated) decryption, which will always work. If the error is malicious it could be exploited, depending on the reaction of the system.

  Finally with padding or not, with no errors on ciphertext and by using
  a wrong private key will we get an error in decryption or just a false
  decrypted plaintext?

If you use a wrong private key $d$, which, by definition, doesn't satisfy $ed\equiv 1 \pmod{\lambda(n)}$, you'll decrypt a wrong message, which will lead to a verification error for OAEP and to a simple wrong message for unpadded RSA.


What is the branch number of this matrix? We have the following matrix:
$$\begin{pmatrix}0&1&1&1\\
1&0&1&1\\
1&1&0&1\\
1&1&1&0\end{pmatrix}$$

What is the branch number?

Is this a MDS marix?

The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$. This covers all possible fields of interest for crypto.

Note that you just need to take the given matrix, call it $A,$ form $G=[I | A]$ over the relevant field and determine the minimum weight of the resulting code. Magma (and GAP, Pari, Python) can do this for you easily. This code turns out to be a quasi-cyclic code over the fields $GF(2^n)$ with minimum distance 4.

Edit: It seems that 4 is the limit for the minimum distance of this type of code. In particular a $16\times16$ version, still has minimum distance only 4, for the fields $GF(2^n)$ where $n=1,2,\ldots,8.$ I assume $n=8$ is of interest to the OP, since it corresponds to having bytes as code symbols, as in AES.

This was checked on Magma as well.


How to do a literature search How do I do a literature search of the research literature on cryptography?  Assume there's some topic in cryptography I'd like to learn more about; how do I search the cryptographic research literature to find research papers that might be relevant?  What's the best process to use for finding relevant research?

Here is how you do a literature search, to find relevant research papers in the literature:

You identify some search terms related to your topic, and search for them on Google Scholar and other places (e.g., Crypto.SE, via web search, on Citeseer).  (For cryptographic work, also try searching Google with site:eprint.iacr.org and your search terms, to turn up papers on the IACR's ePrint server.)

Go through each paper that you find in this way and very quickly skim the title and abstract of each paper.  Keep all the papers that look relevant or related to your topic of interest, based upon your skim of the title and abstract.
Take the papers you identified in step one.  If there are any research papers that you know are related, add them to the list.  This is your starting set of relevant papers.
For each relevant paper, you use that paper to help you find other papers that may be relevant:

You read the paper's related work section, to see how it describes related work.  Anything that sounds relevant to your interests, you take that citation and add it to your list of relevant papers.
You search for that paper on Google Scholar and on CiteSeer.  You use them to generate the list of all other (newer) papers that cite that paper, and you look through those results.  Keep all the ones that look relevant, and add them to your list of relevant papers.

As you discover new relevant papers, apply the same process to each of them recursively.
Keep doing this until you don't find anything new (i.e., until the set of papers is closed).

The result of this should be a (possibly large) set of relevant papers.  Now go read all of those papers, to understand what they are doing.

Once you have some research papers that look like they might be relevant, here is how you read go about reading them:

Start by reading the abstract and introduction; that should give you a good overview of what the paper's contributions are.  Don't try to read the rest of the paper.  This should take maybe 15-30 minutes.
If the paper still sounds relevant, you read the paper at least once straight through (skip or skim all proofs or other technical parts that take hard thinking to follow); your goal is to understand the main ideas in the paper, but you don't need to grok every little detail.  That should give you an idea of what the paper is doing.  Normally, this should take an hour or two.
If it still sounds useful, you can then do a careful read-through where you try to understand every detail in the paper, and think critically about why they're doing what they're doing and how it's helpful to you.


Ed25519 key generation the following rfc describes the key-pair generation mechanism for Ed25519; the first two steps are as follows:

  Hash the 32-byte private key using SHA-512, storing the digest in
     a 64-octet large buffer, denoted h.  Only the lower 32 bytes are
     used for generating the public key.
  Prune the buffer: The lowest three bits of the first octet are
     cleared, the highest bit of the last octet is cleared, and the
     second highest bit of the last octet is set.

I am not sure I understand what the seconde step accomplishes.. More concretely, if one were to replace SHA-512 by another hash function, let say blake2 for efficiency is the pruning(encoding) still necessary? and why? are there security relevant properties related to that?

Thanks!

The second step has nothing to do with the first step. It doesn't matter which hash is used in the first step. For X25519, which operates on an equivalent curve Curve25519, the private key is obtained by randomly generating 32 bytes and the first step of using that key is to apply the bit pruning step (clear bits 0, 1, 2 and 255 and set bit 254).

Clearing bit 255 ensures that the key is in the range $0..2^{255}-1$ where the operations are defined. Setting bit 254 improves performance when operations are implemented in a way that doesn't leak information about the key through timing. Clearing the low-order bits counters attacks that force the use of a weak key.


How can I encrypt + authenticate short strings into similar short ciphertexts? I wish to manipulate short ASCII strings (namely unpredictable domain names) into a form which cryptographically assures authenticity and confidentiality, for use in the local part of email addresses.  Furthermore, the resulting email addresses should be valid according to most address validators (including the many many non-standards compliant ones).

I therefore envisage that the resulting ciphertext must be as compact as possible (many validators have arbitrarily short length restrictions) once it is encoded using a very restricted subset of ASCII characters (probably just [a-z0-9\.\-], since many email address validators do not properly accept quoted/escaped characters and may erroneously transform the address in such a way that character case is lost).  Most ciphers that I've tried produce far too much ciphertext to meet these requirements.

As an aside, it may be interesting to note that my proposed encoding uses the same alphabet as the plaintext.

A given plaintext should always produce the same ciphertext (when using the same key), so there should be no random component here.

Strong authenticity is more important than strong confidentiality, but a mere encoding will not provide sufficient confidentiality.  There is no particular requirement for asymmetric ciphers.  For the sake of argument, assume unlimited computational resources are available to perform encryption/decryption.

Suggestions for possible ciphers and/or encoding schemes would be most welcome.

First, convert the string which is to be encrypted into a sequence of bytes. UTF-8 is easy enough; you may reduce the size a bit, depending on what you know on the input strings (e.g. if the strings are domain names, they are ASCII-compatible, so you need only 7 bits per character -- actually a bit less). For the rest of this post, we need to assume that the encoding does not yield any byte of numerical value zero (which is true of both ASCII and UTF-8, if the source string does not have any embedded zero).

Once you have $d$ bytes, append at least $m$ bytes of value 0. This is the authenticity check: an attacker will have at a probability of at most $2^{-8m}$ to produce what will look like a "valid" encrypted string. This is a trade-off: a higher $m$ makes life more difficult for the attacker, but costs you space.

Let $n = d + m$. You now have a sequence of $n$ bytes (note: you can "round up" the size by adding some extra zeros beyond the $m$ zeros). Encrypt that sequence of $n$ bytes into another sequence of $n$ bytes by applying a block cipher with blocks of $n$ bytes (see below). This must be a single application of the cipher, no chaining mode, no IV.

Finally, represent the resulting $n$ bytes as a sequence of characters in your destination alphabet. Since you want to stick to 38 characters (lowercase letters, digits, dot and dash), this means interpreting the $n$ bytes as an integer, and converting it to base 38. In Java, this would may like this:

/*
 * WARNING: this code is completely untested, I write it "on-the-go". I have not
 * tried to run or even compile it. It is also grossly inefficient (although it
 * should be fast enough for most applications).
 *
 * convertToName() converts a sequence of bytes (normally the output of the
 * encryption function) into a string suitable for being the local part of an
 * email address. convertFromName() does the opposite (or returns null on
 * invalidly encoded string).
 */

static String convertToName(byte[] enc)
{
    StringBuilder sb = new StringBuilder();
    BigInteger z = BigInteger.ONE
        .shiftLeft(enc.length * 8)
        .subtract(BigInteger.ONE);
    BigInteger x = new BigInteger(1, enc);
    BigInteger u = BigInteger.valueOf(38);
    while (z.signum() > 0) {
        BigInteger[] qr = x.divideAndRemainder(u);
        x = qr[0];
        int c = qr[1].intValue();
        if (c < 26) {
            c += 'a';
        } else if (c < 36) {
            c += '0' - 26;
        } else {
            c = (c == 36) ? '.' : '-';
        }
        sb.append((char)c);
        z = z.divide(u);
    }
    return sb.toString();
}

static byte[] convertFromName(String name)
{
    BigInteger u = BigInteger.valueOf(38);
    BigInteger x = BigInteger.ZERO;
    BigInteger z = BigInteger.ONE;
    for (int i = name.length() - 1; i >= 0; i --) {
        int c = name.charAt(i);
        if (c >= 'a' && c <= 'z') {
            c -= 'a';
        } else if (c >= '0' && c <= '9') {
            c -= '0' - 26;
        } else if (c == '.') {
            c = 36;
        } else if (c == '-') {
            c = 37;
        } else {
            return null;
        }
        x = x.multiply(u).add(BigInteger.valueOf(c));
        z = z.multiply(u);
    }
    byte[] b = x.toByteArray();
    int encLen = z.subtract(BigInteger.ONE).bitLength() / 8;
    if (encLen < b) {
        byte[] enc = new byte[encLen];
        System.arraycopy(b, b.length - encLen, enc, 0, encLen);
        return enc;
    } else if (encLen == b) {
        return b;
    } else {
        byte[] enc = new byte[encLen];
        System.arraycopy(b, 0, enc, encLen - b.length, encLen);
        return enc;
    }
}

When decrypted, you call convertFromName(), and reject if you get null; otherwise, you should have a sequence of $n$ bytes, which you then decrypt with the block cipher. You check that there are at least $m$ zeros at the end of the decrypted block (that's the authenticity check), and finally decode the string using whatever convention you used in the first place (e.g. UTF-8).

All of the above is just encoding and decoding things. Remains "only" the yummy part: the block cipher. What you need is a pseudo-random permutation of the space of $n$-byte values, selected by a key which you use to encrypt and decrypt.

For $n = 8$ you can use Triple-DES. For $n = 16$, no hesitation, use AES. For larger blocks, there is no completely established rock solid standard, but for $n = 32$ you can have a look at Rijndael: the original Rijndael is defined over blocks of 128, 192 and 256 bits, with keys of 128, 192 or 256 bits (AES is Rijndael with 128-bit blocks, but the versions with larger blocks, while not being "the AES" per se, are considered reasonably robust nonetheless). For larger blocks, see Threefish, which is very new (this is not a good thing for a cryptographic algorithm) and received only limited attention as a block cipher, but goes up to 1024-bit blocks (that's for $n = 128$).

The idea would be the following: in the conversion above, you add enough extra zeros (beyond the $m$ zeros for the integrity check) to reach the next $n$ for which you have a suitable block cipher in the list given above.

On a general basis, you may want to implement "Format Preserving Encryption", e.g. using the Thorp shuffle as described by Morris, Rogaway and Stegers. This could allow you to have a "block cipher" for any $n$, without having to round up to the next value for which there is a suitable conventional block cipher. This is a mixed blessing, though: by keeping $n$ as is without ever adding more zeros than the initial $m$, you are effectively leaking the original length of the plaintext string. By making sure that $n$ is always one of $\{8,16,32,64,128\}$, you are masking part of that information while keeping your "local names" small when possible.

Numerical application: with $m = 3$ (the attacker has only one chance in 16777216 to create an invalid string which will be accepted by the check on $m$ zeros), input strings ("domain names") will yield output strings ("local names for email addresses") of the following length:

if $d \leq 5$, you uses 3DES and get strings of 13 characters;
if $5 \lt d \leq 13$, you use AES and get strings of 25 characters;
if $13 \lt d \leq 29$, you use a cipher with 256-bit blocks, and get strings of 49 characters;
if $29 \lt d \leq 61$, you use a cipher with 512-bit blocks, and get strings of 98 characters.

If you use UTF-8 encoding, $d = 13$ means 13 characters for input. But if you assume that input strings consist only of ASCII characters with codes from 33 to 126 inclusive (no control character, no space), you can store 15 characters in 13 bytes.


Very short block ciphers for equally-short plaintexts I'm trying to develop an encryption technique for encrypting short phrases (such as reversibly-anonymized names) in text. The key-generation and ciphertext-representation details are fungible, but most of the techniques I'm envisioning would be best facilitated by a function with the following properties:

I want to encrypt multiple plaintexts with a common key (which is expected to be at least 256 bytes) in such a way that the encrypted string is no larger than the source text (which may be compressed with a short-string-compression algorithm like smaz, both keeping the data small and increasing input entropy).

I looked at common symmetric-encryption ciphers like AES and Salsa20, but the block sizes of both of these result in the output being significantly longer than our input (which may be as short as a single byte).

Since my key material is expected to be almost always longer than the input, I also considered using a one-time-pad approach like just simply XORing the input against the bytes of the key, but this is subject to a trivial known-plaintext attack: if an attacker can guess one encrypted string's input representation, they can can obtain a partial key that can decrypt any other string of that length or shorter by XORing against that plaintext.

I also considered a stream-cipher-like approach using each byte as a block, but that had the issue of inputs with the same prefix having the same prefix when encrypted (ie. if I know "John Smith" encrypts to "ABCDEFGHIJ", then I know "ABCDEKLMNOPQ" is another string beginning with "John").

Is it possible to symmetrically encrypt multiple shorter-than-the-key byte sequences (without nonces) in such a way that

the output is the same length as the input,
inputs with similar subsequences (eg. identical prefixes) don't have matching (partial) ciphertext,
and other plaintexts can't be derived from a known plaintext (or at least, not trivially)?

It feels like what I'm asking for is a block cipher that can operate on blocks of any width from $8$ to $n$ (where $n$ is the length of the message, or at least the length of the key). Does such an algorithm exist?

Why don't you use a stream chiper like RC4? (ok, RC4 is known to be broken, but there are many others). Am I missing something from your question?


How well does breaking multiple DH key exchanges over the same group scale? Suppose you are running a server with the Diffie-Hellman parameters (so the group G and generator g) generated once. There are many connections made to the server, all using TLS with an DHE cipher suite.

Now, assume an adversary captures all connections and is able to break one key exchange (find the master key). How much harder would it be for that adversary to break 2, 3, ... $n$ of the key exchanges instead?

Of course this will depend on the attack against DH that is used. In a naive brute force attack the adversary starts generating $g^0, g^1, g^2, \dots$ until they find either the exponent used by the server or the exponent used by the client.

Something like:

a := g
e := 1
while e < n:
    a := a ∙ g in the group G
    e := e + 1
    if a == client_key or a == server_key:
        return e

This contains one modular multiplication step (multiply previous value by $g$) and two comparisons. I would expect the comparisons to be very cheap compared to the multiplications, therefore doing this for 2 key exchanges instead of one should only have a small impact on the time required.

Does the same apply to other attacks on DH?

Background:

I think it's a common misconception that to compromise $n$ connections without forward-secrecy, an adversary only needs to break one key and with forward-secrecy and attacker would need to break $n$ keys, and therefore would need to spend $n$ times as much resources to do so. Forward-secrecy only implies that adversaries can't “cheat” the math by stealing the key, it doesn't necessarily mean that breaking multiple key exchanges is more difficult than breaking one.

The simplest index-calculus attack on discrete logarithms is the following. You have a generator $g$, a target $y$ and a bunch of small primes $\ell_1, \dots, \ell_k$. The computation proceeds in three phases.

First generate lots of relations of the form
$$g^{r_i} = \prod_j \ell_j^{s_{ij}}.$$

These relations give you a set of linear equations in $r_i$, $s_{ij}$ and unknown $\log_g \ell_j$. Solve this system for the unknown $log_g \ell_j$.

Now find one relation of the form
$$y g^u = \prod_j \ell_j^{v_j}.$$
From this, the logarithm of $y$ is easily recovered.

The third phase is much, much cheaper than the two first phases. Notice also that the two first phases do not involve $y$, so when you want to compute the logarithms of multiple elements, you only have to repeat the third phase.

I believe these essential characteristics are shared with the more advanced d.log.algorithms, so the cost of computing $n$ logarithms is not $n$ times the cost of computing one logarithm, but merely somewhat larger than computing one logarithm.

Typically, our goal is to make it impossible to compute even one logarithm, so this does not have to be a reason for using different groups. There are good reasons for everyone to use the same group. For prime finite fields, you can use carefully chosen primes that make arithmetic fast and/or secure implementation easy. For elliptic curves, you can use carefully chosen primes and curves that make arithmetic fast and/or secure implementation easy. (Note that index calculus doesn't work for elliptic curves, but I think there are speedups for Pollard $\rho$ when computing multiple discrete logarithms.)


The solution of insert MAC in a ciphertext without Authenticated Encryption supported From Should we MAC-then-encrypt or encrypt-then-MAC?, I understand I should do Encrypt-than-MAC, which the MAC included all the information such as IV and cipher text.

After reading Why choose an authenticated encryption mode instead of a separate MAC?, I know reusing key in Encryption and MAC may trigger unwanted weaknesses. So I got a question, if the language I used don't have authenticated encryption supported, how should I insert a MAC? The author of the answer suggest to use KDF to solve the problem, but KDF need a salt otherwise it won't work. If I place the salt like salt||hmac||IV||ciphertext, since the salt is not protected form the MAC, will it be meaningless to use EtM and/or trigger another weakness?

Articles I have read also:

Using the same secret key for encryption and authentication in a Encrypt-then-MAC scheme

The salt, if used at all for a Key Based Key Derivation Function (KBKDF), may be send in plaintext. There is generally no reason for salts to be kept secret.

As already noted in the comments by SEJPM, there is no direct need for a salt for a KBKDF. You may however well use it to strengthen the security of the KBKDF. The HKDF RFC (section 3.1) nicely explains the reasons why you might want to supply a salt.

Notes:

You could also derive an IV from the KBKDF if you'd use a salt (using another Info parameter, e.g. "IV") - in that case you don't need to send it with the ciphertext;
Generally the authentication tag (HMAC value) is placed at the end of the ciphertext, but that doesn't matter with regards to security.


Can we break RSA with an optical Fourier Transform? We all known that RSA can be compromised using quantum Shor's algorithm. The horsepower underlying this algorithm is the Fourier transform. However, we can use alternatives to perform this function, such as An optical Fourier transform coprocessor with direct phase determination.

In accordance to the paper, you may need a high resolution optical sensor for this task. But how high does it need to be? Can we get a rough estimation using a lower resolution and guess something close?

Are such alternatives viable (in a near future) to break RSA?

PS: The largest optical sensor in existence is a 3.2 gigapixel

The horsepower underlying this algorithm is the Fourier transform

Not quite; the algorithm is to generate a superposition of states, compute the modular exponentiation of those states (generating the superposition of those results), and then use a Quantum FFT (actually, the inverse FFT[1]) to find a periodicity (and from such a period, you can deduce the factorization).

The issue for you is that this is an inherently quantum operation; the hardware you linked to performs a Discrete (Classical) FFT [2], which doesn't operation on superpositions.  And, if you don't perform the inverse FFT on a superposition, then you can't implement Shor's algorithm.

Hence, your idea using an optical hardware within superposition doesn't solve the problem at all...

  Are such alternatives viable (in a near future) to break RSA?

It doesn't appear that way...

[1] Requiring an inverse FFT isn't the main objection - I believe optics can perform that operation as well...

[2] Actually, it's rather easy to compute FFTs (and inverse FFTs) in software - the linked hardware's just claims it can compute it somewhat faster, but software already is pretty fast...


How are Elliptic Curve Cryptography and Pairing Based Cryptography related? I have been doing a project that uses the PBC library developed by Ben Lynn. But I am still not clear on how PBC is related to ECC.
I know that this is a site for complex crypto QA, but I did not know where else my question would be answered. I have tried to learn from online sites, but I don't understand most of them.

If my questions merits a good answer, please help me. Otherwise please give me some pointers in the right direction.

Most pairing-based cryptography (PBC) schemes are based in elliptic curve cryptography (ECC). The main function in PBC is the pairing, which is a function $e$ with two parameters, e.g. $r = e(P, Q)$. The relationship with ECC is that $P$ and $Q$ are points in elliptic curves over finite fields. The value $r$ is an element of a certain finite field (related to the fields used in the elliptic curves).

Some PBC protocols also need to compute point multiplication, e.g. $kP$, which is also the central algorithm of ECC and therefore can use the same existing techniques and optimizations.


Is Threefish the only cipher with 1024 bits of security? Threefish has up to a massive 1024 bits of security.  Is it the only cipher with such overkill security?

If we are talking about symmetric encryption, the PAGES block cipher based on Speck support key size 1024 bits and PAGES+/PAGES— variants support key sizes up to 2048 bits. However, I have not seen any independent cryptanalysis of these, so I can't recommend them. If we talk about the ciphers which have some cryptanalysis available, the Kalyna block cipher supports up to 512-bit keys.


The collision rate probability decreases when using compression? Some standard compression procedures, like the  IANA's gzip
provided by HTTP protocol, will consume CPU-time anyway...
So we can reuse compressed file, $Z(x)$, in the checksum procedure.
That is, we can use $H(Z(x))$ instead $H(x)$.

Let $H$ be a collision resistant hash function and $P_c[H](S)$
the collision rate probability
about a sample set $S$ of input elements (eg. random numbers).
It decreases when using $Z(x)$? $P_c[H\circ Z](S) \le  P_c[H](S)$   ?

Intuitivally we can imagine some decrease in collision-rate because hashing a file is similar to an aleatory sampling procedure:
if we reduce the redundance in the sample set, we reduce collision probability.
HTML, XML, and many other file formats have a lot of redundancy.

If the intuition is correct, the questions is also about "how mutch better is it"?

NOTICE: I am using the strange term collision rate probability (with a link to this other question) to avoid confusion with the "general collision probability". Please take care to not mix the concepts in the answer.

No. On the contrary, if we model $H$ as a random function chosen independently of $Z$ and $S$, then $P_c[H\circ Z](S)=P_c[H](S)$.

Argument is that $P_c[H](S)$ is dependent only on the width of $H$ and the number of elements in $S$, as long as $H$ is modeled as a random function chosen independently of $S$. Define $S'$ as the set of $Z(s)$ for $s$ in $S$. It holds that $P_c[H\circ Z](S)=P_c[H](S')$, and because compression is reversible, $S'$ and $S$ have the same number of elements.


If a private key decrypts what its public key encrypts, can the public key conversely decrypt what its private key encrypts? Whilst studying the material for the CCNAS exam, I have encountered something on the cryptographic systems chapter that I am not sure about. Cisco Netacad states that "Asymmetric algorithms use two keys: a public key and a private key. Both keys are capable of the encryption process, but the complementary matched key is required for decryption. For example, if a public key encrypts the data, the matching private key decrypts the data. The opposite is also true. If a private key encrypts the data, the corresponding public key decrypts the data.".

Can someone clarify whether the last statement made is correct; that if the private key encrypts the data then the corresponding public key decrypts the data. As far as I know this is not true?

Any clarification here would be appreciated!

You are right if you feel that this is nonsense; it is, fundamentally, a category error.  However, it is an unfortunately popular confusion of ideas that public-key signature is ‘just encryption with the private key’.

There is a tempting grain of truth to this notion—deep in the underbelly of the mathematics of one family of cryptosystems, with no practical consequences whatsoever, and not only is it completely useless to a practitioner but it is likely to get you into deep trouble if you try to act on this idea in any meaningful way.

Here's the tempting grain of truth.  RSA-based encryption schemes and signature schemes involve computing $e^{\mathit{th}}$ powers modulo a large composite $n$ with large prime factors as part of the public operation (encrypting, verifying), and computing $e^{\mathit{th}}$ roots modulo $n$ for the private operation (signing, decrypting).  And there the resemblance ends—there is no resemblance in the rest of the details of how you actually build encryption and signature of messages out of this.

Not only does the resemblance end there, but this tempting grain of truth is limited to RSA-based cryptosystems—while most of the world today has moved on to elliptic-curve cryptography for almost all new applications, in which signature and encryption schemes are completely different, and is preparing in the NIST PQCRYPTO competition to adopt a new lattice- or isogeny- or hash- or MQV- or somethingcrazy-based cryptosystem that will resist all current known methods of quantum cryptanalysis.


Solving discrete log in partially known group Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,s$).
Assume that it is easy to solve the discrete log problem in the subgroup of order $p$.

Questions

I know that if I have an upper bound on $n$, I can use Baby step-giant step to solve the discrete log in $G$. Does Pohlig-Hellman also work if you know the upper bound?
Can I solve the discrete log problem in $G$ using the Pohlig-Hellman algorithm or any other algorithm that has square root complexity in the above group setting?
Can one find $k$ using any of the discrete log solving algorithms?

My probable answers

Assuming that Pohlig-Hellman only works if you precisely know the group order, then no I can't solve the discrete log problem in $G$ as I don't know $n$(or $k$ for that matter).
Not sure what the answer is if I use baby step-giant step but I think you can not find $k$ using Pohlig-Hellman.

Need help in filling the gaps and verifying my answers.

Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows:

Choose small $k'$ such that $k'\ge k$. If the upper bound on $n$ is $n'$, then $k'=\lfloor\log_pn'\rfloor$ can be used.
Set $g'=g^{p^{k'}}$ and $h'=h^{p^{k'}}$. Now, the orders of $g'$ and $h'$ divide $s$.
Use baby-step giant-step algorithm to find discrete logarithm of $h'$ to the base $g'$. If a good upper bound on $s$ is not known, it is possible to run the algorithm multiple times with exponentially increasing upper bound.
Similarly, use baby-step giant-step algorithm to find $s$, for example, by finding discrete logarithm of $(g')^{-1}$ to the base $g'$. If $g$ is not a generator, you may find a value $s'$ different than $s$ (but it will divide $s$). In this case, $g$ lies in a subgroup of size $p^ks'$, so you may just assume that this subgroup is the whole group.
Then, use Pohlig–Hellman algorithm to find discrete logarithm of $h^s$ to the base $g^s$. Both elements are in the subgroup of size $p^k$.
Use Chinese remainder theorem to find the logarithm of $h$ to the base $g$.

To find $k$, first use the above algorithm to find $s$. Then, if you have a generator $g$, find the smallest $k$ such that $g^{p^ks}=e$, where $e$ is a neutral element. If there is no known generator, it is possible to use multiple random elements instead to make the probability of finding the correct $k$ arbitrarily close to $1$. There is no deterministic algorithm that works with arbitrary groups when no generator is known, because it is possible that all known elements will lie in the subgroup of size $p^{k-1}s$, so it will be impossible to tell that the real size is not $p^{k-1}s$ but actually $p^ks$.


Can homomorphic operations on many different ciphertexts be multiplied by a same constant? Assume Alice encrypts messages $m_1$,...,$m_n$ using secret keys $k_1$,...,$k_n$ on a homomorphic encryption scheme (BHHO), so she would get $c_1=Enc_{k_1}(m_1)$,...,$c_n=Enc_{k_n}(m_n)$. Then Alice sends a constant a , some random numbers $a_1$,...,$a_n$ and these ciphertexts to Bob. Can Bob do the following homomorphic operations? (The homomorphic encryption scheme requires that the ciphertext is multiplied by a random number)
$$d_1=Enc_{k_1}(m_1)*{a_1}*a=Enc_{k_1}(m_1*{a_1}*a)$$
...
$$d_n=Enc_{k_n}(m_n)*{a_n}*a=Enc_{k_n}(m_n*{a_n}*a)$$

Yes. Additive homomorphic encryption can also be used to obtain multiplication by a scalar. The way that this is done is by repeated addition, in exactly the same way as you do efficient exponentiation.

Recursively, define:

If $a$ equals 1 then $mult(a,Enc_k(m)) = Enc_k(m)$
If $a$ is even then $mult(a,Enc_k(m)) =
   mult\left(\frac{a}{2},Enc_k(m)\right)+mult\left(\frac{a}{2},Enc_k(m)\right)$
If $a$ is odd then $mult(a,Enc_k(m)) =
   mult\left(\frac{a-1}{2},Enc_k(m)\right)+mult\left(\frac{a-1}{2},Enc_k(m)\right)+Enc_k(m)$

Thus, you only need addition.


Is it possible to decrypt only a portion of a gpg encrypted file? I have very large encrypted files that I need to process in a highly parallel fashion (the files are composed of distinct records of data). Currently, the process begins by first decrypting the data, then starting the parallel work with each worker seeking to it's assigned file offset. I already have a way of aligning to record boundaries, so don't worry about that.

My (limited) understanding of GnuPG encrypted files is that the data is encrypted using a symmetric algorithm and then the key is encrypted with the public key of the recipient. Since I am the recipient, I understand that my public key can list algorithms I support.

Can I make use of this so that when the file is encrypted, I will be able to interpret it in a chunk-like fashion? For example, I could piece together a valid decrypt-able chunk by reading a certain number of bytes preamble of the file and then seeking to a calculable valid offset and continuing my reading and ending at a calculable valid offset?

Thanks!

Yes, it should be possible to decipher a chunk of a large RFC 4880 / OpenPGP file (without deciphering the bulk of what's before), assuming the (private or symmetric) key necessary for sequential deciphering is available, and the entity that prepared the enciphered file did so without using the file format's compression feature (even though using it is the default and most common). There is an attribute in the public key format allowing the recipient to require that compression is not used (see RFC 4880 section 13.3.1), thus what's asked should be possible.

However

The integrity of the separately deciphered chunk can not be ascertained; it seems that as a bare minimum, the file should be integrity-checked once (e.g. the signature by the alleged sender verified) before starting to decipher it as chunks.
There is a risk that some untested implementation (or one predating the OpenPGP spec) does not honor the "don't compress" flag correctly (that is, compress even though one of the intended recipients forbids). An option in this case would be to sequentially decipher then re-encipher the file without compression for future direct access.
Usual libraries implementing OpenPGP decryption are not designed with direct access in mind, and will need to be modified, as follows.

The general idea would be to process the beginning of the file as usual, up to the point where the symmetric key and algorithm used for encryption of the bulk of the data is known; then (when the chunk to decipher is not near the beginning of the file) seek to an appropriate location considering the block size (8 octets for 3DES, 16 octets for AES). OpenPGP uses a block cipher in CFB mode with a slight modification at the beginning, thus we must skip two octets and an appropriate multiple of the block size, then decipher as in normal CFB, using as IV the ciphertext block immediately before the ciphertext block containing the first octet of the chunk to be deciphered.

Note: In the above, "chunk" is used as in the question, for some large portion of the useful data in the file. And "block" designates the amount of data at the input and output of a block cipher; that's 16 octets (128 bits) for all variants of AES. RFC 4880 also uses "block" for that meaning, and occasionally others (e.g. in "block of text"). RFC 4880 consistently uses "packet" to designates a section of the file with a certain format; see section 4 for the general format of packets, section 4.3 for the various kinds, and section 5 for details. "Blocks" in the sense I use live in a Symmetrically Encrypted Data Packet.


zero knowledge framework for c programs - how to prove correct C program execution with private inputs I am looking for a zk framework that could be used for proving correct execution of programs written in C (or any other high level language) such as:

 I know x s.t. SHA-256(x) = y (y is public, x is prover's private input)

or in pseude code:

 void compute(_ *prover_input, _ *verifier_input, _ *output){
    *output = sha256(*prover_input) == *verifier_input;
 }

So far I found pepper project which seems pretty close but it lacks the prover's private input part/zero knowledge part.

I also want to compute more functions than sha and combine them in one proof.

pepper project does not lack private input functionality. It does support that with exo_compute method. Probably it didn't when you asked the question, but now it does.

Check here for more details about exo_compute. Also, I have implemented in a pull-request the scenario you mentioned where a prover knows the pre-image of a hash function and he/she does not disclose it to the verifier. See here for the source code and here for more details about the PR.


'Superblock' ciphers? I'm a noob with very fragmental knowledge of basic crypto. So please excuse me if this question is really stupid.

If I understand everything correctly, there are two basic schemes for ciphers: a stream cipher, where every byte is encrypted by itself, and a block cipher, where some fixed length block of bytes is encrypted.

In a stream cipher encrypted bytes are in the same order as message bytes; in a block cipher bytes are mixed inside of a block but order of blocks stays the same.

So my question is: are there any kind of "superblock" ciphers where order of blocks in the ciphertext is different from plaintext? Does it even make sense to do this? Or there is no point because block ciphers are already secure enough?

Obviously such a 'superblock' cipher will not be suitable for any kind of streaming applicatons but may be for something like disk encryption?

There is already enough transposition in usual block ciphers to provide enough security. You could add a simple transposition cipher on top of a block cipher but there is little reason to do so.

It would be pretty easy to perform time based side channel on the cipher is it is spread across a disk or SSD. So that would already bring down the added security.

There may also be horrible performance decreases on certain media, as already mentioned in the comments.

Basically I don't see how such a scheme would add much security, and the implications of performing the transposition are too severe.

So yeah, I guess that block ciphers + common disk encryption schemes are already "secure enough" if there is such a thing.

Besides all that, if the block cipher gets broken, don't you think it would be relatively easy to put the blocks in the right position again?

Axapaxa also makes good observation on how this won't protect single block messages.


Are there any security drawbacks for simply encrypting and MACing my JWS token (JWT)? This question, while related, doesn't answer the security aspect I have in mind. I understand that signatures make it impossible for the tokens to be modified. But if I want the JWS token content to be non-visible, I keep hearing people mention JWE. But is there a security reason why I shouldn't be encrypting them myself?

If I take the JWT, encrypt it with AES-256-CBC (I prefer CBC over GCM because I don't want to fall into equal IV attacks), then MAC it with some hashing function like SHA-512 (HMAC-SHA512), convert both the ciphertext and the MAC to base-64, and put them in a printable string. Am I vulnerable to some security attacks if I use the outcome to authenticate users on a web application? Or is just "not nice"?

Looking at the RFC of JWE, I see there's a similar example. But given I'm not an expert in cryptography, I'm not sure whether I'm missing something.

[I]f I want the JWS token content to be non-visible, I keep hearing people mention JWE. But is there a security reason why I shouldn't be encrypting them myself?

On the contrary, there is a security reason why you should avoid JWT altogether: software implementing it tends to be riddled with vulnerabilities which are encouraged by a poor design, where the adversary tells you which algorithm to use in the alg field and the software happily obliges.

The standard examples of exploits are specifying the none algorithm to disable verification altogether, or specifying a secret-key authenticator like HMAC-SHA256 when you meant to use a public-key signature like RSA—the adversary knows the public key, and can therefore compute HMAC-SHA256 under that public key that will pass HMAC-SHA256 verification.

Instead, you are much better off just using a single authenticated cipher on a binary blob of data.

  If I take the JWT, encrypt it with AES-256-CBC (I prefer CBC over GCM because I don't want to fall into equal IV attacks), then MAC it with some hashing function like SHA-512 (HMAC-SHA512), convert both the ciphertext and the MAC to base-64, and put them in a printable string. Am I vulnerable to some security attacks if I use the outcome to authenticate users on a web application? Or is just "not nice"?

This just doesn't follow the dogma of JavaScript and JWT cultists.  I would say it is not nice for JWT to inflict misbegotten cryptographic disasters on the world in the name of…overengineering or something.

That said, while AES-CBC/HMAC-SHA256 in encrypt-then-MAC composition using randomly chosen IVs is generally OK, you should be careful composing primitives this way, especially ones with sharp edges like AES and CBC:

Do not touch anything before you have verified the authenticator (in constant time!).  It may be tempting to have one function to decrypt the message, and another function to verify the authenticator, and hope that downstream users will do both—but this is a disaster waiting to happen.  Make one function that either verifies and decrypts, or fails altogether without divulging any plaintext.  Unauthenticated data is pure evil—don't touch it!
Pay close attention to security contracts; note that CBC and GCM are different types of thing.  You are evidently aware of the importance of authentication, which is good—I am emphasizing this just because your parenthesis seemed to compare CBC and GCM directly, which is apples-to-oranges because they have totally different security goals; while encrypt-then-MAC with AES-CBC and HMAC-SHA256 is a more similar type of thing to AES-GCM in that they have the same security goals and differ only in usage requirements (and size of authenticator).
If you're having a sequential conversation, AES-GCM is may be a better option than AES-CBC/HMAC-SHA256 if it is simpler to use: you can safely use the number of messages you have sent so far as the nonce, and have the receiver require that number to be the nonce.  This enables the receiver to quickly drop forgeries on the floor, and which ensures that a large class of insecure implementations will immediately fail to interoperate rather than silently leak secrets.

(When AES-GCM was introduced to TLS in RFC 5288, they made the mistake of allowing arbitrary sender-chosen nonces; TLS 1.3 in RFC 8446 fixed this mistake so that broken implementations will fail fast and noisily.)
If counting is hard because of, say, VM state rollbacks, random IV generation might be hard too for the same reason.  If this is relevant, you may want to use a SIV-type scheme, synthetic IV, like AES-SIV, which chooses the IV as a pseudorandom function of (an optional nonce and) the message; at worst, if you repeat a nonce, the adversary can tell whether the whole message was repeated or not.
Make sure to generate known-answer test vectors for the whole AES-CBC/HMAC-SHA256 composition that you can automatically do self-tests with.
AES invites timing attacks unless you can guarantee all the way down your software stack that you're using hardware support for it like AES-NI.  It can be computed in constant time software, but it's very slow to do so.  Alternatives like  Salsa20 in the the authenticated cipher NaCl crypto_secretbox_xsalsa20poly1305 do not have this flaw.  Of course, I don't know how easy it is to use anything other than AES in your software stack; if the tradeoff may be between using AES here and throwing up your hands and giving up on security, maybe AES is OK.

Side note:

  I understand that signatures make it impossible for the tokens to be modified.

There are two very different things that JWS conflates under the term ‘signature’, which makes for exceptionally bad API design.

Signatures enable anyone who knows a public key to verify a message, but only the owner of the private key can sign messages.

Signatures are verifiable by a third party, and so are useful as an adversarial audit trail—if you claim to an arbitrator that a vendor stole your money, but they can present the check to the arbitrator, the arbitrator can verify it to determine that you're lying.

Signatures are relatively expensive to compute, costing hundreds of thousands of CPU cycles per message.
Authenticators or message authentication codes (MACs) allow anyone who knows a secret key to verify or authenticate messages.

Authenticators are not verifiable by third parties—if Bob shows Charlie a message he claims Alice sent him, the putative authenticator from Alice doesn't mean anything because Bob could have forged it too.

Authenticators like Poly1305 can be some of the cheapest cryptographic primitives ever, costing under one cycle per byte.  (HMAC-SHA256 is nowhere near the fastest authenticator but it is still much faster than public-key signature.)


Does the size of a ECDSA key determine the hash algorithm? I am a bit lost in understanding what I read on authentication, signature, etc. For instance, is the size of the ECDSA keys produced by ssh-keygen -t ecdsa -b 256 linked to the hash used (SHA256) when computing the signature?

No, in general the hash isn't determined by the curve definition by NIST. Reasonable mappings of course exist (for a 224 bit curve you would probably use a hash with output size of 224 such as SHA-224). The hash used should however be specified by the protocol itself.

The ECDSA key size as indicated by the -b of the openssh argument is linked to the hash algorithm used. This is defined in section 6.2.1 of the RFC 5656:

  The Elliptic Curve Digital Signature Algorithm (ECDSA) is specified
     for use with the SSH ECC public key algorithm.

  The hashing algorithm defined by this family of method names is the
     SHA2 family of hashing algorithms [FIPS-180-3].  The algorithm from
     the SHA2 family that will be used is chosen based on the size of the
     named curve specified in the public key:

+----------------+----------------+
|   Curve Size   | Hash Algorithm |
+----------------+----------------+
|    b <= 256    |     SHA-256    |
|                |                |
| 256 < b <= 384 |     SHA-384    |
|                |                |
|     384 < b    |     SHA-512    |
+----------------+----------------+

Note that currently you can only use the P-256, P-384 and P-521 (secp256r1, secp384r1 and secp521r1) prime curves defined by NIST in SSH. So the argument for the bit size also determines the domain parameters used.


Reason for DES table representation Currently in college I'm learning about DES, and everywhere I look the table S-boxes are represented as follows:

S1  x0000x  x0001x  x0010x  x0011x  x0100x  x0101x  x0110x  x0111x  x1000x  x1001x  x1010x  x1011x  x1100x  x1101x  x1110x  x1111x
0yyyy0  14  4   13  1   2   15  11  8   3   10  6   12  5   9   0   7
0yyyy1  0   15  7   4   14  2   13  1   10  6   12  11  9   5   3   8
1yyyy0  4   1   14  8   13  6   2   11  15  12  9   7   3   10  5   0
1yyyy1  15  12  8   2   4   9   1   7   5   11  3   14  10  0   6   13

Is there any reason at all why this table is set up like this? Why not with the last two bits as row and the first 4 as column? Or even as a single row with the number as identifier, as I seem to have managed to do in a spreadsheet here (see A39:D103 for a single-index list)?

It demonstrates that for any fixed value $(x_1,x_6)=(a_1,a_6)$ of the first and last input bits, $$S(a_1,x_2,x_3,x_4,x_5,a_6)$$ forms a permutation as $(x_2,x_3,x_4,x_5)$ ranges over
 $\{0,1\}^4$ thus giving structural information about the DES
S boxes.


How would low-precision Gaussian sampling impact the security of BLISS? For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and StrongSwan, I used 32-bit floating-point pre-computed constants instead of integer arrays, which I assume will be available on my targeted platforms.
And the picture shows 16384 iterations of accumulative sampling distribution image of my BLISS-I sampler preset.

In essence, my questions are:

How will low-precision Gaussian sampling impact security or anything?
And is using 32-bit floating-point a bad idea in cryptographic sampling?

Note the peak singularity in the picture is due to horizontally scaling before shifting and arithmetic performed rounding towards zero, not an error in the implementation. (And the image generation algorithm has been modified)

The purpose of Gaussian sampling is to prevent the signature from leaking information about the product of the secret key and the callange, and the better quality the samples, the better security.

As we know, the reason NTRUSign is broken is because it's not zero-knowledge. When you sign about 400 messages with the same key-pair, the distribution of the signatures roughly makes up a (high-dimension) cube whose edges follows that of the secret key vectors.

The same would apply to BLISS if attacker would be able to statistically distinguish bad signatures from good discrete Gaussian. The attacker would then draw a rough picture of Sc - challenge multiplied by secret vectors, then take challenge out of the equation there by recovering the secret private key.

This is why we need to calculate some transcendent functions to high precisions to perform Gaussian and rejection sampling.

I'll soon update this answer once I've learned more from references such as this about how much precision is needed to achieve full and/or practical zero-knowledge.

Also, the distribution of signature polynomials z1 and z2 are Gaussian after rejection sampling, where as I generated Huffman coding table for the pre-rejection distribution as of the 2016-09-15 release. Obviously I did not fully understand the rejection sampling process.

Based on this, I did the following calculation:

$ awk "BEGIN { s = sqrt(2*${pi})*215 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
538.925079, 29.944378,
39.452107
$ awk "BEGIN { s = sqrt(2*${pi})*107 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
268.209225, 26.924290,
39.375418
$ awk "BEGIN { s = sqrt(2*${pi})*250 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
626.657069, 30.597140,
39.467662
$ awk "BEGIN { s = sqrt(2*${pi})*271 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
679.296262, 30.946228,
39.475846
$

Looks like 40-bit precision might do for now.


Why do we use encryption modes of operation to convert block ciphers into stream ciphers? Just wondering Why to use encryption modes of operation to convert block ciphers to stream ciphers?

A block cipher in itself can - as the name implies - only transform one block. The ECB mode, which is basically the reapplication of the block cipher for each plaintext - is insecure, as it leaks information about the plaintext. The reason for this is that repetition in the plaintext blocks would lead to repetition in the ciphertext blocks. Block ciphers are deterministic, i.e. given a key and plaintext block as input they will always generate the same output.

So we need to have a mode of operation to convert fewer or more bytes than the block into ciphertext and back again. This mode needs to be non-deterministic. For this reason an Initialization Vector needs to be used. The IV makes sure that we never have the same ciphertext block even when encrypting multiple plaintext messages. We also like the property of the mode of operation to be online: it can process plaintext data when it becomes available, and the data size doesn't need to be known in advance.

There are basically two block modes of operation: ECB and CBC. ECB has already been discussed, it's just the reapplication of the block cipher over consecutive plaintext blocks. CBC uses the IV and then the ciphertext as vector for the next block encryption. As CBC still operates on blocks it cannot handle randomly sized plaintext. For this CBC needs to be paired with either a padding mode of operation or ciphertext stealing. Ciphertext stealing however isn't completely generic; it requires at least one block of plaintext. Padding modes open up the ciphertext to padding oracle attacks. Finally CBC also requires an unpredictable IV.

A stream cipher (mode of operation on a block cipher) has the nice property that it is secure and it can handle single bits or bytes at a time. It is online, which means that it is always ready to process data. Because it operates on bytes it doesn't require a padding mode. They generally just require a unique IV.

A stream cipher may offer more advantages such as being able to encrypt/decrypt in the middle of the stream, to use the cipher only in encrypt/decrypt mode and to pre-compute the key stream used for encrypting /decrypting the plaintext. Counter mode (CTR or SIC mode, to use a specific term) offers all of these advantages.

So basically we need a block cipher mode of operation to be able to encrypt / decrypt messages of any size and any content without opening ourselves to attack. And stream ciphers have nice properties that make them more applicable / secure for many problems.

CTR mode is used as underlying mode of operation for many AEAD (authenticated cipher modes) because of these properties. CTR mode is part of GCM, CCM and EAX modes of operation and even for SIV (which uses a deterministic IV which doubles as an authentication tag).


Secure AES IV with static salt I have an (offline) shared secret key (symmetric) which is used to encrypt/decrypt data.
Now this data belongs to a specific user which is known on the backend and frontend. My idea was to use the username/id as salt. But for AES we only have the iv.
Doing this would make sure that the data on the frontend can only be encrypted if the correct user is logged in, because without the correct salt/iv. The data would be nonsense.
But this iv would not be random anymore.
So do you have a suggestion for me on how to deal with the problem? Also, the secret key and the username/id is the only thing both endpoints know.

You did not mention the mode of operation for any block cipher that is necessary.

CBC mode requires the IV random and unpredictable so this is not your way.

CTR mode requires an $(IV,Key)$ pair never occurs more than once. One must never use the same $(IV,key)$ pair again, otherwise, confidentiality is lost.
CTR mode generally uses 96-bit nonce and 32-bit counter to form the Initial value. If the nonce reoccurs and counters repeat then these blocks can be revealed with crib-dragging. The nonce can be chosen randomly that will have a 50% probability of collision after $2^{48}$ random nonce generation. Counter/LFSR-based nonce generation is also recommended by NIST.

CTR mode can be a solution for you.
The above modes don't provide you more than confidentiality. We can, and we should go more;

GCM provides you confidentiality, integrity, and authentication. Since GCM uses the CTR mode for encryption, you will have the same (IV, key) reuse problem.
If the IV has 92-bit length then $J_0 =IV || 0^{31} ||1$ is passed to the CTR mode as the IV where the 32 bits is used as a counter which starts  form $1$. SO if you reuse the same IV under the same key, you will have the same problem in the CTR mode.

XChaCha20-poly1305 is ChaCha20 with an extended nonce that we can use random nonce more securely. It has 192-bit nonce sizes and one has a collision with 50% probability once generates $2^{96}$ random nonces under the same key. Though this has the same $(IV,key)$ problem the probability of getting it is not-going-to-happen.

There is also AES-GCM-SIV mode. This is nonce-misuse resistant and even the IVs are the same the mode will only leak that the messages are the same. This requires additional passes over the data.

Therefore, one can use AES-GCM-SIV to mitigate all possible problems or use xChaCha20-poly1305.
For the user, you should note that the IV/nonce of the encryption is never meant to be secret. They can be stored, usually prepended, with the ciphertext. During the client-side encryption, they can be created. Therefore the user doesn't need to know anything about the IV/nonce after the encryption, the server can store them with the ciphertext. The user only needs the secret key and must keep it secret all the time.


how to calculate the average key search for AES-128bit? Assume that an attacker has a special purpose application specific
  integrated circuit (ASIC) which checks $5\times 10^{8}$ keys per second, and she has a budget of $\$1$ million.
  One ASIC costs $\$50$, and we assume $100\%$ overhead for integrating the ASIC (manufacturing the printed circuit boards, power supply, cooling, etc.).

  How many ASICs can we run in parallel with the given budget?
  How long does an average key search take? Relate this time to the age of the Universe, which is about $10^{10}$ years.

I know that we can run $20\ 000$ ASICs with ONE million budget, but I don't understand how to calculate the average key search, is it $2.5 \times 10^{19}$?

Since key search is "embarrasingly parallel", i.e., you can have different ASICs searching different parts of the key space, you have $$20{,}000\approx 2\times 10^{11}$$ processors and the keyspace is of size $2^{128}$.
There are $$3600\times 24\times 365.25\approx 2^{24.9}$$ seconds in a year so you can check $$2^{11} \times 2^{24.9} \times 2^{28.9}\approx 2^{64.8}$$ keys per year, the last factor being $2^{28.9}\approx5\times 10^8$. So this gives
$$ 2^{127} \times 2^{-64.8} =2^{62.2}\approx 10^{18.72} \approx 5.25 \times 10^{18}$$years if I haven't made a mistake somewhere.

Also I interpreted your

  can search 5.108 keys per second

as $5\times 10^8.$

Edit: Fixed computation. Thanks, @dave_thompson_085


Affine cipher: calculate the key from a known plaintext/ciphertext pair Suppose I have a ciphertext that I know is encrypted using an affine cipher in $\mathbb{Z}_{26}$. The plaintext begins with es and the corresponding ciphertext is FX. How can I calculate the key?

Given that you have parts of the plain text and its corresponding ciphertext, this is called a known plaintext attack.

Given an affine cipher that has a key that is composed of 2 parts $a$ and $b$, you can express it as a system of 2 equations with 2 unknown.
Assuming the usual mapping $\mathtt{a} \to 0$, $\mathtt{b} \to 1$, etc., you need to solve the following system of linear equations:
$$\left\{ \begin{array}{l}
4a+b = 5 \\
18a+b = 23 \end{array}\right.$$
where the encryption function is $x \mapsto ax+b$. Solve it exactly as you would in $\mathbf{R}$, just be careful when dividing.


What is the relation between computational security and provable security? I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security.

  Let $(E,D)$ be an encryption scheme that uses $n$-bits keys to encrypt $l(n)$-length messages. $(E,D)$ is computationally secure if
  $$E_{U_{n}}(x_{0}) \approx E_{U_{n}}(x_1)$$

And then it introduces the secure game (e.g. CPA, CCA)? I think it is a part of provable security.

"Unconditional security" (or "information-theoretic security" or "perfectly secrecy") and "computational security" are two opposite classes of security.
But I do not think "computational security" and "provable security" are two independent classes of security. I know that computational security emphasizes the power of attacker is bounded (polynomial-time algorithm). And the provable emphasizes the mathematical assumptions or cryptography primitives. But it also related to the computational power.

‘Provable security’ just means there is a theorem.  It is a misleading term of art that should be carefully restricted to the literature if used at all, because it gives people false confidence: a system can have ‘provable security’ in the sense that there is a theorem, and could be completely breakable.  There are different kinds of theorems, but let's focus on whether there is a theorem or not and walk through some examples of provable vs. conjectured security.

Why do we think it is difficult to find $x$ given $y = x^3 \bmod{pq}$ when $p$ and $q$ are independent uniform random 1024-bit primes and $x$ is a uniform random nonnegative integer below $pq$?

Some of the smartest cryptanalysts on the planet have been banging their heads against this problem for nearly half a century, and have only a consistent track record of failure to show for it.  Maybe tomorrow someone will find a way to do it: we haven't ruled it out.  For example, if they found a way to factor $pq$, they could easily compute $y^d \bmod{pq}$ where $d$ solves $$3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}.$$  Indeed, with unlimited budget or a quantum computer they could do this easily.
This is the RSA problem, with computational conjectured security.  Of course, this system is not directly useful for applications, because most applications don't naturally deal in random 1024-bit primes or uniform random ‘messages’ modulo a product of 1024-bit primes.  It is primarily a building block for practical cryptosystems.

Why do we think it is difficult to find $m$ given $m + p$ for $m, p \in \operatorname{GF}(2^t)$, when the distribution on $p$ has statistical distance $\varepsilon$ from uniform and $m$ has any distribution?

There is a theorem that the distinguishing advantage of any decision algorithm, that is the probability beyond 1/2 of guessing uniform random $b$ given $m_b + p$ for any choice of $m_0, m_1$, is bounded by $\varepsilon$.  No breakthroughs in cryptanalysis can change the result—any failure of security is guaranteed to be a consequence of pad reuse or poor pad generation.
This is a formulation of the one-time pad theorem, with information-theoretic provable security.  Of course, this system is not directly useful for applications, because you need a method to choose $p$ from a space as large as your space of possible messages, and do it independently for every message.  It is primarily a building block for practical cryptosystems.

Why do we think it is difficult to find $m$ given $(x^3 \bmod{pq}, m + H(x))$ where $x$ is a uniform random secret, $p$ and $q$ are uniform random secret 1024-bit primes, and $H$ is a uniform random public function?

There is a theorem, using the one-time pad theorem in (2) as a lemma, that if there is a decision algorithm with distinguishing advantage $\varepsilon$ against this system, then there is an algorithm that recovers $x$ from $x^3 \bmod{pq}$ with high probability; in other words, if the RSA problem of (1) is hard, then decrypting $(x^3 \bmod{pq}, m + H(x))$ to recover $m$ is hard.  As in (1), breakthroughs in cryptanalysis could lead to factoring $pq$ to break this; similarly, since we're using the random oracle model breakthroughs in cryptanalysis of the specific hash function we choose for $H$ could break this.
This is a weaker version of RSA-KEM/DEM, with computational provable security.  The if/then structure of this theorem, using the one-time pad lemma to prove it, enables cryptanalysts to focus their effort on the RSA problem, rather than dividing effort between the $(x^3 \bmod{pq}, m + H(x))$ problem, the RSASSA-PSS problem, the RSA-KEM problem, etc.  Of course, this system is not actually secure in a practical sense; you want a real DEM, which $m + H(x)$ is not—if you used this system, you would set yourself up for EFAILure.  And if anyone solved the RSA problem, this would still have computational provable security; the theorem would just be vacuous!

Why do we think it is difficult, given a message $m \in x\cdot\mathbb F_q[x] \setminus \{0\}$ and its authenticator $a = m(r) + s$ for uniform random $r, s \in \mathbb F_q$ and $q$ a prime power, to find another message/authenticator pair $(m', a')$ also satisfying $a' = m'(r) + s$?  (Here we are interpreting a message as a polynomial over the field $\mathbb F_q$ with zero constant term, e.g. by breaking it into $({\leq}\log_2 q)$-bit chunks and injecting them into $\mathbb F_q$ as coefficients.)

There is a theorem that $$\Pr[a' = m'(r) + s \mid a = m(r) + s] \leq \ell/q,$$ where $\ell$ is the maximum length of a message.  In other words, the one-time forgery probability is bounded by $\ell/q$.  As with the one-time pad theorem in (1), no breakthroughs in cryptanalysis will change this theorem.
This is a universal hashing one-time authenticator, with information-theoretic provable security.  Of course, this works only for a single message, so this is mainly useful as a building block for practical cryptosystems like crypto_secretbox_xsalsa20poly1305 or AES-GCM.  And, of course, the security depends on the choice of parameters: the theorem is still true when $q = 2$, but a forgery probability bound of 1/2 is not very secure!


how to use AES block cypher when there are only 47 byte space? If I have only 47 byte for encrypted data, and want to use AES block cypher, is there a method that I could make full use of them, or if I could only use 32 bytes of them, since the block should be multiple of 16 byte?

This is what a block cipher mode of operation is for:

  ...  A block cipher by itself is only suitable for the secure cryptographic transformation (encryption or decryption) of one fixed-length group of bits called a block.2 A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.[3][4][5]

You might consider:

Using an authenticated mode of operation such as GCM
Offload all the work to an existing library for whatever your purpose is (PGP for data at rest or TLS for data in transit), which will handle all of these details for you.


Is XTS basically the cheapest form of (secure) double-encryption? XTS, as given by the below equation, is a mode of operation primarily targeting full-disk encryption scenarios.

By the way it works it also doubles the keylength although a meet-in-the-middle attack applies (by enumerating all the whitening values). However one only needs to calculate the whitening value once per sector.

So is there any way to break XTS or a double application thereof in less time and/or space than expected?

The expected time for standard XTS is time $2^{512}$ for 256-bit AES and $2^{513}$ time and $2^{512}$ space for double encryption.

Relation to the title:
XTS is the most well-known / used scheme for turning a 256-bit cipher into a 512-bit mode. It does this in such a way that each block requires merely one finite field multiplication and one encryption operation and every few blocks (e.g. 32+) require one additional encryption operation which means it should be a very "cheap" way of doing double encryption. So the question: Is this as good as it sounds?

The equation as documented by VeraCrypt:

$$C_1=E_{K_1}(P_1\oplus(E_{K_2}(n)\otimes\alpha^i))\oplus(E_{K_2}(n)\otimes\alpha^i)$$

with $C_1$ being the ciphertext, $P_1$ being the plaintext, $K_1$ and $K_2$ being the keys, $n$ being the sector index, $i$ being the block index within the sector, $\oplus$ denoting bitwise XOR, $\otimes$ denoting multiplication in the binary Field $GF(2)\bmod x^{128}+x^7+x^2+x+1$ and $(E_{K_2}(n)\otimes\alpha^i)$ being called "the whitening value".

Justification of the expected time / space values:
Single Encryption case:
This is essentially "single-key" XEX, providing 256-bit security combined with a 256-bit keyed permutation, one needs $2^{512}$ to find the correct whitening key and the correct permutation.
Double Encryption case:
Standard meet-in-the-middle attack: Enumerate all the possible intermediate values ($2^{512}$ time and space) and then try decrypting all the ciphertexts with all possible keys, looking for intermediate matches.

So is there any way to break XTS or a double application thereof in less time and/or space than expected?
The expected time for standard XTS is time $2^{512}$ for 256-bit AES and $2^{513}$ time and $2^{512}$ space for double encryption.

Yes, there are better attacks than that.
With XTS a single sector is encrypted with a single $E_{K_2}(n)$ value, so the attacker can treat it as constant. It is only 128 bits, so a brute force attack can find both it and the AES key $K_1$ in about $2^{384}$ time. Once the attacker knows $K_1$, they can separately, given multiple sectors, attack the key $K_2$ in negligible time compared to the first step.
A meet-in-the-middle attack applies on double XTS as normal, in about $2^{385}$ time and $2^{384}$ space.
Note that with AES-128 the above would not be the case, since $K_1$ is the same size as the block, so a brute force takes $2^{256}$ time regardless of whether you are looking for the key or the encryption of the sector index.
There are of course other weaknesses that have to do with the fact that it is deterministic and lacks authentication. You can look at it as a sector sized cipher in ECB mode, if the attacker can see multiple ciphertexts for the same sectors. Any random string is a valid ciphertext, due to the absence of authentication or even padding.
XTS should not be used as general purpose encryption when IVs and authentication can be used.


How to Distribute the Shares using Secret Sharing for arbitrary Monotone Access Structures Consider 4 people, $A$,$B$,$C$,$D$, & a secret $s\in\{0,1\}^k$. Construct a scheme
which enables the following subsets of people to retrieve the secret $\{A,B\}$, $\{A,C\}$, $\{B,C,D\}$.

I know that we can use Shamir's secret sharing scheme to do so, and A should be allocated more shares than the others. But how do we do the allocation when given an arbitrary monotone access structure?

I will make a start by observing that not every monotone access structure can be realized by means of $(t,n)$ threshold secret sharing (here we require $t$ out of the $n$ shares need to be available for reconstruction).

First let us define a monotone access structure. Let $P$ be a set of participants. An access structure $\Gamma$ is a collection of nonempty subsets of the power set $2^P$. This structure is called monotone, if $X\in \Gamma$ implies $Y\in \Gamma$ for all supersets $Y\supseteq X$.

Note that defining monotone access structures perfectly makes sense in context of secret sharing, since every set in the access structure can reconstruct the secret, so every superset containing this set can trivially do so.

Shamir does not provide a general solution

Let us construct a counterexample for threshold secret sharing:

Consider the set of participants $P=\{A,B,C,D\}$ and a monotone access structure $\Gamma=\{\{A,B\},\{C,D\}\}$. We assume we use a $(t,4)$ threshold scheme to share a secret $k$ among the
participants $A,B,C,D$ and $k$ can only be reconstructed by subsets which are elements of $\Gamma$.

Now let $a,b,c$ and $d$
be the weights of the shares that are assigned to the users of $P$. Then it must hold that $a+b\geq t$ and $c+d \geq t$, where $t$ is the threshold.

WLOG let $a\geq b$ and $c \geq d$. Since

$a+b\geq t$ and $a\geq b$ we have $a+a\geq a+b \geq t$ which gives that $a\geq t/2$.
Furthermore, since $c+d\geq t$ and $c\geq d$ it follows that $c\geq t/2$.

This implies that $a+c \geq  t$ and thus $A$ and $C$ are able to reconstruct $k$, but $\{A,C\}\notin \Gamma$.

Towards secret sharing for monotone access structures

Ok, now we go on to realize secret sharing for general monotone access structure. Let $P=\{P_1,\ldots,P_n\}$ be the set
of participants.
We need some definitions first:

Minimal authorized subset: Let $\Gamma$ be an access structure then
 ${\cal C}\in \Gamma$ is a minimal authorized subset if $H \notin \Gamma$ whenever $H\subset {\cal C}$ (i.e., whenever we remove a participant, then the set will no longer be authorized).

Now we call the set of minimal authorized subsets associated to $\Gamma$ a basis and
 denote it by $\Gamma_0$. And it is sufficient to work with the basis henceforth (as $\Gamma$ can be obtained by taking the closure, i.e., by monotonicity).

If we look at a $(t,n)$ threshold scheme, then we have $\Gamma = \{G \subseteq P : |G|\geq k\}$
 and $\Gamma_0 = \{G \subseteq P : |G| = k\}$.

Maximal unauthorized subset: Let $\Gamma$ be an access structure and call  $M=\{{\cal B}_1,\ldots,{\cal B}_m\}$
 the set of maximal unauthorized subsets if for every ${\cal B}_i$ holds: ${\cal B}_i\notin \Gamma$
  and ${\cal B}_i\cup P_j\in \Gamma$ for each $P_j\notin {\cal B}_i$ (i.e., whenever we take a participant that is not
  yet included we will obtain an authorized set)

Now we can define a dual representation of an access structure $\Gamma$ denoted as $\Gamma^*$.

We can write an access structure $\Gamma = \bigvee_{{\cal B}\in \Gamma} \bigwedge_{P_i\in \cal B} P_i$ or as a sum of products
  (replacing conjunctions by $\cdot$ and disjunction by $+$).

Then the dual access structure is obtained by exchanging the operators,
 i.e., $\Gamma^* = \bigwedge_{{\cal B}\in \Gamma} \bigvee_{P_i\in \cal B} P_i$ (or as a product of sums).

We have the following: Let $\Gamma$ be an access structure on $P$ and $M=\{{\cal B}_1,\ldots,{\cal B}_m\}$ the
 set of maximal unauthorized subsets, then $\Gamma_0^*=\{{\cal A}_1,\ldots,{\cal A}_m\}$ such that ${\cal B}_i=P\setminus {\cal A}_i$
 is the set of minimal authorized subsets in the dual form.

Ok, let us take additive perfect secret sharing over a prime field $Z_p$, i.e., the secret $k$ is represented $k=\sum_{i=1}^m s_i \pmod p$ for random
 $s_i$.

Then we can come up with the following matrix, where we have $b_{i,j}=1$ if $P_i\in {\cal A_j}$ and $b_{i,j}=0$ otherwise.

Now, we can distribute
 the shares $s_1,\ldots,s_m$ in the following way. Every user $P_i$ obtains the set of shares $S_i=\{s_j: b_{i,j}=1\}$ (i.e., a participant obtains a share if he shows up in the respective set of the dual basis or equivalently, obtains no share if he shows up in the respective set of the maximal unauthorized subsets).

I will not come up with an explicit example anymore today. But this secret sharing enables every authorized subset in $\Gamma$ to reconstruct the secret $k$ and any non-authorized set will not be able to do so.