How to encode and decode message into polynomial form on NTRU This question is based on a previously asked question. How to make a message into a polynomial on NTRU encryption?
I am tasked to implement NTRU with toy parameters such as $N=7$ or $N=11$ and I have some questions.

Does the message length have to be smaller than or equal to the parameter $N$? Can I do encryption on a message larger than parameter $N$ or do I have to break them up?
One method mentioned was to convert the message into ASCII and then ternary form and then add them up to be the input as follow:

h 01101000 X^3+X^5+X^6
e 01100101 1+X^2+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
o 01101111 1+X+X^2+X^3+X^5+X^6
w 01110111 1+X+X^2+X^4+X^5+X^6
o 01101111 1+X+X^2+X^3+X^5+X^6
r 01110010 X+X^4+X^5+X^6
l 01101100 X^2+X^3+X^5+X^6
d 01100100 X^2+X^5+X^6

However, in this case, how do I decrypt the message given that the decrypted message would be the addition of all the polynomials? Or do I have to encrypt and decrypt each letter separately?

NTRU operates on the ring $R = \mathbb Z[x]/(X^N -1)$. Therefore all parameters must be lie in this polynomial ring.

1.Does the message length have to be smaller than or equal to the parameter N? Can I do encryption on a message larger than parameter N or do I have to break them up?

That really depends on the encoding. The linked example suggested using binary encoding. In this case, if ASCII is used then you can encode it with degree 7 polynomials. Therefore, if your $N =7$ then you cannot encrypt more than one ASCII character. You have to divide your message character by character to encrypt, assuming that you are using ASCII characters for your messages.
Other encodings are possible like ternary $\{-1,0,1\}$, however, for simplicity keep the binary at the beginning.

However, in this case, how do I decrypt the message given that the decrypted message would be the addition of all the polynomials? Or do I have to encrypt and decrypt each letter separately?

You have to encrypt each of them separately. Note that the example is not ternary encoding it is the binary encoding. Check them like this;
$$ \texttt{h 01101000} = \color{red}{1}\cdot X^6 + \color{red}{1}\cdot X^5 + \color{blue}{0}\cdot x^4  + \color{red}{1}\cdot X^3 + \color{blue}{0}\cdot x^2 + \color{blue}{0}\cdot x^1 + \color{blue}{0}\cdot x^0$$
In ternary, actually, one expects to see some $-1x^i$ at least in some of the encodings if one doesn't select all of them deliberately not including the $-1$.

The below is a sample SageMath code for encoding a character into a polynomial. The full code running with the NTRU encrypt/decrypt is at GitHub.
Zx.<x> = ZZ[]

def encodeASCIIToPolynomial(c):

    C = ord(c)
    M = 0
    i = 0
    while(C > 0):
        M = M + x^i*(C %2)
        C = C//2
        i += 1
    return M

def decodePolynomialToASCII(D):

    x =0
    for t in D:
        x = x + t
        x = x *2
    return x

message = 'Z'
print("Message to Encrypt            ", message)
m = encodeASCIIToPolynomial(message)
print("Message encoded to Polynomial ", m)
print("Decoding back to character     ",chr(decodePolynomialToASCII(m)))


Secure function evaluation for Boolean formulae Under the assumption that "secure" encryption exists, secure evaluation of functions represented by Boolean circuits is possible by  Yao's garbling scheme [Y1]. My question is whether secure evaluation of functions represented by Boolean formulae is an easier problem (i.e., possible in the information theoretic setting).

(This is true, for example for secret sharing: Benaloh and Lichter [BL] gave an perfect scheme for access structures described by monotone Boolean formulae, but for monotone Boolean circuits one needs to assume secure encryption [Y2].)

References:

[BL]: Benaloh and Lichter. Generalized secret sharing and monotone functions. Crypto’88

[Y1]: Yao. How to generate and exchange secrets. FOCS’86.

[Y2]: Yao. Protocols for secure computations. FOCS'82

For log-depth circuits, it is possible to use an information-theoretic version of Yao's garbled circuits. Note that in a garbled gate, each key is used to encrypt twice. Thus, if the keys on the input wires are double the length of the keys on the output wires, then one-time pad encryption can be used and the result is information theoretically secure.

See the paper Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation by Vlad Kolesnikov, and references within.


KDF vs Stream Cipher I was wondering why someone would go and use HKDF (or any KDF) when they can use a stream cipher instead.

It seems like a stream cipher will always be one-way, whereas a KDF might not be (see AES or DES key schedules for example). So using a KDF might be dangerous if you use it to both derive public and private values (although it seems like the most used one, HKDF, is constructed to be one-way. Which is good since it is used in TLS to derive private keys as well as public IVs).

I can see two reasons why a KDF might be of a better fit:

it takes a SALT parameter. So you can use it several times with the same key, but by varying the parameter you will get different output. If you would do that with a stream cipher you would need to remember a state.
it has a work factor. So with the SALT and that you can use it as a password hashing function. But then we're kind of off track.

But these two things don't seem to be specific to a KDF...

It seems like a stream cipher will always be one-way, whereas a KDF might not be (see AES or DES key schedules for example).

A KDF has nothing to do with DES or AES key schedules. Key schedules are internal functions of the block cipher, they aren't designed to be KDF's. And KDF's are certainly supposed to be one-way functions.

From SP-800 SP 108 chapter 7.1, Cryptographic Strength:

  The security strength of a key derivation function is measured by the amount of work required to distinguish the output of the KDF from a truly uniformly distributed bit string of the same length, under the assumption that the key derivation key, $K_I$ [ed: the input keying material], is the only unknown input to the KDF.

  So using a KDF might be dangerous if you use it to both derive public and private values.

The output of a KDF should be indistinguishable from random, so this statement is false - which has probably to do with your statement that they may not be one way.

  it takes a SALT parameter. So you can use it several times with the same key, but by varying the parameter you will get different output. If you would do that with a stream cipher you would need to remember a state.

Salts are used to further strengthen the security proof for HKDF. In SP 108 they can be part of the Context and are then called a Nonce (and, given that the salt is large enough, random salts are unique in a computational sense). A random IV would do the same thing for a stream cipher.

Salts are not required for key based KDF's as the input keying material should provide enough entropy.

But I think you are mixing up key based KDF's such as HKDF and password based KDF's such as PBKDF - see below.

  it has a work factor. So with the SALT and that you can use it as a password hashing function. But then we're kind of off track.

A work factor is only needed if the input material is not strong enough. This is basically the case for password-based KDF's such as PBKDF2, bcrypt, scrypt and Argon2. The work factor is used to strengthen the input keying material (somewhat).

Counter mode encryption doesn't explicitly contain any ways of inputting labels, salts or context. A KDF construction makes these explicit.

With regards to the output, a KDF can be used with different info (label / context) to generate different keys, using the same input keying material. This is important if you integrate such a function in e.g. a HSM (security token), where you want to keep the output as key within the token (instead of splitting it up manually in software).

Finally, many KDF's contain not just expand functions to generate enough output keying material, they also contain extract functionality to compress the entropy in the input keying material. Many stream ciphers require keys that are indistinguishable from random and/or a specific length. So they don't provide extract functionality.

A KDF is build from PRF's; a PRF provides the required security to create proofs for the KDF. Actually, counter mode is often used for KDF's, but they employ a PRF instead of a PRP such as a block cipher (of course the PRF may be created out of a block cipher itself). So in the end many KDF's do output a stream of pseudorandom bits.


Question about Novotney's paper on Weak Curves This is the paper - https://wstein.org/edu/2010/414/projects/novotney.pdf
In Section 2.1
I see 2 chunks of code/commands in SageMath
sage: #Group Order Compare SLOW
sage: m = 21345332
sage: p = 4516284508517
sage: E = EllipticCurve(GF(p), [7,1])
sage: Q = E.gens()[0]
sage: mQ = m*Q;
sage: print E.order().factor()
sage: time mRec = PolligHellman(Q,mQ)
sage: print mRec
11 * 13 * 31582419389
Time: CPU 49.14 s, Wall: 49.14 s
21345332

sage: #Group Order Compare FAST
sage: m = 21345332
sage: p = 4516284508517
sage: E = EllipticCurve(GF(p), [7,1])
sage: Q = E.gens()[0]
sage: mQ = m*Q;
sage: print E.order().factor()
sage: time mRec = PolligHellman(Q,mQ)
sage: print mRec
2^3 * 19 * 23 * 67 * 2089 * 18913
Time: CPU 0.16 s, Wall: 0.16 s
21345332

E seems to be the same in both cases - but E.order.factor() is different. How can that happen?
I see this pdf referred to here also - http://koclab.cs.ucsb.edu/teaching/ecc/project/2015Projects/Sommerseth+Hoeiland.pdf
From Page 3

the article ”Weak Curves InElliptic Curve Cryptography” written by
Novotney.He looks at the elliptic curve E:y2=x3+ 7x+ 1and Galios Field
over prime p= 4516284508517: When the order of the
point P is 4516285972627 it has the prime factors 11·13·31582419389.
Solving the ECDLP with Pohlig-Hellman takes 49.14 seconds.
When the order of the point P is 9254332285624 it has the prime
factors 2^3·19·23·67·2089·18913.
Solving the ECDLP  with the same Pohlig-Hellman code takes 0.16 seconds.

9254332285624 = 2^3 * 19 * 23 * 67 * 2089 * 18913
So both are the same thing.
So - is it really E.order() or P.order()
How do I get the points which have the order 9254332285624 &
I tried this in sage
p = 4516284508517
E = EllipticCurve(GF(p), [7,1])
P = E.gens()[0]

print (E.order())
4516285972627

print (P.order())
4516285972627

How do I get the point for which the order is 9254332285624?

There is obviously missing information on both lecture projects. With a small try, I've found a curve with the required order.
If you set the field as the prime field $F_P$ where $p=9254331510119$, the curve
$$E(F_p) : y^2 = x^3 + 7x + 1$$
p = 9254331510119
E = EllipticCurve(GF(p), [7,1])
print(E.order().factor())

outputs
$$9254332285624 = 2^3 \cdot 19 \cdot 23 \cdot 67 \cdot 2089 \cdot 18913$$ as required.

Actually, I was lucky since I simply started 9254332285624-1000000  and I did not use the Hasse bound
$$|N - (q+1)| \le 2 \sqrt{q}$$ where $N$ is the number of point on the curve, here $N= 9254332285624$, and $q$ is the number of elements of the finite field, here we have the prime field $F_p$. With removing the absolute value we have this form
$$q+1-2{\sqrt q} ≤ N ≤ q+1+2{\sqrt q}$$
$$q+1-2{\sqrt q} ≤ 9254332285624 ≤ q+1+2{\sqrt q}$$
and calculating
$$9254332285625 - 4 \sqrt{2313583071406} \leq q \leq 9254332285625 + 4 \sqrt{2313583071406} $$
$$9254326201438 < q < 9254338369812$$
So, if you seek the primes in the above range ( possibly with a next_prime function of SageMath) you will definitely find your candidate primes, which are expected little ( exactly 407391 primes on this range) to satisfy the required curve order.

The SageMath code with Hasse Bound;
expected_order = 2^3 * 19 * 23 * 67 * 2089 * 18913

#This is specific to this order!
start = floor(expected_order - 4 * sqrt(expected_order/4))
end   = floor(expected_order + 4 * sqrt(expected_order/4))

p = start -1

primeCount = 0

for x  in range(start,end):
    p = p.next_prime()
    primeCount = primeCount + 1
    if p > end:
        break

    E = EllipticCurve(GF(p), [7,1])

    if E.order() == expected_order:
        print ( p)
        break

print("Finished")
print("Number of tested primes =", primeCount)

and the output;
9254331510119
Finished
Number of tested primes = 177222


Are there any advantages in using proprietary encryption? Proprietary software generally relies on the fact that in keeping the encryption algorithm private, it gets an extra layer of security implying "Security through Obscurity." Obviously this phrase has been hotly debated and surely is only acceptable if discovering the mechanics of a proprietary algorithm doesn't actually reduce it's security.

Is there any other reason you would use a proprietary encryption since my research has proven there to be many more disadvantages than advantages!

Yes, there are advantages to the attacker.

Using a well vetted encryption algorithm provides a better assurance of security. There may be cryptographic algorithm flaws and/or coding mistakes.

As noted, relying on the algorithm being private just adds a layer of false security.


Are there historical examples of Occam's Razor being useful to cryptography research? Previously, I asked what is the simplest digital signature scheme known, under the assumption simpler implementations could provide valuable insights on the nature of the problem.

  Among competing hypotheses, the one with the fewest assumptions should be selected. (...) In science, Occam's razor is used as a heuristic technique (discovery tool) to guide scientists in the development of theoretical models
  https://en.wikipedia.org/wiki/Occam's_razor

I specifically asked for implementations that didn't use number theory, because numeric operations (division, modulus) require some added complexity to implement in any "neutral" language that doesn't have numbers.

I received a plenty of negative comments claiming simpler schemes aren't proven to be secure, that simplicity is subjective and the general sentiment was that the question was pointless.

My question, thus, defies my own beliefs: has Occam's Razor ever proven useful for cryptography at all? Is there, for example, any historic occurrence of someone starting with a complex cryptographic scheme, looking from simpler solutions, and eventually finding answers that led to a better understanding of the problem itself?

The definition you cite says that "among competing hypotheses, the one with the fewest assumptions should be selected". If you take this literally and don't understand fewer assumptions as simpler, this principle is widely accepted in cryptographic research: Having a provably secure scheme means that it can be shown to satisfy some security definition under certain assumptions. If you propose a new scheme and prove its security under weaker (or less) assumptions than what was needed for previous schemes, this is considered to be a substantial contribution.

As an example, consider RSA. A necessary assumption for RSA to be secure is that factoring is hard. However, nobody has succeeded so far in proving that under that assumption, RSA is actually secure. There exist security proofs for (variants of) RSA, but they require additional assumptions. At Eurocrypt 2009, a paper [1] received the best paper award for proposing an encryption scheme that is provably secure assuming only that factoring is hard. That scheme is not simpler than RSA, but the hypothesis that it is secure can be based on fewer assumptions.

[1] Dennis Hofheinz, Eike Kiltz: Practical Chosen Ciphertext Secure Encryption from Factoring. EUROCRYPT 2009.


Size of Key Material of TLS_DHE_RSA_WITH_AES_256_CBC_SHA What is the size of key material required for generating MAC keys, encryption keys and IV when use TLS_DHE_RSA_WITH_AES_256_CBC_SHA ?
How to calculate it?

TLS_DHE_RSA_WITH_AES_256_CBC_SHA is

256-bit AES encryption
SHA-1 message authentication
Ephemeral Diffie-Hellman key exchange
Signed with an RSA certificate

We can find the answer in rfc5246

                        Key      IV   Block
Cipher        Type    Material  Size  Size
------------  ------  --------  ----  -----
NULL          Stream      0       0    N/A
RC4_128       Stream     16       0    N/A
3DES_EDE_CBC  Block      24       8      8
AES_128_CBC   Block      16      16     16
AES_256_CBC   Block      32      16     16

MAC       Algorithm    mac_length  mac_key_length
--------  -----------  ----------  --------------
NULL      N/A              0             0
MD5       HMAC-MD5        16            16
SHA       HMAC-SHA1       20            20
SHA256    HMAC-SHA256     32            32

Note 1: the values in bytes.
Note 2: This mode is archaic and exist in TLS since TLS1.0. You should stick to TLS 1.3 which has huge cleanup and has only 5 cipher suites and all use Authenticated Encryption with Associated Data (AEAD).


Interchangeability of hash outputs I'm looking at tweetnacl, its crypto_sign_keypair, crypto_sign, and crypto_sign_open functions modify and use the output of crypto_hash in various ways.

I would like to swap crypto_hash for another hash function with the same length output. While I would normally avoid doing something like this due to lack of knowledge, in this case it seems like it might be fine. The output of crypto_hash is presumably uniformly distributed, seemingly random, and so tweetnacl is surely not making any assumptions about the output of its hash function. If it's replaced by another function with the same length output, then I assume tweetnacl will use its output just as happily?

If it's replaced by another function with the same length output, then I assume tweetnacl will use its output just as happily?

Yes, it seems to be a normal collision-resistant cryptographic hash function, replacing it by any other will not significantly alter the security properties (unless one of them is broken) but will of course break interopability.

In fact if you could find a security-relevant difference between two secure hash functions (given only oracle-access) at least one of them would be broken.


What are the consequences of removing a single byte from a sha256 hash? I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash.

Sha256 would meet this criteria since it outputs 32 bytes.

However, I'd also like to include a "version" byte in case I need to change the hash algorithm in the future. This would require 33 bytes.

One simple solution is to simply chop off the last byte and only use the first 31 bytes for the lookup.

Does this bias the hash in any way?
My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
My assumption is this would increase the likelyhood of a hash collision by 25600%. Is that correct?

Does this bias the hash in any way?

We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash function must depend on the input bits; removing one bit doesn't affect the others.

  My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?

First of all, hash functions are not really reversible since they are compression functions, that is, they map from a large input space to a shorter space.

$$ H:\{0,1\}^* \rightarrow \{0,1\}^l$$

If we want to talk about collision resistance, see the next answer.
For generic pre-image search, yes; it will decrease the computational power, as you noted.

  My assumption is this would increase the likelihood of a hash collision by 25600%. Is that correct?

Collision resistance is measured by the generic birthday attack, that is, $\sqrt {2^l}$, $l$ being the output size of the hash function. SHA256 has $\sqrt {2^{256}} = 2^{128}$ generic birthday attack time.

In your case we will have $\sqrt {2^{256-8}} = 2^{124}$ as generic birthday attack time. Thus, we have a $2^{4}= 16$ speed-up in the attack time.

TL;DR: Truncating the hash to 31 bytes will be safe (see also this stack exchange answer

Note 1: Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019..

Note 2: SHA-224 defined in FIPS180-4 is calculated by truncating the SHA-256 hash value with using different initial constants for domain separation so the value is not the same as the first 28 bytes of the SHA-256 value.


How to find the inverse of a 3x3 MDS matrix I implemented a block cipher similar to AES.
But the reason I can't decrypt is that I can't get the inverse MDS matrix.
The MDS matrix I used is a 3x3 MDS matrix on $GF(2^8) \implies GF(2^8)$ like AES

\begin{bmatrix}
1 & 2 &2 \\
2 & 2 & 1\\
2 & 1 & 2\\
\end{bmatrix}

The encryption process is the same as that of AES mixcolumns, and the MDS matrix used is as above.

I need the MDS inverse matrix required for decryption.
What is the inverse of this MDS matrix on $GF(2^8)$?

I searched for Euclid-Wallis Algorithm or extended euclidean algorithm but I did not understand it well.

How can I find the inverse of a 3x3 MDS matrix?

Your matrix contains 2 which is not an element of $\operatorname{GF}(2^8)$ unless it means $x$. In this case, we can use SageMath to find the inverse as
R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1))
S.is_field()
S.cardinality()
y^8 + y^4 + y^3 + y + 1

A = matrix(S,[[1,y,y],[y,y,1],[y,1,y],])
A.inverse()

That produces this output
True
256
0

[                                  1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1]
[y^7 + y^6 + y^5 + y^4 + y^2 + y + 1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1                                   1]
[y^7 + y^6 + y^5 + y^4 + y^2 + y + 1                                   1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1]

The matrix written in standard binary representation is:
$$\begin{bmatrix}
  00000001 & 11110111 & 11110111 \\
  11110111 & 11110111 & 00000001 \\
  11110111 & 00000001 & 11110111
\end{bmatrix}$$


Why does DES use exactly 16 rounds? Why does DES use exactly 16 rounds and not more or less than 16? What is the significance of using 16 rounds?

From Schneier's description of DES in Chapter 12 of Applied Cryptography (12.3):

  DES with any number of rounds fewer than 16 could be broken with a known-plaintext attack more efficiently than by a brute-force attack.

This explains the "Why not less than 16".

As for the "why not more than 16", that is a tradeoff for speed of execution (more rounds = less speed).


Multiparty dataset intersection count Typically, Private Set Intersection (PSI) protocols let you learn the subset of items on each party's dataset that are in the intersection. The problem in this case is a relaxation of these kind of constructions. I would like to learn only the number of elements on the intersection.

I could achieve this by using proxy re-encryption on a 2-party setting, however it is non-trivial (at least to me) to do the same on an n-party setting without disclosing the intersection of any parties subset.

I wonder if this problem has a specific name and whether it has been studied before (some literature you can point me to). Any idea on how to achieve this is also welcome.

This problem was studied under the name of private set-intersection cardinality (PSI-CA) by De Cristofaro et al. They give protocols for the two-party case both in the honest-but-curious and malicious setting, and the complexity grows only linearly in the size of the sets. A result for the multi-party case was given by Egert et al. using Bloom Filters.

In case you are interested in only testing whether two sets are disjoint without revealing anything else then the problem has been studied by Kiayias and Mitrofanova and under the name private intersection predicate evaluation.


EC: Why does $h>200$ need to hold? From BSI-TR-03111 (PDF), on page 15:

  The class number of the principal order belonging to the endomorphism ring of E SHOULD be at least 200.

This value commonly is referred to as $h$ in that publication.

I‘ve got two questions related to this:

What does $h$ mean/denote?
Why should it be 200 or larger?

Don't confuse h which is commonly adopted for the cofactor in EC (Cf p13 of the doc). The class number $\mathcal{H}(K)$ for any number field K is the cardinal of the class group Cl(K).
Take a look to any course in algebraic number theory and specially H. COHEN and his famous book " A course in computational Alg. Numb Th ..."
The ring theory is very vast, and the link with EC lies in the structure of its endomorphism Ring which can be viewed as an Order in a quadratic field.
In H. COHEN you can understand that computing the class number for an random EC is not so easy, this is the reason why this value can't be chosen too small.


Can you help me with this Random Number Generator function? By someone's suggestion, I am posting this question from math.stackexchange.com.

I want to find out a suitable function or algorithm, which can provide a random sequence like this…

Input: $3$
Output: $\{1,2,3\}$ or $\{1,3,2\}$ or $\{2,1,3\}$ or $\{2,3,1\}$ or $\{3,1,3\}$ or $\{3,2,1\}$

Same as if I will enter a number $N$, output will be a random permutation of the set $\{1,2,...N\}$.
How can a I write this type of algorithm? And can you help me understand the logic behind it?

The classical way to generate a random permutation is the Fisher-Yates shuffle; it takes an underlying random number generator, and produces a random permutation.  With just a bit of care, it can generate each permutation with equal probability (assuming the underlying random number generator outputs are independent and uniformly distributed).

The only downside is that the algorithm requires N to be small enough so that you hold the entire permutation in memory; that doesn't sound like that's a problem from you.


How to choose a padding mode with AES Depending on the framework you are using, there are various padding modes that can be used with AES encryption. For example, with .NET we can choose PKCS7, ISO10126, ANSIX923, Zeros or None.

I understand that the encryptor and decryptor need to use the same mode to be interoperable.

What considerations are there when choosing a padding mode? With the exception of 'None', does it even matter which you choose? Can some be considered more secure than others?

Padding None can be used with stream ciphers and AES-CTR in order to keep the ciphertext the same length as the plaintext. Padding zeros cannot always be reliably removed, and so should be avoided. Any of the others can be reliably removed and are fine for use.

Padding None leaks information about the length of the plaintext. Apart from that there is no security implication in the choice of padding. All padding gives the attacker is a partial insight into the contents of the last block. In effect this is a known plaintext attack.  If the cipher can't resist a known plaintext attack then the problem is with the cipher, not the padding.


Is PCP soundness error optimally 1/2? Everywhere I look in PCP literature I find the soundness error advertised as $1/2$. For example, here on page 17 it says (regarding soundness)

  SCI uses 14 repetitions to reduce the probability of error to $error = 1/2$

and then

  the security analysis guarantees that this verdict is correct with probability $1 − error$

This implies that even after additional tests, soundness is no less than $1/2$. I interpret this and similar statements in other papers to mean that on average an adversarial prover's false proof will be accepted half the time. This would be unacceptable for most applications (such as computational integrity). I must be misunderstanding the context for these statements.

It seems that in order to minimize the error below $1/2$, the verification process (and maybe even the proving process) must be repeated $k$ times for a soundness error of $2^{-k}$.

In the full version of Delegating Computation: Interactive Proofs for Muggles on the bottom of page 18 it says that it is well known that interactive protocols with input size $n$, completeness $2/3$, and soundness $1/3$, are equivalent to interactive protocols with completeness $1-2^{-n}$ and soundness $2^{-n}$. Though soundness $1/3$ differs from $1/2$ mentioned in the question, a similar equivalence likely exists. Apparently the equivalence is proven somewhere in Goldreich's lengthy paper Modern cryptography, probabilistic proofs and pseudorandomness, volume 17 of Algorithms and Combinatorics.


How can we authenticate a public key with limited secure side channel? I'm looking for a method for 2 peers verifying the authenticity of each other's public key that was transfered over an insecure channel and where the needed secure side channel can only transfer short values (significanlty shorter than the length of a cryptographic hash) but in both directions. Are there standard methods for this?

Otherwise, the most naive approach would probably be only comparing a small part of each others public key, e.g. the first few bytes, or alternatively the first few bytes of a cryptographic hash of the keys. In this question it is already mentioned that this is not a good method when the prefix gets too small, but couldn't this be somewhat compensated by also exchanging randomized starting positions (instead of starting the comparison at the beginning or any other fixed position) over the secure channel to minimize the probability that a man-in-the-middle attack works?

PGP supports a so-called fingerprint of the public key, which really is a 20-byte hash expressed in hexadecimal as 10 groups of 4 characters. The recommendation is to read it over the phone. That's doable, but seldom done.

In the context, we only need second-preimage resistance, thus 20 bytes are a bit overkill. With a slow password hash (scrypt, argon2) we can safely get this down to 5 groups of 5 characters in a 25-character alphabet 0123456789CFGHJKMPRTVWXZ+, for $5\cdot5\log_2(25)>116$ bit.
Note: that alphabet is likely to produce reasonably safe-to-spell-at-work codes, and is easily keyable if the software remaps Sto 5, Bto 8, ODQto 0, IJLto 1, UYto V, and so on)

With a challenge-response we can reduce this further. We can use a slow password hash using the (hash of) the public key as password and the challenge as salt.

please enter CK9Z 5H7C what do you get ?
got 01W8 RR4G

A substitution has probability $<2^{-37.1}$ (one in 150 thousand millions) of going undetected, which is perfectly fine in practice.


GCM as a general purpose cryptographic hash? Why are hash functions (e.g SHA-3) so complicated when GCM apparently provides secure hashing and has a relatively simple construction?

Is this purely about speed? I imagine that GMAC with a fixed key (GCM mode without ciphered data) is much slower, if you just need a key-less hash.

GCM does not provide secure hashing. In general, a MAC has all the properties of a hash only against an adversary who does not know the key. If you want to use the function as a MAC then the key has to be public and then A MAC is not a secure hash. With most common MAC constructions other than HMAC, if you know the key, you can easily construct, at least, a second preimage.

For example, look at how the authentication tag GHASH of GCM is calculated. I use the notations from the Wikipedia article; the plaintext is $A_1A_2A_3\ldots$ (split into blocks), $H$ is calculated from the key (so it would be some public constant to use GHASH as a hash) and the $X_i$ are calculated incrementally to produce the hash (so if $X_i = X'_i$ for some $i$ and two different messages then the hash will be the same).
$$ \begin{align}
X_0 &= 0 \\
X_1 &= A_1 \cdot H \\
X_2 &= (X_1 \oplus A_2) \cdot H = ((A_1 \cdot H) \oplus A_2) \cdot H \\
\end{align} $$
Let $A'_1 = A_2 \cdot H$ and $A'_2 = A_1 \cdot H$. Then $A_1A_2A_3\ldots$ and $A'_1A'_2A_3\ldots$ are (assuming that $A_2$ didn't happen to be equal to $A1 \cdot H$) two distinct messages with the same hash (and the same length, incidentally). And that's just from a trivial computation — with a bit more work first preimage can be broken too.


Why do public keys need to be validated? For some curves it's necessary to validate the public-key of the other side before running an elliptic-curve Diffie-Hellman key-exchange. Apparently if you don't validate the public key, small subgroup attacks can leak your private key.

I have a few questions related to this issue:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?
Which validations need to be performed? Just check if the order of the point is large enough?
Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$.  (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^2 = x^3 + ax + b \bmod p$?  Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^2 = x^3 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to.  That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem?  Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation).  The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor.  For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values).  If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret.  This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^2 = x^3 + ax + b \bmod p$; that's cheap and totally foils this attack.  The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value).  As far as I know, all curves can have implementations which are vulnerable.


How is input message for SHA-2 padded? I read about how is an input message prepared to be hashed by MD4,MD5 or SHA-1:

  Step1 Append padding bits

  The input message is "padded" (extended) so that its length (in bits)
  equals to 448 mod 512. Padding is always performed, even if the length
  of the message is already 448 mod 512. Padding is performed as
  follows: a single "1" bit is appended to the message, and then "0"
  bits are appended so that the length in bits of the padded message
  becomes congruent to 448 mod 512. At least one bit and at most 512
  bits are appended.

  Step2. Append length

  A 64-bit representation of the length of the message is appended to
  the result of step1. If the length of the message is greater than
  2^64, only the low-order 64 bits will be used.  The resulting message
  (after padding with bits and with b) has a length that is an exact
  multiple of 512 bits. The input message will have a length that is an
  exact multiple of 16 (32-bit) words.

  ... algorithms steps

I read that hose 2 steps are always the same for input messages for MD4, MD4 and SHA-1. How about  SHA-224 / SHA-256 / SHA-384 / SHA-512? How do they 'prepare' input to compute a hash? The same way maybe?

SHA-1, SHA-224 and SHA-256 append  the  bit  “1”  to  the  end  of  the message, followed by k zero bits, where k is the smallest, non-negative solution to the equation l+1+k ≡ 448 mod 512, where l - message length. In second step they use 32-bit words.

SHA-384, SHA-512, SHA-512/224 and SHA-512/256 use different equation: l+1+k ≡ 896 mod 1024 and in 2. step use 64-bit words.

If you want to learn more, you should read Fips-180-4.


mbed tls DTLS v1.2 system with -ECDHE-ECDSA, mutual auth and pre-installed public/private keys, no unnecessary messages or ASN.1/X.509 decoding I am designing an IoT system based on Silicon Labs EFR32 MCUs with hardware accelerated support for SHA-256, AES-128-CBC and ECC (m255) computation. The system will communicate over a proprietary radio communication protocol in an untrusted environment, and both flash and ram footprint and the number of exchanged messages is vital to be kept low.

The DTLS functionality described in https://tools.ietf.org/html/rfc6347 is massively overweight for my application, which has the following features and needs:

micro-controller to micro-controller communication using proprietary radio (not LoRa, Zigbee or similar) in a hostile environment, radio is slow and costly in terms of battery life
non-blocking SW model with callbacks and timer hooks
physical channel: unreliable delivery, active attacker/listener, reordering and replay; similar to UDP.
client/server model with client verification similar to HelloVerifyRequest/ClientHello in DTLS to avoid DOS attacks on the other radio devices
exclusive use of TLS-ECDHE-ECDSA-WITH-AES-128-CBC-SHA256 (m255) known at production time
known maximum MTU size for radio channel
pre-installed public/private key-pair in both peers in compact binary form (no ASN.1 or X.509 code), identical to both peers having each other's certificates without negotiation, with eternal validity
no IP, not be reachable online, communication between two micro-controllers that use a proprietary protocol for communication
pause/start the tunnel without it closing when no traffic comes in the paused state. Shouldn't renegotiate when in paused state, but keep using the session keys until either age-limit or data-limit hit. Needs to be possible to wake up by an unencrypted agent
one bi-directional secure, mutually authenticated application-layer traffic tunnel using ECDHE/ECDSA, no port-numbers needed.
client knows unique serial number of server, server knows only it's own serial number
keep-alive signaling; successful payload message transfer should be seen as keep-alive equivalent to reduce message volume
renegotiate session keys when either age-limit or data-limit hit
client knows the unique serial number of the server, needs to do server device discovery among potentially many devices both after and before session establishment. That a device has been seen is not considered secret information

When I look at what already finished functionality mbed DTLS has, it looks like I can't get it to not exchange certificates between peers or negotiate the cipher suite (despite knowing the only valid setting in production). I want to cut out all the unnecessary, already known flights of messages to reduce both setup time and battery consumption.

I want to have two interfaces towards my L1 radio layer where only a rough selection of incoming traffic has been performed: send() and receive(), which should be asynchronous and non-blocking.

The code and RAM size for ASN.1 decoding and parsing is massive for my application, so I want only the 256+256 bits of the public/private key-pair, and the known unique serial number of the peer to be stored instead of doing ASN.1 and X.509 parsing.

Is there any way to obtain the features that I want, or do I need to write this code myself, implementing heartbeat signaling, session establishment/renegotiation, application layer tunnel traffic encryption/authentication/decryption, etc based on mbed tls DTLS primitive functions?

Is there any known example of a similar scenario that I can look at? Any list of good advices to follow in order to avoid creating exploitable weaknesses in my implementation?

Thankful for any helpful input
/Daniel Nilsson

You can write your own protocol instead of using DTLS. But there's no realistic chance that you'll get it right. Designing a secure protocol is hard, and you should definitely use a proven and tested one rather than roll your own.

You can do DTLS with raw public keys, which would avoid X.509 altogether. This saves a number of things: code size, RAM usage (but not a lot, compared to a self-signed certificate), and handshake message size. You still need two round trips to establish a session using raw public keys. This does have security and deployment drawbacks: you have to distribute all the peers' public keys before you can start communicating, and you have to manage repudiation on your own.

If you find an implementation of it, that is. Mbed TLS doesn't support it, although there's an old pull request for it. Reportedly tinydtls can do it.

Do use session caching and resumption whenever possible. Session resumption removes the cost of public-key cryptography and reduces the number of round trips to start the connection from 2 to 1.

TLS 1.3 will let you establish a session with a single round trip, but DTLS 1.3 isn't ready yet.

In the absence of a usable implementation of DTLS with raw public keys, you may be forced to partially roll your own: use DTLS with pre-shared symmetric keys (this is widely supported by (D)TLS implementations), and use a separate protocol to distribute the symmetric keys. But it would be safer to achieve this by using DTLS to effectively distribute the symmetric keys, and session resumption to avoid doing asymmetric cryptography every time.


How to break a Quagmire 3 cipher? What would be a good way to go about attacking a Quagmire 3 cipher?

I understand that it is polyalphabetic with a key and an indicator. I have started by taking the cipher text, taking every n-th letter and putting that in a string, computing the index of coincidence for the n strings I get and then averaging that. I would assume that whatever n value corresponds with the closest average index of coincident to English (0.066) would be the number of alphabets, i.e. the length of the indicator.

Where do I go from there? Or is my approach incorrect?

All the Quagmire ciphers (see e.g. here for definitions) are combinations of a Vigenère shift cipher and a keyword-based simple substitution cipher, where the substitution cipher is used to scramble the alphabet before and/or after the Vigenère encryption.

In particular, the Quagmire III cipher in effect scrambles the plaintext alphabet before doing a normal Vigènere encryption (with a key that is derived from the "indicator" by also scrambling its alphabet the same way), and then unscrambles the alphabet of the resulting ciphertext.  Equivalently, we may view it as just a Vigenère cipher, but using a non-standard (and typically secret) mapping from letters to numbers instead of the usual A=0, B=1, C=2, etc.

This has a couple of notable consequences:

All the usual methods of determining the key length for a Vigenère cipher, like Kasiski examination or calculating the index of coincidence, will work just as well for a Quagmire cipher, at least as long as they make no explicit assumptions about which letters are most common in the plaintext.
Once you've determined the length $k$ of the repeating Vigenère key (a.k.a. "indicator"), you can simply take every $k$-th letter of the ciphertext and apply frequency analysis just as if you were attacking a simple substitution cipher (since that's effectively what you have at this point).

Furthermore, the $k$ different substitution alphabets corresponding to the $k$ different indicator letters are related in a particular way: mathematically, they are all powers of the same cyclic permutation (in the strict sense; no fixed points allowed) of the alphabet.  (This is also true of the basic Vigenère cipher; in that case, the underlying cycle is simply the one-letter shift A → B → C → ... → X → Y → Z → A.)  Thus, once you manage to solve one of the $k$ substitution ciphers, the rest should be significantly easier (and you can also compare the solutions to make sure they are correct).

Also, the cycle structure of a power of a cyclic permutation is itself somewhat restricted: it cannot have fixed points (unless it is the identity permutation) and all of its cycles must have the same length that divides the size of the alphabet.  In particular, for a 26-letter alphabet, the power of a cyclic permutation always consists of either one 26-cycle (making it also cyclic), two 13-cycles, 13 two-cycles or 26 fixed points (in which case it is the identity).  Of these, the first two possibilities (one 26-cycle or two 13-cycles) are by far the most likely, so if you see anything else (especially if it's not one of the remaining possibilities above), you'll know that you've made a mistake somewhere.

Given sufficient ciphertext, breaking this cipher via the methods described above shouldn't be particularly difficult.  Indeed, determining the key length using the index of coincidence method doesn't even need all that much ciphertext; I tried it on the Kryptos K1 and K2 ciphertexts (using a Wilson score interval correction to reduce sampling noise for large key lengths) and it pretty clearly identified the key length of K1 (63 letters) as 5, 10 or 20 letters (actual keyword: PALIMPSEST, 10 letters) and the key length of K2 (369 letters) as most likely 8 letters (actual keyword: ABSCISSA).  However, with a limited amount of ciphertext and a long key, solving the individual substitutions may require a considerable amount of trial and error.

Also, it's worth noting that this method does not automatically yield the keywords used to encrypt the text.  Indeed, it cannot, since the Quagmire ciphers have many equivalent keys.  However, simply considering all the possible solutions for the substitution alphabet and the shift amounts may turn up one that arises from a particularly natural pair of keywords.


Decrypting a blowfish cipher with three keys Disclaimer: I'm pretty new to cryptography and I don't have a strong mathematical background. I apologize in advance if I missed something blatantly obvious.

I participated  in a security CTF this weekend and I was unable to solve one of the problems. It's been three days now and I still take a crack at it whenever I have some free time, it's driving me crazy. It just seemed so simple at first.

The title was "triple Schneier, no Rivest" and it gave an apparently encrypted file and three qr codes which contained this data:

# First QR
key=5EBE2294ECD0E0F08EAB7690D2A6EE69
iv=26AE5CC854E36B6B
# Second QR
key=3FDD884B0F6491110CE7A27CD9C670E2
iv=2384D24993B7A941
# Third QR
key=5A1F31323B5F3E79DF1A1A2ABC89B85F
iv=B9B9F5320FDD8706

This is the file encoded in base64:

ewx68DgfNLMEabX/dl62gVO4zki0vaZHWv6E+WCK8i0BH/rsKtIIV0ZlB8Z+fCFWwPQ04ZAi5Np6
s9lG4KnxUyVSAW/E1ccQ9QcOVxTTwduGdZ5+/ypgRIDKbx9B3mE8cZu0KBQ5k+Y1TfhlqYLwzs9E
Xld9C3IMIrzBChFFoVmGEOZT/I/idBoE++ZDDlMGZMsZO37l2/Th/73y5qNn6Ezp1uuqAPoeZbAB
ZSOaGnkKYnMPcjqoJR47NP4L3j0Wt39nZtbvHjQfIAyefqliklsChbTEGeRavqJX8zOg1W5zi3Q/
qKWilBOT5eLhtH9WxOa7aY8gxjcPQWzzXhSUtlZeCXUt2DW+

It's 264 bytes long, the IV in each key is 8 bytes long and each key is 16 bytes long. Plus the mention of Schneier in the title, I'd say it's a pretty safe bet we have a blowfish cipher.

I've tried decrypting the file with the first key, then with the second, and then with the third. I also tried different libraries/implementations of the algorithm.

I even wrote a python program to try all possible permutations of the three keys, but none gave me a plaintext.

I'm obviously missing something big.

Here's my last attempt at it, which I think condenses most of the other things I've tried:

for kr in key_permutations:
    out_name = ''.join( [ str(k['id']) for k in kr ] )
    output = [ first_input ]
    for k in kr:
        cipher = blowfish.Cipher(k['key'])
        i = b''.join(output)
        sys.stdout.buffer.write(i)
        output = cipher.decrypt_cbc(i,k['iv'])

    open(out_name,'wb').write(b''.join(output))

key_permutations is a list of 3-uples where each element is a dictionary with a key, its corresponding iv and an arbitrary ID. I'm using this blowfish library.

So I guess the questions are three:

Is there a way to make sure this is indeed a blowfish cipher?
What methods are available, given those 3 keys, to try and crack the code
What does Rivest have to do with Blowfish?

Thanks in advance!

The encryption is EDE with Blowfish CBC. To decode the cryptotext ct reverse the encrytion, ie do

CBC_Decrypt(key3, iv3, ct, t3)
CBC_Encrypt(key2, iv2, t3, t2)
CBC_Decrypt(key1, iv1, t2, pt)

After this the plaintext pt will start with:

El truco estaba en desencriptar utilizando el metodo 3DES pero con distintos algoritmos de encripcion. Aunque usualmente se utiliza 3 veces DES, es posible utilizar 3 algoritmos distintos con el metodo de 3DES ....


Can elliptic curve (25519) be used to encrypt file? This is probably a simple question, but I haven't been able to see it stated anywhere. Is it possible to directly encrypt a file (of any length) with some form of EC using the 25519 curve.

I know it's common to exchange a key with EC and then use symmetric encryption (AES) to encrypt a file, however I was curious if it was possible directly ?

I've seen the salsa20 and chacha stream ciphers but I am unsure if they are suitable. If so is there a pre-existing tool that can be used or is something like libsodium the way to go.

As you probably have guessed, I'm still in research mode and I'm fairly keen to use as many pre-existing tools as possible.

No, you cannot "directly" encrypt a file using ECC without generating your own algorithm. Encrypting a file would be extremely inefficient; this is because the block size of ECC is very small, leading to a very high overhead both with regards to data usage (the ciphertext would be strictly larger than the plaintext) as well as CPU-usage.

Yes, any curve can be used to encrypt something if it is suitable to perform ECDH. If ECDH is used then the curve can be used to implement EC-IES.

  I've seen the salsa20 and chacha stream ciphers but I am unsure if they are suitable. If so is there a pre-existing tool that can be used or is something like libsodium the way to go.

Any secure cipher is suitable. It may be smart to go for some existing protocol/library if you haven't implemented a secure protocol or library yet.

Using authenticated encryption should be preferred.


Searching for a dining cryptographers problem variant When I frist read about the famous dining cryptographers problem, in a book years ago I remember the author made a twist on it, demonstrating the generalization of the problem.

Basically the dining cryptographers wanted to know who has the best income. But since they all worked for secret agencies, they were not allowed to tell each other. So they had a system where they would write their income down in some order without giving away information to their sitting neighbors on what their income is.
I'm unable to recall the way that system worked and I can't remember what book it was.

I was hoping somebody recalls this twist on the problem or the book.

I believe I found the reference I was looking for. I believe it's from the book 'Einführung in die Kryptographie' from Albrecht Beutelspacher, Jörg Schwenk and Klaus-Dieter Wolfenstetter, published by Springer. I read it back in college.

In chapter 5.2 on 'Multiparity Computations' they talk about 'Wer verdient mehr' ('who earns most'). The idea is that in a multi-party with >2 participents one of them (Alice) starts by adding their income, i_1, to a random number r, writes it down on a note and passes that note around. Everybody else then adds their income i_n to the number. Once the note arrives back at Alice, Alice then can subtract the random number r and is able to compute the average income of the round, so they can compare if their income is above or below average without exposing any other information. Of course this only works if all participents answers are trustworthy.

A interesting approach. But I was wrong with my assumtion that it had anything to do with the 'dining cryptographers' problem.


Is Pohlig-Hellman Cipher the only option? I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a and b.

So far, the only cipher I could find that would work like this is Pohlig-Hellman Exponentiation Cipher. But as I understand, it has the following drawbacks:

It is slow - though, this is not really a concern for me
I can't find any actual implementations of the cipher. It shouldn't be too difficult to implement from scratch, but still...

Is there another cipher that can accomplish the same thing?

If you define $E_a(M) = M \oplus  a$ then the key $ab$ can also be defined as $a \oplus b$ as follows:

$E_b(E_a(M)) = (M \oplus a) \oplus b$

$E_{ab}(M) = M \oplus (a \oplus b)$

However using the same key and/or message more than once in XOR will leak the other one. So I think it's potentially not what you're looking for.

As far as I know, SRA is also a variant, where you get regular RSA where both parties use the same modulus (and prime numbers) and create their own encryption, decryption exponents; and keep it secret. This way you achieve the same commutativity as in PH.


For elliptic-curve cryptography, does a 256-bit key imply that $x$ and $y$ are each 256-bits or 128-bits? In the wikipedia article, the claim is made that "256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key". Since, in ECC, the public-key consists of a point $(x, y)$, when they say a "256-bit public key", does that imply both $x$ and $y$ are each 256-bits? Or that, together, they are 256 bits (meaning that each would be 128 bits)?

In ECC, the xxx-bit curve implies the modulus length. Also, this implies the length of each coordinate in $(x,y)$. Therefore, $x$ and $y$ are each 256-bit


Given paramaters of an Edward's curve and x, determine a y value if it exists I'm making a demonstration cryptosystem using ECC ElGamal. I've currently got a working implementation of Edward's Curve operations and a basic ElGamal implementation (Encrypts only points on the curve), and in order to perform the mapping operation described in this answer, I need to determine the $y$ value of a point on an Edward's curve $g$ given an $x$. I have a basic understanding of the way an Edward's curve works but the finite fields are a bit much for me to be confident in properly implementing this based on intuition. Any help is appreciated.

The equation for an Edwards curve is $x^2 + y^2 = 1 + dx^2y^2$. Assuming you know the curve parameters then, given that you know $x$, you are solving the above equation for one unknown, namely $y$. We can rewrite this as a quadratic equation in one unknown and solve it. Note that all operations are $\bmod{p}$ where $p$ is the characteristic of the field the curve is defined over (remember that dividing by $z$ is equivalent to multiplying by $z^{-1}\bmod{p}$, square roots also have different rules).

$$x^2 + y^2 = 1 + dx^2y^2$$
$$y^2 - dx^2y^2 + x^2 - 1 = 0$$
$$(1 - dx^2)y^2 + (x^2 - 1) = 0$$

Now let $a = (1 - dx^2)$, $b = 0$, and $c = (x^2 - 1)$ (so we have $ay^2 + by + c = 0$ i.e. a quadratic equation). Note that you can also move some terms around in the upper equation and end up at the same result.

$$y = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$
$$y = \frac{-0 \pm \sqrt{0 - 4(1 - dx^2)(x^2 - 1)}}{2(1 - dx^2)}$$
$$y = \frac{\pm \sqrt{-4(1 - dx^2)(x^2 - 1)}}{2(1 - dx ^2)}$$
$$y = \pm \sqrt{\frac{1 - x^2}{1 - dx^2}}$$

Now substitute in $x$ and $d$. Note that there are two solutions to the equation. Without your x coordinate having some sort of encoding that indicates which y value should be used it is impossible to recover the "correct" y as both values result in distinct valid points.


Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors? I recently read Squeamish Ossifrage's answer on generating RSA keys from (short) randomness where they make the following comment:

  (You might want to keep the certificate secret too.)

As the answer talks about multiple primality tests, let's start with a simpler one: The Pocklington-Lehmer test.

So my question:
Assuming we are given a semiprime $n$ of unknown factorization and a Pocklington Certificate of primality for either one of $n$'s prime factors. Can we efficiently factor $n$?

Here's a summary of Pocklington's theorem / criterion:

Let $n$ be the number of which we want to prove primality. Then a list of pairs pair $(a_i,p_i)$ is  the pocklington-lehmer certificate for the primality of $n$ if

$\prod_i p_i>\sqrt n$ that is the product of the $p_i$ is larger than the square root of $n$
$\exists B: n-1=B\cdot \prod_i p_i$, that is the product of the $p_i$ is a factor of $n-1$
$\forall i: p_i\in\mathbb P$, that is, every single $p_i$ is a prime itself (this primality can be proven recursively using this theorem or a list of known primes)
$\forall i:a_i^{p_i}\equiv 1\pmod n$
$\forall i:\gcd(a^{(n-1)/p_i}_i-1,n)=1$

Can we efficiently factor n?

Sure can, at least with that formulation of Pocklington's theorem.  From the certificate, we can obtain values $a_i, p_i$ with $a_i^{p_i} - 1 \equiv 0 \pmod p$, (where $p$ is the prime factor that the certificate applies to).

So, if we compute $a_i^{p_i} - 1 \bmod n$ (where $n = pq$), we know that that is 0 modulo $p$, but is extremely unlikely to be 0 modulo $q$ (the other prime factor).  So, compute the gcd of that and $n$, and that's the factor $p$.

On the other hand, if you go to the formulation on Wikipedia, instead of the listed criteria 4, we have $a^{n-1} \equiv 1 \pmod n$.  Of course, knowing a value $a$ that meets that criteria leaks nothing, as (assuming $n$ is prime) any $a$ that's between 1 and $n-1$ will meet that criteria.

If you create a certificate based on that, then it may be possible to factor, but that would depend on how the prime was generated (e.g. if the large factor $r$ of $p$ was not that much smaller than $p$, then it is easy; if it is just slightly larger than $\sqrt{p}$, then you need to hope that $(p-1)/r$ happens to be smooth (which is unlikely).


What is the relation between the existence of a cryptographic hash function and the existence of a PRG? Does the existence of a PRF/PRG/one way function imply the existence of a hash function? I did not find a proof of the existence of a cryptographic hash function, so I want to know whether it is based the same axiom (the PRG axiom)?

There is a black-box separation between one-way functions and collision resistant hash functions. This was proven at Eurocrypt 1998 by Dan Simon, in the paper entitled Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?. Of course, this doesn't mean that it's not possible using non-black-box reductions, but no one knows how to do this.


Reusing AES-CTR Keys and IVs for File Encryption I’m implementing some file encryption module with random-access capability and AES-CTR seems the right way to go.

I understand that reusing Keys and IVs can expose the file to ‘Stream Cipher Attacks’ when portions of the file are being modified (assuming previous versions of the file are still available).

I want to avoid re-encrypting the entire content of the files when they are modified and so I thought to combine CTR with ECB.
First encrypt the block with CTR and then re-encrypt the resultant cipher text with the same key again:

CTR-Cipher = Plain xor AES(IV + counter, Key)
Final-Cipher = AES(CTR-Cipher, Key)

Would that allow me to reuse the key and the IV? Or are there other secure alternatives to support random-access based encryption without a lot of re-encryption?

Yes, there are secure alternatives to support random-access based encryption.

I did not come up with a way to break the proposed combination.
Still, instead of inventing a new mode, I would recommend to take consider existing modes for this kind of operation, such as XTS mode. The existing modes are more studied, and (in some ways) more efficient. XTS mode (as well as some other modes) only invokes cipher once per block of input. Rogaway has created a paper describing the most common modes of operation, which contains good study of XTS mode, including some critique.

Alternative: IEEE P1619

IEEE P1619 has developed standards for disc encryption. These standards contain cryptographic mechanisms for keeping disc storage encrypted. As disc storage (often) requires frequent rewrites of disc sectors, these standards capability of rewriting sectors.

IEEE P1619 specifies both length expansionless encryption mechanisms and mechanisms with length extension (P1619.1). XTS mode is one of the most commonly used cipher modes of operation, if you want to avoid length extension. It likely proves the security features you expect from CTR with ECB combination, i.e.
it works on narrow blocks (16 bytes) and allows you to pass in index of the sector. Some narrow block a problem. In that case, you mate take a look at wide block encryption such as EME2, XCB from P1619.2.

Alternative: Per Block IV (Traditional)

Just for reference I also mention traditional (well studied way to do this). This approach may prove useful in case you lack cryptographic library or hardware with appropriate modes from P1619.

A well known way to do random-access based encryption is to consider data as blocks and generate random IV per each block each time a block is updated. This of course mess that the encrypted data will expand, but the percentage is not very large: consider e.g. one kilobyte blocks and 16 byte IVs: $\frac{16}{1024}\approx1.6\%$. This is only a small cost. Note: When expanding length, it is commonly good idea to add authentication tag as well.


Using public-key signature instead of having API key I am designing an application that will need an API key. At first I believed that generating a long, random token would be secure enough (say 32 chars string that includes 0-9, a-z and A-Z), and then I could store it or its hash on the server-side for authenticating clients. But after Googling some HN threads I found that sending API keys in HTTP headers might leak if HTTP request logs have been leaked at some time in the future, and then the attackers could very easily use the keys to impersonate the clients.

Then I looked at the AWS model, which I have always wondered how it actually works. AWS doesn't just give you an API key, it gives you a couple of tokens, probably like a private-public key pair and the client's HMACs, some request-specific string (HTTP method, HTTP path, timestamp, etc...), and then the server simply authenticates the client by checking the signature with the public key.

Now, if this public-key signature is truly much more secure than the usual API key, I want to know whether my implementation is secure enough:

When the user registers, the server generates a ed25519 or curve25519 key pair, the server gives the user the private key as an API key and the server stores the public key.
When the user sends a request that needs to be authenticated, he computes the current timestamp and then signs it with libsodium's  crypto_sign() and sends the signature in an HTTP header.
When the server authenticates the user by simply verifying the signature using libsodium's crypto_sign_open()

In that way, the user never has to send a static API key that might get stored and leaked in some log's store in the future. Additionally, the server should check the timestamp in order to verify it is not an old one that might be involved in some weird replay attack. Also, I am assuming that the server is using HTTPS with TLSv1.2 at least.

I feel that I am right, but I also understand that I should not invent my own security. I just need your recommendation of this type of public-key signature authentication

Using public key cryptography instead of a long-term shared secret is slightly more complicated but has major advantages. One of them being that the server doesn't learn the secret key. This protects against accidental leaks, but also insider threats.

If this is an option, you can use client TLS certificates. Most HTTP client libraries support this, but web server often have limited support for this. Namely, they support ACLs based on the presence (or not) of a certificate, but that's pretty much all they do. And it's not always possible to retrieve client information from web applications.

The scheme you describe (the server sends something that the client has to sign) works. However, you shouldn't use a time stamp, which would be vulnerable to replay attacks, but a nonce.


How to find common answers without revealing differences? Say Bob and Alice are trying to figure out the fruits they like, but don't want to reveal the fruits they dislike. How could they compare their list of liked fruits and reveal only the common set to the other person?
In this scenario, each party knows the full list of possible fruits to pick from. (It's shared information.) But if one person likes a fruit and the other doesn't, the person who doesn't like the fruit shouldn't know that the other does like it. There can't be a third party involved, so this operation needs to happen without sharing information outside of these two people.
Example fruit set: [apple, banana, grape]. (1 indicates interest, 0 indicates disinterest.)
Bob's selection: [1, 1, 0].
Alice's selection: [0, 1, 0].
In this case, how can Bob and Alice figure out that the shared answer set is [0, 1, 0]?
Bob doesn't want to share that he likes apples, because it wasn't a shared interest. (An odd scenario, but it works for the sake of this example...) And from Alice's perspective, she doesn't know anything about Bob's preference for apples or grapes, because she indicated that she doesn't like those. Similarly, Bob doesn't know anything about Alice's preference for grapes, because he indicated that he's not interested in grapes.
Because they don't want to share their preferences with a third party, they want to find a way to find the common set themselves without revealing disinterest. Is this possible?
I'm not well versed in cryptography, but it seems like private set intersection may be what I'm looking for? Is this the right direction?

I'm not well versed in cryptography, but it seems like private set intersection may be what I'm looking for?

Yes. In private set intersection (PSI) if we have elements from a universe $U$ (e.g. the set of 128 bit integers) and Alice has $N_A$ elements and Bob has $N_B$ elements, most good PSI protocols will try to give you $O(N_A+N_B)$ communication and computation complexity. However, if $|U|\approx N_A\approx N_B$, e.g. when you have a dictionary of 100 fruits most of which are liked by both parties with high probability, then there's another way to go about this. Namely you could also consider this as a generic 2-party computation of $|U|$ parallel AND gates using the bitvector encoding used in the question.
So, as a guidance:

For small scales, e.g. $|U|\leq 2^8$ use setup-less PSI protocols, e.g. this DH-based one.
For large scales, e.g. $|U|\geq 2^{20}$ and small set sizes, i.e. $N_A,N_B\leq \frac1{\log_2|U|}|U|$ use dedicated PSI protocols, e.g. OT-Phasing.
In all other cases consider using OT-Extension based AND gate evaluation, i.e. one party entering their interest vector as the choice vector and the other party entering an all-zero vector for the zero-bits and their interest vector for the 1 bits. Then have receiver share the received bitvector with the sender.


What role does RSA play in DHE_RSA cipher suite? I've read in this article, that encrypting a premaster key with a RSA public key is not safe from forward secrecy attacks. If an adversary, records all communication between a client and a server. And the server later is decommissioned and retrieved by the adversary and the adversary also retrieves the private key stored in the server. He can decrypt the premaster key and generate a master key and decipher all recorded communication between the client and server.

To prevent forward secrecy attack, one can implement Diffie-Hellman Ephemeral Mode for the premaster exchange.

Now to my question. What role does RSA play in this if DHE is used? Because I've seen cipher suites with RSA and DHE in it.

Ephemeral Diffie-Hellman (DHE or ECDHE) uses two ephemeral key pairs that should be discarded after use. However, to establish a secure connection it is required that you know the entity that you establish the connection with. If that isn't the case then an impersonation or man-in-the-middle attack is possible.

So RSA in this case points to the key pair of the server, the public key of which is in the server certificate. This certificate is used to establish a chain to a trusted (root) certificate in the certificate store, e.g. the one in your browser or system store. This chain is verified and validated so that the public key of the server can be trusted to a certain degree (the level of trust established by trusting all of the CA's in the certificate store is an ongoing debate).

Now that you've established trust in the public key the private key of the server can be used for two related goals:

entity authentication of the server and
making sure that the ephemeral public keys and parameters have indeed been generated by the client and server.

The RSA algorithm is used for the private key calculation at the server to sign the messages used to perform the key agreement to agree on the master secret. This master secret in turn is used to derive the session keys used to encrypt the data streams. The client uses the RSA algorithm for the verification of the public keys, parameters and to make sure that the server controls the private key used for the signature generation (server entity authentication).

The advantage of directly encrypting the master secret (in the old RSA_ cipher suites) is that it establishes the master secret and performs the entity authentication in one single operation. Fortunately DH and certainly ECDH is relatively fast compared to RSA private key operations.

Notes:

obviously the certificate needs to have an RSA public key, so ECDSA certificates cannot be used by the server;
the client is not authenticated by default - to authenticate the client it is required for the server to explicitly request client authentication, this is why you need to login on most websites (or authenticate yourself when paying, of course);
the certificates themselves may be signed by a different algorithm than RSA, and if client certificates are used then they may use a different algorithm as well.


Does SHA-1 hash have quasi commutative property? Although I have tested with a program and found negative answer, I want to be sure.

No, $\operatorname{SHA-1}$ does not have any property remotely similar to the quasi-commutative property, that
$$\forall x,\forall  y_1,\forall y_2, f(f(x,y_1),y_2)=f(f(x,y_2),y_1)$$

That's for that natural mapping of $f(x,y)$ to $f(x\|y)$, where $\|$ stands for concatenation. No function (except trivially narrow) can exhibit such property and also aim at being similar to a random function. And the only striking property distinguishing $\operatorname{SHA-1}$ from a random function (beside being $\operatorname{SHA-1}$) is that it has the length-extension property (which allows, given $\operatorname{SHA-1}(x)$ and the length of $x$, to exhibit non-empty $y$ such that $\operatorname{SHA-1}(x||y)$ is known).


How was the special DES key 0E329232EA6D0D73 found? The DES key 0E329232EA6D0D73 has the unusual property that decrypting a ciphertext block consisting entirely of zeros gives a plaintext block consisting of eight repetitions of the same byte (0x87).

How was this key originally found?

That value 0E329232EA6D0D73 was found by brute force. I would be surprised if there was a significantly better method: that would be tantamount to a cryptanalytic break of DES, very different from the few we know.

A sketch of the brute force method (with details about parallelization omitted) goes:

for each $K$ of 64 bits among the $2^{56}$ valid DES keys

decrypt with key $K$ a ciphertext block consisting entirely of zeroes, giving $P$
if the eight bytes in $P$ are equal

output $K$ and stop

output nothing found and stop.

For a perfect cipher, $P$ would be essentially 8 random bytes for each $K$ tried, therefore the if condition would be met with odds $2^{-56}$ for each $K$. Under that approximation for DES (which is not invalidated by the complementation property, since the ciphertext is fixed), odds that nothing found is output are $(1-2^{-56})^{(2^{56})}\approx1/e\approx36.8\%$. Correspondingly, odds that a value of $K$ is found are $1-(1-2^{-56})^{(2^{56})}\approx1-1/e\approx63.2\%$.

It turns out that we are in the second (and most likely) case (proof: the assertion in the question holds). Knowing this, finding a solution $K$ by the method outlined requires at most $2^{56}$ decryptions. That's not much harder than finding a DES key by brute force from plaintext/ciphertext pairs, which was feasible in few days with a budget of \$250,000 (including NRE) in 1998, see the EFF DES Cracker. The only difficulty compared to that is the slightly unusual stop condition. But in a FPGA-based implementation like Copacobana, or a GPU-based one, that adds very little cost.

Update: the EFF DES Cracker was designed to have a flexible enough stop criteria, and was used to first publicly find that particular key, as a demonstration that it works. Quoting the EFF¹:

  The EFF DES Cracker first solved a challenge posed [circa 1996] by world-renowned cryptographer and AT&T Labs research scientist, Matt Blaze. The "Blaze Challenge" was designed to only be solvable by "brute force" cryptanalysis of DES. Mr. Blaze challenged the world to find matching pairs of plaintext and ciphertext numbers, consisting of nothing but repeated digits. Blaze himself was unaware of any such pairs until the EFF DES Cracker revealed the first known pair. It found that a hexadecimal key of 0E 32 92 32 EA 6D 0D 73 turns a plaintext of 8787878787878787 into the ciphertext 0000000000000000.

¹ This links to an archive of the original. Some of that material is still on the current EFF website, but sadly the date was lost in modernization, becoming August 2016 rather than July 1998.


Why it is said that “zk-SNARKs need a trusted setup” to work? What is the meaning of a "trusted setup" in this context? It is often said all around that zk-STARKs and Bulletproofs does not require a trusted setup. How do zk-STARKs and Bulletproofs manage to avoid the need for a trusted setup?

It is not true that zk-Snarks need a trusted setup. It's just that all the zk-Snarks that depend on pairings (that I know of) hinge on a "trapdoor", the knowledge of which makes the scheme insecure. And before 2019, those were the only known zk-Snarks.
zk-Starks do not rely on pairings. Neither do bulletproofs. Bulletproofs are arguably not Snarks, since the verification time is not succinct.
The DARK scheme gives you a trustless zk-Snark (https://eprint.iacr.org/2019/1229). Recently, a gap was found in this paper but the cryptographers who found the gap were able to modify the scheme so that it is now secure and hinges on weaker cryptographic assumptions than before: https://eprint.iacr.org/2021/358.


Does a one-time pad of digits 0-9 have any weaknesses? I'm working on one of those unsolved puzzles, and one theory I have is that one or more sections of it are using digits of pi, e, or some other irrational number as a one-time pad.
(The obvious approach would just be to try well-known irrational numbers, but I've tried that without success and if it is that there must be some other complication.)
Are there any cryptanalysis methods that that allows for that wouldn't apply to a one-time pad composed of letters?  One thing that occurred to me is that since letters can't be shifted by more than 9 places, it ought to show very small peaks in its frequency distribution, one-tenth the size of ones for plain text and displaced about five letters to the right along the alphabet.  But I don't know how much practical use that would be.
The question is probably equivalent to whether a Gronsfeld cipher has any weaknesses that a Vigenere cipher doesn't.

The one-time pad can be made of digits 0-9, and you can read more about that here. One could also use binary digits, 0 and 1, or letters such as A-Z.  Those three alphabets are the most common.

Are there any cryptanalysis methods that that allows for that wouldn't
apply to a one-time pad composed of letters?

No, there are not.  A properly generated one-time pad is going to have equal strength no matter whether it is composed of letters A-Z, numbers 0-9, or the binary digits 0 and 1.
The CIA, for example, was fond of using one-time pads composed of numbers 0-9 during the Cold War.
However, in practice, using numbers or binary could possibly introduce errors because of fractionation.  In other words, using letters might be more straightforward.

One thing that occurred to me is that since letters can't be shifted
by more than 9 places, it ought to show very small peaks in its
frequency distribution...

Don't worry about that.  It is not the case.

The question is probably equivalent to whether a Gronsfeld cipher has
any weaknesses that a Vigenere cipher doesn't.

One can see what you mean by this, but Gronsfeld and Vigenere are a very different kind of cipher from the one-time pad.


Rehashing PBKDF2 hashes - do iterations stack? Let's suppose I have a bunch of PBKDF2 hashes in a database. For the sake of keeping this simple, let's say I've used 10 iterations. A few years later I decide to upgrade to 20 iterations. I want to upgrade all hashes in one go so I rehash the old hashes instead of waiting for all users to log in. Do I use 20 or 10 iterations?

Basically, what I'm asking is this:

pbkdf2(20, password) == pbkdf2(20, pbkdf2(10, password))
pbkdf2(20, password) == pbkdf2(10, pbkdf2(10, password))

By == I mean equivalent in terms of security.

Which of the two is true?

PBKDF2 consists of a chain of one way functions. The one way functions are dependent on each others output and this output is computationally unique. That means that there are no shortcuts of creating a specific outcome.

So yes, you can chain the PBKDF2 functions that way. However, it won't be binary compatible with just using PBKDF2(20, password) as the concatenation of the steps that make up PBKDF2 will be different for both, even if you re-use the same salt.

Reusing the salt won't lead to problems, as the output of the previous PBKDF2 is randomized, so it will be different from any other password / output of the first stage.

Notes:

PBKDF2 directly uses the number of iterations, i.e. the work factor will increase linearly. Unfortunately computer processing power doesn't, it seems to continue to increase faster than that.
It may be a good idea to store some kind of version number with the PBKDF-2 hash so it is possible to distinguish between different forms of hashing (such as single PBKDF2 or extended PBKDF2 use as described.
TL;DR, option 2 is correct - yes iterations do stack.


Murder Mystery Party For a "Murder Mystery Party", one person is chosen anonymously to be the murderer
(i.e., only the murderer knows who the murderer is) by shuffling cards with
everyone randomly taking a private card (one card has "You Are The Murderer!"
written on it).

How can I do this cryptographically over an open communication channel without
trusting any third party?

I'm hoping this simple problem has a simple solution that doesn't involve full
mental poker or
oblivious transfer methods.
Is there a trick that somehow combines inputs from everyone (which include the
randomness used for the selection so that everyone can trust that the process
was random) to publish something that only one "winner"
would recognize?

With some assumptions I think you can do this with a simple protocol.

We will break i into two parts: attempt an allocation which may succeed with reasonable liklyhood. And verify it. If verification fails try again.

The first step we can do by each party randomly selecting for himself if he is the chosen one with probability 1/n.

Verification we do with secure multiparty summation. Sum the bits of all parties and if it is 1 verification succeeds. and any other value it fails.
First we need to establish 2 way secure channels(e.g using DH key exchange). A simple summation would be for one party to pick a random R add it to his bit and pass along, where each party adds it's bit and passses along until finally the first party removes R and reveals. This can be broken by a collosion of 2. Alternativly, each party secret shares it's bit by distributing to all parties a random share which sum up to their bit. Then sum up all shares from all parties to reveal total sum.

This however allows a member to force himself to be selected or not.

To deal with this problem we can have everyone commit to a random value $X_i$ and then together they pick a random $R$. Each player will use their secret combined with the shared random ${X_i} + R$ as a random seed. This allows at the end of the game to verify everyone picked random numbers fairly.
Picking a shared random $R$ can be done by each party picking a random $R_i$ and publishing a commitment to it and then all parties reveal. take the sum or the xor of all as $R$.

Success probability of the first phase is $(1-1/n)^{n-1}$ which approaches 1/e . So we are likely to success after only a handful of iterations.


The meaning of "scheme" This question is a bit different from other questions here, but I think it is suitable to correctly understand the terminology of cryptography.

Consider the following two sets of terms:

Encryption scheme, signature scheme
Identification scheme, commitment scheme, secret-sharing scheme

The latter are actually "protocols", while we usually do not consider encryption/signature as (interactive) "protocols". Moreover, the word "scheme" is not usually applied to terms like "hash functions", "pseudo-random generators", "one-way functions", etc.

What does the term "scheme" mean? When is it meaningful to apply this term to a cryptographic construct? How does it relate to "protocols"?

As @mikeazo correctly states, I don't think there is any formal or precise definition for the term "scheme".  It is probably used loosely in a way that might well mean a "protocol", "mode of operation", "cryptosystem", "cryptographic algorithm", or even something else entirely.


One-way function and $EXP$ All examples of one-way functions I have see till now are closely related to the assumption that $NP\neq P $ (or even weaker ones, such as $UP\neq P$), but why not considering the theorem $P\neq EXP$?

In particular, why not building functions that in one way are in the class $FP$ and the inverse function computable in $FEXP$ (the class of functions extending the class $EXP$)?

If $P=NP$, then any one-way function can be inverted.  Any one-way function can be inverted using non-deterministic polynomial time.  Therefore, the assumption that $P\ne NP$ is necessary (but maybe not sufficient).


How to sequence SHA256 block circuit to obtain hash of a message comprising multiple 512 blocks? I am trying to obtain a circuit that computes the SHA256 hash for an input message that is greater than 512 bits.

I understand how the message is to be padded (we append a 1 and then some zeroes, and then the last 64 bits contain the length of the original message and so on).

After I do the padding, I have two 512-bit blocks.

I want to use the circuit (for the compression function) that is provided here:

https://www.cs.bris.ac.uk/Research/CryptographySecurity/MPC/

The first 512 wires of the circuit are the input; the last 256 wires are the output. I think I know how to use the circuit for the first block. I can simply feed my first 512-bit block into the first 512 wires of the circuit.

But I am not sure how to proceed for the second block. In particular I need to update the h0, h1, ... , h7 values but don't know how to as I cannot identify where the wires corresponding to them are in the circuit.

Any help would be much appreciated.

One can't use the circuit exactly as given.

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

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

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


Power analysis and exponentiation by squaring I am trying to understand how one can retrieve the secret exponent via a simple power analysis.

Lets suppose that the exponentiation by squaring algorithm is implemented in its simplest form :

Function exp-by-squaring(x,n)
    if n<0 then return exp-by-squaring(1/x, -n);
    else if n=0 then return 1;
    else if n=1 then return x;
    else if n is even then return exp-by-squaring(x2, n/2);
    else if n is odd then return x * exp-by-squaring(x2, (n-1)/2).

As i understand,if i am to probe the consumption while the machine is calculating the exponent i will be able to see the individual operations on the spectrogram. There will be a spike between different operations so i will be able to tell when it entered the "even" condition or when it entered the "odd" condition. This simply gives me an idea about the exponent and not the actual exponent.

So if the secret exponent is 2012 (https://math.stackexchange.com/questions/563708/exponentiation-by-squaring), i will simply see that the even condition was entered 6 times and the odd condition was entered 4 times but how exactly do i use that information to find the secret exponent?

Thanks in advance

You can begin by first reading the seminal paper of Paul Kocher. He gave the reference for Timing and Power analysis attacks. The best is to read the papers, and understand the philosophy of Side Chanel Attacks.
The method he described, has been enhanced by many authors, and it become impossible to ignore how to securelly implement algorithm on embedded systems.
After that the most destructive attacks is the one introduced by Dan Boneh known as the "Faults Attack".


Issues with Seeding Random Number Generator Using Password I am looking into zero-knowledge proof-based security. I noticed that a server never needs to be sent the user's password to authenticate them - the password can be used to generate another value that is sent instead. The server has the password so it can generate that value on it's side. This way the user can prove they are who they say they are without sending the password. This shared secret value can be used to seed a random number generator, which can then be used to perform actions on their messages that make the data look random to a would-be-attacker but can be undone by the receiver (which has the seed and can recreate the scrambling process).

Such a system seems to have the following problems:

The attacker can now break the system by predicting the password. Since people tend to use passwords that are partially based on real words a attacker doesn't normally need to consider all 26^k possibilities for a k digit password
Even if you use a salt/nonce/timestamp to mutate the resulting key, it needs to either be sent to the server (allowing the attacker to use it) or the server must know it without being told, allowing the attacker to also know it without being told.
Even if you transform the password with something like HMAC the fact remains that the original password is not particularly secure. An attacker can simply pass their guesses at the password through whatever algorithm is used to transform the password.
If you want to have some counter or other data that mutates the password on a session by session basis (and you don't want to send the mutator but rather have user and server infer it from their past interactions e.g. number of logins) the user has to either remember the mutator (meaning they will be locked out of their account if they lose/forget/incorrectly remember the mutator) or have it stored on their machine (preventing them from logging in on different devices)

A possibility would be to only accept passwords with a minimum level of unpredictability (making salts, nonces and mutators less necessary) but users won't be keen to remember a soup of letters and numbers.

Is there any other issues with using the user password to generate the shared secret (the shared secret would be the seed of a random number generator) I would need to overcome?

I'm still not entirely sure what you're asking but you can use password authenticated key agreement (PAKE). It will prevent off-line brute-forcing of the password.


What is many:1 and collision in MD5? This is in reference to this answer on Stackoverflow. If you read the first paragraph of the answer, you'll find this line:

  It's always a many:1 mapping (meaning there will always be collisions) since every function produces a smaller output than it's capable of inputting (If you feed every possible 1mb file into MD5, you'll get a ton of collisions).

What is this many:1 and what are collisions? Does many:1 mean two different inputs would have the same hash outputs?

Does many:1 mean two different inputs would have the same hash outputs?

Yes. This is a consequence of the pidgeonhole principle: as MD5 has a much larger number of potential inputs ($2^{2^{64}}$ or so) than outputs ($2^{128}$), some inputs must lead to the same output, i.e. collide.

Cryptographic hashes all have this "limitation", because they have a constant output size and allow much larger inputs. However, with good cryptographic hashes (MD5 is very broken in this sense), you have no way of finding those collisions. This is called collision resistance and is one of the properties we require of hashes.


Ed25519 choice of private key implementation This answer to another question describes the different values chosen as private key and public key by various Ed25516 implementations. What are the advantages / disadvantages of each?

(Table cropped from diagram in the linked answer, originally taken from "How do Ed5519 keys work?" by Brian Warner.)

To perform an Ed25519 signature operation, you need to know three values, denoted by $\sf RH$, $a$ and $A$ in the diagram.  Now, as it happens, these values are not independent:

$A$ can be derived from $a$, and
both $\sf RH$ and $a$ can be derived from the seed $k$.

Thus, all you really need to store is the seed $k$; everything else can be derived from it.  Alternatively, it's possible to store $\sf RH$ and $a$ like NaCl does, which saves you the (minor) effort of one SHA-512 hash computation whenever you need to sign something.

There's no particular need to store the public key $A$ as part of the private key, since it can be derived from $a$ and you need to know $a$ anyway to be able to sign.  However, deriving $A$ from $a$ requires an elliptic curve multiplication, which is a reasonably expensive operation compared to the other key generation steps.  Thus, also storing $A$ as part of the private key provides a modest performance gain compared to storing just $k$ or just $\sf RH$ and $a$.


Key scheduling for ISAAC Does ISAAC use key scheduling? I do not know programming.

Is it safe if ISAAC derives subkeys using ISAAC itself?

The author of ISAAC notes:

  I provided no official seeding routine because I didn't feel competent to give one. Seeding a random number generator is essentially the same problem as encrypting the seed with a block cipher. ISAAC should be initialized with the encryption of the seed by some secure cipher. I've provided a seeding routine in my implementations, which nobody has broken so far, but I have less faith in that initialization routine than I have in ISAAC.

No official seeding algorithm means no official keystream or key scheduling.

The first sentence of that quote is a red flag for security. If someone knows the algorithm well enough to provide an initialization algorithm then it should be him.

But I suppose he thought that his algorithm would run fine if random values were assigned to each of the 259 32-bit words required to store the state of the RNG. (There is insufficient evidence for that.)

I think that despite it being unconventional, it would be fine for an algorithm designer to say "these values all must be filled with numbers from a HWRNG or key-derivation function," but instead he talks about block ciphers and encryption. (Those next two sentences aren't absolutely technically correct, but perhaps, since it was invented in 1993, the language didn't exist at the time.)

The unofficial initialization algorithm has no key schedule. It does not use subkeys. Instead it alternates between adding one of eight 32-bit seed words to eight words of the RNG state and slightly mixing up those 256 bits in a loop. (Note that just because the seed is 256 bits doesn't mean this algorithm has 256-bit security.)

His implementation actually loops too many times, writing to memory that doesn't belong to the 256 word array he's using. That's called a buffer overflow and it has the potential to be really dangerous. (Which can be as bad as allowing attackers to run arbitrary code on your computer remotely.)

That's another huge red flag. Something you may forgive from a pure mathematician who had to learn programming just to create reference code. But definitely not something you expect from a professional programmer.

... But even if we knew none of that,

Don't use ISAAC!!!

Why?

There is insufficient evidence to believe that the algorithm is cryptographically secure.
It's much slower than modern encryption algorithms.
There is insufficient evidence to believe that the algorithm is cryptographically secure.
The amount of memory it uses is relatively large.
There is insufficient evidence to believe that the algorithm is cryptographically secure.
The author didn't provide evidence for why we thought has algorithm was secure. Merely that he didn't find any biases using empirical data.
There is insufficient evidence to believe that the algorithm is cryptographically secure.


Does AES-NI offer better side-channel protection compared to AES in software? Does AES-NI offer better side-channel protection compared to AES in software? Also, it would be great of you could provide according references in your answer.

Yes, AES-NI was specifically designed to be constant-time and thus offers better side-channel protection than (some) software implementations. Note however that these day there exist quite fast side-channel resistant software implementations for AES, which are in-use by the better crypto libraries. AES-NI mainly offers a speed advantage over these implementations.

From the Intel® Advanced Encryption Standard (Intel® AES) Instructions Set Whitepaper:

  The AES instructions are designed to mitigate all of the known timing and cache side channel leakage of sensitive data (from Ring 3 spy processes). Their latency is data-independent, and since all the computations are performed inter
  nally by the hardware, no lookup tables are required. Therefore, if the AES instructions are used properly (e.g., as in the following code examples) the AES encryption/decryption, as well as the Key Expansion, would have data-independent timing and would involve only data-independent memory access. Consequently, the AES instructions allow for writing high performance AES software which is, at the same time, protected against the currently known software side channel attacks