What is the difference between: ecdsap, ecdsak, and ecdsab in the output of "openssl speed"? What do the letters P/K/B refer to? openssl speed tests the speed of different protocols on your computer:

$ openssl speed something
Error: bad option or value

Available values:
...
ecdsap160 ecdsap192 ecdsap224 ecdsap256 ecdsap384 ecdsap521
ecdsak163 ecdsak233 ecdsak283 ecdsak409 ecdsak571
ecdsab163 ecdsab233 ecdsab283 ecdsab409 ecdsab571
...

For the ECDSA options, there are the above list of available ciphers (likely this list is different on different PC's).

What is ecdsap vs ecdsak vs ecdsab? What do the letters P, K, and B mean at the end of the ECDSA algorithm?

First: If you're looking for a signature scheme, forget all of those; I recommend Ed25519.  It too uses elliptic curves, it's standardized in RFC 8032, and there are implementations widely available.  It's safer and faster and simpler than any of the signature schemes you listed: ECDSA is an archaic design, and most or all of the curves mentioned there fail to satisfy modern security criteria for curves.

With that caveat in mind, to answer the question you asked:

The nomenclature $\mathrm{ecdsa}tn$, for a type $t \in \{\mathrm p, \mathrm k, \mathrm b\}$ and number $n$, mostly corresponds to ECDSA over the NIST Curve $t{\operatorname-}n$ defined in FIPS 186-4, over a field of about $2^n$ elements.  For example, ecdsap256 uses NIST Curve P-256, or just NIST P-256 for short.  Prior to FIPS 186-4, the curves also appeared in SECG standards.  One of the curves, secp160r1 as used by ecdsap160, does not appear in FIPS 186-4, presumably because it provides too little security.

(The methods allegedly used to choose the curves are prescribed in ANSI X9.62, and some of the curves also appear in it, and possibly also in IEEE P1363, but what self-respecting anarchist cypherpunk has the cash to shell out for a copy of a bureaucratic standard like that?)
The field size $2^n$ means that the highest expected cost for Pollard's $\rho$ to compute discrete logarithms that you, the defender, can hope for is approximately $\sqrt{2^n\pi/4} \approx 2^{n/2}$; for more on prime, field size, curve shape, and curve order, see an answer to an earlier question, and for more on other security criteria, see SafeCurves.
The letters p, k, and b represent different types of curves with different properties.  I include the full gory details for the sake of curiosity, not because you should be discriminating on these criteria—as before, ideally, you would just use Ed25519, which uses a curve, edwards25519, not in this list at all.

The p curves are curves over prime fields $\mathbb Z/p\mathbb Z$ with allegedly* randomly generated parameters.  They all have the short Weierstrass form $y^2 = x^3 - 3x + b$ for a coefficient $b$ chosen from an unexplained seed.

Using a prime field rather than an extension field, particularly a binary extension field, is the most conservative choice for an elliptic curve.  The most widely used one is probably NIST P-256, also known as secp256r1.

In addition to being defined on a prime field, all of these curves have prime order, meaning the number of elements on the curve (with coordinates in the field and not an extension) is prime.  Thus all of these curves fail SafeCurves because they cannot admit the Montgomery ladder for fast constant-time scalar multiplication, or complete Edwards formulas for fast constant-time arithmetic, which require a cofactor of at least 4; and they are not rigid.  Some of them additionally fail SafeCurves for other reasons.

ecdsap160: secp160r1, defined in [1], §2.4.2, p. 10, over the prime field of characteristic $p = 2^{160} - 2^{31} - 1$ by $y^2 = x^3 - 3 x + b$, where $b$ is 1C97BEFC 54BD7A8B 65ACF89F 81D4D4AD C565FA45, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 1053CDE4 2C14D696 E6768756 1517533B F3F83345.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{80}$ curve additions, which is a plausible cost today,† so it is not endorsed by NIST and it falls far short of the SafeCurves requirement of $2^{100}$ cost for Pollard's $\rho$.
ecdsap192: secp192r1, a.k.a. NIST P-192, defined in [2], §2.2.2, p. 6 and [3], §D.1.2.1, p. 90, over the prime field of characteristic $p = 2^{192} - 2^{64} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 3045AE6F C8422F64 ED579528 D38120EA E12196D5.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{96}$ curve additions, and while it is endorsed by NIST, it falls short of the slightly higher standard imposed by SafeCurves.
ecdsap224: secp224r1, a.k.a. NIST P-224, defined in [2], §2.3.2, p. 8 and [3], §D.1.2.1, p. 90, over the prime field of characteristic $p = 2^{224} - 2^{96} + 1$ by $y^2 = x^2 - 3x + b$ where $b$ is B4050A85 0C04B3AB F5413256 5044B0B7 D7BFD8BA 270B3943 2355FFB4, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{112}$ curve additions.  It fails SafeCurves additionally because its twist has composite order with no particularly large prime factors, enabling a variant of Lim–Lee small-subgroup attacks, and therefore requiring the additional complexity of point validation in protocols using it.
ecdsap256: secp256r1, a.k.a. NIST P-256, defined in [2], §2.4.2, p. 9 and [3], §D.1.2.3, p. 91, over the prime field of characteristic $p = 2^{224} (2^{32} - 1) + 2^{192} + 2^{96} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed C49D3608 86E70493 6A6678E1 139D26B7 819F7E90.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{128}$ curve additions.
ecdsap384: secp384r1, a.k.a. NIST P-384, defined in [2], §2.5.1, p. 10 and [3], §D.1.2.4, p. 91, over the prime field of characteristic $p = 2^{384} - 2^{128} - 2^{96} - 2^{32} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is B3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112 0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed A335926A A319A27A 1D00896A 6773A482 7ACDAC73.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{192}$ curve additions.
ecdsap521: secp521r1, a.k.a. NIST P-521, defined in [2], §2.6.1, p. 11 and [3], §D.1.2.5, p. 92, over the prime field of characteristic $p = 2^{521} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 0051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3
B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88 3D2C34F1 EF451FD4 6B503F00, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed D09E8800 291CB853 96CC6717 393284AA A0DA64BA.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{259}$ curve additions.  It is not assessed by SafeCurves, presumably because there is a much better curve E-521 over the Mersenne prime $2^{521} - 1$, but it turns out to pass all the same criteria as NIST P-256 and NIST P-384 at a somewhat higher security level: embedding degree $(\ell - 1)/4$; CM discriminant ${>}2^{100}$; not rigid (manipulable but not trivially so); no Montgomery ladder; twist embedding degree $(\ell' - 1)/6$, twist cofactor $5\cdot7\cdot69697531\cdot635884237 = 1551184646225159645$, prime twist subgroup order $\ell' \approx 2^{460.57}$; no Edwards addition law.

The k curves are curves over binary extension fields $\operatorname{GF}(2^m)$ with a special property, called Koblitz curves.  Specifically, each exponent $m$ of the field size is prime, and each curve has the Weierstrass form $y^2 + xy = x^3 + ax^2 + b$ where $a, b \in \{0,1\}$, chosen so that the Frobenius map $\varphi\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$ (which can be efficiently computed by bit-shifting) has trace 1, which has the consequence that $[2^m]P = \varphi(P) - \varphi^2(P)$, making the evaluation of scalar multiplication particularly cheap, as noted by Koblitz in 1992 after whom the class of curves is named.

The security of binary elliptic curves against discrete logarithms is not as well-understood (see in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18), so all of these curves fail SafeCurves.

The class of curves named Koblitz curves is sometimes considered to include any curve with an efficient endomorphism to speed up computations as proposed by Gallant, Lambert, and Vanstone in 2001, not just binary curves.  secp256k1, used by Bitcoin, is an example of a prime Koblitz curve.  These endomorphisms make some people nervous but are not known to destroy security.

ecdsak163: sect163k1, a.k.a. NIST K-163, defined in [2], §3.2.1, p. 17 and [3], §D.1.3.1.1, p. 94, over the binary field $\operatorname{GF}(2^{163})$ by $y^2 + xy = x^3 + x^2 + x + 1$.
ecdsak233: sect233k1, a.k.a. NIST K-233, defined in [2], §3.3.1, p. 19 and [3], §D.1.3.2.1, p. 95, over the binary field $\operatorname{GF}(2^{233})$ by $y^2 + xy = x^3 + x^2 + 1$.
ecdsak283: sect283k1, a.k.a. NIST K-283, defined in [2], §3.5.1, p. 21 and [3], §D.1.3.3.1, p. 96, over the binary field $\operatorname{GF}(2^{283})$ by $y^2 + xy = x^3 + x^2 + 1$.
ecdsak409: sect409k1, a.k.a. NIST K-409, defined in [2], §3.6.1, p. 23 and [3], §D.1.3.4.1, p. 97, over the binary field $\operatorname{GF}(2^{409})$ by $y^2 + xy = x^3 + x^2 + 1$.
ecdsak571: sect571k1, a.k.a. NIST K-571, defined in [2], §3.7.1, p. 25 and [3], §D.1.3.5.1, p. 99, over the binary field $\operatorname{GF}(2^{571})$ by $y^2 + xy = x^3 + x^2 + 1$.

The b curves are curves over binary extension fields $\operatorname{GF}(2^m)$ with allegedly* randomly generated parameters.  They all have Weierstrass form $y^2 + xy = x^3 + x^2 + b$ for a coefficient $b$ chosen from an unexplained seed.

Unlike the binary Koblitz curves, the allegedly-random binary curves have neither a rigid form, nor special structure admitting efficient implementation.  Like the binary Koblitz curves, they are binary, and so their security is poorly understood.

ecdsab163: sect163r2, a.k.a. NIST B-163, defined in [2], §3.2.3, p. 18 and [3], §D.1.3.1.2, p. 94, over the binary field $\operatorname{GF}(2^{163})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 02 0A601907 B8C953CA 1481EB10 512F7874 4A3205FD, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 85E25BFE 5C86226C DB12016F 7553F9D0 E693A268.

There is also a similar curve sect163r1, generated by a variant of the ANSI X9.62 Annex A.3.3 procedure.
ecdsab233: sect233r1, a.k.a. NIST B-233, defined in [2], §3.3.2, p. 19 and [3], §D.1.3.2.2, p. 95, over the binary field $\operatorname{GF}(2^{233})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 0066 647EDE6C 332C7F8C 0923BB58 213B333B 20E9CE42 81FE115F 7D8F90AD, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 74D59FF0 7F6B413D 0EA14B34 4B20A2DB 049B50C3.
ecdsab283: sect283r1, a.k.a. NIST B-283, defined in [2], §3.5.2, p. 22 and [3], §D.1.3.3.2, p. 97, over the binary field $\operatorname{GF}(2^{283})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 027B680A C8B8596D A5A4AF8A 19A0303F CA97FD76 45309FA2 A581485A F6263E31 3B79A2F5, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 77E2B073 70EB0F83 2A6DD5B6 2DFC88CD 06BB84BE.
ecdsab409: sect409r1, a.k.a. NIST B-409, defined in [2], §3.6.2, p. 24 and [3], §D.1.3.4.2, p. 98, over the binary field $\operatorname{GF}(2^{409})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 0021A5C2 C8EE9FEB 5C4B9A75 3B7B476B 7FD6422E F1F3DD67 4761FA99 D6AC27C8 A9A197B2 72822F6C D57A55AA 4F50AE31 7B13545F, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 4099B5A4 57F9D69F 79213D09 4C4BCD4D 4262210B.
ecdsab571: sect571r1, a.k.a. NIST B-571, defined in [2], §3.7.2, p. 26 and [3], §D.1.3.5.2, p. 100, over the binary field $\operatorname{GF}(2^{571})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 02F40E7E 2221F295 DE297117 B7F3D62F 5C6A97FF CB8CEFF1 CD6BA8CE 4A9A18AD 84FFABBD 8EFA5933 2BE7AD67 56A66E29 4AFD185A 78FF12AA
520E4DE7 39BACA0C 7FFEFF7F 2955727A, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 2AA058F7 3A0E33AB 486B0F61 0410C53A 7F132310.

References:

Recommended Elliptic Curve Domain Parameters, Standards for Efficient Cryptography: SEC 2, Certicom Research, version 1.0, 2001-09-20.
Recommended Elliptic Curve Domain Parameters, Standards for Efficient Cryptography: SEC 2, Certicom Research, version 2.0, 2010-01-27.
Digital Signature Standard (DSS).  Federal Information Processing Standards: FIPS PUB 186-4, United States National Institute of Standards and Technology, July 2013.
Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287.
C.H. Lim and P.J. Lee, ‘A key recovery attack on discrete log-based schemes using a prime order subgroup’, in Burton S. Kaliski, Jr., ed., Proceedings of Advances in Cryptology—CRYPTO 1997, Springer LNCS 1294, 1997, pp. 249–263.
Stephen D. Galbraith and Pierrick Gaudry, ‘Recent progress on the elliptic curve discrete logarithm problem’, IACR Cryptology ePrint Archive: Report 2015/1022, 2015-10-22.
Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200.

* NIST claims to have no documents about the origin of the seeds under which the parameters of curves over prime fields were pseudorandomly chosen.  I have not verified that they followed the ANSI X9.62 Annex A.3.3 procedure.  See also the bada55 curves and the SafeCurves commentary on rigidity. N.B.: This is not evidence of a back door.  (In contrast, Dual_EC_DRBG was clearly designed to have a back door that cryptographers rapidly recognized—the back door was even patented under the not-very-subtle euphemism of ‘key escrow’.)  This is only evidence that the authors didn't think hard about inspiring confidence that there is no back door.

† For comparison, the Bitcoin network today computes over $2^{80}$ SHA-256 evaluations in a day.


AES S-Box Affine Mapping - how to do it? For the byte substitution layer in AES how do we determine B(i)?  I follow how to use the multiplicative inverse table and using that to get B`(i), but how do I actually calculate the affine mapping?  Is this normal matrix multiplication?

Yes it is a normal matrix multiplication but within Galois finite field. We have to use Galois defined operations of  $+$ and $\cdot$. Example might clarify everything. Let's say we have the $b'$ vector, and it's value is $170 = 10101010b$ Just remember tat $b'_0$ is the least significant bit of that value.

$b_0 = (1 \wedge b'_0) \oplus (0 \wedge b'_1) \oplus (0 \wedge b'_2) \oplus (0 \wedge b'_3) \oplus (1 \wedge b'_4) \oplus (1 \wedge b'_5) \oplus (1 \wedge b'_6) \oplus (1 \wedge b'_7) \oplus (1) = (1 \wedge 0) \oplus (0 \wedge 1) \oplus (0 \wedge 0) \oplus (0 \wedge 1) \oplus (1 \wedge 0) \oplus (1 \wedge 1) \oplus (1 \wedge 0) \oplus (1 \wedge 1) \oplus (1) = 0 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus (1) = 1 \oplus 1 \oplus (1) = 1$

$b_1 = (1 \wedge b'_0) \oplus (1 \wedge b'_1) \oplus (0 \wedge b'_2) \oplus (0 \wedge b'_3) \oplus (0 \wedge b'_4) \oplus (1 \wedge b'_5) \oplus (1 \wedge b'_6) \oplus (1 \wedge b'_7) \oplus (1) = (1 \wedge 0) \oplus (1 \wedge 1) \oplus (0 \wedge 0) \oplus (0 \wedge 1) \oplus (0 \wedge 0) \oplus (1 \wedge 1) \oplus (1 \wedge 0) \oplus (1 \wedge 1) \oplus (1) = 0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus (1) = 1 \oplus 1 \oplus 1 \oplus (1) = 0$

$\vdots$

Just remember that here also $b_0$ is the least significant bit of the result.

Here's a little python from my experimental implementation for You:

result = 0;

inverse = RijndaelHelper.Inverse(value)

for i in range(8):
    row = (0xF1 << i | 0xF1 >> (8 - i))

    t = row & inverse;

    sum = 0;
    for j in range(8):
        sum ^= (t >> j) & 0x1;

    result |= sum << i;

result ^= 0x63;


RSA public key exponent generation confusion Quote from Wiki:

  $e$ having a short bit-length and small Hamming weight results in more efficient encryption — most commonly $2^{16} + 1 = 65537$. However, much smaller values of $e$ (such as $3$) have been shown to be less secure in some settings.

Does this mean that it is secure to choose the smallest possible public key exponent possible that is larger than a certain threshold, such as $65537$? If it is not so, how are values of the public key exponent generated in more secure RSA implementations?

Usually the public exponent is first chosen. Often it is the fifth prime of Fermat (e.g. -f4 for openssl), 65537. It's the fifth number as the index starts with 0.

This number in binary is:

0000 0000 0000 0000 0001 0000 0000 0000 0001

Fermat primes are primes with just 2 bits set. 3, 5, 17, 257 and 65537 are the only known Fermat primes. Because only two bits are set the exponentiation is relatively fast compared to other exponents.

After the choice of public exponent the primes $p$ and $q$ are chosen in such a way that they comply with the chosen public key. To be precise, this means that $p - 1$ and $q - 1$ need to be relative prime to $e$. This is slightly different than most text book methods of generating an RSA key pair where $p$ and $q$ are chosen first.

Smaller and much larger exponents may be vulnerable to some kind of attacks. Usually other properties for which the keys are used - mainly padding - cause these attacks to be impossible. Cryptographers and standardization institutes however like to play it safe, so current implementations almost unanimously choose the fourth prime of Fermat as public exponent.

Choosing a high valued public exponent will hurt performance because higher values will take more time during the modular exponentiation used for encryption and verification. In the worst case the exponentiation is as slow or even slower than the private key operation. If $e$ is randomized then it is usually 16, 32 or 64 bit value at most (e.g. original implementations of PGP). Some implementations (.NET) only accept small public exponents.


Additive ElGamal cryptosystem using a finite field I'm trying to implement a modified version of the ElGamal cryptosystem as specified by Cramer et al. in "A secure and optimally efficient multi-authority election scheme", which possesses additive homomorphism between ciphertexts, as opposed to the original version, which presents multiplicative homomorphism.

The BIG problem (as always) is that the paper is annoyingly scarce on the "small" details. Here's what I have so far:

Configuration parameters

size of $ p $
size of $ q $
message space

Key generation

pick a prime number $ p $ of a given "key size", ensuring that $ p - 1 $ has a large prime factor $ q $ (of a given size)
pick $ g $ as a generator of the cyclic group $ \mathbb{Z}_{q}^* $
generate a random number, $ s \in \mathbb{Z}_{q} $, and compute $ h = g^s \pmod q $
The public key is $ (g, h) $ and the private key is $ (s) $

Precomputations

Since the scheme requires computing discrete logarithms in order to perform the decryption (see below), the messages must be small so we precompute each $ g^m \pmod q $ and we store them in a lookup table

Encryption

pick a random value $ \alpha \in \mathbb{Z}_{q} $
compute $ (x, y) = (g^{\alpha} \pmod q, h^{\alpha} g^m \pmod q) $

Decryption

$ y x^{-s} \pmod q \equiv h^{\alpha} g^m g^{-s \alpha} \pmod q \equiv g^{s \alpha} g^m g^{-s \alpha} \pmod q \equiv g^m \pmod q $
we use the precomputed lookup table to find the corresponding message, $ m $, for the computed $ g^m \pmod q $

Questions:

I'm not sure if the implied modulus of each operation is $ q $, as I added myself to the above formulas. Could someone please clarify this? The paper omits it...
If, indeed, the modulus of the operations is $ q $, then I need to add it to the public key, right? If I do this, doesn't the scheme become insecure?
Regarding the private key, the paper does not specify the set from which to select it, and I assumed it to be $ \mathbb{Z}_{q} $. Is this correct?
what should be the size of $ p $ (in bits) in order to have similar security as provided by RSA 1024?
what should be the size (in bits) of the large prime factor of $ p - 1 $?

As far as I can tell from your description, the modulus is $p$. To multiply two group elements, you compute $xy \mod p$; because the generator $g$ you choose has period $q$ it'll all work out fine.
No, $p$, $q$, and $g$ can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete logarithms rather than factoring.
Yes.
and 5. The Ecrypt report on algorithms and key sizes http://www.ecrypt.eu.org/documents.html is a good place to look. It's not an easy question because it depends on how hard you think it is (and will be in the future) to solve discrete logarithms.

There's an existing, open-source implementation of additive ElGamal (in Python) used in the Helios voting system (http://heliosvoting.org) that you might want to look at.


Is Wikipedia's table about SHA-2 collisions correct? I was looking a Wikipedia article on SHA-2, and the "Comparison of SHA functions" table seems to indicate that SHA-2 is less secure than SHA-1.

Is this true, or is the table wrong / misleading?

What does $2^{28.5}$ mean for SHA-256 compared to $2^{60}$ for SHA-1 (table in SHA-1 article says $2^{53}$)? How does it relate to MD5 article, which says:

  The security of the MD5 hash function is severely compromised. A
  collision attack exists that can find collisions within seconds on a
  computer with a 2.6 GHz Pentium 4 processor (complexity of $2^{24.1}$)

Assuming that no collisions have been found for the SHA-2 family, does that still mean it takes less work to find a collision than SHA-1? Or do these numbers ($2^{28.5}$, $2^{60}$, $2^{53}$, $2^{24.1}$) mean different things?

If the table is wrong, how should it be corrected?

No. The wikipedia article is in my honest opinion misrepresenting this article on a reduced round attack on the SHA-2 family of hashes.

  Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.

In other words, no collisions have been found in any of the SHA-2 hashes.

The numbers that the are shown in the table mean different things for SHA-1 and SHA-2. In the case of SHA-1, the theoretical attack finds a collision in the actual SHA-1 algorithm. In the case of SHA-2, the collision is found in a modified algorithm with only 24 of the normal 64/80 rounds. In practice, this means that the best collision attack against SHA-256 still has the theoretical upper bound of $2^{128}$ complexity, and the best collision attack against SHA-512 a $2^{256}$ complexity.


Generating OTP using Digital Dead Drop I've had a thought and I'm wondering if this would be a useful way to devise and distribute a one-time pad. It relies on a digital dead drop and a hash function.

The digital dead drop could take a variety of forms.

For wide distribution it might be a Twitter, Facebook, or Instagram feed, a cloud storage container (Dropbox, Pastebin, etc.) or similar method.
For local distribution it could be a wireless server set up in a public area using Raspberry Pi, Beaglebone, or similar hardware. It could even be a physical dead drop using thumb drives. Such repositories could be password protected if desired.

The "payload" for the dead drop would be delivered and retrieved using VPN access from a public computer, and could be any set of 5 files. These could be anything: photos from the NOAA weather satellite, text files from Shakespeare, videos pulled at random off Youtube, whatever. Each group of 5 files would be in a labeled folder and numbered 1 to 5.

To generate the key, an user would run SHA-3-512 on each file, generating five hashed outputs. Each user would have a unique ID number, such as 12345, 24315, etc., and would arrange the five keys in that order to generate his or her unique one-time pad key, with a total length of 2560 bits.

The ciphertext would contain some indicator of the user's ID and the label from the repository folder, to allow the recipient to generate the proper key.

I've identified some security problems with this method already. The most obvious is the nature of the input files. The input relies on security through obscurity, with the input files "hidden in plain sight" either as innocuous Twitter posts or files on an obscure server available only within a small public area. But granting that this is a significant problem of operational security, is this method otherwise usable?

EDIT TO ADD: Based on some of the feedback (thanks to all who have written), I've thought of a variation that could resolve some of the problems with the dead drop while maintaining the basic principle of obscurity and utility. It's a variation on a book code.

Each user is issued a digital book, in PDF format, Word format, or text (text explicitly divided into pages). Each user has a unique book, but they can be any sort of innocuous writing: A complete Shakespeare, a Handbook of Chemistry and Physics, a complete edition of the Talmud -- any long book will work.

User generates the OTP key by copying single pages of the book into individual files, and hashing those files.

As for your idea to use a hash to create your OTP, please read Hash functions to generate one time pad to avoid the obvious OTP pitfall of getting its definition wrong.

  …

  As a reminder: a one-time pad…

  has to be truly random,
  must be at least as long as the plaintext,
  is never reused in whole or in part, and
  is kept completely secret.

  Only when all four points are met, we´re talking about OTP.
  …

Now, that linked Q&A asks if hashing PRNG output would be good enough to create an OTP stream… but your fixed-files idea is not much different in the end (just less volatile in relation to the data you're hashing, making the file-based solution worse).

You're failing the OTP definition in point 1 because files are not truly random. A hash won't magically make it truly random.
You're failing the OTP definition in point 3 because reuse of even a tiny portion of an OTP is a big problem (key reuse issues which lead to partly recoverable data/plaintext).
You're failing the OTP definition in point 4 because it is not kept completely secret. Obscuring the files used as hash source isn't secret by any means. Which brings us to your “…Fortunately it is possible to make them very obscure.” – This is irrelevant and a flawed assumption in a “governmental adversary” scenario as you describe it. The most obvious scenario (among many) which will be a neck-breaker is simple surveillance. For that reason, “security by obscurity” is not really considdered a safe solution in cryptographic realms. This is one of the reasons RSA & Co. have been developed.

Last but not least: you're also missing authentication which is another security problem related to your idea. Related to that, check Q&As like “Why should I use Authenticated Encryption instead of just encryption?” and maybe the related Wikipedia article about “Authenticated Encryption”.

Wrapping it up

My advise would be to rather rely on well-vetted cryptographic solutions which are publically available: an encryption algo (for example, something like ChaCha20), a MAC (to enable authentication), a KDF (to allow users to create according keys based on one or more common secrets), and potentially something like RSA to allow users to agree on a common secret via public-key encryption.

If you – as your comment describes – want to avoid using dedicated encryption algos and regard hashes to be “less obvious” (which I personally don't agree to), you should know that you can build a steam cipher from a hash (see “Building a stream-cipher out of a hash function?”, you can use a hash to create a MAC (see HMAC), and you can even create a KDF with a hash (see HKDF). If you do this, be sure to rely on a secure hash. MD5 nd SHA-1 are considered broken and should therefore be avoided for these purposes. Yet, SHA-2 and SHA-3 are also available and secure.

And if you really insist on using a “Digital Dead Drop”, you could use that instead of public-key encryption to agree on a common secret. Yet, I would advise against it as “security by obscurity” is generally a bad idea… especially when facing a governmental adversary.

This should be somewhat what you're looking for and cover all issues your scenario descibes.


What kind of attack could one perform if you generate private keys using SHA3(master_key || nonce)? I'm aware HMAC is more appropriate than SHA3(master_key || nonce), but I do not understand what kind of attack could be performed against that strategy. How could an attacker use this fact to figure out your private keys?

KDFs

What you are trying to describe are different implementations of a key based key derivation function (KBKDF) which in turn is a specific form of key derivation function (KDF) that uses a key (and not a password).

The attacker would not be able to reverse the hash when using SHA3(master_key || nonce). The reversal could not even happen for SHA-1; the fact that SHA-1 is broken for collision resistance does not matter for this construction. HMAC is more appropriate because a keyed hash / PRF has better cryptographic properties than a hash.

$H(k | c)$ is actually a known KDF called KDF1 or 2 (those just differ in initial counter value $c$). As described here it is probably still secure. However, if you want real, standardized, proven security I'd probably recommend HKDF using SHA-512 as underlying hash. That should be secure until SHA-512 is broken to the extreme.

On HMAC

HMAC protects the underlying hash function against certain attacks. It should always be secure if a large enough key is used and the underlying hash is sufficiently secure - but that's even the case for MD5. HMAC also alleviates length extension attacks for the underlying hash. However, for SHA-3 there should be no length extension attacks possible, so SHA3(master_key || nonce) would not be affected by length extension attacks anyway.

HMAC is rather overkill for SHA-3 as it hashes the key twice after applying two different masks, while the protection it offers is inconsequential to SHA-3. So HMAC-SHA3 could considered an option because the HMAC construction is secure with any sufficiently secure hash. The more efficient KMAC construction is described in SP 800-185 and could be used instead - if it is available in the programming environment anyway.

TL;DR

Now that you know that you need a KBKDF, I suppose it is a good idea to use a well described one. I'd strongly recommend HKDF or HKDF-expand. NIST SP 800-108 has a few more KBKDF's, but NIST standardized HKDF afterwards for good reasons.


How to generate a list of unique random strings? How would you generate a list of distinct random strings, where all strings are alphanumeric and have a fixed length?

There are three general solutions to the non-duplicate random number problem:

If you want a few numbers from a large range then pick one and reject it if it is a duplicate. If the range is large, then this won't cause too many repeated attempts.
If you want a lot of numbers from a small range, then set out all the numbers in an array and shuffle the array. The Fisher-Yates algorithm is standard for array shuffling. Take the random numbers in sequence from the shuffled array.
If you want a lot of numbers from a large range then use an appropriately sized encryption algorithm. E.g. for 64 bit numbers use DES and encrypt 0, 1, 2, 3, ... in sequence. The output is guaranteed unique because encryption is reversible. The Hasty Pudding Cipher can be set for any convenient range of numbers.


Ciphertext manipulation for ciphers with intermediate tags I have been looking into the CAESAR submissions as I'm interested in a cipher that can process a stream of unknown or large size (E.g. socket, file) while providing authentication. My understanding is that the current standard approach is for the application to slice the data into blocks and use some well-known AEAD mode like GCM (including the chunk number to prevent block suppression, duplication, and reordering).

However, ciphers like Keyak v2 take care of this by themselves by supporting intermediate tags, which combined with being online makes for a good fit for the above use case. Note that tags in Keyak v2 authenticate all plaintext chunks prior to that tag, thus protecting against suppression, duplication, and reordering of intermediate chunks; also worth mentioning that this is a Encrypt-and-MAC approach.

All this got me thinking of potential attacks against ciphers making use of intermediate tags. The way Keyak v2 is designed an attacker can't remove intermediate chunks from the ciphertext, but (s)he would be able to remove as many blocks as (s)he wanted starting from the back. This is interesting as is something you can't do against for example GCM because the MAC is applied over the whole ciphertext. A (contrived, I know) example would be for an attacker to remove the last blocks of the transmission of a number:

Original Ciphertext: 1000|Tag1|0000|Tag2
Modified Cipphertext: 1000|Tag1

The victim would have no way to detect such ciphertext modification as long as the removal of the block doesn't break the semantics of the underlying protocol (like in this example). I know that this is also possible if you're slicing the data at the application level and using GCM, but I expected the likes of Keyak v2 to solve it somehow. Unless I am missing something important, this looks like a relatively big downside of intermediate tags.

What's wrong with my reasoning? Is this just a risk we have to assume if we want to process streams in this way?

As the specification of Keyak v2 explains:

  To produce a tag that depends on the full message and not only on the message bits that have been injected in a single duplex instance, Motorist
  performs some dedicated processing at the end of each message called a knot. It extracts
  chaining values from each duplex instance, concatenates them, and injects them into all
  duplex instances. This makes the state of all duplex instances depend on the full sequence
  of messages. Then it extracts a tag from a single duplex object.

right within chapter 1 (emphasis mine). Note that Motorist is the underlying construction of Keyak 2.


Computational Complexity: ECC multiplication vs Modular multiplication How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime?

I.e. on a given elliptic curve of size $|t|$, what's the complexity of computing $kP$ with respect to $|k|$ and $|t|$?

And in comparison, what's the computational complexity of a modular exponentiation of form $g^a \bmod p$ with respect to $|g|=|p|$ and $|a|$?

It would already be a big help to know the answer for double-and-add and square-and-multiply respectively.

If you only care about computational complexity, it's similar:

In ECC: the number of double-and-add steps is proportional to $O(|k|)$ (one double every bit, one add for each $1$ bit, in the non-windowed algorithm). Each double/add is a sequence of a constant number of field multiplications, squarings, additions and subtractions. Multiplication and squarings are the expensive ones, and using Karatsuba algorithm, they are $O(|t|^{1.58}$). Therefore the result is $O(|k||t|^{1.58})$.
Modular exponentiation is the same. Square-and-multiply is $O(|a|)$. Each square/multiply is $O(|p|^{1.58}$). Therefore the result is $O(|a||p|^{1.58}$)

Of course, if you need to be more precise, you'll have to decide on a specific point multiplication / modular exponentiations algorithms, since there are ones that use windows and precomputation tables; and in ECC, also specific formulas for point addition and doubling.


Homomorphic Encryption and the Approximate GCD Problem Confusion Note: I asked this question on Math.StackExchange yesterday and it wasn't answered, so I thought I would repost it here, in hope of getting an answer

I am reading Homomorphic Encryption and the Approximate GCD Problem, specifically Section 3.2 on page 23, which outlines a basic encryption scheme:

  The user chooses a large odd integer $p$ to be the secret key for the system.

  A plaintext is a single bit $m$.  To encrypt a message $m\in\{0,1\}$ and obtain a ciphertext $c$, the user chooses $q,e \in\mathbb{Z}$ independently and randomly from some distribution for each encryption and computes $$E(m,p) =qp+ 2e+m$$

  The binary size of $q$ is generally chosen to be greater than the binary size of $p$. The binary size of $e$, which is referred to as the error, is much smaller than the binary size of $p$. We will discuss the exact sizes for these parameters later on.

  The decryption function for this system is given by
  $$D(c,p) = (c\mod p)\mod 2$$

  To see that the decryption function is correct for a ciphertext $c=qp+ 2e+m$, observe that
  \begin{align}D(c,p) &= (qp+ 2e+m\mod p)\mod 2
\\&= (2e+m)\mod 2\\
&=m \end{align}

  Note that for this to work we need \begin{align}2|e|+ 1&<\frac p2\\|e|&<\frac p4−\frac 12\end{align} so that $(2e+m\mod p) = 2e+m$.

However, what I am struggling with is, if we choose $e<0$ then \begin{align}2e+m\mod p &= (p-2|e|)+m\\&\neq2e+m\end{align} by the definition of modulo (at least as seen by most common programming languages):

  $a\mod b=r$ where $a=qb+r$ and $0\leq r<b$

Since $p$ is specified to be odd, then we have
\begin{align}&((p-2|e|)+m)\mod 2 \\
&=((p\mod2)-((2|e|)\mod 2))+(m\mod 2)\mod 2\\
&= ((1-0)+m)\mod2\tag{as $p$ is odd}\\
&= (1+m)\mod 2\tag{as $m$ is either $1$ or $0$}\\
&\neq m\end{align}

I'm just trying to understand why we specify $$|e|<\frac p4 - \frac 12$$ and not $$0<e<\frac p4 - \frac 12$$

as, as far as I understand, the decryption doesn't work when \begin{align}0<-e&<\frac p4 - \frac 12\\
\frac 12 - \frac p4 < e &< 0
\end{align}

  Example

  Choose $p=1583$, $q=52498$, then $|e|<\frac{1583}{4}-\frac 12 = 395.25$ so choose $e=-241$

  For $m=1$, we have \begin{align}c&=52498\times 1583+2\times (-241)+1\\
&= 83104334-482+1\\
&= 83103853\end{align}

  We decrypt this as follows \begin{align}D(c,p)&=(c\mod p)\mod 2\\
&= (83103853\mod 1583) \mod 2\\
&= 1102 \mod 2\\
&= 0\\
&\neq m=1\end{align}

  We can see that \begin{align}(c\mod p) &= 1102\\
&= (2\times 550.5) + 1\end{align} and $550.5 > 395.25$ which doesn't satisfy the constraint on $|e|$

Can someone either confirm that my logic is correct, or explain to me where it is falling apart please.

The reference linked states in its Notation section (page vii):

  $a\bmod p\;\;$ Denotes reducing $a$ modulo $p$ into the interval $(-p/2, p/2]$

Thus the definition of $\bmod$ used is the non-standard
$$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;-p<2r\le p$$

This can be viewed as the offset of $a$ from the nearest multiple of $p$ (with nearest selecting the lower as a tie-breaker), as suggested by a comment.

This can be programmed as r = ((a + (p-1)/2) % p) - (p-1)/2, making sure that

things are evaluated as signed integers (which in C can require some explicit casting for unsigned p);
the addition of (p-1)/2 does not cause overflow.


Linear cryptanalysis complete key guessing In linear crypt analysis, partial sub keys are guessed and verified for its correctness with the help of plaintext and ciphertext.

From the partial sub key, how it is possible to guess the complete key?

For example, if we are guessing and verifying the key bits $K_5,K_6,\ldots,K_8,K_{13},\ldots,K_{16}$ for its correctness. But how can we get the complete key? That is $K_0, \ldots, K_{16}$.

As in @Guut Boy's answer it may be possible to brute force the remainder of the key bits.

Another technique would be to find  another multi round linear characteristic which can be used to brute force another subset of key bits. Of course your success probability in doing this would depend on the overall probability of the new linear characteristic, but if the key bits determined by the new characteristic overlap some of the key bits already guessed, this may speed up your attack.


How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext? RSA is not designed to be used on long blocks of plaintext like a block cipher, but I need to use it to send a large (encrypted) message.

How can I do this?

The solution to this problem is to use hybrid encryption. Namely, this involves using RSA to asymmetrically encrypt a symmetric key.

Randomly generate a symmetric encryption (say AES) key and encrypt the plaintext message with it. Then, encrypt the symmetric key with RSA. Transmit both the symmetrically encrypted text as well as the asymmetrically encrypted symmetric key.

The receiver can then decrypt the RSA block, which will yield the symmetric key, allowing the symmetrically encrypted text to be decrypted.

This can be shown more formally as the following. Let $M$ be the plaintext, $K_{AES}$ be the randomly chosen AES key, and $K_{Pu}$ be the receiver's public RSA key you already have.

$$ C_1 = E_{AES}(M, K_{AES}) $$
  $$ C_2 = E_{RSA}(K_{AES}, K_{Pu}) $$

Then, send both $C_1$ and $C_2$.

Let $K_{Pr}$ be the receiver's private RSA key. The receiver can then recover $M$ as

$$ K_{AES} = D_{RSA}(C_2, K_{Pr}) $$
  $$ M = D_{AES}(C_1, K_{AES}) $$

(To allow streaming decryption or large messages, you would usually send $C_2$ first and then (the much larger) $C_1$.)


AES-CBC pre-determined IV vs. null IV Is there any security advantage to using a pre-determined IV in CBC mode over a null IV? I'm implementing a license key system similar to this article on CodeProject, but I'm confused by the authors use of a pre-determined IV embedded in the client code alongside the key. Presumably a properly randomized IV wasn't used because the resulting license key would be too long, but wouldn't a null IV be just as (in)secure?

There's no practical difference between zero IV and any other constant IV here.

With some older ciphers that have a small enough keyspace (or weaknesses that allow reducing it) you could have a rainbow table for the encryption of the zero vector which might make zero IV a weaker choice in some cases, but that would be impossible for AES with its 128-256 bit keys.

Note that when a key is only used to encrypt a single plaintext, a constant IV is secure.


How do institutions like banks do RSA with big primes? When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small primes compared to those in used by banks, one would often choose the Fermat number $65537$ as public exponent $e$, then the private exponent $d$ is $4267793$, which is a huge number when used as an exponent. How do banks etc. decrypt their data when they choose primes for $p$ and $q$ which are 100s of digits?

First of all to encrypt/decrypt data such institutions as banks use some block or stream ciphers for instance AES (Advanced Encryption Standard), which are very fast compared to RSA algorithm, hundreds times faster to process same amount of data. But block and stream ciphers use symmetric key (which is usually 128-256 bits random number, much smaller than RSA keys), it means that both parties A and B who exchange data encrypted with ciphers need to have same symmteric key and for that they need to share securely this key.

To exchange a symmetric key an asymmetric encryption is used. RSA is an example of an asymmetric encryption system. Most asymmetric encryption systems are much slower than symmetric ciphers, mostly due to usage of big numbers (as you mentioned) in computation.

So to exchange a shared symmetric key, used to encrypt large amount of data, we encrypt this key using RSA public key of recipient. Because only small key (e.g. 256 bits long) is encrypted using RSA, quite small amount of time (e.g. 0.5-1 second) is used for that. After that large symmetrically encrypted data and small asymmetrically (using RSA) encrypted key are send to recipient. On the recipient side the opposite is done - first the symmetric key is decrypted using RSA private key and second large data is decrypted using symmetric key with block or stream cipher like AES.

Also usually some integrity check is done, e.g. by using MAC (Message Authentication Code) - MAC is computed on sender side and checked on recipient side. Or instead of MAC a digital signature (using e.g. DSA, Digital Signature Algorithm) is create on sender's side using sender's private key and verified on recipient's side using sender's public key. MAC is an integrity check value created using symmetric algorithms (e.g. AES, 3DES), while digital signature is created using asymmetric algorithms (e.g. RSA or DSA).

To answer your question about large numbers - in order to compute those large exponents by some large modulus arbitrary length big numbers simulation is done with numbers having thousands of bits, i.e. around one thousand decimal digits. I'll give an example of how exponentiation can be computed in a quite fast way instead of straightforward multiplication (which can take forever). All the multiplications, additions, subtractions and divisions are simulated as a huge numbers arithmetic in the memory using algorithms similar to those that we studied at school to e.g. multiply or divide long numbers on paper. To do a fast exponentiation a technique called Exponentiation by Squaring is used. We will compute value of C = M^E (mod N). This algorithm is proportional to the number of bits in exponent E, i.e. does several big number operations (approximately two multiplies and two divisions) per each bit in number E, so if E is from 1024 to 2048 bits (these lengths are usual for RSA) then algo makes around 1024 to 2048 blocks of 2 to 4 arithmetic operations on big numbers. There are two main versions of that algorithm exist, one is iterating through bits of exponent left to right (MSB-first (Most Significant Bit first) order), another one is iterating right to left (LSB-first (Least Significant Bit first) order) (cited from here):

// LSB Binary Exponentiation Algorithm (scans exponent's E bits right to left)
// Input: Exponent: E of k bits, message M
// Output: Ciphertext: C = M^E (mod N)
C =1 ; S = M;
// Scan E's bits from LSB to MSB (right to left).
for i := 0 to k-1
  begin
    // Multiply by degree of M.
    if (E_i = 1) C = C * S (mod N);
    // Square degree of M.
    S = S * S (mod N);
  end;

// MSB Binary Exponentiation Algorithm (scans exponent's E bits left to right)
// Input: Exponent: E of k bits, message M
// Output: Ciphertext: C = M^E (mod N)
C = 1;
// Scan E's bits from MSB to LSB (left to right).
for i := k-1 downto 0 do
  begin
    // Square result.
    C = C * C (mod N);
    // Multiply by M if E's bit is set.
    if (E_i = 1) C = C * M (mod N);
  end;


Would EdDSA be broken by replacing H(R, A, M) with H(A, M)? An EdDSA signature is (R, S) where R = r*B and S = r + H(R, A, M)*s. Notation from Wikipedia en.wikipedia.org/wiki/EdDSA.
Given that the hash function H, is indeed collision-resistant, would using S = r + H(A, M)*s be a secure variant?
In the original EdDSA paper, the authors mention the need for R to protect the signature scheme in case the hash function is not collision-resistant. To me, it indicates that the scheme could possibly be secure even when R is left out from the hash function input.
The reason I ask (in case it is of interest) is that using H(A, M) would be more threshold-friendly. Threshold signatures with that modification in place could be done using 1 round instead of 2 rounds.

This answer is assuming you are not removing the private key $a$ from the computation of $S$, and instead actually meant what is said in the title of the question:

$S = r + a H(A, M)$

Removing $a$ from the computation would be terrible.

The first issue that comes to mind is malleability, on top of collision resistance.
The signature process for EdDSA actually goes as follows:

Input: message $M$, secret key bits $(h_0, h_1, \ldots, h_{2b-1})$,
basepoint $B$  and public key point $A$

$a \gets 2^{b-2} + \sum_{3 \leq i \leq b-3} 2^i h_i$
$h \gets H(h_b,\ldots,h_{2b-1},M)$
$r \gets h\mod \ell$
$R \gets r\cdot B$
$h \gets H(R, A, M)$
$S \gets (r + a h) \mod \ell$

Return: $(R,S)$

As you can see, if you do not include the value $R$ in the hash $h$, the value $S \gets (r + a h) \mod \ell$ can easily be modified in a way that would allow to produce new signatures for the same message:

pick a random $k$
compute the point $R' = R + k\cdot B$
compute the value $S' = S + k \bmod \ell$

And you now have a new, different signature $(R', S')$ for the same public key $A$ that will verify for the message $M$.
This is possible because the value $r$ behind computed with the secret key, it is not meant to be public and is not necessary for verification. This property was used in a fault attack in 2017.
Malleability is not necessarily unwanted in cryptographic scheme, but is often frowned upon since it can very easily lead to issue with implementations.
Threshold cryptography is rough and full of dangers, and I wouldn't advise coming up with a malleable scheme as these have already proven to cause issue with threshold schemes.


Using $key^{th}$ multiple of $\pi$ as a one-time pad With a key $k$ of sufficient length, say 128 bits, is it possible to use $k^{th}$ multiple of $\pi$ as a one-time pad?
Please enlighten on the security as well as practical aspects (only if secure of course).

That is not practical since either you keep a sequence of the bits of the $\pi$ or regenerate them every time. You may need to store 64GB sequence if you want to encrypt such files.
Then you need to multiply it with the 128-bit number. That is not practical, consider multiplication of 64GB number with a random 128-bit number.

OTP needs true random bit sequences like flipping coins, $\pi$ is not since the sequence is there! It is known to everybody.

In modern Cryptography, we use the 128-bit random key with a PRF to produce a long enough secure key-stream to encrypt the message like ChaCha. This is the way we encrypt messages. They are very fast like 3GB/s with AES-NI.
No need to store or heavy calculation like you proposed.

It is not KPA secure yet CPA!. Given message and ciphertext, we can find the 128-bit key by dividing.

How the 128-bit key is transferred is not clear. The better way to use DHKE than a KDF than encrypt with xChaCha20-Poly1305 with this you will get forward secrecy - if you DELETE the key after decryption - integrity, authentication, and integrity where your scheme only may provide confidentiality.


How does RSA public and private key structure look like? So I was reading this wiki about the RSA algorithm and I read this article to understand it better. My goal was to create a simple program that would generate private and public keys. I got to the point where I have the e and n variables for the public key but I have no idea what should I do with them. What's the rule to follow while connecting two of this variables? Sure I can just do it my way because it's not a big deal to transform them into strings and put "&" between them, but this way this key would be readable only by my program and this is not what I try to accomplish. I can't find anything about it on the internet so I ask here for help.

Probably the most widely used standard for this is defined in PKCS#1 (available as RFC8017 as well as PDF from RSA Labs).

In apppendix A, the ASN.1 syntax for the keys is defined to be

RSAPublicKey ::= SEQUENCE {
             modulus           INTEGER,  -- n
             publicExponent    INTEGER   -- e
         }

for public keys. Usually DER is used as the ASN.1 encoding rule. And of course, implementing ASN.1 in all its generality is not particularly easy, but implementing this subfunctionality shouldn't be too hard.


Authentication protocol for communication with Arduino Uno I am using an ECDH key exchange to establish a shared secret between an Arduino Uno and an Android device. For this purpose I am using this library and more specifically Curve25519. This is the confidentiality part of the secure communication I want to establish.

Now, before establishing shared secret between the Arduino Uno and the Android device, I want to have two-way authentication. It would be nice to have some sort of session IDs in order to be able to communicate with multiple Arduino Uno devices from a single Android device.

What do you suggest? Please consider the memory size of Arduino Uno (2kB RAM, 32kB flash).

I am going to assume we're at the application layer here and you're implementing end-to-end (E2EE) encryption.

A public key infrastructure (PKI) could help solve the mutual authentication issue. Without more detail of the project, here is one way to accomplish this.

Both Arduinos and Android share a trusted certificate authority (CA).
Arduinos or Android create their own keys and send a certificate signing request (CSR) to the CA.
CA signs the CSRs and returns them to their respective devices.
Arduinos and Android can now mutually authenticate with each other during ECDH (or maybe even ECDHE).

Here, you're essentially mimicking how TLS provides authentication and confidentiality, but at the application layer. Session Ids can be created by using a secure hash function with your shared secret and some other data. That data will depend upon what you want your session ids to provide (constant ids, unique ids, etc).


Is it bad to expose the public key? I am studying about blockchain and have been focusing on encryption protocols that allow authentication. The digital signature of public and private key seems solid, I have focused on the algorithm ED25519.

But in some places, some people say about not exposing the public key because through the public key and signature it would be possible to derive the private key. Some say that quantum computers will easily accomplish this task.

At first, I thought the reason for the bitcoin addresses was to make the public key "human-readable." But I see that there are some security points having a public key hash.

So I have some doubts:

Is it really a risk of exposing the public key without any treatment?
If so, what are the alternatives?
How does bitcoin, for example, validate the transaction signature with a public key hash and not the public key itself? (After all, it would be "impossible" to reverse a sha256 hash to its origin)

From a cryptographic standpoint it is OK to expose a public key in the sense of revealing its value. The most basic assumption in cryptography involving public/private key pairs is that the value of a public key is public; hence its name.

It is extremely important that an adversary can not alter a public key. Any exposition that would allow alteration must be avoided !

Also, a public key is highly characteristic; so one might not want to reveal one's public key, in order to remain untraceable (and anonymous). However, that might not be enough: unless the signature scheme is designed to prevent this, revealing one's signatures might allow traceability (for some systems it is even possible to reconstruct the public key from signatures).

It is correct that not revealing a public key deprives adversaries from information that a sufficiently powerful adversary can use to find (an equivalent of) the private key and break the system. But we need a public key to be public so that signatures made with the owner's private key can be publicly checked. Concluding that one should not reveal a public key is like saying one should keep the location of a bank's safe room secret: that's an assumption ruled out by design, because it would make the design unfit for the intended purpose.

Yes, hypothetical quantum computers usable for cryptanalysis would allow an adversary to attack a known public key of the kind we use now (and in the blockchain). On the other hand

Currently, available quantum computers are less useful for cryptanalysis than available lightsabers are to break into a bank's safe room.
There is plausible reason to fear that in the signature systems that we use, a few signatures are as good as the public key to an attacker with such hypothetical quantum computer usable for cryptanalysis.

Update: regarding

  How does bitcoin for example validate the transaction signature with a public key hash and not public key itself?

It obtains the public key, validate (or reject) it by hashing it and comparing to the trusted public key hash, then validates the transaction signature against the validated public key. For more, see indiscreteLogarithm's answer.


How Multiplication Table is generated for GF(2^2) field I was unable to solve the multiplication table given in the book for $\mathrm{GF}(2^2)$.However, I have managed to solve the addition table.

Acoording to the Book multiplication is the AND operation, but when I applied this I did not get the answer given in the book.

This is the Table given in the book:

I couldn't replicate the same answers for 10x10 or 11x11.

$\mathrm{GF}(2^2)$ is the finite field of 4 elements, and has minimal polynomial $x^2+x+1$. Throughout this question I will use $ab$ to denote $ax+b$ (ie $10=1*x+0$) - this is standard notation when considering finite fields over $\mathbb F_2$ since it aligns with how we consider bits in bytes.

As you have already seen, addition is done by bitwise xor:
$ab+cd := ab\oplus cd$

For multiplication, we do standard polynomial multiplication, but then must reduce by the minimal polynomial. That is, we use the identity that $x^2=x+1$. So:

$$\begin{aligned}
 ab\cdot cd
   &= (a*x+b)(c*x+d)
\\ &= (a * c)x^2+(a* d + b * c)x + b*d
\\ &= (a* d + b * c +  a * c) x + [b*d +  a * c]
\end{aligned}$$
Now, as discussed above + is xor (denoted $\oplus$), and the hint given by your book is that multiplication of the coefficients is the same as an AND operation (which I'll denote with $\&$):

$$\begin{aligned}
 ab\cdot cd
   &= (a\&d \oplus b\&c \oplus  a\&c) x \oplus [b\&d \oplus  a\&c]
\\ &= [a\&d \oplus b\&c \oplus  a\&c][b\&d \oplus  a\&c]
\end{aligned}$$


How could block encryption in counter mode be secure from viewpoint of entropy? A good block cipher e.g. AES running in counter mode is commonly considered to be secure. Assuming a perfectly random key, one could in this case from $128$ bits generate up to $2^{128}·128$ bits for stream encryption.

However, these bits could evidently have only $1/(2^{128})$ bit of entropy each on the average. Isn't it a paradox that such an encryption could nonetheless be secure?

Summary: an entropy argument shows that block encryption in counter mode can't be perfectly secure.

The remark that any block cipher in CTR mode generates a keystream with very low entropy per bit of keystream is correct. That hints CTR mode is not secure against an hypothetical unbounded adversary. In fact that holds as soon as more bits of keystream are used than there are in the key (or sooner): that unbounded adversary could enumerate all the possible keys, and rule out some keystreams as impossible.

This does not contradict that AES128 is practically safe in most but not all situations, against a real bounded adversary.

As an example of why I write "most but not all situations", consider the feasible case where an exbibyte of data (a fraction of a day's worth of global internet traffic) is enciphered with AES-128 in CTR mode; that's $2^{56}$ blocks, and odds that two ciphertext blocks are exactly identical are a low but sizable $2^{-17}$; should that occur, an hypothetical adversary able to detect and locate that equality (which is much more difficult than the encryption itself, but might still be feasible) would have learnt one tiny bit of information about the corresponding plaintext blocks: they can't be exactly identical; and thus, assuming an all-zero plaintext was characteristic of non-activitly, the adversary would have learnt that there has been activity in at least one of the two spots where the equality is detected.


Prove that the following MAC is insecure I am trying to prove that the following MAC is insecure, but I don't know how to exploit the properties of the pseudorandom function $F$ involved:

Gen generates a uniform $k \in \{0, 1\}^n$.

To authenticate a message $m_1 || m_2$ with $|m_1| = |m_2| = n$, compute the tag $F_k(m_1)||F_k(F_k(m_2))$.

Any help?

I won't give the answer to homework questions, but I will give a hint.

Suppose you learn the tags for $m_1 || m_2$ and $m_3 || m_4$; what other messages could you deduce the tags for?


Is there a relation between security of rounds of DES and Luby Rackoff rounds? DES uses 16 rounds of feistel networks but not considered secure . Where Luby Rackoff constructions which are inspired by DES its proven by Patarin that 7 rounds is secure .

Is there a relation between number of rounds in DES and patarin's results ?

Luby rackoff results are based on assuming the Round Function to be Secure Pseudo Random Functions.  Where as the round functions of DES are not that secure enough which needs more rounds (Triple DES needs 48 rounds )


Why Victor must not know which tunnel Peggy chooses? In the classic description of Zero Knowledge Proof of Knowledge, Victor must wait outside the entrance to the cave while Peggy goes to the fork and choose a side. It's only once Peggy has entered a tunnel and is out of view that Victor comes at the fork and shout the side he wants her to come out from.

I am wondering why this setup is necessary for the proof to really be Zero Knowledge.

Let's try a much simpler experiment. Victor and Peggy walk together down the primary tunnel until the fork. Peggy goes alone in one side and come out the other. Victor did not hear the secret to open the door, but he is now convinced that she knows it. Peggy presented a proof of her knowledge without Victor learning anything apart the fact that Peggy has this knowledge.

Why is this simple setup not enough to model ZKPK?

Here are some hypotheses that I'm working with:

The analogy is crafted this way to model the fact that the attacker would always have a probability of $p=0.5$ to guess the correct answer during the interactive proof. If Victor sees Mallory enter the tunnel and not come out the other side he will instantly know that Mallory does not know the secret. To model a setup closer to reality, the indirection is added so that Mallory can fake knowledge half the time.
The analogy is crafted this way to make a point that Victor does not know some part of the mechanism. In our case, the door in fact only opens in one way, and once Peggy is at the door, she only uses her knowledge half the time. Maybe this is to model a mathematical aspect of the proof. I am dissing this one out but I've seen mentioned.
Victor must not be able to convince anyone else that Peggy has the knowledge she claims. This is often presented with the extra story where Victor taped the whole thing while still not being able to convince a third party because he could have conspired with Peggy and staged the experiment.

I feel this third point is the crucial part.

However, it departs from the usual description of simply proving you know something without revealing it.

Hey, I'm Peggy and I can prove to you that I know a secret without telling it to you!
Oh, and by the way, in addition to not knowing the secret you won't be able to even tell anyone else the simple fact that I know the secret, booya.

Is the concealment of this meta information about the relationship between Peggy and the secret what really makes it Zero Knowledge?

Are there practical consequences of having a scheme that discloses it? (If the proof is interactive Victor wouldn't be able to impersonate Peggy anyway, right?).

To make the point more practical and concrete, let's consider the following simple protocols:

Victor sends a plaintext to Peggy and ask her to send it back signed with her secret key. He verifies the result with Peggy's public key. Proof that Peggy has the private key.
Victor encrypts a piece of data with Peggy's public key and asks Peggy to send back the hash of the data. If the hash match, he has a proof that Peggy knows the private key.

Why are these Protocols not Zero Knowledge proof of knowledge? (or are they?)

The description of this "kid zero knowledge" example follows the strucure of how interactive proofs that are
zero-knowledge usually work:

The prover sends a commitment (walks into one of the two sides)
The verifier challenges the prover (tosses the coin to decide which side the prover should walk out)
The prover gives a response (walks out the side the verifier has told him).

An essential part of interactive proofs that are zero-knowledge which seems to be the source of your misunderstanding is the
zero-knowledge property. This means (informally) that a verifier can efficiently simulate a transcript of a proof without having
access to the prover (and thus only knows the statement to be proven but not the information the prover has) and such
 a transcript cannot be distinguished from a real transcript from a real proof run.

Note that this fact that an interactive proof is efficiently simulatable without having access to the prover, nicely captures the fact that the proof can not leak any information beyond the validity of the statement to be proven. In a real interaction, the verifier can be convinced that the prover knows what he wants to prove, but the transcript can not leak any further information since it can be efficiently simulated. So this idea of indistinguishability of real and simulated transcripts is a nice way of formally modeling the zero-knowledge property.

So now lets look at your example:

  Let's try a much simpler experiment. Victor and Peggy walk together down the primary tunnel until the fork. Peggy goes alone in one side and come out the other. Victor did not hear the secret to open the door, but he is now convinced that she knows it. Peggy presented a proof of her knowledge without Victor learning anything apart the fact that Peggy has this knowledge.

In this example you CAN NOT simulate such a protocol without having access to the prover. You will never succeed in
producing such a transcript without having access to the party knowing the secret (PIN).

However, in the original example you can just throw away all the runs of the protocol where the verifier wants the
prover to come out the other tunnel (where the coin toss does not yield the same choice as Peggies choice for the tunnel to walk in) and only keep those where Victors coin toss says that Peggy has to come out the same tunnel she went in
(and thus does not have to know the secret).

Your other approaches

  Victor sends a plaintext to Peggy and ask her to send it back signed with her secret key. He verifies the result with Peggy's public key. Proof that Peggy has the private key.

As in your modified Alibaba example, you cannot simulate a transcript without having access to the prover (who knows the signing key - assuming that
you work with a secure signature scheme).

  Victor encrypts a piece of data with Peggy's public key and asks Peggy to send back the hash of the data. If the hash match, he has a proof that Peggy knows the private key.

This protocol is efficiently simulatable, but you would have to prove all properties required by zero-knowledge proofs to hold that you can show that it is an interactive proof that is also zero-knowledge.


Mathematical explaination of file encryption for multiple persons with multiple keys Let's say I want to encrypt a document which only can be read by John, Mike, and Dave. This can easily done with PGP/GPG:

Import John‘s, Mike‘s, and Dave's public key
Encrypt the document using those keys, and send it to them
Each of them can decrypt the document using their own private keys.

What I don't understand is the math behind this. How to encrypt data using more than 1 keys? When I studied cryptography at the campus, I learnt the basics of RSA, but only limited to someone encrypting a document for me using my public key, then decrypt it using my private key. Never tried doing this for multiple persons.

What PGP (like pretty much any software that can do bulk data encryption with public keys) does is hybrid encryption.  Basically, it generates a random key for a symmetric cipher (e.g. AES), encrypts the file with that randomly generated key, and then encrypts the random key with the recipient's public key and attaches it to the encrypted file.  When decrypting, it first uses the recipient's private key to decrypt the encrypted symmetric key attached to the file, and then uses that symmetric key to decrypt the actual content of the file.

Wikipedia's article on PGP has a nice diagram illustrating this process:

Diagram from Wikimedia Commons, by "xaedes & jfreax & Acdx"; used under the CC By-SA 3.0 license.

One of the main reasons why hybrid encryption is so widely used is that symmetric ciphers like AES tend to be much (as in, hundreds or thousands of times) faster than asymmetric ciphers like RSA in encrypting large amounts of data.  But it also has a number of other convenient features — including, notably, that it's very easy to extend the process to allow for multiple recipients, simply by making multiple copies of the random symmetric key, encrypting each one with a different recipient's public key, and attaching all of these encrypted keys to the message.  The recipient then just needs to locate the correct encrypted key (e.g. based on attached metadata, or even just by trying them all until they find one that decrypts into something sensible and consistent), decrypt it and then proceed to decrypt the data with it.


Finding Elliptical curve points and encoding text using them I recently got into learning Elliptical curve cryptography and are currently building a project in C#.

Everything is working well so far, I can encode and decode points, and thanks to this forum I can do point addition and doubling really fast. Now I want to take the next step and start using really big numbers, so far I've been working off different ECC samples and papers normally using really small primes and numbers for clarity. The end goal is to being able to encrypt and decrypt a text, this will later be used for digital signing of this text. So what I must figure out now is:

What standard curves could I use? I know curves like p192 etc exists, am I allowed to use these?
How can I find valid points to use for messages and generator on these huge curves? So far I've done it using brute force on smaller curves with a small prime. I can't find any using my previous brute force approach since the numbers are too large.
Whats a good way for encoding/decoding text using ECC? Should I simply map each valid character to a point on the curve and perform encryption/decryption once for each character and translate between the character and point using a lookup table?

Thank you!

What standard curves could I use? I know curves like p192 etc exists, am I allowed to use these?

Yes, of course you may use those, for more curves - including safer ones - check the safecurves website.

  How can I find valid points to use for messages and generator on these huge curves? So far I've done it using brute force on smaller curves with a small prime. I can't find any using my previous brute force approach since the numbers are too large.

This is part of key generation procedure. For Elliptic Curve the private key is a vector (usually of order N) and the public key is calculated for this particular vector. So this is basically asking how EC key generation takes place (for which there are tutorials available online, I won't completely explain it here).

  Whats a good way for encoding/decoding text using ECC? Should I simply map each valid character to a point on the curve and perform encryption/decryption once for each character and translate between the character and point using a lookup table?

No, you shouldn't directly encrypt anything with EC crypto, try and look up ECIES instead, it is basically ECDH key agreement coupled with symmetric cryptography on the derived key. Start with ECDH and then implement ECIES. Progress on with ECDSA if you want to have signatures.

EC is different than RSA in this regard, you cannot just alter the padding scheme (as there is no padding scheme).


Regarding matsui's Paper on Linear Cryptanalysis of DES I am going through the the Paper by Matsui on Linear Cryptanalysis of DES. In that, he says

$NS_{5}(16,15)=12$

And then in the next paragraph he says considering the expansion and permutation phases the following equation holds good:

$X(15)\bigoplus F(X,K)[7,18,24,29]=k[22]$

Can somebody help me understand this, because I can't find a relation between the first equation and the second one?

Let us denote by $x = x_5x_4x_3x_2x_1x_0$, where $x_i \in \{0, 1\}$ the input of a DES S-box and by $y = y_3y_2y_1y_0$, with $y_i \in \{0, 1\}$ its output. Basically, $\mathrm{NS}_5(16, 15) = 12$ means that for S-box #5, the relation $x_4 = y_3 \oplus y_2 \oplus y_1 \oplus y_0$, where $y = S_5(x)$, holds with probability $\frac{\mathrm{NS}_5(16, 5)}{64} = \frac{12}{64} = \frac{1}{2}-\frac{5}{16}$, which is a fairly biased value (one would expect this value to be very close to $\frac{1}{2}$ in an ideal situation).

Starting from this observation, Matsui builds the 1-round linear approximation $X_{15} \oplus F(X, K)_7 \oplus F(X, K)_{18} \oplus F(X, K)_{24} \oplus F(X, K)_{29} = K_{22}$ that holds with the same probability $\frac{1}{2}-\frac{5}{16}$. Note that, for S-box #5, $x_4$ can be traced back to $X_{15} \oplus K_{22}$, taking into account the $\mathrm{EP}(.)$ transformation as well as the key-schedule algorithm, and $y_3y_2y_1y_0$ can be propagated to bits 7, 18, 24 and 29 of the output of the round function, this time taking into account the effect of the bit permutation $\mathrm{P}(.)$.


Cipher Feedback Mode - sizes of the blocks and shift registers I have a question regarding the resulting sizes of the blocks and shift registers in Cipher Feedback Mode.

In the web there are different pictures to illustrate the CFB-mode.

Now on the first picture there are no shift registers at all. I dont understand which special case the first picture describes. Is really the entire ciphertext (after the XOR with the plaintext) is taken as the argument in for the next block or just s bits?

What if I use the CFB-128 Mode with the following assumptions:

IV size is 128bits
Key is 128bits
CFB-Mode is CFB128
Plaintext is 256bits.

Is the resulting ciphertext of this operation always the size of the Key (128 bits in this case)? If yes is the ENTIRE ciphertext taken as the argument for the next Encryption block? I am confused about the sizes and the pictures describing it.

EDIT: Another question which I have is: What is the resulting ciphertext at the end?
Is it just the last ciphertext block or is it a concatenation of all blocks (c0+c1+c2...+cn)?

I dont understand which special case the first picture describes. Is really the entire ciphertext (after the XOR with the plaintext) is taken as the argument in for the next block or just s bits?

It depends on what version of CFB you're using.  In the olden days, they used to try to encrypt (but not integrity protect) communication channels.  What some random (non-attacker generated) errors could do on these channels is insert or remove a few bits or bytes.  If we consider (say) CBC mode, this insertion or deletion would cause the blocks on the sender and receiver to not line up, and so receiver would just get gibberish.  What the special property of CFB-s is that, assuming if we insert/delete a multiple of s bits, the next 64 bits (assuming DES, after all, this is the olden days) would be garbled, but then (assuming no further errors) everything else would be received properly.  Now, the cost of this is that each set s bits would require a separate DES encryption/decryption, however this was deemed an acceptable cost.

Now, in the more modern days, we don't care about this resynchronization property (we assume instead if the decryption result isn't exactly the same as the original plaintext, it needs to be discarded), and so if we use CFB mode at all, we use the full size (CFB-128, assuming AES, after all, we've stepped back into the modern days).

Because we don't care about CFB-s for s < 128, modern descriptions omit the shift registers (which are no longer needed).

And, to answer your questions

  Is the resulting ciphertext of this operation always the size of the Key (128 bits in this case)?

Nope; the size of the ciphertext is always the same size as the plaintext, that is, 256 bits (plus the IV if you explicitly send it).

  What is the resulting ciphertext at the end?

The ciphertext generated by the CFB process is all the blocks.  After all, if we encrypt a 256 bit block, it'd be rather hard for the decryptor to reconstruct it if we handed him a 128 bit block...


RSA signing - does EMSA-PKCS1-v1_5 padding need to be verified? I am working with an embedded system that accepts firmware updates only if they are validly signed by a particular 2048-bit RSA private key (the embedded system's bootloader knows the corresponding public key).

On the publishing side, the signature is generated by:

computing the SHA-256 hash of the firmware image
padding it according to EMSA-PKCS1-v1_5 (which involves prepending a fixed 1792-bit string)
signing the concatenated 2048-bit value by exponentiation with the RSA private key

On the embedded side, the signature is verified by:

independently (re-)computing the SHA-256 hash of the received firmware image
recovering the concatenated 2048-bit value from the signature by exponentiation with the RSA public key
verifying that the first 1792 bits of the value exactly match the expected padding string
verifying that the last 256 bits of the value (i.e. the SHA-256 hash computed on the publishing system) exactly match the hash computed on the embedded system

So, the question:

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system?

(This is a theoretically-motivated question; I want to educate myself.  It's not a significant added cost on the embedded side to verify the padding.)

P.S. I've attempted to search for existing questions/answers already, and Attacking RSA signature verification that ignores padding is very close.  In that case though, I gather that the implementation basically searched the entire recovered 2048-bit value for a substring matching the recomputed SHA-256 hash; and the possibility of having garbage data after the hash specifically made attacks like this Kindle HDX hack possible.

In this case I'm specifically wondering whether it's a bad idea to simply ignore/remove the first 1792 bits (assumed to be the padding) and only compare the last 256 bits to the expected hash.  Does that open the possibility for the same type of attack?  Or for different attacks?

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system?

Yes. That's paramount for small RSA public exponent $e$.

For $e\in\{3,5,7\}$, the easily computed integer $s=h^{(e^{-1}\bmod2^{254})}\bmod2^{256}$ is an acceptable signature for any message with an odd SHA-256 hash $h$ (that is about one message out of two). The attack can be extended to $e=9$, and with significant computational effort to $e=11$, by trying multiple messages until $s$ thus computed verifies $s<\sqrt[e]N$. The number of odd $h$ to try is about $2^{256}/\sqrt[e]N$.

That works because by construction of $s$, it holds $s^e<N$, therefore $s^e\bmod N=s^e$. Therefore $(s^e\bmod N)\bmod 2^{256}$, which is what's checked by the question's faulty signature verification procedure, is $h^{(e^{-1}\bmod2^{254})e}\bmod2^{256}$, that is $h$ for odd $h$ (notice such $h$ is coprime to $2^{256}$ and $\lambda(2^{256})=2^{254}$, where $\lambda$ is the Carmichael function, such that $\forall m>0$ and $\forall a$ coprime to $m$, $a^{\lambda(m)}\bmod m=1$).

If there is an attack working for $e\ge13$ for the question's parameters, I want to know. But as the saying attributed¹ to the NSA goes: "Attacks always get better; they never get worse".

The conclusion is that we should fully check RSA signature padding. In my opinion, it's not a sufficient reason to systematically avoid very small $e$, which should only be an extra precaution taken when we can afford the $\approx8$ time penalty in signature verification incurred by using the standard $e=F_4=2^{(2^4)}+1=65537$. Additionally, we should use a padding with an argument of reducibility to the RSA problem like that in RSASSA-PSS, or ISO/IEC 9796-2 scheme 2 or 3.

Incorrect verification of PKCS#1 V1.5 type 01 signature at least used to abound. That was first made public by Daniel Bleichenbacher's RSA signature forgery based on implementation error (account by Hal Finney of Crypto 2006 rump session). Among later derived attacks: Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann, Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and the BERserk vulnerability. I have always wondered if "never attribute to malice what can be attributed to incompetence" really applies to these faulty implementations.

¹ by Bruce Schneier in Applied Cryptography IIRC.


How to use a random 32 byte sequence as a curve25519 public key According to the Wikipedia Curve25519 article, Curve25519 "accepts any 32-byte string as a valid public key and does not require validation"

However, I need to provide BouncyCastle with a 33 byte key. I have attempted to simply prepend 0x02 or 0x03, and this sometimes is accepted. However I often get the exception "x value invalid for Curve25519FieldElement" or "Invalid point compression".

Is the wikipedia article incorrect, and e.g. do I need to ensure that the x coordinate does not exceed the Curve25519 group order 2^252 + 27742317777372353535851937790883648493?

Indeed, you seems to be right since when taking a look at the BC code, we find in the Curve25519FieldElement object that:

if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0)
{
    new IllegalArgumentException("x value invalid for Curve25519FieldElement");
}

So in BouncyCastle it appears that you have to make sure that x.CompareTo(Q) < 0, which effectively means that you should restrict your x coordinate to something below the $Q$ value, however this is not the group order, but the field order, which is $2^{255}-19$. This is normal, since this represents an element of the Field...

Now, you've remarked that the Curve25519 has been designed to accept all 32 byte public keys as a valid point encoding:

Firstly, a value on 32 bytes is within $\{0,1,\ldots,2^{256}-1\}$, that is $2^{256}$ possibilities, while the field order is $2^{255}-19$, which means that you only have $2^{255}-19$ elements in your field...

But now, the function Curve25519 is actually defined in the paper thanks to the theorem 2.1 as being a function that producing $s$ (in little endian) out of an integer $n$ and a point $Q$ (both encoded in little endian), such that $s$ is the unique $s\in F_{2^{255}-19}$ such that $X_0(nQ)=s$  for the function defined as $X_0:E(F_{(2^{255}-19)^2}) \to F_{(2^{255}-19)^2}$ such that $X_0(\infty)=0; X_0(x,y)=x$, if we let $q\in F_{2^{255}-19}$ and $n$ be an integer for all $Q\in E(F_{(2^{255}-19)^2})$ such that $X_0(Q)=q\bmod 2^{255}-19$, and here this modulo reduction is why you are having a problem, I think.

This is actually pretty well explained in the paper:

  Fix $q\in\{0,1,\ldots,2^{256}-1\}$ and $n\in 2^{254}+8\{0,1,\ldots,2^{251}-1\}$. By Theorem 2.1, there is a unique integer $s\in\{0,1,\ldots,2^{255}-20\}$ with the following property: $s=X_0(nQ)$ for all $Q\in E(F_{(2^{255}-19)})$ such that $X_0(Q)=q \bmod 2^{255}-19$.

Here your public key is the value $q$ and $n$ is the secret key.

Which means that we actually have collisions in the Curve25519 function, which are handled within the function. I imagine that BouncyCastle, depending how they've implemented this, might be converting the computed values into Curve25519FieldElement only AFTER having passed the values through the Curve25519 function...

So I think you are probably providing the public key in a wrong way, using the wrong object to store it... Which is not a problem when used as the output of the Curve25519 function, but is a problem when using your own values.

You might want to compute for your point $P$ the output of $X_0(\underline{1}\cdot \underline{P})$ and then encode that value as a public key, to have the correct format.


Does this protocol provide Perfect Forward Secrecy / are there potential security flaws? We have

a HMAC key (128 bit/16 bytes)
an AES key (128 bit/16 bytes)
an AES IV (128 bit/16 bytes)
a random salt (128 bit/16 bytes)

Each packet is signed with a HMAC (SHA256)

After each packet is sent, all those keys are packed together into a 64 byte array (HMAC + AES Key + AES IV + salt). Take the SHA512-hash of that nonce. Take the result and:

xor the first 16 bytes with the HMAC
xor the second 16 bytes with the AES key
xor the third 16 bytes with the AES IV
xor the fourth 16 bytes with the salt

The keys are generated using the Windows's Random Number Generator and shared via RSA with OAEP padding (PKCS #1 v2.1).

No, this protocol does not provide perfect forward secrecy. Record the initial key transport message (shared via RSA-OAEP). If the attacker later gets access to the corresponding RSA private key, and decrypts the original key transport message, the entire symmetric key evolution sequence for that session will trivially unfold.


Is AES-CTR or ChaCha20 vulnerable to a time-memory trade off? Is AES-CTR or ChaCha20 vulnerable to a time-memory trade-off attack?

According to this paper it seems to be, which would put AES-CTR at a clearly breakable $2^{64}$ security level (for AES-128-CTR).  Since AES-128-CTR is not considered breakable something is wrong with this statement and I would like to know what.

This is not a concern; the model of costs that the paper uses is unrealistic.  In the paper, they state:

  In other words, the attacker is given unlimited amount
  of time in preparation

(Section 2, second paragraph)

That is, they assume that the attacker can easily spend $O(2^{128})$ time (or more, if necessary) to generate a Hellman table (or Rainbow table) for AES-128.

Yes, once an attacker does that, he can attack AES-128 (at least, against the plaintext he used while building the rainbow table) faster than he would otherwise.

However, it is generally believed that $O(2^{128})$ effort is infeasible, even as a one-time effort.


Determine whether bit sequence is hash? I would like to know whether it is possible to determine whether a value of for example 256 bit length is a SHA-256 hash or a random, equally distributed value. Is there any research related to common hash functions? Can this property be derived from the avalanche effect?

I would like to know because I would like to include plain text hash values in a steganographic medium, where the stegosystem bases on white noise to be turned into sentences, with number of words per sentences, that have the same distribution of length as usual in this language. Encryption of the hash values is not possible, because at that point of the designed protocol, no key exchange has been performed, yet.

Thank you for all answers or questions related to this problem.

A SHA-256 hash is, until broken by cryptanalysis, indistinguishable from 256 bits of random noise. The only way to defeat this is by enumerating inputs until you find a matching hash.

If there isn't much entropy in the input (e.g., it's an English word, or it's a value that repeats), it will be relatively simple for an attacker to distinguish it from random noise and possibly even determine the data that was originally hashed.


Shanks's Babystep Giantstep Algorithm running time BigO I am working through Introduction to Mathematical Cryptography and am not in school anymore, so I don't have any advisers or peers to ask (my background is a BS in math). In the text they present the Shanks's BS-GS Algotrithm with a proof. I am having trouble figuring out how the total running time of the algorithm follows from the running time its parts.

The algorithm says to create two lists which each have length $n$. I understand how this ends up being about $2 \cdot n$ multiplications. Then they say comparing the lists takes $\operatorname{BigO}[\log(n)]$ steps and then jump straight to "hence the total running time is $\operatorname{BigO}[n \cdot \log(n)]$." Since the steps are done separately, why do we multiply instead of add the running times?

This is because, the elements of the full group conceptually end up in an $n\times n$ table, and the comparison of the column (giant step list) must be done on every row of length $n$ since the overlap of the lists is in a single unique row (which allows you to determine the answer you're looking for, e.g., discrete log uniquely). So you repeat the comparison at worst $n$ times, on average $(n+1)/2$ times until you find a collision.

The presentation on Wikipedia is quite good, their $m$ being your $n$ since your listsize $n$ is $\lceil \#G \rceil$, so roughly the square root of the size of the group.


Are RSA-PSS parameters standardized? I wish to agree with a 3rd party on using RSA-PSS algorithm for a implementing a Digital Signature Scheme. I want to avoid selection of RSA parameters like salt length, hash algorithm etc at my side and share the required configuration parameters.

Instead I want to refer to a standard where all the parameters are already standardized so that we both can commonly refer to the same standard. We will perform signing at his side and verification at my side.

Are these parameters stardized by FIPS or IETF or ISO/IEC so that we can avoid a big deal of overhead? If yes, which standard deals with this?

Let's first get rid over two parameters that only have one option: the Mask Generation Function (MGF) and the trailer field. These can only be configured to MGF1 and 1 respectively in RFC 3447 which specifies RSA-PSS.

You won't find a generic standard that chooses one hash over the other for MGF1 because any hash will be considered secure, including the default (SHA-1). On the other hand, there will be many higher level protocols or applications that will have chosen one specific set of configuration parameters.

If we take a look at RFC 4055 where the PSS is used for X.509v3 certificates (the ones you will find used for TLS in e.g. your browser) we'll find that the configuration options can be indicated for a specific public key within a certificate:

RSASSA-PSS-params  ::=  SEQUENCE  {
     hashAlgorithm      [0] HashAlgorithm DEFAULT
                               sha1Identifier,
     maskGenAlgorithm   [1] MaskGenAlgorithm DEFAULT
                               mgf1SHA1Identifier,
     saltLength         [2] INTEGER DEFAULT 20,
     trailerField       [3] INTEGER DEFAULT 1  }

As you can see, all values have their default, so this would be an easy set of rules to comply with. Within certificates the public key and its parameters are signed, so the security of the parameters should be guaranteed.

However, there is one additional detail:

  The maskGenAlgorithm field identifies the mask generation
           function.  The default mask generation function is MGF1 with
           SHA-1.  For MGF1, it is strongly RECOMMENDED that the
           underlying hash function be the same as the one identified by
           hashAlgorithm.

Of course that would mean changing the default by specifying the MaskGenAlgorithm and mgf1SHA1Identifier for field [1]: maskGenAlgorithm. As SHA-1 is considered broken and therefore not an option for hashAlgorithm, that means that another hash algorithm should be chosen.

As all other parameters are set, that means the hash function becomes the only configuration parameter.

Now as SHA-2 is in common use is it probably the best family of hash algorithms to choose from. SHA-224 and SHA-384 are simply shorter output functions of SHA-256 and SHA-512 and they don't make much sense for signatures. So that leaves the choice of one of the two. SHA-256 is used most and has hardware support on many chips. SHA-512 is using 64 bit operations and is both fast and secure on 64 bit chips.

For compatibility reasons and the hardware support I'd probably slightly favor SHA-256. It still has plenty of security and hashes data at over twice the speed using hardware support.

So there we are: SHA-256, MGF-1 with SHA-256, 20 byte salt and a trailer field set to 1. Just communicate this with your friend by explicitly describing it in your protocol and you're all set when it comes to PSS.

That just takes care of the PSS parameters. You'd also want to specify how you're going to trust the public key (oh dear, did I mention X.509 certificates?), and what (minimum) key size to use. Any key size of 3072 bits or over is OK, but I'd stick to 3072 bits which has the same security level as SHA-256's collision resistance at ~128 bits of security.