How is pre-master secret encrypted when ECC is used? The certificate used in https://de.wikipedia.org/wiki/Authenticated_Encryption
has

public key ECC
public key parameter ECDSA
key usage digital signature

It is used to setup a secure TLS connection.

So far I know, that a so called pre-master-secret is generated by client ant sent encrypted to the server, using its certificate.

But what crypto-primitive is used for encryption in that case? The public key is used for digital signature, ECDSA, but signing something is NOT encryption.

How then is the pre master secret encrypted?

How then is the pre master secret encrypted?

It isn't.
What you're looking at is the ECDHE key exchange for TLS.
The short description is that the server and client run a classic Diffie-Hellman  key exchange (on an elliptic curve) and use the resulting shared secret as the pre-master secret. This is unlike the RSA Key-Transport case where the client picks a pre-master secret and sends a public-key-encrypted copy to the server.

Now for the technical details (from RFC 5246: "The Transport Layer Security (TLS) Protocol Version 1.2"):
The client sends its list of supported cipher suites (in ClientHello) and the server responds with the cipher suite picked, which is TLS_ECDHE_ECDSA_CHACHA20_POLY1305 in this case (happens in ServerHello). In the same run the server sends its public, ephemeral ECDH key (in ServerKeyExchange) which is most likely a point of Curve25519. The client receives this and responds with his hown public key (again a point) and the client also computes the shared point and then uses the full x-coordinate as the pre-master secret. As soon as the server receives the client's public key it also computes the pre-master secret (ie the x-coordinate of the shared point).

Now both parties share the same pre-master secret, exchanged using ECDHE.


No Birthday Attack to TCR I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” , which compared TCR (Target Collision Resistant) and ACR (Any collision Resistant). It says

  we wish to stress one important practical advantage of TCR over ACR: because $x$ must be specified before $K$ is known, birthday attacks to find collisions are not possible

I understood the definition of the notion of $TCR$, but my question is:

Why is a birthday attack is not possible?

My other questions related to the same paper:
Dependence on Keyed Hash Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance

I am literally quoting the paper here. You should really try to read the paper properly first before asking questions.

  In the notion of [22] the adversary does not get credit for finding any old collision. The adversary must still find a collision $M, M'$  but now $M$ is not allowed to depend on the key: the adversary must choose it before the key $K$ is known.

I can't really give an example of this, just as I can't give an example of why I can't produce light with a brick.


Transferring Encrypted One-time pad over the internet I was working with one-time pad, and as I understand , for one time pad to be 100% secure a key shouldn't be repeated. So assuming Alice and Bob have to exchange messages over the network secured over OTP, they both have to have the same key, which should happen by physically meeting and sharing the key on a drive for a example.

However I thought, if Alice and Bob had another type of encryption, symmetric encryption like AES, and they wanted security over OTP without meeting, couldn't just Bob generate OTP, encrypt it with AES, and send it to Alice over the network, and then it would be equally secure since the encrypted OTP was gibberish and still is gibberish before being encrypted and after being encrypted, therefore it is not susceptible to brute-force or cryptanalysis or other.

Am I correct ?

No, encrypting the key with another cipher (AES) reduces the security of OTP to the security provided by this cipher (AES) or by the security measurement used to protect the encrypted key.

First of all, another requirement for OTP to be 100% secure is, that the key is chosen from random.

Example:

Assume Alice and Bob share a secret AES-Key $K_{shared}$. Alice generates a new, random key $K_{OPT}$ and encrypts it using AES: $C = Enc_{K_{shared}}(K_{OPT})$.
Alice sends the encrypted key $C$ over to Bob (lets ignore the
problem of authentication etc. for the moment).
Eve intercepts the message. In order to retrieve $K_{OPT}$, Eve has to decrypt the message $C$. This takes only as much effort as it takes to break the cipher based on the key $K_{shared}$.

The encrypted $K_{shared}$ is supposed to look like gibberish, but only to the extend, that a cipher(AES) is able to achieve.

If you are actually looking into exchanging a OPT key without meeting take a look into Quantum Key Exchange: https://en.wikipedia.org/wiki/Quantum_key_distribution
But thats more like the art of black magic than cryptography ;)


How to confirm my implementation is constant time I'm implementing Schnorr signatures following a variant used in Bitcoin Cash (BCH) of this algorithm: GitHub - Schnorr Signatures for secp256k1.

A notable difference is that the BCH schnorr algorithm uses this variant: IETF - Variant for k calculation.

I'm in scala using bouncy castle from Java. I calculate k by using something i call here nonceRFC6979 which is the implementation what i showed on the link above

    def sign(unsigned: ByteVector, privkey: PrivateKey): Result[Signature] = {
      val d = privkey.toBigInteger
      val N = ecc.domain.getN
      val G = ecc.domain.getG

      /** Calculate k*/
      val nonceFunction = nonceRFC6979
      nonceFunction.init(N, new ECPrivateKeyParameters(d, ecc.domain).getD, unsigned.toArray, additionalData.toArray)
      val k0 = nonceFunction.nextK.mod(N)
      if (k0.equals(BigInteger.ZERO)) Failure(Err("Fail to generate signature"))

      /** R = k * G. Negate nonce if R.y is not a quadratic residue */
      val R = G.multiply(k0).normalize
      val k = if (hasSquareY(R)) k0 else N.subtract(k0)

      /** e = Hash(R.x || compressed(P) || m) mod n */
      val P        = G.multiply(d)
      val pubBytes = P.getEncoded(true).toByteVector
      val rx       = R.getXCoord.toBigInteger.toUnsignedByteVector
      val e        = Sha256.hash(rx ++ pubBytes ++ unsigned).toBigInteger.mod(N)

      /** s = (k + e * priv) mod n */
      val s = e.multiply(d).add(k).mod(N).toUnsignedByteVector

      /** Signature = (R.x, s) */
      val sig = rx ++ s
      Successful(Signature(sig))
    }

this is the nonceRFC6979 implementation its identical from HMacDSAKCalculator on calculating nextK the only difference as mentioned before is that we append some extra data here named additionalData

Now I'm trying to make this signing algorithm constant time to avoid timing attacks. My understanding is that multiplycould be an issue particularly kG. from looking at the above code and for those that know Bouncy castle, what should i bee looking into to check that this is indeed constant?

How to confirm my implementation is constant time? I'm in scala using bouncy castle from Java.

This code is not constant time, for no platform is specified. Computing platforms that run in constant time or cycles are the exception. I don't know any device with internet and video currently for sale that does. That's actually contributing to make attacks harder!

For cryptographic security, what matters is Data-Dependent Timing Variation: execution time that varies depending on the data manipulated¹. The question's code most likely exhibits some DDTV, since it apparently uses Java's BigInteger type, which is not designed to avoid DDTV, and doesn't even come close. Bouncy Castle is riddled with DDTVs where it uses BigInteger, more or less sizable depending on version and platforms, at least in it's generic RSA decryption code (the only part I have studied in depth). The BC developers approach that issue by lowering DDTV when that's easy, and trying to hide it with some degree of noise when that's not. That's probably the best they can in the framework of a portable Java crypto library.

Except starting from scratch using techniques geared for constant-time down to the bare hardware for all the crypto primitives (like done for crypto accelerators in high security devices, and in BearSSL), I see little hope to reach zero DDTV, which is the most satisfying option form a security standpoint, and is practiced.

For lack of that, the only option is try making DDTVs low enough that they do not open to attack, and try to assess that. It's complicated.

In the following I'll discuss just a few down-to-earth incremental countermeasures that can be added on top of existing libraries, and may help. I'm sure neither that its necessary, nor sufficient, nor even certainly without security drawback.

One general-purpose countermeasure, effective in theory (even perfectly so) is to start a timer at the beginning of the calculation, set to elapse after it ends considering a worst-case scenario (perhaps, the experimental maximum time plus a few times the experimental standard deviation $\sigma$), and at the end of the calculation wait precisely until the timer elapses before releasing the result. But that's a portability nightmare; adversaries (or poor control of the platform) can increase the computation time (e.g. by adding workload) or slow the CPU so that it exceeds the timer; or maybe adversaries will manage to get a measure of CPU time not accounting for waiting that the timer elapses.

Another countermeasure adds a random delay. It needs to have fine granularity. A simple method draws a uniformly random integer and wait that number of cycles (or if not possible, dummy loops²), with the maximum integer calibrated for an average of a few $\sigma'$ ³ for lack of a more rationally determined value⁴. While it is possible for an attacker to mitigate such delays by correlating different experiments, or repeating the same and averaging or keeping the minimum measured time⁵, they are useful by adding uncertainty in the adversary's inputs, which tends to make a successful attack require more measurements, thus more time.

Problem with the above delays (final or randomly added) is that they are not or marginally useful against side channels other than pure timing (differential power analysis, electromagnetic and audio variants, hardware features like caches..).

A general class of countermeasure targeting a wider spectrum of side-channel attacks is blinding. The general principle is to mix-in a random value that changes how the computation is made (hence its timing and other side-channel leakage, in a manner unrelated to secret data), but not its final outcome, thanks to mathematic properties.

One blinding countermeasure applicable to computations modulo $n$, for example that of $s=(k+e\cdot\text{Priv})\bmod n$, is to

add $r_i\cdot n$ for random(s) $r_i$ (say in range $[0,2^{64})$ ) to some or all inputs (here $k$, $e$, $\text{Priv}$ ) of the formula
perform the computation modulo $u\,n$ instead of $n$, for some $u$ (say in a range $[2^{63},2^{64})$, fixed or dynamically chosen at random),
finally reduce modulo $n$.

Another countermeasure in that spirit, with a chance to make timing differences in elliptic curve scalar multiplication less exploitable, while only increasing the execution time moderately (like 30%), is to indirectly generate $k$ and compute $R=k\times G$ (where $\times$ is point multiplication on the elliptic curve):

Choose some parameter $m\approx2^{32}\sqrt n$ and precompute $G_m=m\times G$ ($m$ can be fixed and public including a power of two, or a secret randomly chosen at a time when performance does not matter much).
Generate random $k_a$ and $k_b$ in $[0,m')$ with $m'\approx m$, perhaps fixed $m'=2^{\left\lceil\log_2(m)\right\rceil}$
Compute $R=(k_a\times G_m)+(k_b\times G)$ where $+$ is point addition on the elliptic curve.
Use $k_a\cdot m+k_b$ instead of $k$ in the computation of $s=(k+e\cdot\text{Priv})\bmod n$. The choice of the equivalent $k$ is not quite perfectly uniformly random, but it remains fine for the purpose of Schnorr signatures. The reduction modulo $n$ can be differed to the final computation of $s$. The test $k=0$  can be replaced by a check of $R=\infty$ (in practice that will only occur if there is some bug or fault, e.g. in the RNG, and the best course of action is to zeroize/burninate the private key, if that causes no huge loss).

Conclusions:

Forget about constant time on most modern computing platforms.
Zero DDTV is desirable and achievable, commonly in hardware, and even in software, but forget about it when using Java's standard BigInteger class.
Starting from this code, the most reachable short-term objective is mitigating DDTVs to bring them below the level where they are demonstrably exploitable by known means in practical conditions.
How, and how to assess it, are vast subjects, barely touched in this answer.

¹ We really only care for data that is secret, but in this code fragment a lot is.

² With the issue that they could get optimized out by a smarter compiler, or JITC of the target platform.

³ Contrary to the previous $\sigma$, this $\sigma'$ needs to account mostly for DDTVs, not for platform-related variability.

⁴ Computing how much is necessary would require some model of the actual DDTVs, and an hypothesis on the time available for the attacker.

⁵ Which (from an attacker's perspective) is a more robust strategy than averaging if measurements are plagued by spurious activity adding to the timings. A distribution of the random delays that seldom is minimum, including near Gaussian as resulting from multiple equal delays spread along the calculation to thwart resynchronization, will give a harder time than a uniform delay to an attacker that must rely on this strategy.

Orphan note: It conceivably could help to replace random sources used in random delays and blinding by a CSPRNG, keyed by a long-term random symmetric key and the input of the computation (here, the message to sign). That will make timing deterministic, thwarting any attempts to remove the random delays (explicit, or induced by blinding) using multiple measurements with the same input. But that might not be a good idea: it's typically a better attack strategy to correlate timing measurements with as many varying inputs as possible, rather than repeating fewer measurements to make them more precise; the timing is deterministic only inasmuch as the adversary can't force the re-seeding of the fixed long-term random symmetric key; and being deterministic can well turn a disaster if the adversary manages to extract that key, or if the input of the computation is secret, or if the adversary is trying to synchronize a fault-injection attack.


Why is ISAAC not a pseudo random number generator? I have been accused of confusion over the nature of the ISAAC algorithm.  The bulk of evidence suggests that it is a cryptographically strong pseudo random number generator.  By bulk I mean the number of authoritative references pointed to by a Google search of "isaac prng cipher".  I offer:-

Bob, the guy who wrote it

Apache Commons random number generator

The Aumasson paper assessing it as a generator

CCAN random number module

Yuen, Practical Cryptology and Web Security

In fact, the only place that describes ISAAC as definitely a cipher is crypto.SE and the Wikipedia article and we all know the authority that can be attributed to Wikipedia.

Yuen's book is perhaps the most telling. It clearly categorises ISAAC as a PRNG but then goes onto construct a cipher system using it as a key stream generator.  Yuen goes into great detail how to create a seeding mechanism as there is no official key entry, and codes an XOR mechanism for enciphering.  This approach is repeated in the Rosetta Code entry for ISAAC, as is the description of ISAAC as a PRNG.

It appears to be the case that ISAAC is a PRNG.  As such, and as any PRNG can, that qualifies it to be a building block of a cipher. In that respect, so can the middle square method be used as a construct within a cipher system if you add some XOR code onto the end.   I suggest that is the basis of all of the confusion.  But ISAAC is first and foremost a PRNG, isn't it?

Trying to distinguish a synchronous stream cipher from a CSPRNG seems to me a bit like trying to distinguish ice from frozen water.  Any secure stream cipher is a CSPRNG, and any CSPRNG can be used as a stream cipher.

Insofar as there is any difference, it mostly comes down to intended purpose and API design.  A typical CSPRNG API might take an initial seed value (equivalent to the key of a stream cipher), and allow the user to request small chunks of random output bits, whereas a typical stream cipher API would be initialized with a key and (usually, for modern cipher designs) an IV / nonce, and allow the user to pass in plaintext or ciphertext to be XORed with the output keystream.

Also, speed may not be as important a design criterion for general CSPRNGs as for stream ciphers, since one rarely needs a lot of pseudorandomness quickly unless one is using it as a keystream for encryption.

Now, the ISAAC reference implementation definitely provides a PRNG-style API: you pass in a seed array of 256 32-bit integers, and then request output in 32-bit chunks (either one at a time, or 256 chunks at a time by directly accessing the input/output buffer).  The C API does effectively allow treating the seed / output buffer as an array of 1024 bytes (as shown e.g. in the ISAAC challenge code, which seeds the generator with an ASCII string), but the conversion is implicit and platform-dependent (due to endianness issues).

However, while the ISAAC API is that of a PRNG, the algorithm itself is clearly designed with performance in mind, and intended to be competitive with earlier stream cipher designs such as RC4.  So, yes, ISAAC as presented by Jenkins is primarily a PRNG, but it's meant to be usable as a stream cipher.


Reasons for Chinese SM2 Digital Signature Algorithm In the IETF RFC draft named "SM2 Digital Signature Algorithm" a signature algorithm is specified. The RFC does however not mention why this signature algorithm has been defined. Nor does it specify what the advantages of this scheme are over ECDSA. It seems that SM2 is the preferred EC signature format in China.

So the two related questions are:

Why was SM2 defined?
What are the (operational) differences compared to ECDSA?

Note that there seems to be a set of SM2 Elliptic Curve domain parameters defined as well.

According to [SM2 Algorithms Parameters] linked in the draft (and found on Wayback machine), here are the domain parameters:

y^2 = x^3 + ax + b

p =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
b = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
n = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
Gx = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
Gy = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0

The SM2 digital signature algorithm.  Fix a curve $E/k$ over a field $\mathbb F_p$.  Fix a standard base point $G$ of prime order $n$ on $E/\mathbb F_p$.  Fix a hash function $H\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$.

A public key is the encoding of a point $P \in E/\mathbb F_p$ together with an string $Z$ identifying a principal.
A signature on a message $m$ under the public key $P$ with identifier $Z$ is is a pair of integers $(r, s)$ in $[1, n - 1]$ such that $r + s \ne 0$ and $$r \equiv (H(Z \mathbin\| m) + x([s]G + [r + s]P)) \pmod n.$$
The signer knows the secret scalar $d$, the private key, such that $P = [d]G$.  To make a signature, the signer picks a scalar $k$ uniformly at random, and computes

\begin{align}
    r &\equiv (H(Z \mathbin\| m) + x([k]G)) \pmod n, \\
    s &\equiv (k - r d)/(1 + d) \pmod n,
  \end{align}

rejecting and starting over if $r \equiv 0$, $r + k \equiv 0$, or $s \equiv 0 \pmod n$.

This is a valid signature because

\begin{align}
    [s]G + [r + s]P
    &= [s]G + [(r + s) d]G \\
    &= [s + s d + r d] G \\
    &= [(1 + d) s + r d] G \\
    &= [(1 + d)(k - r d)/(1 + d) + r d]G \\
    &= [k - r d + r d]G \\
    &= [k]G.
  \end{align}

Why?  There has been relatively little analysis of the SM2 signature scheme that I can find in the anglophone cryptography literature beyond some side channel attacks.  The most salient aspect of it to my eyes is that it is just different from various other national pride digital signature schemes.

The SM2 signature scheme has a small advantage over ECDSA (US) and ECGDSA (Germany) for verifiers: the verifier need not compute any inverses modulo $n$.  Otherwise the signer's costs are similar to the others.  Security analysis of ECDSA is extraordinarily complicated and unsatisfying, in contrast to Schnorr; I expect the same is true of the others.

My guess about why SM2 was chosen is precisely to be different from all the others, for the sake of nationalism—they are all worse in performance and confidence than the much simpler inversion-free Schnorr-based EdDSA.


AES-128 with weak key Doing malware research (simple crypto locker) I found out that it uses AES-128 with weak key - every one of the sixteen bytes is represented by (a-z,A-Z,0-9). Thus simple brute-force attack should iterate through $62^{16}$, that is approximately $2^{96}$ keys. I have a file before encryption and after.

Is it feasible in modern world to brute-force it to find a key with a budget of $3-4k?

No, it's not.

Here, Bruce Schneier estimates the cost of finding a SHA-1 collision. He estimates that this would require approximately 274 CPU cycles and cost about \$700 thousand in 2015. Trying 296 AES keys would require approximately 2100 CPU cycles and cost about \$50 trillion.


Digital signing and encrypting e-mail There is a feature in Thunderbird under Account Settings > Security, in it are two options one can use: digital signing and encryption. What's the difference between it and Enigmail? Are they both equally secure or is the other more secure and reliable? As I understand it, one do need to have CA or S/MIME from a third party to use that secure feature from Thunderbird? Is it advisable to use that than Enigmail or can I combine the two?

What's the difference between it and Enigmail?

They're using different signature / encryption standards.
The Thunderbird built-in uses S/MIME which relies on the CA PKI.
Enigmail implements OpenPGP which relies on the web-of-trust and TOFU.

  Are they both equally secure or is the other more secure and reliable?

It depends.
There's a lot of configuration going on under the hood with OpenPGP and S/MIME and depending on the settings both formats can be (in)secure. The rest of security just depends on personal preference and actual usage. The security part relies on whether you can be bothered to actually get your own key signed and sign other people's keys with OpenPGP and whether you trust the CA model with S/MIME. If you don't mind your encrypted message to be put into an attachment then there's no issue with S/MIME and if you do mind, OpenPGP can put it encoded into the message.

  As I understand it, one do need to have CA or S/MIME from a third
  party to use that secure feature from Thunderbird?

Yes and No.
You don't need to get a certificate from a centrally trusted CA to use S/MIME. You may as well roll your own CA and install it to all recipients or just use a self-signed certificate that needs to be explicitely trusted by other parties.
However, if you are not a company targeting internal emails only with S/MIME, you really should get an S/MIME certificate signed by a trusted CA, because otherwise other people have no guarantee that you're actually the one (or the even the address) who you claim to be.

  Is it advisable to use that than Enigmail or can I combine the two?

In theory, yes, in practice though it depends on the user-interface and the implementation to see whether nested encryption is possible. Nested signatures are no problem at all. Using both in the sense of "I write to Phil using Enigmail and to Bob using S/MIME", this is no problem at all.


Relaxing Semi-Honest Security in Multiparty Computation I am currently reading Lindell's tutorial on simulation-based proofs and I am trying to understand the reasoning why the security notions are they way the are.

In simple words, in the case of semi-honest adversaries, we require that there exists one simulator for each party that can simulate the party's view based on its input and output. This simulator should produce a indistinguishable view no matter what the actual inputs (also of the other parties) to the protocol are.
If we have constructed some protocol, we prove its security in the presence of semi-honest adversaries, by following, roughly, two steps.

Define an explicit simulator for each party that outputs, based on the party's input and output, a view that is indistinguishable from a view of that party from a real protocol run.
Assume towards contradiction that the real and simulated views are not indistinguishable and construct an adversary that breaks some underlying building block, e.g. an encryption scheme, commitments, or another protocol.

Hence, as far as I understand, this indistinguishability means that no (non-uniform) distinguisher, even knowing all inputs of all parties, given a real or a simulated view for one party, can tell whether the view was simulated or not.

Assuming my understanding of this is correct, my question is, whether a weaker version of this notion would also make sense, whether it already exists, or whether it would just be equivalent to the existing notion in some way.

Imagine some, very abstract, protocol between $P_1$ and $P_2$, where each of them has its own secret key and they use semi-honest 2PC to compute some shared key based on their own keys.
Assume I have a protocol for this functionality and simulators for both parties that work for all inputs, apart from a negligible fraction of "bad" input keys.
Intuitively, such a protocol should be a secure protocol in the presence of semi-honest adversaries (I think), but according to my understanding of the definition this would actually not be the case, since there does exist a distinguisher for some negligible fraction of inputs.
Here, it seems that requirement for not having a distinguisher for all inputs is too strong.

Does my intuition make sense or is it flawed?
Is there such a relaxed notion?

I'm not sure that the issue here is uniform versus non-uniform, but I'll address this first. It is possible to provide a uniform definition. In order to see what it would look like, I recommend reading Oded Goldreich's uniform treatment of zero knowledge http://www.wisdom.weizmann.ac.il/~oded/PS/uniform.ps.

In any case, your question is more about quantifying over all possible inputs, versus over a specific distribution. (Note that in Oded's uniform treatment, the quantification is over all poly-time samplable distributions. Here, you wish to guarantee security for a specific distribution only.) It is possible to define such a notion and it does make sense. The only question is if it buys you something. I have used such a notion once, in order to construct a secure password authentication protocol; see the definition in http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps (Section 2.3.2). In this definition, the password is chosen randomly from a dictionary as part of the ideal and real models. You could do the same thing and choose a random key.


How can an all-zero encryption key result in plaintext ? In the Krack-attack paper, the section 6.3 says that a vulnerability on Android devices involves installing an all-zero encryption key when the message 3 is re-sent.

In his demonstration, he shows via Wireshark that the credentials of the user were sent in plaintext.

How can any algorithm result in a cipher equal to the plaintext if it's key is all-zero ? Am I missing something ?

If the key and nonce are identical then it is possible to recreate the counter mode key stream. WPA2 is using CCM, which uses counter (CTR) mode underneath. This basically generates a key stream which is XOR'ed with the plaintext message. If you have more messages then it becomes easy to retrieve messages by XOR'ing multiple streams together.

If the key is an all zero key then all the adversary has to do is to decrypt the ciphertext of course. Once you have the key then all the security is lost. However, the ciphertext will still not be the same as the plaintext, so what Wireshark is showing in the video must be the decrypted ciphertext.

In other words, the explanation is slightly over-simplified in my opinion.


Simple explanation of weak one way function I find difficult to understand what a weak one way function is. From textbooks:

$\exists$ poly $Q$, $\forall$ PPT  $\mathcal{A}$ such that: $$\Pr[x\leftarrow\{0,1\}^n; y=f(x); \mathcal{A}(1^n, f(x))=x' : f(x')=y] \leq 1 - 1/Q(n)$$

What does this mean in practice?
The part that I find confusing is: $1-1/Q(n)$, does this mean that we can invert all except a polynomial part which we cannot invert?

The part that I find confusing is: $1-1/Q(n)$, does this mean that we can invert all except a polynomial part which we cannot invert?

This is relaxation from Strong OWF, in which, any polynomial time algorithm will succeed in inverting $f$ on random input with negligible probability.

In weak OWF,  any polynomial time algorithm will fail to invert $f$ on random input with non-negligible probability.

  What does this mean in practice?

There is a theorem state as;

Theorem: If there is a weak OWF, then there is a strong OWF. In particular, given a weak OWF $f:\{0,1\}^* \to \{0,1\}^*$, a there is a fixed  $m\in \mathbb{N}$  polynomial time input length $n \in \mathbb{N}$ such that $f'$

$$f'(x_1,\ldots,x_m) = (f(x_1),\cdots ,f(x_m))$$

is a strong OWF. In particular this holds for  $m=2\,n\,q(n)$.

For a proof see

Therefore, in practice, we know at least one way to construct a strong OWF from weak OWFs.


Trying to implement the algorithm in Wikipedia regarding key exchange I am trying to understand the reconciliation technique mentioned in Wikipedia page for Ring-LWE key exchange.
Basically, if we intentionally choose x, y (or the coefficients of calculated shared key of Alice and Bob)
to be different in terms of range or one in range (-floor(q/4), round(q/4)) and another not in that range, then w should be 1 for at least one of them.
Then that party sends w which would be 1 to the other part and then we do the reconciliation technique of $Mod_2$:

$Mod_{2}(v,w)={(}v+w.{\frac {q-1}{2}}{ )}{\text{ mod }}q{\text{ mod 2}}$

Which essentially would do the following (and the bits are supposed to match):

k1 = ((x + (q-1) / 2) % q) % 2
k2 = ((y + (q-1) / 2) % q) % 2

So what I have done (in SageMath) is that I randomly choose 2 values one in the range and one not in that range and then followed the reconciliation
and it does not workout, half of the time bits don't match. Obviously, I am not understanding something here. Any help would be appreciated.

What I assume is that the difference between x and y in a real world implementation should be small (errors are supposed to be small) and that is why reconciliation does not work

arr = {
        "correct" : 0,
        "incorrect" : 0
        }

q = 40961

for i in range(0, 10000):
    x = ZZ.random_element(-floor(q/4), round(q/4))
    y = ZZ.random_element(round(q/4) + 1, q)

    if x not in range(-floor(q/4), round(q/4)) or y in range(-floor(q/4), round(q/4)):
        print "critical error! (range does not match)"

    k1 = ((x + (q-1) / 2) % q) % 2
    k2 = ((y + (q-1) / 2) % q) % 2

    if k1 != k2:
        # print "error!"
        # print k1
        # print k2

        arr["correct"] = arr["correct"] + 1
    else:
        arr["incorrect"] = arr["incorrect"] + 1

print arr

output >> {'incorrect': 4980, 'correct': 5020}

There have been several rLWE key exchange protocols proposed; what you're looking at is the protocol proposed by Professor Ding here.

In this protocol, the errors are assumed to be small even values; on the Wikipedia page, you can see that they always add the error vector in the form of $2e_i$.  Your test fixture is generating relatively large errors without any regard to whether they're even or odd.  Unless you fix that up, yes, the reconcilliation process will generate random values.  It still won't work great unless you make sure that the errors are actually small (you appear to be trying it with large errors); but you appear to be testing that deliberately.


What are the issues of look-up table based implementations? Cryptographic libraries mostly use pre-computed lookup tables to implement block ciphers. These lookup tables require large amout of memory and a series of cache miss/hit makes them vulnerable to cache timing attacks.
Are there any other disadvantages of lookup table based implementations?

The disadvantages are simply the side-channel attacks that you mention.  I can think of no other disadvantages from either a cryptographic or hardware angle.    I have a description of cache and attacks from a hardware perspective.

The advantages are pretty clear:

simplicity in implementation so that the mathematics is correct;
it's faster than a bit-slice implementation, and
it's smaller than doing the inverse mathematics for the irreducible polynomial.

Also, in non-x86 environments, these attacks are be mitigated through a cache lock where you do not flush the cache so you cannot miss.


What affect does the permutation layer have on the avalanche effect? If the permutation is not well thought out, how will this effect the cipher's avalanche effect. For example, if the permutation in PRESENT was in some way different (just made up without any thought) would this adversely affect the avalanche effect? How else might a poorly designed permutation adversely affect PRESENT or other block ciphers?

Permutation layer diffuses the small changes globally(tries to spread over the complete block).

If permutation is not well thought out, then diffusion may be weak and changes may not spread throughout the complete block. The cipher output may be treated as concatenation of output from multiple identical ciphers with smaller block length. For Example

Consider there is no Shift-Rows operation in AES, then Change in a state will stay in a Column and will not diffuse to other columns. Thus Ciphertext can be treated as output of 4 independent 32 bit block ciphers.

In Case of PRESENT, if the permutation P was not spread over the complete block(64 bits, keeping the change within small set of bits), or there was a chunk of bits which does not get effected by change in other bits over multiple rounds, the cipher will have a major weakness.


Speed of the General number field sieve So according to the wikipedia page https://en.wikipedia.org/wiki/General_number_field_sieve the algorithm has complexity $$\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)$$ but I am not too familiar with this notation.

I understand the big-O notation for complexity if somebody could explain how this is similar and what it means for the running time it would be appreciated!!

Also I know that this is subexponential in the size of $n$ running time, but I am unsure how to show this just from this complexity.

Since the numeric constant in the exponent is approximately $1.923 $ the expression for the average number of iterations, say time complexity $T$  given by
$$T=\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)$$
is proportional to (for $n$ large enough so that $o(1)$ term is negligible)
$$T\propto \exp \left(1.923 \times  (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}
\right)$$
which is upper bounded as (ignoring a multiplicative constant in front)
$$T\leq \exp \left(2   (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}  \right)=T_0^2.$$

Clearly $T$ is polynomial/exponential if and only if $T_0$ is.

Now consider the more general expression
$$f(\alpha,n)=\exp \left(  (\ln n)^{\alpha}(\ln \ln n)^{1-\alpha}
 \right),\quad \alpha \in [0,1],$$
and note that when $\alpha=1,$ $f(1,n)=\exp(\ln n)=n,$ hence it is exponential in the bitsize $\log_2 n$ of the input $n.$

Also note that when $\alpha=0,$ $f(0,n)=\exp(\ln\ln n)=\ln n,$ hence it is polynomial in the bitsize $\log_2 n$ of the input $n.$

However we have $T_0=f(1/3,n)$ with $\alpha=1/3$ above so the complexity we have is a linear combination in the exponent of polynomial and exponential complexities. This is referred to as subexponential but superpolynomial complexity.


AES reverse Rijndael key schedule with decryption round keys I want to get the original encryption key (32 byte) of AES 256 (CBC) implementation.
The implementation has the values of the inversed round keys values hard coded into the decryption function.
I have the 15 rounds*32 byte decryption keys
Is there an algorithm that I can use to get the original generating key?
I know that I can reverse the expansion of the encryption key, but the round keys for decryption has the addition "inversion" generated by this:

// inverse-cipher-ify the decryption round key (fips-197 section 5.3)
    for (var r = 1; r < rounds; r++) {
        for (var c = 0; c < 4; c++) {
            tt = this._Kd[r][c];
            this._Kd[r][c] = (U1[(tt >> 24) & 0xFF] ^
                              U2[(tt >> 16) & 0xFF] ^
                              U3[(tt >>  8) & 0xFF] ^
                              U4[ tt        & 0xFF]);
        }
    }

Can this be reverted too?
Thank you

Yes, in fact it is quite simple. You are looking at the round subkeys for what is called the equivalent inverse cipher. The decryption round subkeys are generated by performing the InverseMixColumns operation on the encryption round key, the exact same operation used by the decryption function. The code you posted uses a series of byte table lookups (U1 to U4) and XORs to perform the InverseMixColumns operation. Note that the round subkeys are 128-bits or 16 bytes, as that is the size of the block.

In order to convert the decryption round subkey into the encryption one, all you need to do is perform the forward MixColumns operation on the subkeys, except for the first and last round keys, as these are whitening subkeys and are not changed. And of course you need to use them all in reverse order.


is H1 (H2(x)) hash function collision-resistant If H1 is collision-resistant then is H1 (H2(x)) collision-resistant?
I think yes but I don't know how to prove it

Hint: what do you know about H2? What happens if H2 is not collision-resistant, i.e. you know two different messages that result in the same hash with H2?


Streaming API to authenticated encryption In regards to NaCl, I asked DJB he had any intent to add a streaming API to an authenticated cipher. His response was obvious in retrospect, that one should never release a decrypted plaintext before verifying the authenticator.

However, this got me to thinking. Streaming is important — for instance, when working with extremely large datasets. Is it possible, or even advisable, to mimic a streaming interface?

One simple approach would be to chunk the data every certain number of blocks. Once you've received enough blocks, output the IV and a complete ciphertext into the cryptostream. When you've received the next set of blocks to complete a chunk, generate a new IV and repeat. To decrypt, take the first block of the cryptostream and consider this to be the first IV. Read a full chunk, and decrypt. Output the result as the first chunk of plaintext. Repeat.

This runs all the data through an authenticated cipher and verifies the authenticator before releasing the plaintext, but it does not verify the whole ciphertext before releasing some plaintext. Is this problematic, or is it generally considered safe? Is it safe in some circumstances, depending on your particular problem? Or does it invariably introduce serious flaws?

I realize that this is well into rolling-your-own-crypto territory, and do not plan to implement this myself. That said, what's the verdict on the approach? Are there alternative solutions to the problem? Is there a general approach that one can use to safely encrypt extremely large datasets with authenticated modes, or are any solutions still highly dependent on the exact problem being solved?

Update: Hoang, Reyhanitabar, Rogaway, and Vizár published a paper which defines the "STREAM" protocol that addresses this problem.

As pointed in the question, a conservative API to authenticated encryption should only ever release authenticated plaintext on the deciphering side. Anything else is too open to attacks (padding, timing, denial of service, unamit).

In a streaming API, this forces aggregation of data into blocks, each authenticated. The simplest method is fixed size ciphertext blocks (blocking related to characteristics of plaintext, e.g. at end-of-line for text, is too susceptible to information leak; on-demand blocking by the receiver requires feedback on the communication link, that could leak information, and is overly complex).

One obvious drawback of blocking is that it increases the overhead; however, even with 128-bit overhead per block (which is enough for an IV and authenticator), 8kiB blocking leads to less than 0.1% overhead, and this is acceptable in many use cases. That's basically what the OP is proposing.

One other very real problem with this blocking strategy is that we must resist suppression, duplication, and reordering of authenticated blocks by an adversary, with the intend of altering the plaintext correspondingly. The scheme proposed in the question does not, and is vulnerable to these attacks.

To correct that, one method is to include a block sequence number in the authenticated data, starting at 0 at start of data, and incremented by one at each block. That does not even necessarily increase the size overhead, as this block number needs neither to be encrypted, nor explicitly transmitted. Using GCM, we can have this block number implicitly included in the authenticated data, but not transmitted. With an Encrypt-then-MAC authenticated encryption, we can insert the block number after encryption and before MAC-ing. With a MAC-then-encrypt authenticated encryption, we can enter this block number in the MAC-ed data, and remove it before encryption.

Another method to correct that is to use a different key for each block, generating them with a fast KDF.

With such tweak, I do not see any systematic flaw in the use of authenticated encryption with blocking, packaged in a streaming API to authenticated encryption, beyond the obvious inherent (but practically acceptable) dangers, in particular

the adversary can interrupt the flow of authenticated data and deduce something from how the receiver reacts to that, especially if there is a retry mechanism other than "redo from start".
the receiver is likely to perform actions detectable by the adversary on the basis of what is in a block; that's enough to leak information that would not leak in non-blocked authenticated encryption (for example, assume the plaintext is known to contain either 98 or 99 ! characters, with spacing much higher than the block size, each ! causing a power consumption burst on the receiver side, and the adversary gets a power meter reading every second allowing to reliably discern if that burst occurred or not. Then when blocking is used, she can use that to determine whether there are 98 or 99 ! characters, by restricting the flow of information to one block between two meter readings; something that likely would not be possible without blocking assuming there is 5% uncertainty in the difference between two consecutive power readings).


Using a PRP $\pi: \{0,1\}^{16} \to \{0,1\}^{16}$ to construct an ideal cipher Say we have an ideal 16-bit PRP. Since it appears that a permutation with a small domain can be used to turn it into a PRF, which can then be used in a Feistel network. On the surface, it makes it look like this means a trivial random permutation implemented using nothing more than a lookup table could then be used to create an ideal cipher with an arbitrary block and key size, which is obviously not the case. There must be something I am missing.

The way I see it:

A small, random permutation can be implemented in practice using a lookup table.
A random permutation can be used to implement a keyed PRP, e.g. $C = \pi(P \oplus K) \oplus K$.
A PRP with a small domain can be used to construct a secure PRF.
A secure PRF in a Feistel network can be used to create a secure block cipher.

A random permutation with a small domain can be implemented easily using a lookup table. Were I any more naïve, I would have proclaimed that I had just discovered an information theoretic secure cipher that fits the ideal cipher model, but obviously that is not the case. Why is this?

This is not a cryptosystem review question in disguise. I am simply curious to know the reason why an ideal but small PRP cannot be used to construct a cipher that fits the ideal cipher model.

There are $2^{16}!$ distinct permutations of the 16-bit strings $\{0,1\}^{16}$.  For any fixed Feistel structure built out of one of these as you suggest, there are still only $2^{16}!$ possible outcomes.

There are $2^{128}!$ distinct permutations of the 128-bit strings $\{0,1\}^{128}$.  In an ideal cipher, for any fixed key $k$, $E_k$ is an independent uniform random permutation: each possible permutation has probability $1/2^{128}!$ of being $E_k$.

But in your construction, there are at least $2^{128}! - 2^{16}!$ permutations that $E_k$ cannot be.  (There may be more because conceivably some pairs of permutations may collide under the Feistel structure, pending further analysis to rule that out.)  So no matter what Feistel structure you choose, or non-Feistel composition of the permutation, you cannot get an ideal 128-bit block cipher out of a random 16-bit permutation.

What about a pseudorandom permutation family?  Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter.

Table lookups are, indeed, a common design element in cryptographic primitives, including the venerable DES.  You can view AES as a composition of table lookups and xor, but as the rest of the paper demonstrates this implementation strategy will lead you into trouble, which is why alternative designs like Serpent and newer designs like Salsa20 don't even tempt implementors into using secret-dependent table lookups.

Further, to make a thing that can be computed with, rather than a probability distribution that can be studied, you need to choose particular tables—and as Don Coppersmith and his team at IBM learned in 1974, the choice of tables can be tricky.


How do different block sizes affect the throughput of GPU implementations of AES? I am confused about the effect of different block sizes on AES performance. As you can see here, there is a huge gap between the throughput of different block sizes. As far as I know, every 16 bytes must be encrypted separately, but I don't know what would happen if the block sizes would be increased.

How would 16 bytes of a 1024 byte block be encrypted? Indeed, I can't understand the effect of block size to throughput!

Remember, a GPU consists of a large number of computational engines, all controlled by the same instruction stream.  That is, there might be 64k processors, and all those processors can work on different pieces of data, but they must all do the same thing to all of them.  We refer to this as SIMD parallelism.

With that in mind, how can they encrypt and decrypt a large amount of data quickly?  That depends on the mode they use.

If they use ECB mode, well, ECB mode applies the AES transformation to each 16 byte section independently.  So, given a 1 Megabyte plaintext, then hand off each 16 byte section to a separate computational engine, and then have all the engines perform the AES encrypt operation on the 16 bytes they were given.

A similar trick works for CBC mode decryption.  In that case, the transform is doing an AES decryption on each 16 byte block, and then exclusive-or'ing the result with the previous ciphertext block.  Similar to the ECB mode case, all that can be done in parallel by the GPU computational engines.

However, if you're asking about CBC mode encryption, well, that can't be parallelized.  There, to encrypt block N, you first exclusive-or in the ciphertext of block N-1, and (unlike the decryption case) you don't have that until the computation of block N-1 is completed.  Hence (as mentioned on the web page), you can't parallelize it, and the web page doesn't give any results there (because the GPU is actually slower than just having the main CPU do the computation).


Block size vs key size confusion I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k>n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k-n}$ possible keys, right? But doesn't DES/AES have a similar system as a block cipher with keys bigger than the blocks. So surely finding one message-ciphertext pair doesn't narrow down the key search so much!?

As you can see, I'm quite confused and so any help would be appreciated!

I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k>n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k−n}$ possible keys, right?

That is approximately correct (if the block cipher with the wrong key acts like a random permutation; this is generally a safe assumption); if block "one message-ciphertext pair", you mean "a single $n$-bit plaintext/ciphertext block.

However, that's not necessarily what we mean by a "message-ciphertext pair".  We often want to encrypt messages that are larger than $n$ bits; to do this, we use a mode of operation (which uses the block cipher to encrypt larger messages); if we have a larger message (and we know the plaintext and the ciphertext of this larger message), then we usually (depending on the exact mode used) have a number of $n$-bit plaintext/ciphertext blocks.

The upshot of this is that if we have a $k$-bit message (and corresponding ciphertext), this is usually sufficient to allow us to recognize the key (with a possible 1 or 2 false hits; those can be eliminated if we take a message slightly larger than $k$ bits); if $k>n$, then we would get several plaintext/ciphertext pairs against the underlying block cipher


"Weaknesses" in SHA-256d? According to this answer, "SHA-256d" was proposed in one of the Ferguson/Schneier books like so:

SHA-256d(x) = SHA-256(SHA-256(x))

Apparently, the motivation for this construction is to avoid length extension attacks.

Incidentally, SHA-256d is the hash function forming the core of Bitcoin.

According to the comment on the answer linked above, "some minor weaknesses" are known in SHA-256d. What are they?

This started as a comment to CodeinChaos's answer, but did not fit. I'm trying to regurgitate, in layman's terms, my understanding of the consequences on $\operatorname{SHA-256d}$ of the paper he quotes: Yevgeniy Dodis, Thomas Ristenpart, John Steinberger, Stefano Tessaro: To Hash or Not to Hash Again? (In) differentiability Results for H2 and HMAC, in proceedings of Crypto 2012.

This paper does NOT imply that we could determine with sizable advantage over a random choice whether a black box with $256$-bit input and output is a Random Oracle, or implements $\operatorname{SHA-256d}$, using $2^{64}$ queries to that black box, without knowing the initialization value used by $\operatorname{SHA-256}$ (we assume it is replaced by a random $256$-bit value), and using much less computational work than necessary to break $\operatorname{SHA-256}$ with sizable probability. In other words, $\operatorname{SHA-256d}$ remains a secure Pseudo Random Function in that standard definition of the term. That's proven by the standard argument: a distinguisher (in that definition) able to break $\operatorname{SHA-256d}$ can be turned into one able to break $\operatorname{SHA-256}$ with only twice as much queries.

Nevertheless, the paper shows that we can devise protocols involving a hash where using $\operatorname{SHA-256}$ is safe; but using $\operatorname{SHA-256d}$ is entirely unsafe (with negligible effort, not $2^{64}$). An example is this protocol designed to provide mutual proof that each party has made some minimum number of evaluations of some $256$-bit hash function $H$ (note: Alice performs the odd steps, and the next even step is performed by Bob with roles reversed):

Alice draws a random $256$-bit $A_0$ and sends it to Bob, together with the minimum number $k_A\in[2^8..2^{18}]$ of evaluations of $H$ that she wants Bob to perform;
Bob draws a random $256$-bit $B_0$ and sends it to Alice, together with the minimum number $k_B\in[2^8..2^{18}]$ of evaluations of $H$ that he wants Alice to perform;
Alice sets $\hat B_0$ and $\hat k_B$ to what she got at step 2., and terminates the protocol with failure if $\hat k_B>2^{18}$;
Bob sets $\hat A_0$ and $\hat k_A$ to what he got at step 1., and terminates the protocol with failure if $\hat k_A>2^{18}$;
Alice repeats for $j=1\dots\max(k_A,\hat k_B)$:

If $A_{j-1}=B_0$, terminate the protocol with failure;
compute $A_j=H(A_{j-1})$;
compute $\hat B_j=H(\hat B_{j-1})$;

Bob repeats for $j=1\dots\max(k_B,\hat k_A)$:

If $B_{j-1}=A_0$, terminate the protocol with failure;
compute $B_j=H(B_{j-1})$;
compute $\hat A_j=H(\hat A_{j-1})$;

Alice sends $\hat B_{\hat k_B}$ to Bob;
Bob sends $\hat A_{\hat k_A}$ to Alice;
If what Alice got at step 8. is different from $A_{k_A}$, she terminates the protocol with failure; else she declares success;
If what Bob got at step 7. is different from $B_{k_B}$, he terminates the protocol with failure; else he declares success.

When $H$ is $\operatorname{SHA-256}$, this protocol is safe for both Alice and Bob. However if $H$ is $\operatorname{SHA-256d}$, defined as $x\mapsto \operatorname{SHA-256}(\operatorname{SHA-256}(x))$, there is a simple "mirror" attack for Bob:

at step 2., Bob computes and sends $B_0=\operatorname{SHA-256}(A_0)$ and $k_B=k_A-1$ where $A_0$ and $k_A$ is what he got at step 1.; this will pass the test performed by Alice at step 3.; and pass the tests she performs at step 5., with about the same negligible odds of failure as if Bob had chosen $B_0$ at random;
at step 8., Bob computes and sends $\operatorname{SHA-256}(\hat B_{\hat k_B})$ where $\hat B_{\hat k_B}$ is what he got at step 7.; this will always pass the test Alice performs at step 9.!!

This strategy allows Bob to apparently perform his duties with computational effort about a single evaluation of $\operatorname{SHA-256d}$, by circumventing the tests performed by Alice at step 5., which intend was to prevent Bob from choosing $B_0$ as one of the $A_j$ so that most of his work could in fact be done by Alice.

The paper (and the above example, which is inspired from the paper) implies that with a definition of indifferentiability from a Random Oracle sufficiently strong to support a security proof of certain protocols (in particular: mutual proof-of-work protocols) under the assumption that a hash used by this protocol is secure, indifferentiability of $H^2:x\mapsto H^2(x)=H(H(x))$ does not follow from indifferentiability of $H$.

That shows in particular that the definition of a practically secure hash as a random public member of a Pseudo-Random Function Familly characterized by: "even a computationally unbounded adversary can not distinguish, with constant positive advantage over a random choice, if a black box with $n$-bit output implements a random member of the family, or a RO, with a number of queries to the black box polynomial in $n$" (or: "asymptotically less than the birthday bound $O(n^{1/2})$" ) is NOT a measure of security suitable for proving practical security of such protocols.

The paper proceeds to show that $\bar H(x)=H(H'(x))$ where $H'$ is a variant of $H$, is indifferentiable from RO, assuming $H$ and $H'$ are, under a definition of indifferentiability suitable for that goal.

One way of seeing this is that the composition of two random members of a PRFF is secure, but the composition of twice the same random member is not secure w.r.t. an adversary with access to an oracle implementing that random member, which is unavoidable in practice.

Update: although BitCoin involves proof-of-work using a hash, and $\operatorname{SHA-256d}$, I would be extremely surprised if there was some devastating attack due to the use of that hash.


Why CA does not have to be online? I'm learning publick key infrastructure and certificate authority.

But I cannot understand below conecepts.

  Unlike KDC or public key authority, CA does not have to be online to
  provide keys to users

Why? I think KDC and public key authority are same as CA.

Unlike KDC or public key authority, CA does not have to be online to provide keys to users

What they mean by that is that the CA doesn't have to be on-line at the time of negotiation.  That is, when you use TLS to take to Amazon, the CA doesn't have to be a part of the negotiation.  Instead, Amazon can send its certificate and you can verify it (and then use the embedded public key) without the CA being involved direction.  The CA can be (and generally is) shut off from the network during that time.

This contrasts with (say) a Key Distribution Center; when Alice and Bob need to negotiate a shared secret, the KDC is a necessary party within that negotiation.

This implies two things:

Because the KDC must be on-line, that means that it must present an interface to the users; such an interface is a potential attack surface.  As the CA is usually off-line, it is rather more difficult to attack.
Scalability; because the KDC participates in every negotiation, that means that it gets a lot of traffic.  Of course, there are ways to address this, such as redundant KDC servers; however that just increases the attack surface.

Of course, the CA does have to be available at the time of enrollment.  What Amazon gets its certificate, the CA has to generate it and send it to Amazon.  However, this is a comparatively rare event (compared to how often negotiation happens), and so less of an issue.

  I think KDC and public key authority are same as CA.

No, they are not.  A KDC is a central authority that distributes keys.  How it generally works is that the KDC would share a symmetric key with each of its uses; when Alice wants to talk to Bob, it would send a request (using Alice's symmetric key) to the KDC; the KDC would generate a key, and send it to Alice (using Alice's symmetric key) and to Bob (often via Alice) using Bob's symmetric key.


Secure and efficient encryption of a continuous data stream on behalf of a third party using asymmetric cryptography I want to design an API-based system that is able to securely encrypt a stream of data received on behalf of an external user in such a way that the data can only be decrypted using a secret that only the user knows (i.e. after encrypting the data, the server itself would not be able to decrypt it again). Naturally, my first thought was to use asymmetric cryptography for this:

The server would generate a private/public key pair (e.g. using RSA)
The private key would be securely handed to the user and erased from the server, the public key would be stored on the server.
When new data arrives for the user, the server would generate a random key for a symmetric encryption scheme (e.g. AES) and use this key to encrypt the data. It would then use the users public key to encrypt the symmetric key and store it together with the data on the server.
The user could then decrypt the data by downloading the encrypted data with the corresponding encrypted symmetric keys, decrypting the symmetric keys using his/her private key and finally decrypting the data using the decrypted symmetric keys.

The main challenge is that the data which is received on behalf of the user consists of many small packages that arrive continuously over time. In order to encrypt them following this scheme it would thus be necessary to generate and encrypt a new symmetric key each time a new data package arrives, which is doable. However, the decryption of the data could become very inefficient, as the decryption of an RSA-2048 encrypted message can take several milliseconds on modern hardware, so if there are many thousands or even millions of messages for a single user, their decryption could take hours.

I therefore have two questions:

Is this a reasonable scheme? If now, which elements are missing or would be advisable to implement in addition (HMAC, signing, ...)?
Is there any way to increase the efficiency of the decryption process, preferably one that does not involve storing the symmetric key on the server over an extended period (which would be a security risk)?

Edit

The user does not upload the data, it is generated by a third-party on behalf of the user. The motivation behind the scheme is to provide the third party with a secure, asynchronous channel to store data that a user could securely pick up at a later point in time. The assumption is that the third party is not able or willing to provide the infrastructure for this by themselves and instead want to use an external service.

$\DeclareMathOperator{\X}{X25519}\DeclareMathOperator{\H}{HSalsa20}$Here is a candidate protocol.

I have amended the obviously insensible criterion of having the server hand the user a secret key.  Since you haven't identified your specific performance constraints—how many CPU cycles, nanoseconds, or joules are available in your budget for cryptography per data record, on average and/or in the worst case, for the user and the server?—I picked a widely available, widely accepted composition of specific cryptographic primitives: NaCl crypto_box_curve25519xsalsa20poly1305.

Setup.
The user generates an X25519 secret $u$ and public key $U = \X(u, \underline{9})$, using NaCl crypto_box_keypair, and configures server with $U$.

Data arrival.
On receipt of a set $\{d_0, d_1, \dots, d_{n-1}\}$ of $n$ data records of bounded length at time $t$, the server

generates an X25519 secret $s_t$ and a public key $S_t = \X(s_t, \underline{9})$ using NaCl crypto_box_keypair;
computes the shared secret $k_t = \H(\X(s_t, U))$ using NaCl crypto_box_beforenm;
authenticates and encrypts each record $d_i$ with XSalsa20-Poly1305 under key $k_t$ and nonce $i$ giving authenticated ciphertext $c_i$ using NaCl crypto_box_afternm;
transmits $(S_t, i, c_i)$ to the user for each $i$, which adds 32 + 8 + 16 = 56 bytes of overhead per message; and
erases $k_t$, $s_t$, and each $d_i$.

Data usage.
On receipt of a tuple $(S_t', i', c_i')$, the user

retrieves a cached shared secret $k_t'$ for public key $S_t'$, or computes the shared secret $k_t' = \H(\X(u, S_t'))$ using NaCl crypto_box_beforenm and caches it for subsequent records with $S_t'$;
verifies and decrypts the ciphertext $c_i'$ with XSalsa20-Poly1305 under key $k_t'$ and nonce $i'$—or rejects it if a forgery—giving record $d_i'$ if not forged, using crypto_box_open_afternm; and
processes the record $d_i'$.

(The prime marks are a reminder that what the user receives may be a forgery, not what the server transmitted.  The standard adversary can of course generate their own public key altogether and forge messages using that with wild abandon, but can't selectively modify messages transmitted by the server.  See the caveats below.)

Cost.
The main cost is the $\X(a, B)$ calculation, which is very roughly about half a million CPU cycles on typical widely available hardware, or half a millisecond at 1 GHz.  See https://bench.cr.yp.to/impl-dh/curve25519.html for more detailed measurements on specific hardware, and https://bench.cr.yp.to/results-dh.html for comparison of different DH functions (warning: not all DH functions listed there have the same security level or defense against side channel attacks).

Sharing the key between multiple data records, and caching it when processing nearby data records, may significantly reduce the time and/or energy cost—under certain usage patterns.

Can the server work on records in batches, or must it lose its ability to decrypt each individual record the moment it transmits that record to the user?  If the largest batch of records the server can sensibly ingest is $n = 1$, then you can simplify the protocol but there's no faster option short of picking a different DH function or KEM, which will invariably be less widely adopted, such as FourQ.  But if the server can work on larger batches, then it can save time and/or energy by reusing each shared secret for multiple records.

If the server can work in batches, does the user process nearby records together, or are the access patterns uniformly distributed?  If the user processes nearby records, then the user can save time and/or energy by caching the shared secrets in a memo table and skipping X25519 computations.

Note that if the user processes records strictly sequentially, then you can save much more time and energy by eliding the public-key business altogether with a method left as an exercise for the reader.

Caveats.

Don't use the same key material for anything else.  If you are tempted to do so, study domain separation.
The standard adversary—who can adaptively control the data and control the channel from server to user—can't decrypt records or partially modify records, but can forge completely new records, and can block records of their choice, and can waste the user's memory up to the longest data record size by transmitting an attempted forgery of that size.  It is left as an exercise for the reader to identify exactly what potentially relevant security properties this protocol does and doesn't provide.

Payment.
Please send payment for this cryptography engineering consulting work to

  Mx. Squeamish Ossifrage
  Room 641A
  521 Mersenne Curve
  Anytown, ST 25519
  Untied Steaks of Armorica


Shamir Secret Sharing - Threshold decryption implementation I'm implementing Shamir secret sharing in C using OpenSSL.
I've split up the private key and I'm ready to start decrypting the original message using some of the shares.  I set $n = 5$ (5 shares total) and $t = 3$ (3 shares required to decrypt).
The way my encrypted message is stored is in a ${\rm msg} = (c_1, c_2)$ format, so I don't think I can just follow the example on Wikipedia, though I may be mistaken.  Here is how my book tells me to do it (image).  I've highlighted the particular part I'm stuck on:

"The dealer then sends $\langle i, s_i \rangle$ to authority $i$ in a secure manner.
To collectively decrypt an encrypted ballot $c$, where $c = (c_1=g \bmod p, c_2 = Y^r \times m \bmod p)$, $t$ such election authorities $\{i_1, i_2, \dotsc, i_t\}$, where $1 \le i_j \le n$, for $1 \le j \le t$, perform the following calculations (Desmedt & Frankel, 1990):

Each entity uses its share $s_{i_j}$ to calculate $\alpha_{i_j} = c_1^{i_j} \bmod p$ and broadcasts it.
Each entity calculates $c_{i_j} = \displaystyle \prod_{1 \le k \le t, k \ne j} \frac{i_k}{i_k - i_j} \bmod q$ $\color{red}{(\Leftarrow \text{HERE})}$ and $\mu_1 = \displaystyle \prod_{j=1}^t \alpha_{i_j}^{c_{i_j}} \bmod p$. Note that $\mu_1 = c_1^s \bmod p$.
Each entity calculates $\mu2 = \mu1-1 \bmod p$ and $m' = \mu2 \times c2 \bmod p$, where $m'$ is the recovered ballot."

In this portion, I'm confused by the values $i_k$ and $i_j$.  It seems to indicate that $1 \le i_j\leq n$ (values 1–5).  Then it says $1 \le j \le t$ (values 1–3).  Can someone straighten me out?
Let's say I'm using the following keys, just for reference:

Key #2 | 1234
Key #4 | 4567
Key #5 | 5678

Final question: do I need to $\bmod$ each result, or just the final sum?

The index $i$ is running through the $n$ possible participants (1=Alice, 2=Bob, 3=Charlie, 4=Dave, and 5=Eve). Now to be able to easily refer to the $t$ out of $n$ persons — required by the threshold scheme — the index $i_j$ is used: $i_1$ is the first of the $t$ people taking part to the decryption, $i_2$ is the second, ..., $i_t$ is the $t$-th. (If Alice, Bob, and Charlie decrypt, this will be $i_1=1$, $i_2=2$, and $i_3=3$; if Alice, Dave, and Eve decrypt one will have $i_1=1$, $i_2=4$, and $i_3=5$.)

Now there is obviously a typo in you book as $\mu_2=\mu_1^{-1}\pmod p$ and not $\mu_1{-1}\pmod p$.

Additionally, I believe the computation of $c_{i_j}$ given in your book is incorrect: instead $\displaystyle\prod {i_k\over i_k -i_j}$ you should read the public values $\displaystyle\prod {x_{i_k}\over x_{i_k} -x_{i_j}}$ where the values $x_l$ are the public elements defining the polynomial $f$ of the secret sharing scheme.

Hence, read the source instead. The implementation given in the paper is also more efficient as it does not require any inversion mod $p$.

(For the last bit of your question, I assume you were referring to a product not a sum. And yes, you can mod $q$ whenever you want, but it's probably more efficient to keep things as small as possible.)


Help understanding basic Franklin-Reiter related message attack I am trying to understand this attack at the most basic level. I set up the following basic scenario:
Let the public encryption exponent, e = 3.
Let p, be some arbitrary but known (to the eavesdropper) padding of a couple characters.
Suppose an eavesdropper has intercepted two encrypted messages $C_1$ and $C_2$ from Bob to Alice, where,

$C_1 \equiv M_1^3$ (mod n); and,
$C_2 \equiv (M_1 + p)^3$ (mod n)

In the answer to this question, if I am understanding it correctly, that to find M, we must determine $gcd(M_1^3 - C_1, (M_1 + p)^3-C_2)$.
Do I have this right? If so how would I go about using the Euclidean Algorithm to do this? These look like polynomials to me and I am somewhat familiar with finding the gcd of two polynomials using the EA, but I just can't seem to figure out how to apply that here.

It seems you are well on your way to understanding the attack. After you compute the GCD of these two polynomials you are left with a polynomial of the form $X - m$. It is clear why—if $f_1(X) = X^3 - C_1$ and $f_2(X) = (X + p)^3 - C_2$ have a common root $m$, then they are of the form $(X - m)g_1$ and $(X - m)g_2$, for some arbitrary $g_1$ and $g_2$.

So,
$-m$ is the coefficient of degree $0$ of this common polynomial, and all that is left to do is to extract it. Here's a worked out example in Sage:

p = random_prime(2^512)
q = random_prime(2^512)
n = p * q # 1024-bit modulus

m = randint(0, n) # some message we want to recover
r = randint(0, n) # random padding

c1 = pow(m + 0, 3, n)
c2 = pow(m + r, 3, n)

R.<X> = Zmod(n)[]
f1 = X^3 - c1
f2 = (X + r)^3 - c2

# GCD is not implemented for rings over composite modulus in Sage
# so we'll do it ourselves. Might fail in rare cases, but we
# don't care.
def my_gcd(a, b):
    return a.monic() if b == 0 else my_gcd(b, a % b)

print m
print - my_gcd(f1, f2).coefficients()[0] # coefficient 0 = -m


How does TLS 1.3 work with PQC signatures? I know that the first step in TLS 1.3 with modern signatures is hash the message with SHA256/SHA384/SHA512.
Do PQC signatures work the same as modern algorithms in TLS 1.3?

Not necessarily; this varies from signature scheme to signature scheme. In some lattice signature schemes (e.g. FALCON) it is important not to produce two signatures for the same private key and hash value. In the case of FALCON it is therefore specified that the message be randomly salted before hashing and signing (see section 2.2.2 of the FALCON submission). Others require that the message be hashed to a particular mathematical structure and so require more hash data from XOF variants such as the SHA3 SHAKE functions. The wide range of PQC proposals for signature schemes make it impractical to do a comprehensive treatment, but if there is a particular scheme of interest more can be said.


Where can I find test vectors for the PRESENT cipher with a 128-bit key? Where can I find the test vectors for the PRESENT block cipher with a 128-bit key?

The test vectors for PRESENT cipher 128 bit key size are:

$$
\begin{array}{c|c}
\def\tabentry#1 {{\scriptstyle\mathtt{#1 }}}
K & P & C  \\
\hline
\tabentry 0x00000000000000000000000000000000 & \tabentry 0x0000000000000000 & \tabentry 0x96db702a2e6900af \\
\tabentry 0xffffffffffffffffffffffffffffffff & \tabentry 0x0000000000000000 & \tabentry 0x13238c710272a5d8 \\
\tabentry 0x00000000000000000000000000000000 & \tabentry 0xffffffffffffffff & \tabentry0x3c6019e5e5edd563 \\
\tabentry0xffffffffffffffffffffffffffffffff & \tabentry0xffffffffffffffff & \tabentry0x628d9fbd4218e5b4 \\
\end{array}
$$

The intermediate values of 0xffffffffffffffffffffffffffffffff key schedule are:

\begin{align*}
\def\keysched#1:#2 {#1&:\mathtt{0x#2}}
\keysched 0:ffffffffffffffff \\
\keysched 1:22ffffffffffffff \\
\keysched 2:2dffffffffffffff \\
\keysched 3:148bffffffffffff \\
\keysched 4:19b7fffffffffffe \\
\keysched 5:74522ffffffffffe \\
\keysched 6:7966dffffffffffe \\
\keysched 7:47d148bffffffffe \\
\keysched 8:40e59b7ffffffffd \\
\keysched 9:871f4522fffffffd \\
\keysched 10:8003966dfffffffd \\
\keysched 11:f11c7d148bfffffd \\
\keysched 12:fa000e59b7fffffc \\
\keysched 13:e2c471f4522ffffc \\
\keysched 14:ede8003966dffffc \\
\keysched 15:328b11c7d148bffc \\
\keysched 16:3db7a000e59b7ffb \\
\keysched 17:d4ca2c471f4522fb \\
\keysched 18:d9f6de8003966dfb \\
\keysched 19:a25328b11c7d148f \\
\keysched 20:1d67db7a000e59b2 \\
\keysched 21:01894ca2c471f457 \\
\keysched 22:14759f6de8003963 \\
\keysched 23:a30625328b11c7d4 \\
\keysched 24:ec51d67db7a000e3 \\
\keysched 25:d68c1894ca2c4719 \\
\keysched 26:6bb14759f6de8005 \\
\keysched 27:fb5a30625328b11a \\
\keysched 28:00aec51d67db7a07 \\
\keysched 29:1bed68c1894ca2c3 \\
\keysched 30:a902bb14759f6def \\
\keysched 31:2c6fb5a30625328c \\
\end{align*}


Small complex multiplication field discriminant for solving ECDLP I've seen from the SafeCurve criteria that one should try to avoid small complex multiplication field discriminant as it can speedup the discret log computation via the Polard Rho method.

However, I cannot find any information about how this additional information can improve the rho method. Especially, the SafeCurve page seems quite vague, mentioning that we do not know for sure if a small Discriminant (even really tiny like 3 for example) can lead to disastrous consequences or not. May someone explain how this particular structure can (in some cases) improve the rho method?

I first recall some basics on the discrete logarithm problem and the Pollard-rho algorithm before answering you question.

The discrete logarithm problem

Given a point $P$ of prime order $q$ on an elliptic curve, and $Q$ a point in the subgroup generated by $P$, then there exists $k$ such that $Q = kP$ where $0\leq k < q$.

The discrete logarithm of $Q$ in base $P$ is $k$, and the discrete logarithm problem is finding $k$ knowing $P$ and $Q$

The Pollard-rho algorithm

The Pollard-rho algorithm on a generic group of prime order $q$ has a complexity of $\sqrt{\pi q/2}$.

The principle of it is to construct a sequence of points by posing $R_0 = a_0P+b_0Q$ with random integers $a_0$ and $b_0$, then using a function $f$ that acts as a pseudo-random walk to obtain the sequence of points:
$$
R_{i+1} = f(R_i) = a_{i+1} P + b_{i+1} Q.
$$
Eventually, there will be will a point $R_j$ that is equal to a previous point $R_i$ in the sequence. Then, we deduce that:
$$
k \equiv (a_i - a_j)(b_j-b_i)^{-1} \mod q,
$$
if, of course, $(b_j-b_i)$ is invertible (but that will be the case with a high probability).

Now, the birthday paradox gives the aforementioned complexity.

Speeding-up rho

On elliptic curves, it is easy to compute $-P$ from $P=(x,y)$ since $-P=(x,-y)$. Then, we can regroup all the points of the curve by pairs $\{P,-P\}$.

Instead of looking for a collision between a point $R_i$ and $R_j$ in the sequence,
we look for a collision on their $x$-coordinate. The discrete logarithm will be found if we have $R_i = \pm R_j$.

It is as if the search has not been done on all the points, but only on half of them. Then the value $q$ in the complexity is replaced by $q/2$, which gives the complexity of $\sqrt{q\pi/4}$ (which you will find the corresponding page on the website SafeCurves).

Speeding-up rho further

What we did above is possible because we have the map (called endomorphism) $[-1]$:
$$
\begin{array}{rrcl}
[-1]: & E & \longrightarrow & E \\
     & (x,y) & \longmapsto & (x,-y)
\end{array}
$$
that sends a point of the elliptic curve $E$ to its opposite. We can see that if we apply it twice, we go back to the original point. We say this map has order $2$, and that is why we could grouped by pairs. And it is easy to compute.

Now the question is: does there exist other such maps easy to compute that could be used to speed-up rho by a greated factor?

The answer is yes. For instance, the curve secp256k1 has the following endomorphism:
$$
\begin{array}{rrcl}
\phi: & \texttt{secp256k1} & \longrightarrow & \texttt{secp256k1} \\
     & (x,y) & \longmapsto & (\beta x,y)
\end{array}
$$
where $\beta$ is an element of order $3$ (it satisfies $\beta^3=1$ with $\beta \neq 1$) in the finite field of the curve. Then we have:
$$
(x,y) \mapsto (\beta x, y) \mapsto (\beta^2 x, y) \mapsto (\beta^3 x, y) = (x,y),
$$
which means the order of $\phi$ is $3$.

Then we can group the points of the curve by group of three: $\{ P, \phi(P), \phi^2(P)\}$. We choose one of three points as a representant (such as the point that has the smallest $x$-coordinate viewed as an integer). Instead of searching a collision in Pollard-rho on $q$ points, we search a collision on $q/3$ representants. From this, we deduce that on this curve we can divide by a factor $\sqrt 3$ the complexity of Pollard-rho. Combined with the previous speed-up, this gives a complexity of $\sqrt{q\pi/12}$.

Relation with the CM-field discriminant

The key is that we want an endomorphism easy to compute, otherwise it would not be useful to speed-up Pollard-rho. As we can see, those two examples given above are pretty simple. It is because their degree is $1$, which means the rational functions to compute the coordinates of $\phi(P)$ are polynomials of degree $1$.

There is a relation between the CM-field discriminant the existence of an endomorphism of small degree. In the case of the curve secp256k1, the fact that this discriminant is $-3$ is directly related to the endomorphism $\phi$ with this formula:
$$
\left(\frac{1+i\sqrt 3}{2}\right)\left(\frac{1 - i\sqrt 3}{2}\right) = 1,
$$
which means that there is a non-trivial endomorphism of degree $1$, that is the one given above.

I hope I gave some elements to answer your question. I will try to expand and correct some points later.


Hashing using asymmetric cryptography Every now and then, we read that some hashing function has been weakened or broken, but we almost never hear this for asymmetric cryptosystems like RSA or ECC. That's because while asymmetric encryption uses mathematical impossibilities (discrete logarithm or prime factorization computation in polynomial time), hashing functions obfuscate their working by complexification, but it seems impossible to make a collision-free hashing function (that is, there is no algorithm to find collisions faster than bruteforce). Symmetric encryption is in the same case than hashing functions, because these algorithms (like DES) seem to have a shorter lifetime than RSA for example, which has been used for more than 40 years.

My assumption is that there is a difference of nature (and not degree) between on the one hand asymmetric encryption (that isn't vulnerable to cryptanalysis) and on the other hand hashing and symmetric encryption (that are vulnerable to cryptanalysis).

But can we use asymmetric encryption to create a collision-free hashing function? To hash some content, we would encrypt it using a public key that everyone would know (something easy to remember, 55555555 for example), but no one would know the correponding private key. But the result would be of variable length, so to reduce it to a fixed size we would hash it using another hash function. We can use an unsafe hash function, like MD5 for example, in fact it is just the compression feature of the hash function that we want to use here. It is a bit reminiscent of digital signatures, but the other way around. So to summarize, the hashing function would do this:

input —(RSA)—> cyphertext —(MD5)—> hash (128 bits)
         ↑
 key: 55555555

Would such a hashing function be really safe and collision-free?

Short answer: You could do this, but (a) it would be dramatically more expensive, (b) it would not improve security in the way you think it would, and (c) it would by design have back doors.

  Every now and then, we read that some hashing function has been weakened or broken, but we almost never hear this for asymmetric cryptosystems like RSA or ECC. That's because while asymmetric encryption uses mathematical impossibilities (discrete logarithm or prime factorization computation in polynomial time), hashing functions obfuscate their working by complexification, but it seems impossible to make a collision-free hashing function (that is, there is no algorithm to find collisions faster than bruteforce). Symmetric encryption is in the same case than hashing functions, because these algorithms (like DES) seem to have a shorter lifetime than RSA for example, which has been used for more than 40 years.

  My assumption is that there is a difference of nature (and not degree) between on the one hand asymmetric encryption (that isn't vulnerable to cryptanalysis) and on the other hand hashing and symmetric encryption (that are vulnerable to cryptanalysis).

On the contrary, quite the reverse is true.  This notion is a red herring, even if this is a common trope (or perhaps, a common tripe?).

Public-key cryptosystems  are designed out of rich mathematical theories that are rife with exploitable relations.  This is necessary for them to have separate public keys and private keys—the private key, in some sense, is a back door.  But it also exposes them to a rich theory of vulnerabilities, and tends to make them very expensive to compute.

The first RSA challenge published by Martin Gardner in his August 1977 Mathematical Games column in Scientific American (sorry, I don't have a paywall-free link!) with a 125-digit semiprime was estimated to take over 40 quadrillion years to solve, yet was solved in 1994 (paywall-free)—coincidentally revealing my name.  The RSA proposal published in 1978 (paywall-free), considering 40 quadrillion years not enough, recommended 200-digit semiprimes out of an abundance of caution—that is, about 664 bits.  The RSA-200 challenge was broken in 2005 (archived), fifteen years ago, only 27 years after the 1978 RSA paper.

Why did this happen?  It's not because silicon technology sped up by a factor of over a quadrillion.  It's because factoring is full of mathematical relations that turn out to be helpful, and we had tremendous mathematical advances—first with the quadratic sieve, and then with the special number field sieve, and then with the general number field sieve.  These mathematical advances reduced a 40-quadrillion-year computation into a few bucks on Amazon EC2.

(There's a similar story of dramatic breakthroughs for many classes of elliptic curves, and for newer pairing-based designs that have an even richer mathematical structure, but I'll leave that story to Koblitz, Koblitz, & Menezes who tell it better.  Some parts of the ECC story seem to have stabilized, but there's plenty more rich mathematical theory to explore.)

Symmetric cryptography tends to be much easier to make secure.  For comparison, we might take a look at DES, which was developed around the same time.  Martin Hellman predicted in 1979 that DES would be totally insecure within ten years (paywall-free).  Sure enough, within a mere nineteen years (off by less than a factor of two, rather than off by a factor of a quadrillion!), EFF's Deep Crack performed a brute force key search to recover a DES challenge key.  Today, again, it's a few bucks on Amazon EC2.  Meanwhile, cryptanalytic advances against DES have been quite modest—especially in comparison to RSA, and the ratio is even starker if you take into account the cost to compute DES and the cost to compute RSA for the legitimate user.

Today, we have a plethora of symmetric ciphers and preimage-resistant hash functions have withstood scrutiny for decades with essentially no serious cryptanalytic advances against them.  The reason ‘RSA’ persists today is that it is actually a family of cryptosystems that can be scaled up to defend against cryptanalytic advances: we no longer use 512-bit RSA keys; we use 2048-bit RSA keys today—and we're getting nervous about those.  But there's only one DES—so we replaced it by AES to raise the generic security, reduce the cost, and address the mild cryptanalytic advances against DES.

What about collision resistance?  Generally, collision resistance seems harder to achieve—and costlier to compute—than preimage resistance, or pseudorandomness.  The hash functions MD4, MD5, SHA-0, SHA-1, RIPEMD, and HAVAL-128 originally advertised with collision resistance have all been broken.  But many of them share common design elements—MD4, MD5, SHA-0, and SHA-1 in particular—which is why we all got really nervous in the mid-2000s about SHA-2 (which shares the design elements) and NIST launched the SHA-3 competition to choose a very different design in case SHA-2 should fall.

But since then, the story seems to have stabilized (archived).  We now have a number of hash functions that have held up quite well for much longer than MD4, MD5, SHA-0, or SHA-1 ever did, and they've held up well enough that cryptographers are comfortable reducing the costs—the popular hash function BLAKE2 is like the SHA-3 candidate BLAKE, but cheaper; the newer KangarooTwelve is like the SHA-3 winner Keccak, but cheaper—without losing collision resistance.

‘But I wanna collision-resistant hash function built out of number theory!!’
OK, OK, here you go.

Pick an RSA modulus $n = pq$.  (Make sure it is big enough to resist 1994 researchers!)  Pick $g \in (\mathbb Z/n\mathbb Z)^\times$ uniformly at random.  For an integer $x$, define $H_{n,g}(x) := g^x \bmod n$.  (To extend this on bit strings, pad them appropriately and interpret them as integers in, say, little-endian.)  Anyone who can find a collision in this can factor $n$ without much more difficulty.  (Proof and references to related ideas.)

Of course, there's a back door!  Anyone who knows $p$ and $q$ can trivially find collisions: $x$ collides with $x + \operatorname{lcm}(p - 1, q - 1)$.  You were asking, after all, for asymmetric cryptography—which means, just like with Dual_EC_DRBG, that there's a back door!

Maybe stick with SHA-2, SHA-3, or BLAKE2?


Does using a snapshot of running PID on Linux provide enough entropy? I am thinking about running the following linux command on each boot to generate a new random token each boot.

printf '%s' "$RANDOM"`ps -e` | md5sum | cut -d ' ' -f 1

The first part takes a string from the shell's $RANDOM variable and then from ps -e snapshot of every running process and PID at the moment.
The second hashes the string.
The last part simply cleans up the string by removing the trailing space-dash outputted with the hash.

Is this enough to generate a quick random string with enough entropy?

No, it doesn't; not unless you want to have $2^{15}$ bits of non-cryptographically secure random token - the output of the $RANDOM function of bash.

How PID's are created depends on the operating system. The only other information is the starting time really. Neither of those can be seen as random and is easy to guess and even to influence.

There have been some proposed patches to make PID's more random in Linux but they were rejected by the kernel maintainers. They are kind of chicken-egg anyway; to create random ID's the kernel would need to have a good random number generator which you could employ yourself.


Low level explanation of how a message is sent via RSA I understand that RSA encryption uses this formula:

C = M^e (mod N)

public key is e and N

N is pq - p and q are private key.

mod N makes above function one-way - ie cannot be reversed.  Hence given C, e and N, it is not possible (easily) to find M.

Basic idea is that modulo arithmetic on an exponent is a one way function.

The practical bit I am struggling on now is that M (the message) must be a number.  How is the text eg "I love you" converted to a number.  I am looking to understand the basic concepts but also in reality what scheme is used to create a number from the text.  What are the options and what is generally used in practice?  Please explain the mathematics as required.

You could take the byte stream of the text message above:

01001001001000000110110001101111011101100110010100100000011110010110111101110101

and treat as a LARGE binary number.  I guess the numbers would get pretty large like this so probably not the way its done.

How it is done in practice is that no one uses RSA to encrypt messages. They use RSA to encrypt (and sign) an encryption key, and then encrypt the message with the encryption key. They send the encrypted key and the encrypted message to the other party. The other party uses their RSA private key to decrypt the key, then uses that key to decrypt the message. Furthermore, in practice, they also add padding to the key before encrypting it with RSA.

That said, RSA can indeed encrypt any message that is smaller than the modulus N. So, if your byte stream in the question is smaller than the modulus, you can encrypt it with RSA. If the byte stream were larger than N, you could theoretically break it up into smaller messages and encrypt them individually. The problem with this is RSA is deterministic; so you'd have to add some random padding to make it non-deterministic. Typically people just don't bother with RSA for bulk encryption, however.


Most efficient conceivable padding mode, and with no padding oracle When plaintext padding is required, there are various commonly-used padding techniques.  It seems the two most used approaches are :

Always add at least one byte of padding, and have every byte of padding represent the number of bytes of padding added; or else
Always add at least one byte of padding, and have the last byte of padding represent the number of bytes of padding added, whilst the other padding bytes are zero;

The very concept of a padding oracle relies on there being byte arrangements that are invalid based on the padding scheme used.

Another padding scheme seems extremely obvious to me, has no potential for oracle padding exploits (as all byte arrangements are valid), and results in approximately 6% fewer padding bytes being added to messages on average (assuming random distribution of message lengths and random message contents).

I describe the padding scheme below, but my question is simple : since this padding scheme is so obvious, and simple to implement, and eradicates all possibility of padding oracle attacks, and saves a smidgeon of storage space and bandwidth, why am I unable to find anyone else promoting this obvious scheme?  Am I overlooking an obvious flaw?  Has it been proposed before but widely rejected, and if so, why?

This is not a question about using MACs to prevent padding oracle exploits, nor am I suggesting not using MACs just because this padding scheme is impervious to padding oracle exploits, but I am a big fan of eliminating unnecessary weaknesses in individual components of a system even if the careful layering of components can mitigate the weaknesses.  Padding oracles are so easy to have designed to be impossible, if the following scheme works, that I don't understand why we have the padding schemes we do.

The scheme :

If final block is less than full, add zeros until (exclusive) the final byte, then add a byte representing the number of padding bytes added.  (So far, identical to one of the common schemes, EXCEPT that on receipt, we ignore the meant-to-be-zero bytes, and thus if they are corrupted in transit, it will not cause a padding validation failure.)

Assuming block size of 16 bytes, if final block is full, and final byte of final block has numeric value between 1 and 16 inclusive, add an entire padding block, filled with zeros except for the final byte, the which holds the number of padding bytes added (16 in this case).  (Again, at this point, no different to one of the padding schemes already in common use, except that again, on receipt of a padded message, we entirely ignore padding bytes that we expect to be zero, and thus a corruption in transit will not cause a padding validation failure.)

Assuming block size of 16 bytes, if final block is full, and final byte of final block has numeric value of 0, or >= 17, no padding is required.  (This is the one point of difference from the otherwise-identical common scheme.)

In this scheme, all byte sequences are valid, eliminating padding oracle problems.

And compared to the mainstream padding approaches, we save a smidgeon of storage space and bandwidth, because 1/16th of the time (assuming random distribution of message lengths, and random message contents), we have only 16/256ths (i.e. 1/16th) probability of needing to add a full block of padding bytes, meaning 15/16ths probability of saving ourselves the 16 padding bytes, as compared to always requiring a full block of padding as occurs in the equivalent situation with the mainstream padding schemes.

What am I missing, or else why do we live with padding schemes that need extremely careful use to prevent leaking sensitive data?

Thanks in advance for your answers!

Your scheme leaks information about the plaintext, outside of the length of the message. To be precise, it may leak the information that the last byte is between 1 and 16 or not.


Modification of vigenere cipher cryptographically secure? After looking for ages online for a python implementation of the Vigenere cipher, and finding few, I decided to implement it myself. After ironing out all of the flaws, it's now a working (and secure) implementation of the Vigenere cipher. But I had an idea.

What if you increase the size of the alphabet that it's using? eg:

With the size of the alphabet being 1114111 , and all letters of the alphabet having been converted into their ASCII representations (a  = 97):

Encryption:

$c^i = (m^i + k^i) \bmod 1114111$

Decryption:

$m^i = (c^i + k^i + 1114111) \bmod 1114111$

Would this be cryptographically secure? And I'm assuming that it would be more secure than traditional Vigenere?

Vigenère Cipher

Let's look at some different attacks on the Vigenère cipher and determine how much of a role alphabet size plays.

From Wikipedia:

  The primary weakness of the Vigenère cipher is the repeating nature of its key. If a cryptanalyst correctly guesses the key's length, the cipher text can be treated as interwoven Caesar ciphers, which can easily be broken individually.

With a number like 1114111, breaking the individual Caesar ciphers by brute force would still be pretty easy. Maybe if you increase the size even further (128 bits or higher?). However, there could be attacks that perform better than brute force given the nature of the cipher.

Kasiski Examination:
Analyzing repeated groups of ciphertext which could correspond to the key. Extending the alphabet size would not affect this method, the best defense against this would be extending the key (ideally to the length of the plaintext, more on that later).

Key Elimination:
We can guess the key length (or figure it out somehow, like the Kasiski method) and remove the key from the ciphertext. This makes the alphabet size redundant (even if it was well above 1114111) because the key would be removed from the ciphertext anyway. To stop this, our key must be as long as our plaintext (see one-time-pad below).

Frequency Analysis and Friedman Test:
These rely on having information about the plaintext beforehand. Depending on implementation, your method could break these analysis techniques (or at least make them more difficult to implement).

These are just the methods outlined on Wikipedia for breaking the Vigenère cipher (you can of course look deeper into other methods). It should be pretty clear that Vigenère in the modern world can be considered broken, even if you play with the alphabet length and tweak the cipher in little ways.

One Time Pad (OTP)

Your question is tagged with one-time-pad, so I thought I should address this too. The one time pad can be implemented as a Vigenère cipher with a key that has the same length as the plaintext.

The one time pad is perfectly secure, but it has some stipulations and drawbacks.

The key must be truly random, and at least as long as the plaintext.

This means it shouldn't be entered by a user, repeated to fit the plaintext length, or generated using any pseudorandom number generator
Generating true random numbers is difficult and generally impractical*
Practically, you could use a CSPRNG, but then your OTP is only as strong as your CSPRNG (i.e. not a true OTP)

The key must never be reused. The key is used once to encrypt, then once to decrypt, then discarded. Encrypting multiple plaintexts using the same key can open you up to attacks (like Key Elimination mentioned above).

If these conditions hold, then the OTP is perfectly random, because any one key is equally as likely as any other. Which means that any plaintext is equally as likely as any other plaintext to the adversary. So even with infinite time and resources, the adversary could never reverse the cipher (without the key).

* Generating truly random numbers can be done using a TRNG, usually implemented as an external hardware device. You can purchase these as USB input devices or make your own circuit.