OpenSSL & TLS1.2 with aes-cbc and initialization vector I'm trying to manually decrypt DTLS traffic using OpenSSL and TLS 1.2. The cipher suite im using is AES256-SHA256 as listed here. Im able to decrypt the packets with the key that the server and the client negotiate during the handshake without issues, but what i don't understand is that i can set the initialization vector to any value or even null and still i can decrypt the packets.

Here is a code snippet from the program that receives the packet:

EVP_CIPHER_CTX *ctc = EVP_CIPHER_CTX_new();
EVP_DecryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, key, (const unsigned char)"not a real iv");
...
EVP_DecryptUpdate(ctx, (unsigned char*)payload, &len, (unsigned char*)payload, len);
EVP_DecryptFinal_ex(ctx, (unsigned char*)payload + len, &len);

And that decrypts the data fine with the bogus IV.

So apparently either the encryption / decryption is not done in CBC mode.
Or does OpenSSL derive the IV by the decryption key somehow from the packet ?

What i am missing or/and not understanding here ? The DTLS rfc did not talk about this either.

Or does OpenSSL derive the IV by the decryption key somehow from the packet ?

Well, yes.  Actually, it's not that complicated; for DTLS and AES-CBC mode, the IV is the first 16 bytes of the encrypted region, so it just reads it from there, and starts decrypting from there.

In DTLS, we assume that encrypted packets can be dropped in flight (or received out of order), and so the system cannot assume that the decryptor has seen the previous packets.  Everything that is needed to decrypt (except for those parts, such as keys, that were established in the initial negotiation) must be in the UDP packet.  When it comes to IV, well, IV's can be sent in the clear; we need to communicate the IV to the decryptor, and so the obvious approach (which DTLS uses) is just include the IV in the UDP packet.

Now, for TLS, this 'missing records or receiving them out of order' is not an issue (as the TCP stack will ensure that, absent someone in the middle tweaking things, we will receive things as sent).  So, what TLS 1.0 used to do is make the IV for the next record the same as the last ciphertext block of the previous record.  However, it turns out that opens things up to chosen plaintext attacks, hence with TLS 1.1 and on, they also send the explicit IV, just like DTLS has always done.

  The DTLS rfc did not talk about this either.

Actually, DTLS1.2 RFC (6347) just says 'we do it the same as TLS 1.2' (see section 4.1.2.3), the TLS1.2 RFC (5246) explains the explicit IV structure (see section 6.2.3.2)


RSA engine with inaccessible private keys - susceptible to any attacks? We are going to integrate some hardware accelerator for RSA into our next system on chip. This chip can accelerate the core RSA operation, i.e. modular exponentiation $y=A^x \mod(N)$. The private key ($x$) to use can either be provided from the outside or will be stored inside the hardware core, unaccessible to any other hardware /software component. Side-channel attacks are not an issue in this question.

We assume that the software can query the accelerator to do the modular exponentiation using the on-chip key ($x$) and just gets the result ($y$) for any arbitrary $A$ he provides. Would this setup be susceptible to any oracle-kind attack which would allow extraction of the on-chip key $x$? If so is there any countermeasure against this (using padding according to PKCS #v1.5 or RSASSA-PSS)?

Would this setup be susceptible to any oracle-kind attack which would allow extraction of the on-chip key $x$?

Not as far as we know.

Any such Oracle attack that could recover the private key would demonstrate that the "RSA problem" and the "factorization problem" are equivalent.  Currently, that is an open question; such an attack would be a noteworthy advance...


64 bit Elliptic Curve key? For a simple proof of concept project i'm (attempting!) to do, i've started looking into openSSL elliptic curve cryptography.

However instead of the standard key lengths, 160-512. I'm interested in a resultant key of just 64 bits (less secure I know but that's my projects purpose). Is it possible using elliptic curve cryptography?

I'm quite a novice, is there anything fundamentaly wrong with instead generating say a 256 key and cutting it size to 64bit?

Any advice would be greatly appreicated thanks.

I'm not sure if I get your question correctly. Do you like to use a 256 bit curve to generate a (secret) key of this size and later drop 192 bits? If this is the case your 64 bits will be useless because you secret key will not have any relation with the public. Furthermore, in a magic case that this works, your field operations will continue living in a 256 finite field.

If you like to use a 64 bits EC cryptosystem, first thing you need is to stablish the "setup": a tuple that 'configures' this set up. You may like to check the IEEE P1363 for details, but to have a cryptographically good curve (ignoring the fact that 64 bit is very few). As an example for a finite field:

Generate $p$: random big prime of your 64 bits.
Generate $a$ and $b$: in $\mathbb{F}_{p}$
Check non zero discriminant: $\Delta\neq 0$
Calculate the cardinal $|E(\mathbb{F}_p)|$
Check this cardinal is in the hasse interval
Check this cardinal factorises in $n$ and $h$ where $h<<<n$ and $h\in[1,2,4]$

If steps 3, 5 and 6 fails, go back to step 2 or even 1.

At this point you have a cryptographically good curve, then you need the cyclic subgroup where the ECDLP will protect your secrets.

Generate a random $x\in_R \mathbb{F}_p$ until you find a valid point in your curve. (for a valid $x$ there will be two $y$, select at random).
Check $[n]G=\mathcal{O}_E$

Same than before, if you random point doesn't pass check 2, repeat. But the probability to find a good one is bigger as your cofactor $h$ is smaller.

As you can see, this process is not light and it becomes heavier and heavier (exponentially) when you increase your 64 bits.


Compacting a substitution cipher key In a substitution cipher, I recieve 3 bits and than I return another 3 bits.
The key of this cipher could be a matrix represented as:

(0) 0 0 0 => 0 1 1

(1) 0 0 1 => 1 0 1

(2) 0 1 0 => 1 1 1

(3) 0 1 1 => 0 1 0

(4) 1 0 0 => 0 0 1

(5) 1 0 1 => 1 0 0

(6) 1 1 0 => 0 0 0

(7) 1 1 1 => 1 1 0

So, when we receive 000, the cipher will return 011.

When we receive 101, the cipher will return 100.

The key itself can be represented as a stream of 24 bits like this:

0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0

Is there a way to reduce the key to 15 bits?

I other words, can that matrix representation of 24 bits, could be represented with 15 bits?

Not quite, if all possible permutations are allowed.

There are $8! = 40320$ permutations over 3 bits; 15 bits of key allows you to specify $2^{15} = 32768$ of them; hence any mapping of 15 bits will necessarily $40320-32768 = 7552$ of permutations unexpressable.

It is doable if you don't allow every single permutation (e.g. allow only even permutations), or if you allow 16 bits of keying data.


Encryption Scheme & Perfect Secrecy [Katz & Lindell] An encryption scheme consists of the following data

a plaintext space $\mathcal M$
a ciphertext space $\mathcal C$
a key space $\mathcal K$
a key generating algorithm Gen
encryption and decryption algorithms $\operatorname{Enc}_k$ and $\operatorname{Dec}_k$ for each key $k\in \mathcal K$

I would like some clarification on the following extract from Katz & Lindell:

More specifically, my question is:
What does, say, $P(K=k)$ mean exactly? What is the domain and codomain of the random variable $K$? What is the set $\{K=k\}$? Also, what is the domain of Gen?

What does, say, $P(K=k)$ mean exactly?

It signifies the probability that the key $K$ selected by the key generation algorithm $Gen$ is the value $k$.

The notation he is using is that $P(condition)$ (actually, they use $Pr[condition]$, perhaps to emphasize that $P$ isn't a function on the value condition, but rather its probability distribution) is the probability that the condition is true.  For example, if I flip a fair coin, we have $P(\text{heads}) = 0.5$

  What is the domain and codomain of the random variable $K$?

The key space $\mathcal K$

  What is the set $\{K=k\}$?

It's not a set; it's an equality which is true with a certain probability.

  Also, what is the domain of Gen?

The key space $\mathcal K$


How to clock a linear feedback shift register? I have some trouble understanding what happens when a LFSR is clocked. I have tried many examples but I do not get the correct result. Can anyone point out my errors?

I have the following polynomial:

$$f(x)=1+x+x^5+x^6+x^8$$

I am working on this as a part of a known plaintext attack and I have the following keystream:

01010101000110101100

So, the first 8 bits of the keystream must be the IV for the LFSR, and the LFSR should do XOR on third ($x^2$), fourth ($x^3$), fifth ($x^4$) and seventh ($x^7$). In the next line the leftmost bit should go out and the rightmost the value from the XOR operation, the rest should be shifted one place from the line above, hence the structure:

$1 \times x^2 \cdots x^3 \cdots x^4 \cdots x^7$

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0 1 0 1 0 0 0 0

So, the rightmost bits in each line should be the continuing of the keystream after the 8th first bits, this seems to add up for the first three zeros, but after that it's not giving the keystream.

What am I doing wrong?

The keystream 01010101000110101100 can be deduced from its first 8 bits and the polynomial $f(x)=1+x+x^5+x^6+x^8$, as follows.

Start with $b_0=0$, $b_1=1$, $b_2=0$, $b_3=1$, $b_4=0$, $b_5=1$, $b_6=0$, $b_7=1$ (according to the first 8 bits of the keystream in reading order). And for $i$ increasing from $0$ apply the recurrence $b_{i+0}\oplus b_{i+1}\oplus b_{i+5}\oplus b_{i+6}\to b_{i+8}$, where the integers following $_+$ are the orders of the non-zero coefficients in the polynomial. That is:

$b_8\gets b_0\oplus b_1\oplus b_5\oplus b_6=0$
$b_9\gets b_1\oplus b_2\oplus b_6\oplus b_7=0$
$b_{10}\gets b_2\oplus b_3\oplus b_7\oplus b_8=0$
$b_{11}\gets b_3\oplus b_4\oplus b_8\oplus b_9=1$
$b_{12}\gets b_4\oplus b_5\oplus b_9\oplus b_{10}=1$
$b_{13}\gets b_5\oplus b_6\oplus b_{10}\oplus b_{11}=0$

This is using a Fibonnaci implementation of the LFSR, which is convenient since it is such that the first bits output are also the initial state of the LFSR. According to the convention used to define Fibonnaci and Galois implementations, we might be using the fact that the polynomial for a Fibonnaci implementation is the reflection of the polynomial for a Galois implementation (that is, the coefficient for the terms of order $j$ and $d-j$ are swapped, where $d$ is the degree of the polynomial).

If we wanted to apply a Galois implementation, we'd have to deal with the fact that the initial state of the LFSR is not the first bits of output, and thus not immediately known in the context of the question: by common conventions, the first bits of the given keystream simply are NOT the initial state of a Galois LFSR with polynomial $f(x)=1+x+x^5+x^6+x^8$ producing the rest of the sequence immediately afterwards.


Fast cryptographic hash function for short inputs I am looking for a cryptographic hash function optimized for speed on short inputs, in order to implement a pseudorandom generator with expansion factor 2 (e.g. takes 16 bytes of input and outputs 32 pseudorandom bytes).
Here are some natural candidates I tried:

SHA256: good baseline
Blake2: designed for speed on large inputs, does not perform as well on short inputs
AES-CTR: faster than SHA256 when the hardware supports AES-NI. The input is used as a key for AES to encrypt a predefined byte array of the desired output length. However, re-initializing the cipher for each call to the hash function is costly.

I also found this interesting construction: STHash. It is a keyed cryptographic hash function optimized for speed on large inputs. I don't mind having a keyed hash function instead of a general-purpose one.
Is there any analogous construction for short inputs, or a more efficient way to leverage AES-NI than AES-CTR?
Some informal benchmarks
For each hash function, I hash an array of 16 bytes into a 32 bytes array, and I repeat 10 million times. For stream ciphers like AES and ChaCha, I create a new cipher at each iteration with the input as key on a public fixed plaintext and nonce. If the cipher needs a 32-bit key, I just pad the input with 0. If the hash function does not produce enough bits (e.g. SipHash outputs only 128 bits), I run it several times.
I am running Rust Nightly on an Intel® Core™ i7-1065G7 CPU @ 1.30GHz × 8, the experiments run on a single thread.

SipHash 1-3: 476.9ms
Chacha8: 590.4ms
SipHash: 670.3ms
AES-128: 665.3ms
SHA256: 780.4ms
Blake2s: 1413.9ms

For information, some results about Haraka (using a not well-known optimized implementation):

Haraka-v2 256-5: 55.2ms
Haraka-v2 256-6: 69.9ms

Did you try SipHash, especially the reduced-round version SipHash-1-3?
It was explicitly designed for short input, doesn’t require key expansion, is fast on pretty much all kind of architectures, and can output 64 or 128 bit.
The name might be confusing, though: a key is required, but since you mentioned that it wasn’t an issue for your use case, give it a try.


Isn't code signing just digital signature on code? I have been trying to understand why code signing is treated or discussed differently from digital signature.

Digital signature is signing a hashed BLOB with a private key. When the BLOB is code/software, it is code signing.

So, isn't code signing just digital signature in the true sense? Why is it carved out based on the BLOB?

Indeed, code signing is a special case of digital signature, and there is no imperious reason to distinguish the two from the standpoint of defining a cryptographic signature primitive.

There are however reasons to special-case code signature from an IT security perspective, by a having a "code signing" attribute in a digital certificate. It is a useful distinction for a certificate wether it's a code-signing or data-signing certificate; that is, if the signature of a piece of data checking against the public key introduced by the certificate should be considered, or not, as and indication that said piece of data is safe to run as executable code. In a Unix file system context, the distinction might correspond to a rule: allow setting the Execute flag or not on the piece of data received.

A similar useful distinction for a certificate is wether it's a certification authority certificate or not; that is, if the signature of a piece of data checking against the public key introduced by the certificate should be considered, or not, as an indication that said piece of data is a certificate. The distinction might correspond to a rule: entering that piece of data, or not, in the list of certificates that can validate a digital signature.

In both cases, the distinction is made with an attribute in the digital certificate, typically with different rules for certificate issuance according to this attribute.

There are efficiency considerations to account for when selecting a signature algorithm according to context, and that has some degree of relevance when choosing such algorithm for code signature:

Simplicity of the signature verification: especially for early boot code, it might be essential that the signature verification code is short and fully auditable (e.g. because it stands in a special, prohibitively-expensive-to-change memory, and much of the rest of the security sandcastle chain depends on that). That's a reason to use RSA, or Rabin signature. That also applies to digital certificate signature.
Speed of the signature verification: especially for low-power embedded systems, it might be essential that code signature verification is fast. That's another reason to use RSA, or Rabin signature. That also applies to digital certificate signature.
Speed of signature generation. That's seldom a consideration for code, which is typically orders of magnitude harder to write or compile than it is to sign.
Size overhead. That's seldom a consideration for code, which nowadays is typically much larger than a signature.


Dice vs quantum random number generator I recently championed quantum key distribution networks.  This has led me to also question quantum random number generators. It appears that randomness is randomness, even if  made by custom quantum hardware featuring lasers and photon genies.

It would seem that there is a great deal of chaff and hype surrounding quantum generation of anything at all, and so I'm left wondering what is the qualitative difference between:-

which is a 4 Mbps quantum beam splitter[*] selling for ~€1300 and

when coupled with a simple von Neuman[+] extraction technique?

This is not a facile question.  I'm interested in any tangible substantive difference between the two sequences of random bits other than speed. Are they just as random if not as fast? And therefore are quantum RNGs further examples of electronic snake oil?

It's easy to immediately berate such quantum hardware as pure marketing.  No one's as cynical as I am, but the evidence suggests that there are non gullible people (indeed commentators, universities and IT organisations) buying these. £M's are globally spent on researching new /faster quantum generators.  NIST has one.  Why should they bother demonstrating measurements outside of the cone of influence when they could use a smart card or dice?  Are all of the people being fooled all of the time? That's meant to be impossible.

[*] A laser beam is split with a semi-mirror and detection of photons in the two resulting beams produces random bits. There is a white paper here describing this kit.

[+] This experiment produces independent and identically distributed random bits (not 1 - 6) due to the shaker cup eliminating correlations between throws, and the von Neumann extractor removing die bias. 1 truly random bit is generated every two throws (slightly less on average).

From the manufacturer's website:

  Quantis uses Quantum Physics to create truly random numbers

  Existing randomness sources can be grouped in two classes: software
  solutions, which can only generate pseudo-random bit streams, and
  physical (hardware) sources. Software solutions are not capable of
  providing true randomness as they are based on deterministic computer
  programs. Instead, they rely on external entropy sources to build up
  randomness, but these are slow and inefficient, and the quality of the
  randomness may be difficult to verify.  In the latter – hardware RNGs
  – most random number generators still rely on classical physics to
  produce what looks like a random stream of bits. However, in reality,
  determinism is hidden behind complexity for such RNGs without real
  quantum random properties.

They claim that hardware random number generators which do not use quantum properties are actually deterministic but this determinism is hidden.
This is complete nonsense.

There is no evidence that this is true and no theoretical model supporting it.

Even if the universe was completely deterministic as long as the process generating the output is hidden (as they claim) the output will still appear random for all intents and purposes. Randomness is not necessarily a fact about the universe but about the lack of knowledge of an adversary.

Saying that the universe is completely deterministic but that their quantum random number generator works would require the universe to receive no feedback from quantum effects. If this was true we could also not measure them.


Nonmembership witness in universal accumulator We can say that when compared to a Merkle tree, inclusion proofs are constant size by membership witness. Can we say that also for exclusion proof bu nonmembership witness? Is there any advantage of nonmembership witness in an accumulator?

In accumulators based on groups of unknown order (such as RSA or class groups) or accumulators based on bilinear pairings, both membership and non-membership proofs are constant-sized (i.e. independent of the size of the set and the size of the subset you are proving membership/non-membership for).


Could this be a valid variation of the Schnorr protocol? The Schnorr protocol is a 3-steps proof of knowledge of a discrete logarithm, whose interactive version works as follows.

Let $p$ and $q$ be two public primes, such that $q \mid (p-1)$, and let $G$ be  a cyclic subgroup of $\mathbb Z^\times_p$ of order $q$ (i.e. a Schnorr group) with generator $g$. The prover $P$ wants to prove knowledge of $x=\log_g(y)$ to a verifier $V$, by the following steps:

1) $P$ commits himself to randomness $r \in \mathbb Z_q$, and sends $t=g^r \bmod p$ to $V$.

2) $V$ replies to $P$ with a challenge $c$ chosen at random from $\mathbb Z_q$.

3) After receiving $c$, the prover $P$ sends the response $s=r+cx \bmod q$ to $V$.

4) Finally, the verifier accepts if $g^s \equiv t y^c \bmod p$.

My question is:

What is the exact reason why the response $s$ of the prover in step 3 is that one, and not another one? For example, couldn't it also work if the response were, for example, $s=r+c+x$ or $s=rc+x$, and then the verifier had to check if $g^s \equiv t g^c y$ or $g^s \equiv t^c y$, respectively?

As noted by Perseids in a comment to this answer, the formula $s = r + c + x$ would allow an adversary (who has completed the protocol once in the role as verifier with $P$ and already got one valid triplet $t_1,c_1,s_1$) to compute responses to any arbitrary challenge, simply using the formulas $t_2 = t_1$, $s_2 = s1 + c_2 - c_1$.

Your other alternative $s = rc + x$ would however work, given a few additional restrictions:

$c \neq 0$. Since we are working in a prime order subgroup, this implies the existence of a multiplicative inverse $c^{-1}$ modulo the group order $q$. This is not a significant restriction to the original protocol, since $c = 0$ would entail the response $s = r + 0x = r$, which would not prove possession of $x$ and hence be pointless. With the alternative formula, however, $c = 0$ would entail $s = x + 0r = x$, which would leak the private key.
$t$ and $y$ belong to the same prime order subgroup as $g$. This is implicit from the protocol specification, but it might be stressed that $V$ is able to verify that this is indeed the case, by checking that $p, q$ are prime numbers such that $q|p-1$, and that $g^q = t^q = y^q = 1 \bmod p$.
We define $r = log_g(t) \bmod p$ and $x = log_g(y) \bmod p$. The attacker is not required to know the exact value $r$ and $x$ for the following math to work out.

We also need a security claim, in order to define exactly what it is we assume about the original protocol and want to prove with respect to the alternative one. The most appropriate claim would be that an adversary $A$, who does not know $x$ and does not have real-time oracle access to the authentic prover $P$, has only a negligible chance of successfully playing out the protocol with a honest verifier $V$.

It might be noted that an adversary $A$ with real-time oracle access to the authentic prover $P$, would be trivially able to successfully play out the protocol with any honest verifier $V$. Hence, in order not to prove something we already know, we have to assume this is not the case.

Suppose an adversary $A$ is able to impersonate $P$ and provide false proofs of $x$ using the alternative formula. Since $sc^{-1} = (rc + x)c^{-1} = r + xc^{-1}$, such an adversary would also be able to provide false proofs of $x$ using the original formula. Since the latter is impossible, so is the former.

A proof might be outlined as follows:

Let $A$ be an adversary who is able to successfully play out the protocol based on the alternative formula $s = rc + x$, given the restrictions listed above. Let $V$ be a (honest) verifier who expects the $s$ value to comply with the original formula, subject to the same restrictions (in particular that $c \neq 0$). Let $A'$ denote $A$ taking the role of a prover of the $x$ using the original formula.

Now, all we need to do is to add a few steps where $A'$ plays out the protocol steps with $A$ (i.e. himself):

$V$ asks $A'$ to commit
$A'$ asks $A$ to commit and gets a value $t$, such that $t^q = 1 \bmod p$, which $A'$ forwards to $V$.
$V$ replies with a challenge $c$ chosen at random from $\mathbb Z_q^*$
After receiving $c$, $A'$ sends $c^{-1}$ to $A$, gets a value $s$ and sends the response $s' = cs$ to $V$.
Finally, $V$ accepts if $g^{s'} = ty^c \bmod p$.

If $V$ doesn't accept $s'$ as a proof of $x$ given challenge $c$ in step 4, neither would a verifier who expected a response using the alternative formula accept the response $s$ to the challenge $c^{-1}$ as a proof of $x$.

So what does this prove with respect to the security claim? Firstly, assume that the original protocol meets the security claim, but the alternative protocol doesn't. If the alternative protocol doesn't meet the security claim, it means that the adversary $A$ has a non-negligible probability of successfully playing out the above protocol, but since we have just proved that this would mean that $A'$ also would have the same probability of successfully playing out the protocol, this would contradict our original assumption (that the original protocol meets the security claim), and hence it is not possible that the alternative protocol doesn't.


Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p? I have seen the NIST, SEC and Brainpool standards. They have used same prime for a particular bit curve (128,192,256,521). Is the prime value fixed for a particular security (field size)?

In general you start by fixing the field, which translates into fixing the prime, and then you start to look to a suitable (i.e. secure/safe) elliptic curve defined over that field.

Note that, once you've fixed $p$, there are $\sim2p$ isomorphism class of elliptic curves defined over $\mathbb{F}_p$, which grants you a big set where you are supposed to find a curve with all the desired security properties, unless you are looking for very specific properties such as low CM discriminant.

There are two good reasons for it.

First: the field is linked to the curve's cardinality by Hasse's Theorem. which means that by choosing the size of the prime you also strictly bound the size of the cardinality (within a bit).

And second, and most important, a particular choice of the prime provides faster-than-generic modular reductions, which provides performance benefits of elliptic curve computations.

For example, all NIST P curves are defined over Solinas primes (also called generalized Mersenne), except P-521 which is over a Mersenne prime.
The idea is that using Solinas reduction is faster than a generic modular reduction and can be used to speed up the computation.

Similar arguments are used in more modern elliptic curves such as curve25519 which uses a pseudo Mersenne prime ($2^{255}-19$) or FourQ which uses is defined over a field $\mathbb{F_{p^2}}$ with $p=2^{127}-1$.

Note that the Brainpool standard uses random primes, however its deterministic algorithm for curve generation selects first a random prime, and then look for a suitable curve. See appendix A of RFC 5639.


Intersection of two elliptic curves Is it possible to find points that are on two elliptic curves, and how?

More precisely, I'm looking for coordinates $(x,y)$ that satisfy the defining equations of two elliptic curves on prime fields $\mathbb{F}_{p_1}$ and $\mathbb{F}_{p_2}$:
$$
\begin{cases}
y^2 \equiv x^3 + a_1 x + b_1 \mod{p_1} \\
y^2 \equiv x^3 + a_2 x + b_2 \mod{p_2} \\
\end{cases}
$$
Is this even tractable, and if so how can I calculate at least one intersection point? Is it tractable to have the private key on one of the curves (for given generators)?

I'm curious about the question in general, but in order for this to be practically useful to me now, the curves need to be supported by the software I'm working on: two curves among SECP256R1, SECP256K1, BP256R1 or their 224-bit or 384-bit counterparts.

The motivation is a data validation bug in this software that leads to a public key to be interpreted on the wrong curve, but it has to satisfy both curves' equation. I want to understand how easy it is to exploit it and I'd like to write a non-regression test (which only requires the public values).

Interesting problem. One should distinguish between two distinct cases, according as whether $p_1=p_2$ or not.

The case $p_1=p_2$ (let's call this common prime $p$) is easy. You can just subtract the two equations and get:
$$(a_1-a_2)x + (b_1-b_2) \equiv 0 \pmod p $$
which gives either a unique choice for $x$ (if $a_1\neq a_2$) or none at all (if $a_1=a_2$ but the $b_i$'s are distinct). In the former case, you can easily check whether that coordinate $x$ corresponds to an actual point on the elliptic curves; for randomly chosen curves, the chance of this happening is about 1/2. Note however that standard curve parameters often mandate that $a=-3$, in which case you are always in the latter case, and intersections simply don't occur for curves over the same base field.

The case $p_1\neq p_2$ is more subtle, because it isn't obvious how to interpret the question anymore. Mathematically speaking, the problem doesn't really make sense, because the fields $\mathbb{F}_{p_1}$ and $\mathbb{F}_{p_2}$ are distinct, unrelated objects.

One can look, however, for points $(x,y)$ with integer coefficients (or even, in some sense, rational coefficients), with the property that when reduced modulo $p_1$ we get a point on the first curve, and when reduced modulo $p_2$ we get a point on the second curve. Constructing such points is straightforward: take any point $P_1$ on the first curve, any point $P_2$ on the second curve, and apply the Chinese remainder theorem to their coefficients to get what you want. But this may not be the problem you are actually interested in, because if you do that, the bit size of the coefficients of the resulting point $(x,y)$ will be as large as the sum of the bit sizes of $p_1$ and $p_2$ in general.

One could also ask for such integer solutions $(x,y)$ with the additional requirement that, for example, $x$ and $y$ should be at most $\min(p_1,p_2)$ in absolute value (or perhaps $\max(p_1,p_2)$ depending on the application). This amounts to looking for points with small coefficients on the lifted curve
$$y^2 \equiv x^3 + \hat{a}x + \hat{b} \pmod {p_1p_2}$$
where $\hat{a},\hat{b}$ are obtained by Chinese remaindering. Heuristically, if $p_1$ and $p_2$ are roughly of the same size, say $m$ bits, such a point should exist with good probability (there are about $2^m$ possible $x$ coordinates of the right size, and at least one of the corresponding $y$ coordinates fall in the right interval with probability around $2^{-m}$; one can make this rough estimate more precise if necessary). It is not completely obvious how to find such a point, however. The usual technique to find small solutions of algebraic equations is to use some variant of Coppersmith's theorem, but depending on the precise version of the problem you are interested in, the bounds offered by Coppersmith are likely to be insufficient.

If you can say more about your precise application, one could have a closer look. It might even be worth writing a paper about it.


Paper wallet QR codes What is the purpose for and distinction between each of the following keys commonly used in cryptocurrencies?

Address
Tracking key
Passphrase
Private key

For context:
I got a bytecoin paper wallet which has a QR code for each of the 4 things above and just wanted to know what they are for / mainly want to know how to check the paper wallet balance to ensure what was sent to the qr code and is actually there.

As I've rewritten your question:

  What is the purpose for and distinction between each of the following keys commonly used in cryptocurrencies?

Public keys

  Address

You may think of your address like a mailbox that receives money. Anyone can put money into the mailbox, but they cannot take it out.

  Tracking key

A variant of the address that derives many addresses for a single identity. This enables you to check the balance for all of your addresses without using your secret keys, which enable you to spend the money. This is useful to isolate your secret keys, or to use a less trusted device like your phone to check your balance, without enabling it to spend.

Secret keys

  Passphrase

If this is a 12-word phrase you didn't choose, it is the seed. This seed is a convenient way to derive the next key.

  Private key

The secret variant of the tracking key. Deriving the secret keys for all addresses under the same identity. You may prefer to keep this key cold (offline), or on a dedicated hardware device.


Combining Random Hashes - avoiding collisions and ensuring randomness I have a series of integers which I want to convert to random integer (64 bit). The idea here is to produce random numbers very quickly. The issues that good quality random numbers are required with a low collision rate to ensure low correlation between entities. A series of integers are input and a number of desired samples are required that are a random as possible.

The hash?

The random hash is taken from Numerical recipes book and is fast as it used just bit shifts and XORs. This should be very fast. The inputs are a 64 bit integer and output is a 64 bit integer. Some of the numbers can work on 32 bit, so this might be an advantage later on in ensuring there is no overflow.

How to combine hashes?

I understand about using XORs in terms of maximizing entropy and ensuring the combination doesn't exceed 64 bits. However the issue is that if I have series of nested loops over integers then with 2 loops I may get the following

A = 0, B = 1 and then I have A= 1, B = 0 and these will be equivalent so I get a collision i.e.

(Hash(A=0) XOR hash(B=1)) = (Hash(A=1) XOR hash(B=0))

One way around this might be to do the following:

Hash(A) + k*Hash(B) where k = [int], say = 5

What worries me here is that if I have to use a 64 bit representation for i and j, then I am likely at some-point to reach over flow as I might get j near the MaxInt and multiplying by k is going to result in exceeding MaxInt. However if I assume that j is 32 bit, if k is low then I am careful about removing a deductable from i, the MaxInt issue can be avoided. Also I shall have to watch that the sum of i and j doesn't exceed the Max int. I can see using pure XOR's would be useful but it is troubling because of the collision rate.

Using another algorithm here with an increased key length (block cipher) maybe the way forward as we can increase the key length with something like Blowfish to handle many 64 bit integers concatenated to form a key. What worries me with Blowfish is slow with regard to handling the key and this needs to be super quick.

Are there any recommendations out there for a better way to handle this problem?

In summary,

Have inputs:

A: 64 bits
B: 32 bits
C: 32 bits
D: 32 bits
E: 32 bits

The output should be an integer/double that is has the fewest repeats/collisions as described above. The output is not being used for anything other than generation of random numbers, but important that those random numbers are not correlated for the input.

The hash currently being tested is:

inline Ullong int64(Ullong u)
{

  Ullong v = u * 3935559000370003845LL + 2691343689449507681LL;
  v ^= v >> 21; v ^= v << 37; v ^= v >> 4;
  v *= 4768777513237032717LL;
  v ^= v << 20; v ^= v >> 41; v ^= v << 5;
  return v;
}
inline Uint int32(Ullong u)
{
  return (Uint)(int64(u) & 0xffffffff);
}
Returns hash of u as a double-precision floating value between 0. and 1.
{
  return 5.42101086242752217E-20 * int64(u);
}

I'd treat your input as one 192 bit input instead of thinking about 5 separate inputs.
If you don't need security, you can always reduce the number of rounds of cryptographic primitives. If you merely need statistically random output, 20% of the usual number of rounds should be fine with many hashes.

A few suggestions:

SipHash has good performance for short inputs. It's pretty easy to implement as well.

The default version of SipHash has 2 rounds for each 64 bits of the input and 4 rounds of finalization, called SipHash-2-4. Sacrificing security you could reduce that to SipHash-1-2 or even SipHash-1-1.

I expect a cost of 200 CPU cycles using SipHash-2-4 on your 192 bit input on a modern 64 bit CPU and 100 cycles with SipHash-1-2.

A round of SipHash:

v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32);
v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2;
v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0;
v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32);

SipHash treats the input as a sequence 64 bit words. You can use A, BC, DE as the three inputs. SipHash as specified applies some padding at the end, which increases the effective input size.

Since you have constant length inputs, you can simply leave out the padding, so the input is only 3 words instead of 4.
Rijndael-256 truncated to 64 bits. This should have great performance when used with AES-NI, but implementing it yourself will be hard.
MD5

While it's not secure against deliberate collisions, accidental collisions are as rare as one can expect. But it will be a bit slower than the alternatives.
A variant of Skein256

Skein is fast on 64 bit CPUs. Use the variant based on Threefish256, not the variant that uses Theefish512 and merely truncates since, the smaller block size doubles performance for short messages. Remove the finalization compression, it's only necessary for some security properties you don't need.

Then you can proceed to reduce the number of rounds to the smallest value that's still random enough for your purposes.

Personally I'd go with round reduced SipHash.


Homomorphic Encryption: how does the equality test on ciphertexts work? Let's suppose we have a asymmetric crypto-system $H$ which is homomorphic with respect to some function $F$.

Alice encrypts a message $m$ with her private key $e$ in the crypto-system $H$ and obtains the ciphertext $C = H(M)$
Alice sends $C$ to Bob
Bob computes $F$ over $C$ and obtains $C' = F(C)$
Bob sends $C'$ to Alice
Alice wants to check whether $C'$ is equal to some number $n$.

Let's suppose the decryption operation is costly, much more costly than the encryption. Can Alice check the equality by comparing the encryption of $n (H(n))$ and $C'$? Is that possible? With which homomorphic crypto-system(s)?

No, what you want to do is not possible, because encryption is randomized: if you were to encrypt the same message many times, you'd get many different ciphertexts.  Therefore, Alice can't just compare two ciphertexts to see if they are the same; the two ciphertexts will be different even if they decrypt to the same thing.


Use of the info parameter in Hybrid Public Key Encryption I dont understand the use of the info parameter, what does "to fold in identity information" mean? What is the security benefit?

All the algorithms also take an info parameter that can be used to influence the generation of keys (e.g., to fold in identity information) [...]

https://www.ietf.org/archive/id/draft-irtf-cfrg-hpke-07.html#name-hybrid-public-key-encryptio

I dont understand the use of the info parameter, what does "to fold in identity information" mean?

It essentially is context information; that is, protection so that the ciphertext can't be reused in a different context.
Here is a simple example; suppose I encrypt a message to you, and fgrieu intercepts it.  Now, what fgrieu could do is forward that message to you and claim it was from him (he can't read it, however because I wrote it, he knows it must be good :-)
If that's all the system did, he'd succeed; there is no way that the message wasn't from fgrieu.
However, if we were to routinely put the sender's name in the info field ("poncho" in this case), well, fgrieu's attack wouldn't work - the only way you can decrypt the email is to include "poncho" in the info field during decryption, and you know that the specific email came from me (or some other poncho).


Textbook RSA signature forgery when e=65537 Searching about RSA signature forgery I came across this question.
In the answer, it is stated that

for small to moderate $e$ (including $e=3$ and $e=2^{16}+1$, often used in practice), it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, it is easy to exhibit $m_1$ such that $m=m_0||m_1$ is the (non-modular) e-th power of a known integer $\sigma$ (compute $\sigma=⌈\sqrt[e]{m_0 2^{2e|N|}}⌉$ and $m_1 = \sigma^e − m_0 2^{2e|n|}$ of size $2e|N|$ bit); this $\sigma$ verifies as the signature for $m$; and $m$ prints the same as $m_0$ if $m_0$ is a zero-terminated C-string.

And actually I am having a hard time seeing how this can work with $e = 2^{16}+1$.
I would say that $\sigma$ will most probably be greater than the modulus $N$ in this case and the reduction will make everything fall apart.
Should there be a condition on

$m_1 = \sigma^e − m_0 2^{2e|n|}$ of size $2e|N|$ bit

and thus the forgery shall work for $e = 2^{16}+1$ but only with a very large modulus and not standard 1024-/2048-/4096-bit ones?
Can anyone shed some light on this?
Many thanks

The quoted answer is about a question with

To verify, the receiver checks that $\sigma^e \equiv m \pmod N$. (…)
Given $m \pmod N$ but an unknown $m$ (…)

Thus in the context it does not necessarily hold $0\le m<N$ as in the textbook RSA signature scheme of the original article. Rather, the question considers an hypothetical signature system where $m$ can be larger than $N$, and the message is signed as an appendix $\sigma\gets m^d\bmod N$, sent independently of the message.
The line of attack in the old answer is ridiculously complex for this setup. Here is a simpler attack that works for any $e$, and if the receiver checks $0\le\sigma<N$ in addition to the question's $\sigma^e \equiv m \pmod N$.
The attacker

chooses $\sigma$ freely in $[0,N)$, including $0$, and $1$ and $N-1$ which would simplify computation.
decides $m_0$, e.g. ending with an 0x00 byte acting as a $C$ string terminator
if $N$ is $n$-bit, decides that $m_1$ [to me appended to $m_0$ forming $m=m_0\mathbin\|m_1$ ] will be a bitstring of $b=8\lceil n/8\rceil$ bit
computes $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$.

I'll make an example with $N=$RSA-2048, $e=2^{16}+1$, $\sigma=3^{1291}$, message $m$ printing as the 15-byte A test message. in ASCII. Try it online!.

That said, the old answer was bogus, I fixed it; and the present question is right to state that with $0\le m<N$ (common in textbook RSA), an attack is possible for very small $e$ like $e=3$ but fails for $e=65537$ and usual size of $N$.


Suppose I capture encrypted data that I want to decrypt. Could I use a server farm to decrypt? For argument's sake, let's say that I'm a bad actor who produces malware. I've infected around 10,000 computers and smartphones with my malware, which runs in the background and can be used to make someone else's machine run calculations for me.

I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have an array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the workload of hacking this encrypted data to get through it in about 37 days? Why or why not?

I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have my array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the work load of hacking this encrypted data to get through it in about 37 days? Why or why not?

The answer depends entirely on what cryptanalytic problem you're hoping to solve.

Worst case: No.  For example, if you have to compute $2^{2^t} \bmod pq$ without knowing $p$ or $q$ (large random primes of sizes beyond the reach of ECM or NFS) where $t$ is very large, throwing more computers at it doesn't help (without a novel cryptanalytic breakthrough); only making the computer itself run faster—e.g., by designing an ASIC that computes it and running it at a high clock rate cooled with liquid nitrogen—will give you an answer faster.

This is because we don't know of any algorithm to compute $2^{2^t} \bmod pq$ other than starting with $x_0 = 2$ and then computing $x_i = {x_{i-1}}^2 \bmod pq$ sequentially $t$ times: except for vectorization attainable in the squaring operation, parallelism doesn't help.

Best case: Yes.  For example, if you have a password hash and you want to find a password among a large space that a single computer can search in 1000 years to search, and if you have 10 000 you can afford to run, then sure, you can divide the space into about 10 000 subspaces—for instance, all those passwords starting with aaa, aab, aac, etc.—and get a factor of 10 000 speedup by searching the subspaces independently.

Actually, if you have a collection of password hashes and you're content to find one of the passwords, you can get an even better speedup than a factor of 10 000 by a multi-target attack.

In general, you are limited by Amdahl's law: if the fraction of time spent a sequential program that can be parallelized is $P$, then the best possible speedup attainable by parallelism is a factor of $S = 1/(1 - P)$; that is, if it previously took time $T$, then with parallelism it can take at best time $T/S$.

For computing $2^{2^t} \bmod pq$, $P$ is essentially 0—the problem is, as far as we know, inherently sequential (short of factoring $pq$), so $1/(1 - P) = 1$ meaning that parallelism doesn't change the time at all.

For searching among keys $k$ to find one matching a given hash $H(k)$, $P$ is essentially 1—the problem is embarrassingly parallelizable, so $1/(1 - P) = \infty$, meaning that the time can be made arbitrarily small with parallelism.

Will this matter for serious cryptography?  No.
Serious cryptosystems are generally chosen so that the cost of an attack is higher than you can ever afford.  For example, you will never find one of any plausible number of AES-256 keys by brute force, because the cost will far exceed $2^{128}$ evaluations of AES, which you don't have the pocket change to pay for the energy to do, no matter how much you parallelize it.  The same goes for finding any Curve25519 private key by the best known discrete logarithm algorithms given all the Curve25519 public keys in the world.

Note that even with Amdahl's law, trading parallelism for time doesn't necessarily reduce cost: the energy to power 365 computers for a day is about the same as the energy to power one computer for a year.  In some cases—like parallel rainbow tables or distinguished points in a multi-target attack—it does reduce cost!  But you're not guaranteed a cost reduction just by parallelizing a computation.  In other cases—like Grover's algorithm on a (hypothetical) quantum computer—parallelizing the computation may raise the cost!


RSA 3072 is 65,536 more difficult to factor than 2048? If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric then 128-112= 16 and 2^16= 65,536. In that case wouldn't this make 3072 more future proof against quantum computers or does Shor's algorithm mean they will both be equally useless?

Also, how many bits of symmetric is RSA 4096 equal to?

If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric...

To be precise, a 2048 bit composite is estimated to take approximately $2^{112}$ operations using the Number Field Sieve algorithm; 3072 bit composites are estimated to take approximately $2^{128}$ operations using that same operation.

Since the Number Field Sieve (NFS) algorithm is the fastest factoring algorithm known on a classical computer for large general composites, this is taken as the work estimate

  In that case wouldn't this make 3072 more future proof against quantum computers or does Shor's algorithm mean they will both be equally useless?

Once we bring Quantum Computers and Shor's algorithm into the mix, that opens up another algorithm that is potentially more efficient than NFS.  And, for Shor's, 3072 bit integers isn't that much more difficult that 2048 bit ones.


How to construct a prg? Does the adversary know the random seed s? If he does not, isn't one possible construction simply the random seed itself? if the output needs to be bigger than random seed s cant I just add a hardcore bit to the random seed s? Also, regardless of the number of leading bits of the output that are revealed (even n-1 where n is length of output), will the output be computationally indistinguishable from a truly random string?

Does the adversary know the random seed s?

No. Let $G$ be an arbitrary PRG. Given the seed $s$ and a string $y$, it is trivial to check whether $y = G(s)$, thus the output of a PRG cannot be indistinguishable from random if the seed is known. Therefore, this definition would be uninstantiable and thus not useful.

  If he does not, isn't one possible construction simply the random seed itself?

A family of functions $G : \{0,1\}^{i(\lambda)} \to \{0,1\}^{o(\lambda)}$ needs to have two properties to be called a PRG.

It needs to be expanding, i.e. it must hold that $o(\lambda)>i(\lambda)$.
It must hold that or a uniformly chosen seed $s\gets\{0,1\}^{i(\lambda)}$, the value $G(s)$ is computationally indistinguishable from a uniformly chosen string $y \gets \{0,1\}^{o(\lambda)}$.

The PRG you are suggesting is the identity function, which does indeed fulfill property 2 from, above, but not property 1.

  if the output needs to be bigger than random seed s cant I just add a hardcore bit to the random seed s?

Well, the identity function does not have any hardcore predicates, so this does not work.

  Also, regardless of the number of leading bits of the output that are revealed (even n-1 where n is length of output), will the output be computationally indistinguishable from a truly random string?

By definition of a secure PRG, the entire output is computationally indistinguishable from a truly random string. So by a trivial reduction, so is any prefix of the output.


Multiparty Computation to calculate addition of shares without revealling individual shares I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their individual secrets.
Verification of the sum isn't important in this problem, as an error will cause an abort at a later point. The important issue is that they not get information about the numbers held by the other parties.
My other question is can this still be done / does it require a different solution if the addition is over a finite field?

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their individual secrets.

A simple application of arithmetic secret-sharing based secure multi-party computation ("arithmetic GMW") can do that.
The protocol for that goes as follows:

(One-Time Setup) Pick a prime $p$ that is guaranteed to be larger than the sum of all input values (you can safely overshoot the sume by a large margin here, e.g. pick a prime larger than $2^{96}$ for 64-bit inputs). This prime will be used to define the finite field we will work in. If you already have a preferred one, use it here. All arithmetic that follows will be carried out in this field.
Have every party $P_i$ choose $n-1$ random integers uniformly at random from the finite field. Call them $s_{i,j}$ and let $s_{i,n}=x_i-\sum_{j=1}^{n-1}s_{i,j}$. This creates an arithmetic $n$-out-of-$n$ sharing of $x_i$
Have every party $P_i$ send $s_{i,j}$ to $P_{j}$.
Have every party $P_i$ compute $r_i=\sum_{\ell=1}^{n}s_{\ell,i}$, that is, have them all sum up all the shares they receive.
Have every party $P_i$ broadcast their result $r_i$ to all other parties (or only to the one needing to know the sum).
Have every party with with all $r_j$ compute $\sigma=\sum_{j=1}^{n}r_j$. This value is the desired sum.


At what modulus size does the logjam reduction stage become impractical? Attacking a Diffie-Hellman exchange with logjam involves a massive precomputation effort once for the group, and then a comparatively simple reduction stage that is necessary to break each individual handshake. At what DH size does the reduction step, which isn't precomputed, become impractical?

For example, if the reduction stage on an 1024-bit DH group is possible to perform in real-time and the precomputation stage takes one year and \$10 million in hardware (estimates from the original logjam paper), how large would the DH group need to be for the reduction stage to demand the same cost of \$10 million in hardware and a single year (effectively negating the advantage of the precomputation)?

It is hard to put concrete costs to these steps at this scale, and the parameters can be tweaked to make the precomputation more expensive to render the individual log cheaper, but we can try to do it asymptotically to get an idea. The complexity of the precomputation step is
$$
L_p[1/3, 1.923] = \exp\left((1.923 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,,
$$
which in the case of a 1024-bit prime field—and assuming $o(1) = 0$—would amount to roughly $2^{86}$ operations$^1$.

The individual logarithm, on the other hand, has a smaller complexity of
$$
L_p[1/3, 1.232] = \exp\left((1.232 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,.
$$
Once again, if assuming $o(1) = 0$ we would need a roughly $2900$-bit prime for the individual log step to match the cost of the 1024-bit precomputation. The precomputation step for $2900$ bits would be beyond $2^{128}$ operations.

$^1$ This complexity figure often ignores memory and storage costs, which as numbers grow becomes more and more important, but this is a rough approximation anyway.


Is it possible to create a "proof-of-upload" system for BitTorrent ratio tracking? One issue that private BitTorrent trackers that track users' share ratios often run into is how to keep track of people who are screwing with their upload statistics, something known as "stat-hacking". As it is, because uploading and downloading is entirely peer-to-peer, there is no reliable way for the tracker to know purely through the BitTorrent protocol itself how much a client has uploaded or downloaded, except to trust the numbers that each client forwards. While somebody who uploads 1 petabyte in 2 days is an obvious impossibility, somebody simply augmenting their upload by 10% at a time could go unnoticed for a very long time.

Can we devise a cryptographic protocol to ensure that stats about upload and download are accurately reported to the tracker? In particular, it should be resistant to the following related attacks:

The uploader cannot claim empty upload credit - that is, to be able to report to the tracker that a piece was uploaded to a person, without having actually uploaded the piece to that person.
A downloader cannot repudiate their download - that is, the downloader cannot download a piece and then refuse to verify to the uploader that the piece was actually downloaded.

The current specification says that tracker GET requests specify the following variables:

uploaded=... (bytes)
downloaded=... (bytes)
left=... (bytes)

This is great for public trackers but is poorly designed for private trackers. The problem is that the numbers don't always add up as they should and this can be for several reasons. For example, you might notice two users uploaded variables increase by 100MB over a period of time, but the sum of downloaded reported by the swarm might only increase by 150MB over the same period. This could be because someone is cheating, or it could be that someone else has unexpectedly left the swarm without reporting their extra 50MB downloaded. Smaller accounting errors might also occur due to packet loss between peers.

The core problems:

Transfer statistics are only reported to the tracker in aggregate, so in the event of contradictions, it is difficult or impossible to tell exactly which peers were involved in some change of total uploaded or downloaded bytes. (Over time an algorithm might be used to guess cheating clients, but this is still not 100% accurate.)
Since private trackers typically reward users which keep a good upload:download ratio, this creates an incentive for a peer to:

Claim it has uploaded more data than it really has
Claim it has downloaded less data than it really has

To prevent this kind of cheating, the above two problems must be solved. First, it is necessary to introduce some form of detailed accounting. Second, it is necessary to change the way statistics are reported so that there is no longer any benefit or incentive to do the wrong thing.

NOTE: When I first provided this answer, I gave a non-cryptographic method which would only need a relatively small extension of the BitTorrent protocol. However, I then came up with a far superior method involving cryptography, which is now given here. I have moved the non-cryptographic method to another answer so as to not clutter this one.

Cryptographic solution:

The tracker and each peer should have a public/private key pair.
The torrent metadata should contain the tracker's public key, to be used to establish secure communication with the tracker. This ensures encryption and prevents MITM between the tracker and clients.
When a client connects to the tracker, it should inform the tracker of its public key fingerprint. If the tracker does not know the public key, it should request it from the client.
When the tracker responds with a (partial) list of peers, it should include the public key fingerprints for each of those peers.
The tracker should also provide the client with a signed token such as expiry:SIGNATURE(client_ip:client_port:client_public_key_fingerprint:expiry), signed with the tracker's private key. The expiry, a UTC UNIX timestamp perhaps 24 hours from then, ensures that peers can only participate in the swarm while they are welcome by the tracker (i.e. not banned).
As expiry times are important for this protocol to work, the client may need to record and use a clock offset if the time reported by the tracker is very different to its own.
When the client connects to a peer, it should first provide its public key fingerprint and signed token. After the peer verifies the token, they will exchange public keys as necessary, and use them to establish secure communication. This ensures encryption and prevents MITM between peers.
After successfully downloading a number of blocks from an uploading peer, the uploader will request a download chit from the client, to be signed with the downloader's private key. This chit is described in the next section, but to put it briefly, it is proof of bytes sent which the uploader may give to the tracker. A client which refuses to provide valid download chits will quickly be blocked by its peers.
When next connecting to the tracker, a client which has been uploading data should take each downloading peer's public key fingerprint and append the latest download chit(s) it has received from that peer since last time. The client should then sign this list of chits and send it to the tracker.
The tracker should process the chits in sequence, verifying signatures and skipping any chits with which are out-of-order or have very old timestamps (e.g. over 7 days old). The tracker can then log how much data has been downloaded and uploaded by each peer. The tracker should respond with a success code, after which the client should clear those chits from memory (but still keep track of the previously used chit timestamps for each peer).

In addition to much stronger security and full encryption, this system ensures it is impossible for an uploader to unilaterally cheat about how much data they have transferred. While not directly prevented, downloaders who try to cheat will quickly be blocked from participating in the swarm.

Download chit specification:

The chit should contain the following fields:

bytes_downloaded
utc_unix_timestamp
SIGNATURE(bytes_downloaded:utc_unix_timestamp:uploader_public_key:torrent_hash)

How often an uploader requests a download chit may depend on the time since the last chit was requested, when it next intends to contact the tracker, the size of the torrent, and the degree to which the uploader trusts the downloader.
The uploader may either request a chit with the same timestamp as the last chit sent to this uploader for this torrent, or a chit with a new (current) timestamp.
If the downloader has lost the timestamp it last used for that peer on that torrent, or if it never received data from that uploader on that torrent, it should just provide a new chit.
The byte value of the chit should be the number of bytes successfully downloaded from that uploader on that torrent since a chit with an earlier timestamp. If no chit with earlier timestamp is known, this should just be all the bytes successfully downloaded during that session.
Essentially, a chit with the same timestamp can be used to replace a previous chit of lower value, or in case the previous chit was lost during transfer. Since the tracker will only accept one chit with a given timestamp, the uploading peer should always keep the one with the highest byte value. Here's an example session from the perspective of an uploader:

 --> sends 2MB
 --> requests new download chit
<--  receives 2097152:1396945746:3653e8fa74765d18903b77435b87174be1271315
 --> sends 3MB
 --> requests same download chit
<--  receives 5242880:1396945746:81ffed9eca4325b277ba258e2e0 CORRUPTED
 --> requests same download chit
<--  receives 5242880:1396945746:81ffed9eca4325b277ba258e2e01ee20ad462a7b
 --> continues to send another 3MB to peer
 ==> meanwhile, sends download chit to tracker (with associated info)
<==  tracker says OK
 --> requests new download chit from peer
<--  receives 3145728:1396946262:b8b1a71da192440158adc307cab5befaafb2229e
     ...

Of course, a client may be both downloading and uploading from the same peer, so there may be download chits being transferred in both directions.
It is the responsibility of the uploader to request download chits.
It is the responsibility of the downloader to provide valid chits for past data transfers, going back up to at least one hour (or some standard amount of time). That is, a downloader should not be expected to provide download chits for data received more than that time ago, though well-behaved clients should honestly provide chits for older data if they are able.
The uploader should adjust its trust of a downloader's IP and public key based on the reception of valid download chits. If the level of trust drops too low, the uploader should refuse to upload to that peer for some amount of time (perhaps permanently). Note that it is possible for a non-cheating downloader to lose some block data during transfer or have a client crash or system failure and lose knowledge of bytes transferred, which is why some leniency is needed.

Mitigating tracker connection problems:

As a further benefit, this infrastructure could, with some small additions, allow partial decentralisation of the tracker's role. That is, the swarm could still function effectively and record most data transfers even if only some of the seeders could connect to the tracker some of the time:

If you are unable to connect to the tracker currently, but still have an unexpired token from that tracker, you could attempt to use a DHT to find another peer. Once you authenticate to that peer, they can send you a list of other peers they know (PEX). Usually PEX and DHT are disabled for private torrents, but in this case only the clients authorised by the tracker will be able to both know how to look up the DHT and successfully authenticate to a peer in the swarm. There are two options which could be used for the DHT:

A private tracker-specific DHT. Clients would need to keep records of possible bootstrap nodes specific to the tracker, and all communication would need to be authenticated with tracker-signed tokens.
The standard global BitTorrent DHT, but with a special process to find the right hash. The hash would be found by encrypting the regular torrent hash with a special key given by the tracker when you last connected. The key would be shared by all torrents on the tracker, but would be regularly updated (e.g. twice a day). To achieve this, when the client receives its authentication token from the tracker, the tracker should also send the client a list of the keys the client should use at which times during the token's lifetime. Peers found with this method should be encrypted with the same key, and all further communication would be done with tracker-signed tokens.

If the client cannot connect to the tracker to send a list of download chits, it could instead sign them and send them to another peer with token expiry indicating more recent tracker communication. To make this system more fair for the clients doing the work, there could be a standard fee for this, to be paid as a download chit. For example, if the list of accumulated download chits is 2 KB in length (including uploader public key fingerprint), then the client might need to append a chit worth 20 KB or 30 KB for the forwarding peer before signing. In order to cash in their chit, the forwarding peer would need to send the whole signed list to the tracker at any point in the future (or in turn forward the chits again to a third peer). (The formula for the fee would need to be considered carefully.)


How does an S-box introduce confusion I'm trying to find the logic for introducing the S-box, but having trouble understanding why. In a simple cipher, e.g.

c = pt xor key

I understand that I can easially find the key when choosing the plaintext myself

key = pt xor C

But I don't see why an S-box can help in this at all, given that the S-box is public.

C = S[pt xor key]

Because then I could just do

key = S^-1[pt xor C]

I understand by adding multiple rounds and keys, this gets harder, but what is the S-box giving, when we can just reverse it?

Even with two rounds and known plaintext you don't know the intermediate round inputs to the sbox since you don't know the round keys. This necessitates the brute forcing of the key bits, or other structural analysis. There's your confusion.


RSA Timing Attack on "Extra" Montgomery Reduction In "A practical implementation of the timing attack", the authors take advantage of a timing difference that stems from "extra reductions" that occur when multiplying numbers in the Montgomery form. After implementing a toy example of this attack, I thought I understood it. I created two sets of messages, one set containing messages $m$ where $m^3$ did not require an extra reduction ($M1$) and another set where $m^3$ did require an extra reduction ($M2$). I then augmented a square-and-multiply algorithm to take advantage of Montgomery multiplication while tracking the number of extra reductions that took place over the course of the exponentiation.

This quick experiment did appear to show that the set in which $m^3$ did not require an extra reduction ($M1$) on average would have less extra reductions than the other set. However, the difference in the two averages would be much larger than one. Most of the paper seems to suggest the timing attack they exploited relied on the timing difference a single extra reduction (e.g. section 7.1).

I believe I see an attack here, but its not the exact situation that the authors describe. It sounds like the authors are suggesting that a square-and-multiply exponentiation algorithm that relied on Montgomery multiplication would use $n$ extra reductions for messages in the set $M1$ and $n+1$ extra reductions for messages in the set $M2$ which does not make sense to me intuitively. Am I misunderstanding this attack?

Edit: After comparing my attack code with others, it turns out I understood the attack just fine and my experiment was different. The difference between my results and the results from the original paper was due to my selection of the Montgomery parameters. The value of $R$ used to put numbers in Montgomery form can have a major effect on the number of reductions required per multiplication.

Montgomery multiplication
Theorem (Montgomery, 1985). For any odd integer $N$ and any integer $0 \le T < N2^k$, one has: $$T 2^{-k} \equiv \frac{T + UN}{2^k} \pmod N$$ where $U = T N' \bmod 2^k$ and $N' =  -N^{-1} \bmod 2^k$.  Further, one has: $$\begin{cases} T+UN \propto 2^k\\ 0\le \frac{T + UN}{2^k} < 2N\end{cases}$$
The last 2 properties show that $R:=T2^{-k} \bmod{N}$ can be computed in two steps as:

$R \gets \frac{T+UN}{2^k}$
If $R \ge N$ then $R \gets R - N\qquad$ (extra subtraction)

Montgomery arithmetic represents an integer $0\le x <N$ as $\tilde{x} = x2^k \bmod N$.  It defines the Montgomery multiplication of two representatives $\tilde{x}$ and $\tilde{y}$ as $$\tilde{x} \otimes \tilde{y} := (\tilde{x}\cdot\tilde{y})2^{-k} \bmod N\tag{*}$$  Observe that letting $z= x\cdot y \bmod N$, one has $\tilde{z} \equiv (x\cdot y)2^k \equiv (\tilde{x}\cdot \tilde{y})2^{-k} \equiv \tilde{x} \otimes \tilde{y}\pmod N$.
Timing attack
Suppose that each Montgomery multiplication, cf. Eq. ($^*$), is done using the above two-step process.  We see that depending on $\tilde{x}$ and $\tilde{y}$, there may be an extra subtraction to get the result $\tilde{z}$ in the range $[0, N)$.
To fix ideas, suppose that the computation of $S = m^d \bmod N$ is carried out with the square-and-multiply algorithm.  The attack can easily be adapted to other exponentiation algorithm. The algorithm takes as input a message $m$ and private exponent $d = (d_{\ell-1}, \dots, d_0)_2$.

$R_0 \gets \tilde{1}$; $R_1 \gets \tilde{m}$
for $i=\ell-1$ downto $0$ do
$\quad R_0 \gets R_0 \otimes R_0$
$\quad$if $d_i = 1$ then $R_0 \gets R_0 \otimes R_1$
endfor
return $\tilde{R_0}$

The goal of the attacker is to recover the value of $d$.  Observe that the square-and-multiply algorithm processes the bits of $d$ from the left to the right.

Let $d = (d_{\ell-1}, \dots, d_0)_2$
At step $j$, the attacker

 already knows bits $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$
 guesses that next bit is $d_j=1$
 chooses $T$ random messages $m_1, \dots, m_T$ and computes $$X_t = m_t^{(d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1},1)_2} \bmod N\quad\text{for $1\le t \le T$}$$
 prepares two sets $$\mathcal{S}_0 = \{m_t \mid \text{subtraction}\}\quad\text{and}\quad \mathcal{S}_0 = \{m_t \mid \text{no subtraction}\}$$
plays all messages in set $\mathcal{S}_0$ and obtains the average running time $\tau(\mathcal{S}_0)$ for an exponentiation; does the same for $\mathcal{S}_1$ and obtains $\tau(\mathcal{S}_1)$
if $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \not\approx 0$ then $d_j=1$ (the guess was correct); if  $\tau(\mathcal{S}_0) - \tau(\mathcal{S}_1) \approx 0$ then $d_j=0$ (the guess was incorrect)

Iterate the attack to find $d_{j-1},\dots$

In the above description, set $\mathcal{S}_0$ denotes the set of messages such that there is an extra subtraction at iteration $i=j$ in Step 4 of the square-and-multiply algorithm (i.e., Montgomery multiplication $R_0 \otimes R_1$) for the computation of $X_t$; set $\mathcal{S}_0$ denotes the set of messages such that there is no extra subtraction at iteration $i=j$ for the computation of $X_t$.
Note that the attacker can evaluate the exponentiation $X_t$ by herself as she knows $d_{\ell-1}, d_{\ell-2}, \dots, d_{j+1}$.  Further, since $d_j$ is assumed to be $1$, the last operation of this exponentiation $X_t$ will be a Montgomery multiplication $R_0 \otimes R_1$ (i.e., Step 4 is executed at iteration $i=j$).
Correctness
If $d_j=1$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ will be greater than the average time for an exponentiation for messages in set $\mathcal{S}_1$ because there is always an extra subtraction for $\mathcal{S}_0$.
If $d_j=0$ then the average time for an exponentiation for messages in set $\mathcal{S}_0$ or in set $\mathcal{S}_1$ will be (roughly) the same because the sorting between the two sets looks like random. Remember that the attacker made the guess $d_j = 1$.


Can we decrypt in this order when the message is encrypted twice? If we encrypt a message twice with symmetric key $k_1$ first and then $k_2$ like $E_{k2}\{E_{k1}\{m\}\}$ , ideally we should decrypt with $k_2$ first and then $k_1$ but is it possible to decrypt with $k_1$ and then with $k_2$ ?  Using any of the AES Modes preferably ?

What you are asking appears to be 'is AES commutative'?
The short answer to which is no: encrypting with AES with key 1 then key 2 will not (generally) give the same output as encrypting with key 2 then key 1, which is what would be required for naive implementation.

However, there are modes in which AES can be used which would be commutative.
For example, if you run AES in counter mode, then after encrypting with key1 and key2 through counter mode, we would have that the final cipher text $c_i$ was:
$$c_i = m_i \oplus E_{k_1}(i) \oplus E_{k_2}(i)$$

Since XOR is commutative, we can write this as either

$$c_i = [m_i \oplus E_{k_1}(i)] \oplus E_{k_2}(i) = [m_i \oplus E_{k_2}(i)] \oplus E_{k_1}(i)$$

That is, whichever order you encrypt (and thus whichever order you decrypt) with respect to the two keys, you will reach the same ciphertext (and thus the same plaintext).

I haven't looked at it in detail, but I think the following article might be of use to you:
"Is there two key symetric commutative encryption function?".

Edit: Just to point out, if one was to use counter mode in this way, you would have to either make sure the counters are initialised at different values, or that the keys are different - otherwise your 'encryption' would become
$$c_i = m_i \oplus E_{k_1}(i) \oplus E_{k_1}(i) = m_i$$
Which is probably not a good thing...


Where did ChaCha20 and Salsa20 stream ciphers get their names from? This is not a question targeted at a specific crypto implementation, but a question out of curiosity. What's the reason for calling the stream ciphers ChaCha/Salsa?

I couldn't find any information about this on the Internet. Are those names somehow related to their internal structure, or just to make them stand out from all the other ciphers out there? For example, AES used to be called the Rijndael Cipher (derived from the names of its creators), before NIST standardized it.

idle speculation, my personal favourite! i always thought it was after the dance...

Salsa dance - see the video (Video demonstrating salsa dancing fundamentals) and jump to ~1min05sec in, the section titled: "side-side-quarter-turns", if you'd prefer to remain seated...

and from (https://en.wikipedia.org/wiki/Salsa20), The Salsa quarter-round function. Four parallel copies make a round.


Updating the seed key of a PRNG while maintaining initial entropy? Consider a seed key ($n$-bit long) is completely random and entropy of random variable is $n$ and PRNG is using deterministic algorithm and that that deterministic algorithm does not add any entropy to the random variable. Moreover, the PRNG length is $2^n-1$. So, how can we update the seed key of that PRNG to avoid repetitive output while maintaining the same initial entropy of the seed key?

It's a matter of periods in the sequence of numbers generated by the PRNG. If the output of the PRNG has a single period that is of length $2^n$, then you can avoid repetition by appropriately recording the section that you have already used. Thus if you start from $0$ and get the first time to $g_1$, the next time you start from $g_1$ and get to $g_2$, etc. until you have used up the entire period (keep a count of the numbers generated in order to detect that). PRNGs that generate numbers in $[0, 2^{n-1}]$ may not necessarily have the maximal period length of $2^n$. One special kind of PRNGs that have the maximal period length are based on the so-called permutation polynomials mod $2^n$. I used it in one of my software (s13.zetaboards.com/Crypto/topic/7355166/1/), where a literature reference to permutation polynomials as well as a practical  implementation of PRNGs based on them are given.


Uncomputing projective coordinates I am having a hard time understanding how to convert from projective coordinates, back to affine.

I am trying to compute point addition for Edward curves. Say we have the following:
$$\begin{align}
x_i &= X_i/Z_i\\
y_i &= Y_i/Z_i\\
A &= Z_1*Z_2\\
B &= A^2\\
C &= X_1*X_2 \\
D &= Y_1*Y_2 \\
E &= d*C*D\\
F &= B-E\\
G &= B+E\\
X_3 &= A* F*((X_1+Y_1)*(X_2+Y_2)-C-D)\\
Y_3 &= A* G*(D-C)\\
Z_3 &= c* F*G\\
\end{align}$$

[Editor's note: equations match hyperelliptic.org's add-2007-bl]

Now after obtaining values for $X_3$ and $Y_3$, to get back to affine coordinates, would I have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$ ?

Yes, after obtaining values for $X_3$ and $Y_3$ (and $Z_3$), in order to get back to affine coordinates, one would have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$.

However, in most cryptographic applications, we're making point multiplication with a large multiplier, which requires many point additions, which can be carried entirely in projective coordinates. We get back to affine coordinates only at the end of that. Therefore, the field inversion required to get back to affine coordinates is performed once per point multiplication, and represents a low proportion of the computational cost.

Whatever the base field, one can use the extended Euclidean algorithm to compute $1/Z_3$; or better the half-extended version there, which is specialized for the inverse; or $1/Z_3={Z_3}^{p-2}$ where $p$ is the number of elements in the base field. For the base field $\mathbb Z_p$ with $p$ prime, there's also the half-extended binary GCD algorithm there.


Why do we need extra hashing if we could use simpler scheme? Lets say that we use init vector IV, key K and HMAC key H. Message is M.

Mode of operation is CBC !!!

We usually encrypt this way:

C = crypt(M,K,IV) #encrypted data
R = C + MAC(C)  # final result and + is for con cat

But we could just use:

R = len + crypt(M + H,K, IV)  # notice M + H

Is there something wrong with such a scheme? It looks much faster to me and requires like half the computation and complexity.

This scheme is totally insecure. If an attacker modifies any part of the ciphertext except the last block before the ciphertext corresponding to H, your scheme won't catch it.

CBC decryption of a block only depends on the ciphertext of the previous and current block.

(Based on Cbc decryption.png from Wikipedia)

The red parts are left totally unprotected by your MAC scheme. The green parts affect your MAC, but even on them there are some attacks.


Length of encryption password aes-256-cbc I'm encrypting a file with sensitive information with

cat secret | openssl aes-256-cbc -a -salt > secret.enc

I am choosing a random encryption password with openssl rand -base64 32 | head -c [password-length]

Is there any standard, how long it should be? Given the password length, how long would it take to crack and view the contents of the file?

I have read this article, but it seems it supposes that you use a password size of 256 bits.

Edit: I found this picture, which pretty much answers my question. Is it reliable?

https://www.inetsolution.com/blog/june-2012/complex-passwords-harder-to-crack,-but-it-may-not

AES supports three key lengths. They are 128, 192 and 256 bits long. You chose to use the 256 bit algorithm that operates in CBC mode. It's a correct choice.

Now all you need is:

key - 256 bits long
initialization vector - 128 bits long

You can generate them using the command I found here:

openssl enc -aes-256-cbc -k secret -P -md sha1

where the "secret" is your password.

I suggest not using a truly random key and IV, because you have to save them somewhere, and adversary can just read it from your hard drive. It's much better to use a long and complicated password that he has to read from a post-it-note glued to your monitor, and derive the key and IV from it.

As for security, let me put it this way. If I wanted to crack 256 bits long key and 128 bit long IV on my work laptop, I would probably be around a fifth of way done when the universe would collapse. It's much simpler to use rubber-hose cryptanalysis in this case.

EDIT:

Just for you to know you shouldn't use password as a key directly. You need to derive a key from a password. The command I pasted does exactly that. About the security of the password you already answered yourself. 9 characters is the absolute minimum (if there is at least one uppercase letter, one lowercase letter, one number and one symbol). But I strongly suggest using a passphrase instead of a password. They are vulnerable to dictionary hacking, but if you use enough words a dictionary hack also takes years to complete.

There are over a milion words in the English language.

If we use only lowercase letters in our four word passphrase, the dictionary hack has to do in the worst case $1000000^{4} = 10^{24}$ searches. In comparison, there are around 100 characters on the keyboard. A password of 12 of those characters will be cracked in less than $100^{12} = 10^{24}$ searches.

This mean that "singing retracted eleventh elephant" is an equivalent of a 12 character password, and also it's much easier to remember. And if we use a comma somewhere, uppercase letter, or use a word from a different language it gets much safer.


Unblind a RSA blinded signature I have blinded $m = 16$ with $r= 13$, $e = 7$ and $n = 209$.
This resulted in $m' = 464$, which led to a $s' = 8$.

Now, I want to unblind this $s'$ by using $s = s' \times r^{-1}$ but im stuck at filling in the $r^{-1}$?

So let's first recall how blinded RSA works:

Select primes $p=11$ and $q=19$, calculate the modulus $n=pq=209$, choose a public exponent $e=7$. Now calculate the signature exponent $d\equiv e^{-1} \pmod{(p-1)(q-1)}$ ($d=103, (p-1)(q-1)=180$).

Now let's go to the message-dependant processing:
A message $M$ is represented as the integer $m=16$ which is blinded by first choosing a random integer $r=13$ and then calculating $m'=m*r^e \bmod n$ ($m'=46$). Finally the signature operation is carried out using $s'\equiv(m')^d\equiv(m*r^e)^d\equiv m^d*r^{ed}\equiv s*r \pmod n$($s'=8$). Finally calculate $s\equiv s'*r^{-1} \pmod n$. For this you need $r^{-1} \bmod n$($r^{-1}=193$). This yields the signature $s=81$.


Any problems with this secure time synchronization scheme? I have a time authority and I want to securely set a client's time to this authority's time/date within a precision of $\delta$ seconds. The authority's public key is known to the client. This was my idea:

A client sends a request with a 128-bit randomly generated nonce to the authority, and starts a timer.
The server replies with $time\_data$ and $sign(time\_data || nonce)$. $time\_data$ is some representation of time with a high precision and constant length (for example 16 bytes).
The client waits until a response is received or until $2\delta$ seconds have passed.
The client stops the timer, having measured $\Delta t$ since it started, and verifies that ${\Delta t \over 2} < \delta$. Then it verifies the signature using the given time data and the latest sent nonce. If everything passes then it sets the time to $time\_data + {\Delta t \over 2}$. If not go back to step 1.

As far as I can see there is no attack on this scheme that allows any adversary to let the client accept a time that is not within $\delta$ seconds of the actual time of the authority. Am I missing something?

I'm also wondering if there's any way to improve precision above the minimum delay $\Delta t$ of the network without losing security of the synchronized time, similar to what NTP does with estimating network latency.

Yes, this is a perfectly secure solution.

The principle drawback is that the precision available is limited by the round-trip time to the trusted time server.  If the trusted time server is 50ms away (i.e., 100ms round-trip time), which is a plausible situation that might arise in real life, then you cannot synchronize the client's time to within a guaranteed precision of better than $\pm$ 50ms (or so).  If this is adequate for your purposes, then yes, this is a fine solution.  If this is not enough precision, then you have a harder problem, and I'm not sure whether there's anything you can do in the presence of an active adversary.

Despite what has been claimed in the comments, the nonce is essential to security (otherwise a man-in-the-middle could trivially break the protocol).  Keep the nonce.  Do not remove it.  I think you know all that already, just re-emphasizing it for clarity.


TLS: Is Integrity assured when using NULL cipher In specific implementation we're using TLS 1.0, open ssl 0.9.8 but i'm referring to RFC 5246.

For performance reasons, I'm being asked if we can use TLS without encryption.  The hope is that the perfomance cost of using TLS will be less.  The implementation will retain authentication and integrity of communication, but there will be no confidentiality.

The RFC does seem to say in Appendix C that where we see 'SHA' in a cipher suite we should understand HMAC-SHA1.  So I'd interpret the NULL_SHA in e,g, TLS_RSA_WITH_NULL_SHA as HMAC-SHA1 rather than a digest.  In Section 6.2.3.1 we see that even with a NULL cipher a mac can be calculated.  So in theory we can get integrity from TLS without encryption.

However, nobody seems to be using TLS this way, existing TLS tools (e.g. socat, openssl in default configurations) do not seem to want to negotiate null ciphers,

So my questions

Can TLS assure authentication and integrity with a NULL cipher ?  Is this a reasonable optimisation to make, it seems to hold water but i'm not confident..
What is this optimisation likely to be worth ?  The SHA must still be computed and HMAC'd even if AES-CBC is no longer calculated.  I'm not sure how SHA compares to AES, can someone estimate what % reduction in operations there will be to calculate TLSCiphertext ?  e.g could be we expect a 50% reduction in an SSL_write / SSL_read comapred to a TLS session with AES 256 encryption

Then some less important questions

the cipher suites in the RFC dont include a NULL cipher is the
NULL cipher  e.g. there's no DHE_RSA_NULL_SHA.  Openssl headers e.g. tls1.h does provide for a lot of cipher suites with NULL ciphers which dont figure in the RFC.  However, they dont get built into the configuration on my platform which may indicate this is not a normal things to use.  Similarly tools like socat dont seem to negotiate cipher suites with null ciphers..  So I'm wondering if interoperability wise this kind of optimisation is thin ice even if the eco-system is partly controlled.
There's a load of stuff that doesnt get defined in the RFC, like what the possible values are for SecurityParameters.mac_algorithm, validating the MAC on incoming message.  People implementing TLS have a more detailed standard or am i missing something ?

To answer your main question.
Yes, NULL ciphersuites do provide authenticity and integrity checks but not confidentiality for the TLS traffic.

There is still a specified key exchange algorithm (e.g. RSA) for the TLS handshake protocol. The client will generate a pre-master secret and encrypt it with the server's public key for server authentication.
The session key is then derived and the MAC keys are generated from it. Authentication of messages is provided by demostrating knowledge of the MAC keys.

However, the toolkit Openssl warns that NULL ciphersuites offer no encryption at all and are a security risk. They are disabled unless explicitly included.

RFC 4785 classifies them as authentication-only ciphersuites (with no encryption).
Not sure about the your other question.


What is gpg2 algo 1 and 8 concerning its signature-procedure? While signing a test-file, gpg2 creates a file test.sig which contains this:

$ gpg2 --list-packets --verbose < test.sig
# off=0 ctb=89 tag=2 hlen=3 plen=540
:signature packet: algo 1, keyid C109A1FD84E2C2E5
    version 4, created 1510595093, md5len 0, sigclass 0x00
    digest algo 8, begin of digest cd 94
    hashed subpkt 2 len 4 (sig created 2017-11-13)
    subpkt 16 len 8 (issuer key ID C109A1FD84E2C2E5)
    data: 6198169E372BE3023D812F6E7AB24E600C326D77D6F8E690CDE45027F402F20325DEA9FEE9D2E32E04F798F5DB8700F734D65972C150DDF2B8ADD823D00190A5C9722E39C699D45D237343C741D991B78476270D5C5FBD996F032671BCA20890B0B994B4997A500D3AFC8B7446EAE3FF4F66A32DF8ED8E0B7741E4DD17B15D265D19C13D7349CC09E1094381C2BAE20375454A3825C842CC1E968428ABB451AA1B26555F081CE9D3C3A4F0222F86BAD0597A61B2B2FC4846FF400F52D3C58C7E29B2379E6022FBF0FC4C539421F4445EA7C905ABD98380D1218D82EB1ABCB9756B4A5F45AC668499E1405C72BEB5D2BF4F732EF0129B4EFE90C4F4308C4C6B6883A1A44A4A03C355A1D50F8E6172BCEC5F3A0D95696A1481F02D98D68A4CB52DD70E24C3535E2BCEE1DCD4D39DCFD0185DB06CE7BDE45DF5A723FB309819C79F27FBE602C26443D5E68F73911233E71C62D03099CCEF94431B37E17197E45475849938BDD6486E91204D17FE2E56C20F2B083FF44F6B1F63E747B73AAC9E21AFB2C15BD345D3F79AAA6F058D6D1288136727390879509928D874DEA5E285C6952F74137173AC2454FAAC06AEE90F94EC812E449C8E5F09F3419A8BE6981CBF9FB5D4E2DD6424AC316A7EDAB3AE98B9BD8979BB85E97328E882803C8AA522630C4E19B583682BA9F0575DDE642BA2BA3B7FECBCFFEF99C95B2D322B7FFDC30D2D

I assume that algo 1 means RSA, but how can that be used to create data (which I suppose should be the signature) ? What is algo 8?

I assume that algo 1 means RSA

Correct. From RFC 4880:

9.1.  Public-Key Algorithms

      ID           Algorithm
      --           ---------
      1          - RSA (Encrypt or Sign) [HAC]
      2          - RSA Encrypt-Only [HAC]
      3          - RSA Sign-Only [HAC]
      16         - Elgamal (Encrypt-Only) [ELGAMAL] [HAC]
      17         - DSA (Digital Signature Algorithm) [FIPS186] [HAC]
      18         - Reserved for Elliptic Curve
      19         - Reserved for ECDSA
      20         - Reserved (formerly Elgamal Encrypt or Sign)
      21         - Reserved for Diffie-Hellman (X9.42,
                   as defined for IETF-S/MIME)
      100 to 110 - Private/Experimental algorithm

  What is algo 8?

It indicates that SHA-256 was used for computing the hash. Again, from the RFC:

9.4.  Hash Algorithms

      ID           Algorithm                             Text Name
      --           ---------                             ---------
      1          - MD5 [HAC]                             "MD5"
      2          - SHA-1 [FIPS180]                       "SHA1"
      3          - RIPE-MD/160 [HAC]                     "RIPEMD160"
      4          - Reserved
      5          - Reserved
      6          - Reserved
      7          - Reserved
      8          - SHA256 [FIPS180]                      "SHA256"
      9          - SHA384 [FIPS180]                      "SHA384"
      10         - SHA512 [FIPS180]                      "SHA512"
      11         - SHA224 [FIPS180]                      "SHA224"
      100 to 110 - Private/Experimental algorithm

You might want to try to get some practice in reading RFCs. It can be a bit overwhelming at first, but the information is all there - especially for the OpenPGP standard which is extensively documented.


How large should a Diffie-Hellman p be if the messages are encrypted? How large should the prime $p$ and generator $g$ values be in a Diffie-Hellman handshake if the messages are encrypted.

If the key that encrypted the Diffie-Hellman messages becomes compromised, then does that compromise the key generated using Diffie-Hellman?

How large should $p$ be if the Diffie-Hellman exchange is encrypted?  Well, that rather depends on:

How much do you trust the encryption key not to be recovered?
Why are you doing a Diffie-Hellman in the first place?

If you can trust that the encryption key will never be recovered by anyone other than the sender and the receiver, then it doesn't really matter how large of a Diffie-Hellman modulus you use.  On the other hand, you don't need to do Diffie-Hellman at all, you could have one side pick a random value, and send that, encrypted by the key that we trust.

However, if you can't assume that the encryption key may not be compromised, then it would appear that you would have the same requirements on the DH parameters that we have on unencrypted exchanges; which (with the current hardware and DLOG algorithms) is that $p$ be at least 1024 bits, and that $g$ has an order that's a prime at least 256 bits long.

BTW: you asked about the size of $g$; its actual size isn't important.  What's important is its order, that is, the smallest $x>0$ for which $g^x = 1 \bmod p$.  This order $x$ should be a large prime value.  Small values of $g$ can achieve this; in particular, if $(p-1)/2$ is also prime and $p = 7 \bmod 8$, then $g=2$ will always have a large prime order (and, in fact, in such a modulus, you can show that if someone can solve the computational DH problem with $g=2$, then they can solve it in that modulus for any value of $g$ with a polynomial number of queries).

Lastly, you mentioned that you were doing this for a password protocol.  If so, I would strongly urge you not to encrypt the DH value with a password-derived key, but instead use a protocol with PAKE properties (such as SRP or EKE.  One of the properties is that someone who passively watches the protocol messages can't learn anything about what password might be used.  In contrast, if you just encrypt a DH exchange with the password as the key, what someone might try is to decrypt your messages with his guess at a password, and see if the message makes sense.  Even if you don't include any protocol bits in the encrypted message for him to check, what he might try is to see if the decrypted DH value is within the group that you're using to do DH (and if it's not, he has just learned that his guess at a password is not it, and can be removed from his list).  The existing PAKE protocols avoid that sort of possibility.  In EKE, they actually do encrypt the DH value with a password derived key; they are just careful not to leak any information about the password when they do it.


Discrete logarithm modulo a smooth number I am solving the discrete logarithm problem modulo $N$. $N$ is a composite number, I found its factors — lots of small primes and two big primes ($> 2^{50}$).
Does the factorization of $N$ somehow help me? I think I could compute the logarithm modulo each prime and then combine it, but I do not know how to do this exactly. It seems similar to problems for the chinese remainder theorem, but I cannot find the way to do it.

Does the factorization of N somehow help me?

It sure does.

  I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it.

You're real close; you do recombine them using the Chinese Remainder Theorem; however the modulus you use aren't the prime factors, but one less (unless a prime factor is repeated; that gets handled slightly differently).

I suspect the easiest way to explain this might be to write up an example; suppose we have $N = p\cdot q\cdot r$, where $p$, $q$ and $r$ are the distinct prime factors, and we want to solve:

$$a = b^x \pmod{N}$$

So, what we do is to find the three values $y$, $z$ and $w$ with:

$$a = b^y \pmod{p}$$
$$a = b^z \pmod{q}$$
$$a = b^w \pmod{r}$$

and then use the CRT to find the $x$ with:

$$x = y \pmod{p-1}$$
$$x = z \pmod{q-1}$$
$$x = w \pmod{r-1}$$

We do it modulo $p-1$, and not modulo $p$, because $p-1$ is the order of the group $Z^*_p$

Note that there might not be any such $x$ (because $p-1$, $q-1$ and $r-1$ are not relatively prime); if that is the case, then original equation is unsolvable.

If there is a repeated factor (for sample, $p^k$ is a factor of $N$), you do the same, however when you use the CRT, you do that one modulo $p^{k-1}(p-1)$