Does secp256k1 have any known weaknesses? I am wondering whether there are any properties of the curve which would technically make it easier to attack than any other curves of 256 bits in size.

I have heard that being a Koblitz curve, it has a few bits weaker security than some other curves of the same size - I was wondering if anybody has a source for a proof (or sketch proof) of this fact if it is true, and for any other properties that may make the secp256k1 considered weaker.

EDIT: I have found this website http://safecurves.cr.yp.to/index.html which states that the curve does NOT satisfy all of the safety requirements for that website - however I am unable to understand the parameters under which it is considered not safe, and explanation on this would be nice too thanks :)

secp256k1 fails the following SafeCurves criteria, but it doesn't matter for Bitcoin's use of secp256k1:

CM field discriminant.
secp256k1 is a Koblitz curve that admits a fast endomorphism for speeding up scalar multiplications.  There is no particular vulnerability here: the same speedup you get in computing with secp256k1, an adversary gets in trying to break it, but that won't, in itself, render an infeasible attack feasible.  (This is what the ‘few bits weaker security’ refers to.)

SafeCurves conservatively rejects this because it is an additional structure that could be the foundation of future breakthroughs in cryptanalysis, but nobody has made that breakthrough and we have little reason to suspect it's going to happen sooner than any other unpredictable cryptanalytic breakthroughs.
Ladders.
secp256k1 does not admit the fast Montgomery ladder to compute $x$-restricted scalar multiplication in constant time; it does admit the much slower Brier–Joye ladder.

Of course, you can compute fast scalar multiplication in variable time, which exposes you to timing side-channel attacks.  This creates a conflict between fast implementations—everyone notices when things run slowly—and secure implementations—which nobody notices until their money is gone.  The SafeCurves criteria reject such conflicts that encourage performance or security, in favor of designs that encourage performance and security.

This is relevant mainly for applications doing Diffie–Hellman, but Bitcoin itself does not use secp256k1 for Diffie–Hellman, though Lightning does; Bitcoin itself uses secp256k1 only for ECDSA signatures.  (Conceivably, it would also be relevant for applications using exotic signature schemes like qDSA, but Bitcoin is not one of those.)
Completeness.
secp256k1 does not admit the fast complete Edwards formulas to compute elliptic curve addition in constant time; it does admit the much slower complete Weierstrass formulas to compute elliptic curve addition in constant time.

Of course, you can compute fast incomplete addition in variable time with conditionals, which exposes you to timing side-channel attacks; or you could compute fast incomplete addition in constant time with carefully chosen arithmetic that has the same effect as conditionals, which takes more effort to design and audit.  This creates a conflict between fast implementations, secure implementations, and easy implementations, which SafeCurves criteria avoid.

Fortunately, it seems that pretty much everyone who matters in the cryptocurrency world has recognized that this particular kind of security (as opposed to, e.g., economic security from equitable wealth distribution) is important, and now uses libsecp256k1 to very carefully compute secp256k1 curve arithmetic in constant time at a reasonable speed. So this poses more of a danger for the victims of novice implementors in novel scams; as long as you use libsecp256k1 and don't try to rewrite it at home, this doesn't pose a security problem.


Hash into elliptic curves for private set intersection Would it be insecure to hash a message $m$ to an elliptic curve point by multiplying it to some generator $G$ for the purpose of a private set intersection ?
$$
M = hash(m) * G
$$
I keep seeing references that hashing with $M = hash(m) * G$ might be dangerous :

How to Hash into Elliptic Curves, Thomas Icart

Deterministic Hashing to Elliptic and Hyperelliptic Curves, Mehdi Tibouchi

Efficient Indifferentiable Hashing into Ordinary Elliptic Curves, Thomas Icart

hash - Fast hashing into elliptic curve - Cryptography Stack Exchange

the discrete logarithm of $h(m)$ with respect to $G$ is known , which makes most protocols insecure.

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known :
$$
M_s = h(m) * s * G
$$
Private Set Intersection
In the case of a private set intersection Alice and Bob each have a secret key ($s_A$ and $s_B$) and lists of data. To see what data they have in common they encrypt their data twice (once with each secret key) and search for the matches. In this example Alice has the message $m_1$ and Bob the message $m_2$.

Alice computes $M_{1,A} = M_1 * s_A = h(m_1) * s_A * G $
Alice sends $M_{1,A}$ to Bob
Bob computes $M_{1,AB} = M_{1,A} * s_B$ and $M_{2,B} = M_2 * s_B$
Bob sends $M_{1, AB}$ and $M_{2, B}$ to Alice
Alice computes $M_{2, BA} = M_{2, B} * s_A$
If $M_{2, BA} = M_{1, AB}$ then $M_1 = M_2$

In summary we test if
$$
h(m1) * s_A * s_B * G = h(m2) * s_A * s_B * G
$$

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known :

That is correct; it is not known; however that is not sufficient; the relationship between $h(m_1) * s$ and $h(m_2) * s$ would be known (if you know $m_1, m_2$), and that breaks security (at least, within this protocol).
In this protocol, Bob computes (in step 3) $h(m_{1}) * s_A * s_B * G$ and $h(m_{2}) * s_B * G$, and sends them (in step 4) to Alice (and then Bob has no further interaction with Alice).
If Alice has a guess $m'_2$ of Bob's value, what she can do is compute $(h(m'_2) * h(m_1)^{-1}) * (h(m_{1}) * s_A * s_B * G)$ and $s_A * (h(m_{2}) * s_B * G)$; if these are the same, then her guess $m'_2$ is the same as Bob's $m_2$.  Alice can perform this computation with any number of $m'_2$ values, without any further interaction with Bob; allowing her to recover a guessable Bob's secret value after a single exchange.
This works because Alice is able to derive what her exchanged value would have been, had she started with a different secret to begin with.


Can I use asymmetric encryption for more powerful write-protection? I have a game that I am developing which uses a locally-stored internal database. It does not matter to me whether a user can read the file (which, to me, means I don't need a symmetric cipher), but I don't want it to be possible for a user to alter it without completely breaking the game (essentially, to make cheating more difficult). Obviously file permissions alone wouldn't protect against someone on an administrator account or with a rooted device.

My thought was to use an asymmetric cipher where, opposite how it usually goes, the decryption key is public and the encryption key is private. I would then distribute the already-encrypted database and the game could decrypt it. I believe that this would prevent alterations, because the user would have to be able to properly re-encrypt the altered file for the game to be able to read it (unless they also altered the game binaries), which they wouldn't be able to do.

However, I've done a bit of searching and I can't seem to find this method mentioned anywhere, so I don't know if it is a good idea or if I've overlooked something. Is this a good approach?

Also, I want to use SQLite. I know of SQLCipher, but that uses AES so obviously that wouldn't work for me (because it's symmetric and therefore the user could intercept the encryption key by obtaining the key which is used to decrypt). Are there any public-key SQLite encryption libraries?

What you describe is a digital signature, which works using methods very similar to the one you suggest. Examples include elgamal-signature and RSA signature schemes (the second of which I would recommend you read).

Digital signatures allow you to provide a public signature that 'proves' you provided the message. As the author, you would produce database $m$ and a signature $s=s(m)$ confirming it is what you wanted.  You then provide your program with an algorithm $V$, called a verifier.  The verifier tests whether $s$ is a valid signature for $m$. If the signing algorithm was deterministic, an example verifier could just recompute the signature.

As with all crypto code, be wary of implementing a signing algorithm yourself, since there are lots of subtle pitfalls you may hit, such as the RSA homomorphic property.


Removing "security by obscurity" from port knocking Every article about port knocking, for instance  https://wiki.archlinux.org/index.php/Port_Knocking , declares this method as security by obscurity.  Is the following enough to remove that title;

a scheme where a 2048 bit shared key is generated. Every 2 bytes of the key are chunked off to make a list of 128 port numbers (2048/8/2). These port numbers in order are then configured as the port knocking sequence.
the MAC address of the sender is also factored in (maybe as the first 6 bytes of the key)

Does this fix the "Security by obscurity" aspect of port knocking?

I understand that this is a sniffable method. Thanks for your feedback!

The essence of port knocking - namely, the concealment of a service behind a lightweight authenticator - does not categorically suffer from security through obscurity. It really depends on what the characteristics of the authenticator are. At one end of the spectrum, there is "open port 22 if a SYN packet is sent first to port 12345" (obscurity - even nmap becomes a legitimate port knocking client in this case), and at the other end of the spectrum is PK's big brother "Single Packet Authorization" (which can use 2048-bit GnuPG keys together with an HMAC for example). The fwknop SPA implementation can do the later: https://www.cipherdyne.org/fwknop/
(Disclaimer: I wrote fwknop, so I'm obviously biased, but I believe the point still stands.) You may find additional material in the fwknop tutorial useful: http://www.cipherdyne.org/fwknop/docs/fwknop-tutorial.html

Also, the best reference on Port Knocking and SPA is still Sebastien Jeanquier's thesis "An Analysis of Port Knocking and Single Packet Authorization": http://www.securitygeneration.com/wp-content/uploads/2010/05/An-Analysis-of-Port-Knocking-and-Single-Packet-Authorization-Sebastien-Jeanquier.pdf


Extractor for Oblivious Transfer Protocol In a paper that I have been reading (https://cs.nyu.edu/~ganesh/zk.pdf), in one of the proofs, this has been said:

  The simulator works as follows: It uses the OT simulator to extract the prover’s input $x_0$ to the OT.

How exactly does this work? There's nothing defined in the paper itself, and I couldn't find anything related to an extractor for an oblivious transfer protocol. (The paper also uses extractors for ZKPOK, but that has been defined)

The paper is about garbled-circuit-based ZK protocol, in which the verifier generates the garbled circuit, and the prover obtains the wire labels corresponding to his private input $x_0$ through COT (committed OT).

The simulation in your problem works by letting the simulator simulate the ideal functionality of COT, which is defined in Fig. 1 on page 4. Here the receiver is the prover. Now the prover needs to invoke the COT ideal functionality by sending $(choose,b_i)$ to the ideal functionality where $b_i\in \{0,1\}$ is the $i$-th bit in the prover's input $x_0$. Since this ideal functionality is simulated by the simulator, the simulator gets all $b_i$ thus "extracts" the prover's input $x_0$.


Generate ANF from SBox Given an SBox, how can I generate its component equations (in ANF)?
For example, let's say I have this SBox:

6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11

Then, the equations are:

$y_0 = x_1 \oplus x_0x_1 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_0x_2x_3 \oplus x_1x_2x_3$
$y_1 = 1 \oplus x_0 \oplus x_2 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_1x_3$
$y_2 = 1 \oplus x_0x_1 \oplus x_2 \oplus x_0x_2 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_2x_3 \oplus x_1x_2x_3$
$y_3 = x_0x_1 \oplus x_3 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_0x_2x_3$

The same question is asked in cs.stackexchange

This is useful to know in general.

Given the Sbox map, generate the truth tables for the bits of the map.
From the truth tables, obtain the algebraic normal form, via the Mobius transform.

So, given an $n-$bit truth table, say $$T=[f(x): x \in \mathbb{F}_2^n]$$

where $$x=(x_1,\ldots,x_n)$$ ranges over the vector space $\mathbb{F}_2^n$ in standard order, the function has an anf representation given by
$$
f(x)=\sum_{y \in \mathbb{F}_2^n} a_y \prod_{1\leq i\leq n~:~y_i=1} x_i
$$
which means the variable $x_i$ is included in the monomial product corresponding to the coefficient $a_y$ if and only if $i$ is in the support of the vector $y.$

So if we had $y=(y_1,y_2,y_3,y_4)=(1,0,1,0),$ for $n=4,$ the coefficient $a_y$ multiplies the monomial $x_1 x_3$.

The transform computes the coefficients $a_y$ by the sum
$$
a_y=\sum_{x\preccurlyeq y} f(x) ~(mod~2),
$$
where $x \preccurlyeq y$ means the support of $x$ is a subset of the support of $y.$

The complexity is $N \log N$ where $N=2^n,$ so this is a fast transform.


Continuous logarithms in cryptography Cryptographic procedures seem to almost exclusively use discrete logarithms rather than continuous logarithms. Hence, I assume there are good and sound reasons for this.

In essence, answers provided here:
Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?
 state that continuous logarithms, thus, non-discrete logarithms can be computationally fast, while for discrete logarithms no such algorithm is known.

Furthermore, continuous logs can pose the problem of mathematical precision in terms of rounding errors.

For any non-discrete logarithm problem such as:

$$v = \log_{b}e$$

solving for either an unknown base $b$ or an unknown exponent $e$ is trivial when $v$ is known.

So my question is, not considering rounding issues, for now, what about solving for $v$ in the equation above, however when both the base and exponent are unknown, with the base $b$ being prime and $e$ being a random integer greater than 1.

By uniqueness of factorisation, this problem is well defined. If $e$ is uniformly distributed as you suggest it must be uniformly distributed in some finite range, say in $(1,2^N)$. Rewrite the equation as
$$
v \log_2 b = \log_2 e.
$$
Note that the random variable $Z=\log_2 e$ is distributed in $(0,N]$ with a highly nonuniform distribution exponentially biased towards the high end, namely
$$
\mathbb{P}(Z\in (s-1,s)) \propto 2^{N-s+1}
$$
while the primes from which $b$ is drawn are distributed (by the prime number theorem) result in the distribution
$$
\mathbb{P}(W \in (f-1,f)) \propto
\frac{\log(f-1)}{\log f} 2^{N-f+1}
$$
where $W=\log_2 b.$ Note that $s,f$ are reals not integers.

One can set up a faster than brute force search algorithm given $v$ by first searching for $(f,s)$ pairs with $s=f/v$ starting with $f=N$ and decreasing $f$ while testing the nearest integer to $2^{f/v}$ for primality.

Rewriting the original equation $b^v=e$ as the approximation
$$
\left| \frac{1}{b}-\frac{e}{b^{v+1}}\right|<\frac{1}{2 b^{v+1}},
$$
a $v+1$ step continued fraction approximation will be enough to run, prior to primality testing the nearest integer to the approximation.


Is AES strictly speaking a SP network? Forgive me if this seems like a trivial question. I've read that AES is a SP network. However, when reading about P-boxes in SPNs they say that they simply shuffle bits around. In AES the ShiftRows step is definitely shuffling bits around, but MixColumns step is not a bit permutation. Does this make AES something more than a SP network, or can the definition of a P-box simply be stretched a bit?

I think Substitution-Permutation Network is kept for historical reasons. Nowadays, we call SPNs even if Permutation is replaced by a general linear layer. Of course, the AES linear layer (concretely, MixColumns) is not a bit-permutation.


Can an attacker recover the key if a Poly1305 collision is known? Suppose that messages $m_1$ and $m_2 \neq m_1$, both known to the attacker, are both MAC'd through Poly1305 with the same key.  By chance, these two messages hash to the same value.  The attacker knows that $\operatorname{Poly1305}(m_1) = \operatorname{Poly1305}(m_2)$ but not the values of the auth tags (e.g. if they were passed through Blake2 with a secret key).

What attacks can the attacker mount? Can the attacker recover the secret key?

What if Poly1305 is replaced by GHASH or VHASH?

Yes, the attacker can recover the key with high probability in the event of such a collision.  For example, in two-block messages $m_1 \mathbin\| m_2$ and $m'_1 \mathbin\| m'_2$, this means that $$m_1 r^2 + m_2 r = m'_1 r^2 + m'_2 r,$$ so the key $r$ is a root of the quadratic polynomial $$(m_1 - m'_1) r^2 + (m_2 - m'_2) r,$$ of which there are at most two possibilities, one of which is necessarily zero and the other of which you can probably find in your head by this point.*  The same goes for longer messages with more work and more roots to sift through.  Exactly the same analysis applies to GHASH, which like Poly1305 is a polynomial evaluation hash; similar analysis will tend to apply to other universal hash families.

But the nice thing about Poly1305—or any suitable choice of universal hash family—is that the probability of this event is negligible, well below $2^{-100}$, which is good news for the composition as a candidate PRF, and thus also as a candidate MAC.

In particular, suppose the PRF-distinguishing advantage of any adversary against $F$ is bounded by $\varepsilon_F$, and suppose the hash family $H$ (e.g., Poly1305, GHASH, etc.) has collision probability bounded by $\varepsilon_H$.  Then PRF-distinguishing advantage of any adversary making $q$ oracle queries against $m \mapsto F_k(H_r(m))$ is bounded by $\varepsilon_F + \binom{q}{2}\varepsilon_H$ (proof).

Thus this technique is a good way to build a long-input, short-output PRF out of a short-input, short-output PRF and a universal hash family.  This structure is used by, for example, AES-GCM-SIV.

* Strictly speaking, there may be more possible values of $r$ because the polynomial evaluation giving an integer representative in $\{0, 1, 2, \dots, 2^{130} - 2\}$ is further reduced mod $2^{128}$ to make the Poly1305 authenticator.  But this only multiplies the possibilities by a small number, at most 4.


Use large key size for RC4 to avoid RC4 bias I saw a question on StackOverflow where RC4 was initialized by a 1024 bit key (with 2048 the maximum key size, if I'm not mistaken).

Will such a large key size possibly solve any of the bias of the initial bits of the key stream produced by RC4? Does it increase security any other way - other than brute force?

Is there any reason for keys larger than 256 bits for a combined key + IV?

Will such a large key size possibly solve any of the bias of the initial bits of the key stream produced by RC4?

There is a bias in the RC4 output at small multiples of the key size; hence a 16 byte key will have biases at offsets 16, 32, 48, etc (with the bias rapidly growing smaller as the offset grows).  This bias happens less often with larger key sizes.

Other than that specific bias, no, increasing the key size doesn't help.

  Is there any reason for keys larger than 256 bits

Actually, I'm not sure if there's any reason to use RC4 at all...


Is Curve25519 vulnerable to private key exposure in the case of a bad RNG? I'm really excited by what I've learned of advancements in elliptic-curve cryptography. Curve25519 seems to be a great choice at this point in time, but if I recall correctly, some elliptic curve algorithms can be compromised during signature generation by a bad RNG: my understanding was that by a compromised RNG, the private key could be leaked.

From the documentation:

  Signatures are generated deterministically; key generation consumes new randomness but new signatures do not. This is not only a speed feature but also a security feature, directly relevant to the recent collapse of the Sony PlayStation 3 security system.

Granted that if your RNG is compromised, you're going to have a bad time in all regards, does Curve25519 suffer from this private key leak problem as well?

Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different.

If you are just using the output of the random number generator as a private key, Curve25519 (the encryption algorithm) will use that as the secret curve point. That means any structure in the output of the RNG might be visible. So whether it's theoretically exploitable depends on how broken the RNG is.

In contrast, in Ed25519 (the signature algorithm you linked to), the actual elliptic curve point is derived from the private key using a hash function. That means as long as there's enough entropy in the key that the attacker cannot guess it, there should be no visible structure to take advantage of, unless the hash function – SHA-512 – is also broken.

With Ed25519 it's about as good as it can get. The RNG is only used in key generation, signatures require no entropy and so aren't vulnerable. Even if the RNG was slightly biased, it should be hidden by the hash.


Any shortcut to compute the cipher text for AES applied $n$ times to initial message $m_0$? Or compute $n$ for given $m_0, m_n$? Knowing all AES parameters (including the key k) with

$AES(m_0,k)\rightarrow c_0$
$c_0\rightarrow m_1$
$AES(m_1,k)\rightarrow c_1$
$c_1\rightarrow m_2$
...
$AES(m_{n-1},k)\rightarrow c_{n-1}$
$c_{n-1}\rightarrow m_n$

Is there any (much) faster way to compute $m_n$? (instead of computing AES $n$ times)

Or compute $n$ for given $m_0$ and $m_n$?

No, there is no big shortcut possible in practice, as far as we know. One would be a major blow of AES.

A small speedup is pre-computing the subkeys, which saves a small constant factor (like 2) compared to doing that computation on the fly at each iteration. Also, the first and last subkeys can be grouped into one by XOR, saving one 128-bit XOR at each iteration. We could merge the subkeys involved in the AddRoundKey step with tables implementing the SubBytes step, essentially removing AddRoundKey, at the cost of more tables. With dedicated logic, we could bring the time $t$ an iteration takes to few nanoseconds.

IF we first reach $m_i=m_0$ for $i=l<n$, then we know that $m_n=m_{n\bmod l}$ and we have already computed that value. By keeping intermediary values of $m_i$ (say, at regular interval, doubling the interval when we exceed available memory), we can find $m_n$ with little more computations. However, that occurs with probability about $2^{-128}$ for each $l$ with $0<l\le2^{128}$ if we model AES as a random permutation, thus the probability that we can use this shortcut is $\max(1,(n-1)/2^{128})$.

For very large $n$, it is conceivable to parallelize the computation, obtaining the result in sizably less time than $n\;t$. But the expected effort would be in the order of $2^{128}$ AES computations, which is perhaps a million times more than what was wasted so far in bitcoin mining, thus impractically large.

Another thing that we can do, in theory: first reduce $n$ modulo the Least Common Multiple of all possible periods $l$, that is A003418$(2^{128})$. For example, we can state with certainty that for $n=(2^{128})!+42$, we have $m_n=m_{42}$, which is pretty easy to compute. However, any $n$ allowing that shortcut is too large to store as an explicit integer.


How does GRC password generator get 512 bit of secret data? I'm trying to understand how GRC password generator can get 512 bit of secret data while encrypting 128-bit of data.

The generator address is located here: https://www.grc.com/passwords.htm
See the "The Techie Details" section at the end of the webpage.

They wrote:

  The result of the combination of the 256-bit Rijndael/AES secret key,
  the unknowable (therefore secret) present value of the 128-bit
  monotonically incrementing counter, and the 128-bit secret
  Initialization Vector (IV) is 512-bits of secret data providing
  extremely high security for the generation of this page's "perfect
  passwords". No one is going to figure out what passwords you have just
  received.

Diagram they provide:

What I tried is

I made a new IV (128-bit):

Buffer([00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00])

A monolitic counter - what is actually encrypted (128-bit):

Buffer([00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 01])

An encryption Key (256-bit):
, 32 bytes)

Buffer([00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00])

They XOR the IV with the monolitic counter (or the last encryption result with the monolitic counter, if there is a last result).

They say it gives them 512-bit of secret data. But when I encrypt everything I get 16 bytes (128-bit) of data:

<Buffer ad 86 de 83 23 1c 32 03 a8 6a e3 3b 72 1e aa 9f>

How do they get 512 bit of "secret" data? And how they XOR 512bit of data with 128-bit from the monolitic counter?

And how they XOR 512bit of data with 128-bit from the monolitic counter?

He doesn't.  Look carefully at the algorithm you posted.  All XOR operations occur on 128 bit values.  The 256 bit entry is the key for a 256 bit AES implementation.  The SPDT switch starts off using the secret IV and then switches to running with a 128 bit counter.  The 512 bits comes from 512 = |IV| + |counter| + |key|. This is all a bit  nonsensical as he's putting in  512 bits of (alleged) entropy and only generating a password of 128 bits.  This is exactly what you've proved to yourself.
 Typically the AES-CTR-PRNG algorithm is as below (without any switches) and Steve's method is characteristically unusual.

  How do they get 512 bit of "secret" data?

Who knows?  It's probably calls to CryptGenRandom (Steve's a Windows man), but perhaps it's just hard coded somewhere. And in assembly only no doubt. Or it might come from his Ultra-High Entropy Pseudo-Random Number Generator based on Latin Squares. Another doozy.

  No one is going to figure out what passwords you have just received.

Reach for the salt.  This is clearly false.  Any SSL intercepting router along the line can decrypt and read the web traffic (on the fly).  And Steve knows too.  Perhaps the moral of this question is - do not use a web service to obtain your password or key from.  If you're really stuck for a key /password either use dice or just randomly hit keys on the keyboard.  That was good enough for top secret one time pads during WW2 so it should suffice for you.

You have actually asked the wrong question.  You should have asked who is Steve Gibson?  Google him and find out.  There are masses of articles.  I can't write any more without sacrificing my composure and professionalism.


PBKDF2-HMAC Collisions Trying to understand the well known property of these collisions when used with SHA1, SHA256, etc. where a given key is larger than the block size of the digest function. In these cases the smaller of the collisions will have a size of 20 characters for SHA1 and 32 for SHA256 (1/2 the hexadecimal digest length), so does this mean to brute force a PBKDF2-HMAC-SHA1 an attacker only needs to consider passphrases of 20 characters or less? And therefore 32 or less if using SHA256? Are longer passphrases effectively pointless?
Thanks.

"brute force a PBKDF2-HMAC-SHA1" is not about collisions (at least, if a single hash is targeted, or if there's salt at the input of the password hash). It's a preimage attack.
The hash output by SHA-1 is 160-bit. That's 20 bytes (not characters; these are different notions, and why we have character encodings). It can take $2^{160}$ values. The output of PBKDF2-HMAC-SHA-1 has a parameterizable size that can be smaller (by truncation) or larger (essentially by aggregating 20-byte results), but the parameter is often set to 20 bytes, and we'll assume that.

Does this mean to brute force a PBKDF2-HMAC-SHA-1 an attacker only needs to consider passphrases of 20 characters or less?

No. It implies that a random value the size of the hash has probability $2^{-160}$ to match a given hash. The practical consequence is that trying at random is hopeless.
Passwords are often restricted to a subset of ASCII with about 95 characters, thus there are about $2^{131.714}$ passwords of 20 such characters or less (most of them exactly 20-character). If PBKDF2 is parametrized to perform 1000 SHA-1 hashes per PBKDF2 (which is the lowest parametrization ever consider by its definition, and has become grossly insufficient), hashing half these passwords would require over $2^{140}$ hashes, that is over $2^{40}$ (a million million) times more than wasted so far by humanity bitcoin-mining. That's just not an option.
Password search typically does not try all possible passwords over more than few characters; commonly ≈6 among ≈70 characters (only very powerful attackers could target all combinations of 10 characters when there's even mild password/key stretching). What password search does is try passwords that people could plausibly choose, approximately in decreasing likelihood of being chosen.


what is the order for the brainpool twisted curves? Per What is the difference between regular and "twisted" ECC curves? I guess the brainpool twisted curves and the brainpool regular curves use the same point addition and point doubling algorithms.

Domain-parameters.pdf#page=15 mentions the parameters for the 160-bit regular curve and the 160-bit twisted curve. For the regular curve it has a $p$ parameter and for the twisted curve it has a $Z$ parameter. I assume the $Z$ parameter is the prime number you need to do the modulo of after every operation.

What about the order $q$? Is the order the same for both curves?

If the curves are the same thing then couldn't one just treat them as aliases of one another? Like when you're randomly selecting $k$, between [$1, n-1$] and then multiplying the base point by that then you'd get the same answer no matter which curve you used?

What about the order $q$? Is the order the same for both curves?

Yes. This can be verified with the following commands:

openssl ecparam -name brainpoolP192t1 -genkey -text -noout -param_enc explicit

openssl ecparam -name brainpoolP192r1 -genkey -text -noout -param_enc explicit

This can be additionally verified by opening up RFC5639, which lists $q$ for both the twisted and non-twisted curves and shows them to be the same.

  If the curves are the same thing then couldn't one just treat them as aliases of one another? Like when you're randomly selecting $k$, between [$1, n-1$] and then multiplying the base point by that then you'd get the same answer no matter which curve you used?

No. As demonstrated thusly:

# generate private keys
openssl ecparam -name brainpoolP192t1 -genkey -noout -out brainpoolP192t1.pem
openssl ecparam -name brainpoolP192r1 -genkey -noout -out brainpoolP192r1.pem

# generate public keys
openssl ec -in brainpoolP192t1.pem -pubout -out brainpoolP192t1.pub
openssl ec -in brainpoolP192r1.pem -pubout -out brainpoolP192r1.pub

# sign using brainpoolP192r1
openssl dgst -sha1 -sign brainpoolP192r1.pem file.txt > signature.bin

# verify using brainpoolP192t1
openssl dgst -sha1 -verify brainpoolP192t1.pub -signature signature.bin file.txt

$p$ is the same as is $q$ but $a$ and $b$ are different.


Why is this the inverse of a Enigma Machine rotor? I am learning about how the Enigma Machine works and I found this example of one letter being encrypted by an Enigma Machine. It shows the letter "G" going through three rotors and then it goes into the reflector, then back into the inverse rotors. This is where I get confused.

The rotors are

Rotor I:   BDFHJLCPRTXVZNYEIWGAKMUSQO
Rotor II:  AJDKSIRUXBLHWTMCQGZNPYFVOE
Rotor III: EKMFLGDQVZNTOWYHXUSPAIBRCJ
Reflector: ABCDEFGHIJKLMNOPQRSTUVWXYZ  # not sure if this matters
           YRUHQSLDPXNGOKMIEBFZCWVJAT

I would think that the inverse of the rotors would just be each rotor reversed like this.

Inversed Rotor I:   OQSUMKAGWIEYNZVXTRPCLJHFDB
Inversed Rotor II:  EOVFYPNZGQCMTWHLBXURISKDJA
Inversed Rotor III: JCRBIAPSUXHYWOTNZVQDGLFMKE

but on the example I linked to

Inversed Rotor I:   TAGBPCSDQEUFVNZHYIXJWLRKOM
Inversed Rotor II:  AJPCZWRLFBDKOTYUQGENHXMIVS
Inversed Rotor III: UWYGADFPVZBECKMTHXSLRINQOJ

I don't see any relation between the rotor and the inversed versions of them. So, is this example wrong, or am I missing something?

The example is using a shorthand notation for the rotors that somewhat obscures the way they actually work.  For example, the first rotor in your example, BDFHJLCPRTXVZNYEIWGAKMUSQO, actually applies the following permutation of the alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
BDFHJLCPRTXVZNYEIWGAKMUSQO

Applying this rotor in the reverse direction thus, obviously, gives the inverse permutation:

BDFHJLCPRTXVZNYEIWGAKMUSQO
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Now, the same inverse permutation can also be written equivalently as:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
TAGBPCSDQEUFVNZHYIXJWLRKOM

You can check that these are, indeed, the same permutation: both map A → T, B → A, C → G, and so on.  The only difference is the order in which the individual input/ouput letter pairs are listed: in the first version, they are sorted by the output letter, while in the second version they are sorted by the input letter.

Now, the page you're reading is using a shorthand notation where the permutations are always sorted by the input letter, and only the output letters are actually shown.  This gives a nice and compact notation, but it does make it a bit harder to e.g. see whether two permutations are actually inverses of each other.


What basic knowledge is required to understand SIKE? I'm interested in learning about Supersingular Isogeny based Key Encapsulation mechanism.
Currently, I only know all the basic knowledge about how standard Elliptic Curve Cryptography,  works, using Weierstrass equations. This includes the the mathematical group structure on how the Elliptic curve points are defined, and operations like point doubling and addition. I also learned how to implement it in C , with parameters of cryptographic size.
Since, SIKE is dependent on Elliptic curves, and mapping between curves, I'm guessing that my basic knowledge of how Classical Elliptic Curve Crypto works, would provide me (a beginner) some vantage point to begin understand how SIKE takes off from the ground up.
I realise, that the security of SIKE is not dependent on the classical Discrete Logarithm problem.
I cannot find online material, that presents SIKE and the mathematical basis required for it for a beginner.
Even, if that's not the case, I'm willing to learn the math required from the ground up.
Every, help will be greatly appreciated!
Thankyou, everyone in advance!

Craig Costello has tried writing precisely what you're interested in, see SIKE for Beginners. It refers to numerous other surveys for isogeny-based crypto which may be useful (lecture notes by De Feo, and surveys by Galbraith-Vercauteren and Smith).
Galbraith also has a book on the math behind crypto. Chapter 25 deals with isogenies, so may be useful for mathematical background (but does not discuss SIKE).


Is the Salsa20-GCM composition secure? AES-GCM seems to be used by everyone, but I have never seen even one post about Salsa20-GCM. Is it secure? Wikipedia mentions that GCM uses a block cipher, but also that it uses CTR mode.

I am seeking an authoritative citation that I can reference in my project documentation, but personal opinions and arguments are welcomed too.

As SOJPM says in their answer, the proofs for AES-GCM assumes that AES is a PRP. I can't believe that there is anywhere in the proof that using a PRF (possibly truncated) would break things -- but I haven't looked carefully for this. Depending on how the GCM proof is structured, (using/not using) the PRP/PRF switching lemma [1] may suffice, but I don't remember well enough to say for certain.

I think that the closest reference you will find is [2], which analyses the ChaCha20-Poly1305 construction in IETF protocols [3]. As both ChaCha20 and Salsa20 can be assumed to be a PRF, this change is not significant; similarly GMAC and Poly1305 are fundamentally the same (a MAC based on a polynomial-evaluation hash). However, the scheme in [1] is not precisely ChaCha20-GCM; unless you want to dive into the GCM proofs (either to check that a PRF is ok at every point, or that you can use/not use the PRP/PRF lemma) I think it is the closest analysed scheme that you will find.

[1] https://eprint.iacr.org/2004/331

[2] https://eprint.iacr.org/2014/613

[3] https://tools.ietf.org/html/draft-irtf-cfrg-chacha20-poly1305-10


ElGamal Generator g problem Having an ElGamal encryption scheme with p=19 which value can not be assigned to
g?

The answers were :  1,7,11,2

I think you can't assign value 1 to g.

We can choose a generator which is a primitive root. We can check that 1,7,11,12 are not primitive roots for p=19. So they cannot be chosen as a generator.Given any number we can check if it is a primitive root or not.
(https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number).


Can the lengths of HTTPS requests be used to deduce which public pages on a site are visited? I thought of this recently:

There are some websites which have many publicly accessible pages, some of which could be embarrassing despite being public (e.g. Wikipedia). The HTML for these pages also references other resources (other pages, images, Javascript, etc) whose sizes are also known to the attacker.

An attacker can observe the lengths and timing of requests made over an HTTPS connection. Given this, can an attacker reliably deduce which page a victim visits despite the connection being "secure"?

I know there is some message padding to integer multiples of a certain length; however, could the lengths of enough messages be combined to give a good guess as to which pages the victim visits? Also, has there been any work done on this or a similar attack?

Here's an example:

Website A has 3 public pages with the following sizes:

A1 100 bytes - embarrassing
A2 200 bytes
A3 100 bytes

Let's assume that A1 and A2 reference an external resource with size 300 bytes.

If an attacker observes a response with length 100, she knows the victim has requested either page A1 or A3. Then, if she observes a response of length 300, then she can deduce that the victim has visited page A1.

Yes, you can often learn a lot just from the length of encrypted data (more generally the segmentation pattern of an encrypted stream). All the attacks that I know about leverage the data-dependent effects of compression.
It sounds like your question covers both HTTP requests and responses. There are indeed attacks that target exactly this side-channel. See the discussion here:

CRIME attack: if the user's HTTP requests support compression (which is possible as a TLS option) then private cookie data can be stolen by causing the victim to make many HTTP requests that include attacker-controlled content, and then measuring the size of the resulting (compressed) requests.

BREACH attack: Similar but works on the HTTP response.

Regarding the length of HTTP responses, here is a proof of concept showing how the length of different images from Google Maps can be used as a "fingerprint" of what area you are browsing.
This one is probably the simplest example of this kind of attack, and closest to the simple fingerprinting thing you describe:

Vincent Berg: I can still see your actions on Google Maps over SSL

The same concepts generalize to encrypted streams. When the compression uses variable-bitrate encoding, it leads to different segmentation/burst timing patterns.

You can recover actual spoken text from an encrypted VoIP audio stream:

Andrew M. White, Austin R. Matthews, Kevin Z. Snow, Fabian Monrose: Phonotactic Reconstruction of Encrypted VoIP Conversations:
Hookt on fon-iks. IEEE S&P 2011

You can identify the movie being watched (e.g., over Netflix, Youtube, etc):

Roei Schuster, Vitaly Shmatikov, Eran Tromer: Beauty and the Burst: Remote Identification of Encrypted Video Streams. USENIX 2017
Andrew Reed, Michael Kranch: Identifying HTTPS-Protected Netflix Videos in Real-Time. CODASPY 2017


Is there a rule of thumb for ZK protocols? There's always a small chance for many zero knowledge protocols that the prover had a lot of luck to prove something to the verifier.

Take the Ali Baba cave as an example:

The prover has a 50% chance of guessing the side of the cave correctly. That's why the procedure has to be done multiple rounds for the probablility of the prover not knowing a secret becomes reasonably small.

In this example the probability of guessing something correctly is $2^{-n}$, where $n$ is the number of rounds.

My questions are:

Is there a rule of thumb for how small this probability has to be?
What's the value of this probability in today's ZK protocols?

As usual, choosing the security parameters represents a tradeoff between the security and the efficiency. Therefore, it also strongly depends on two things:

how crucial it is that no one breaks the security guarantee (if an adversary succeeds at "guessing correctly" the challenge, hence can break soundness, how dangerous is that? How strong is the incentive for an adversary to break the system? Could he e.g. become super-rich by succeeding at doing so?)
how widely deployed might the system become (will it be used a few times, or hundredth of thousands of time?)

A very rough rule of thumb in this case could be (note here that we are talking about a statistical success probability during a run of a protocol, things would be very different if this was instead a computational security level, e.g. the average number of operations needed to break a scheme):

When the system has initially a soundness $1/2$, and reaching a better soundness involves parallel repetition of the entire protocol:

If the system should be very efficient and does not protect extremely valuable resources (or alternatively, if the incentive to break the system is not huge), a basic choice could be to settle for a $2^{-40}$ success probability.
If the system protects very valuable goods, or if there is a very strong incentive to cheat, but getting good efficiency is also very important, settling for a $2^{-80}$ success probability should be fine.
If people using the system are paranoid, or achieving strong efficiency is not such a concern while security is of paramount importance, go for $2^{-128}$ success probability.
In all cases, divides the target success probability by the number of times the system might be used in its lifetime (or the number of tries an adversary can plausibly get). E.g. a widely deployed system can be expected to be used by, say, $2^{20}$ individuals a few times each, so divide the target success probability by at least $2^{20}$ (such that the initial number, before dividing, becomes the probability that someone eventually ends up breaking the security by chance during the lifetime of the system).

When the system has natively the possibility to use a larger challenge space (e.g. Schnorr proof):

in this case, dividing the success probability by $2^k$ often involves sending only $k$ more bits in the proof. When soundness is that cheap, there is no need not to settle for a completely safe security margin, without optimizing for a few bits - e.g. going for a $2^{-128}$ or $2^{-256}$ success probability looks reasonable.


Does anyone have a KAT for 3DES KO-2? Does any one have, or can refer to a Known-Answer-Test (KAT) for Triple DES Keying Option 2?

(Keying Option 2 means $C = DES_{k_1}(DES^{-1}_{k_2}(DES_{k_1}(P)))$ for encryption and $P = DES^{-1}_{k_1}(DES_{k_2}(DES^{-1}_{k_1}(C)))$ for decryption, where $k_1$ and $k_2$ are independent parts of the key bundle.)

I have developed an implementation of 3DES Keying Option 2 in a FOSS library called TurboPower Lockbox (or at SourceForge). I need some KAT vectors to validate my implementation. I've done a good search, but every 3DES KAT I have found has either been KO-1 or KO-3.


Modified ElGamal encryption (ElGamal encryption with messages in the exponent ) is implemented in a pairing friendly elliptic curve. Is it secure? In my scenario, I need to distinguish if the encrypted message is 0 or not. The message is encrypted by Elgamal encryption but with the message in the exponent. i.e. $(C,R)=(g^my^r,g^r)$ where $y$ is the public key. I wonder if my goal is just to distinguish if the plaintext is 0 or not, and the scheme is implemented in a paring friendly elliptic curve. In this case, I think I can use pairing to check if $e(C,g)=e(R,y)$, if the equation holds, then the plaintext is 0. A similar case, in helios voting protocol, the encrypted vote is either 0 or 1, if this voting scheme is implemented in a pairing friendly elliptic curve, I if it actually make the encryption non-sense?

Yes! Good observation! Although note that the original Helios paper by Ben Adida does not mention such implementation details, i.e., on which curve to instantiate the ElGamal encryption scheme.
Your observation basically stems from the fact that the decisonal Diffie-Hellman (DDH) assumption does not hold on pairing-friendly curves. On the other hand, one needs to assume the DDH assumption for the semantic security of the applied ElGamal encryption scheme. Therefore, the choice of the ElGamal encryption scheme implicitly implies that one needs to choose a suitable group, where the DDH assumption holds. If a pairing-friendly curve is chosen, then DDH does not hold, hence also the semantic security of the ElGamal encryption scheme is lost.


How to decrypt an RSA ciphertext given an oracle providing the lower 8 bits of decryptions? I have access to an oracle that can encrypt and partially decrypt a number with RSA-1024 algorithm.

For encryption:
\begin{equation}
C = M^e\bmod n
\end{equation}
But for decryption, result will be $\bmod256$:
\begin{equation}
\textit{partialM} = (C^d\bmod n)\bmod 256
\end{equation}
Also I know $e=65537$, and $d$ and $n$ will remain unchanged.
I want to know if it's possible for a given $C$ to find $M$.
If yes, how?

So this feels like a homework question, as such I"m not going to give you the full answer, but yes, yes you can.  https://en.wikipedia.org/wiki/Homomorphic_encryption#Unpadded_RSA
Is the best starting point I can give without giving away the barn, but essentially rsa is homomorphic, and you can exploit that and repeated calls to the oracle to do what you want.


Hardness of Short Interger Solution in lattices Short Integer Solution ($SIS_{n,m,q,\beta}$) is defined as

Given a matrix $A \in \mathbb{Z}_{q}^{n \times m}$, find a non-zero vector $x \in \mathbb{Z}^{m}$ such that $A \cdot x = 0\mod q$ and $||x|| \le \beta $.

In paper Trapdoors for hard lattices and new Cryptographic Constructions, SIS is proved to be hard by reducing standard worst-case lattice problem approx. SIVP to SIS i.e., if we solve a random instance of SIS, then any instance of approx. SIVP is solved.

In paper On the complexity of computing short Linearly Independent Vectors and Short Bases in a lattice, approx. SIVP is proved to be NP-COMPLETE.

By this, can we say Short Integer Solution (SIS) problem in lattices is NP-Complete?

No, we cannot say that Short Integer Solution ($SIS$) problem is NP-Complete.

The results from those two papers are not directly related like that, because on the first one, the reduction is from $SIVP_\sqrt{n}$ to $SIS$ while in the second paper, $SIVP_c$ is proven to be NP-Hard for any constant $c$.

Until now, there is no proof that $SIVP_\sqrt{n}$ is NP-Hard and, since it has been proven to be in the intersection of NP and coNP, researchers believe that it is not NP-Hard.


What is a fair exchange scheme? The Wikipedia entry Fair exchange has only two lines, and the only paper I can find describing such a protocol is extremely complicated.

Is this a new field in cryptology or can someone give an example of actual use or provide a simple implementation?

Fair exchange protocols aren't new by any means, but there is a lack of layman-friendly material out there, unfortunately. I think the high prevalence of theoretical cryptography in fair exchange protocols may be partially responsible for that.

At any rate, here is the basic idea behind a fair exchange protocol. Suppose you have two parties, Alice and Bob, who wish to trade (cryptographic) "items" somehow. However, you run into a problem: suppose Alice sends her item to Bob, but Bob then refuses to send his item to Alice. In that case, it is not a fair exchange: Bob got Alice's item, but Alice got nothing in return, the poor thing.

Fair exchange protocols seek to ensure that scenario never happens---either they both get each other's "item" or they both get nothing. If the "item" being exchanged fits certain criteria, then fair exchange protocols can be improved upon to have other nice properties, like no longer requiring a trusted third party or being able to detect a dishonest third party.

There are other questions on this site which go into more details about specific fair exchange situations, like

Is there a way to do fair exchange between two parties who don't trust each other?
Alice trusts Bob only when Bob trusts Alice

which both link to useful papers. Further, there are some really nice results in the Google results for fair exchange cryptography. Some of them are indeed quite technical in nature, but usually you can read the abstract and maybe the introduction without getting too involved in the mathematical specifics of the protocol in question. One link in particular stands out as being a layman-friendly explanation. The other links should give you some idea of what "items" are traded, often digital signatures. Fair Exchange in E-commerce gives a really nice overview of the field, especially in the first few pages, and also has friendly terminology definitions on page "11" (page 3 of the pdf), defining terms such as "optimistic" fair exchange schemes (which only require a trusted third party to intervene in the event of a cheating player).


does re-encrypting the same value with multiple keys reduce security I found myself wondering today, how much security is lost if you take a plaintext - assume that its content, including any metadata is unknown to an attacker, for example it may be random data - and encrypt it with multiple keys (not chained) and give all resulting ciphertexts to an attacker, how much higher is the probability of an attacker discovering the plaintext, vs only having a single ciphertext.

An example:

Take plaintext $P_1$ and encrypt it with $K_1$, and send the resulting ciphertext $C_1$ to attacker $A_1$.

In addition: take the same plaintext $P_1$ and, and encrypt it with $K_1$, giving $C_1$. Then take $P_1$ and encrypt it with $K_2$ giving $C_2$, then $K_n$ giving $C_n$ and send all $n$ ciphertexts to attacker $A_2$.

How much more likely is attacker $A_2$ to discover the value of $P_1$, than $A_1$?

Does re-encrypting the same value with multiple keys reduce security?

The answer is "it depends"; there are some attack models and encryption methods where the security is reduced, there are other cases where there appears to be no security reduction.

Let us go through some models where we actually see a security reduction:

Plaintext guessing attack and deterministic encryption

In this attack model, the attacker has a guess to the plaintext $P_{guess}$ and wants to confirm whether $P_1 \stackrel{?}{=} P_{guess}$.  What he can do is guess random keys $K_{guess}$ and compute $E_{K_{guess}}(P_{guess})$ and he if that appears in one of the ciphertexts he's been given.  If he happens to guess a key $K_i$, then ciphertext $C_i$ will match, and he will get confirmation that his guess is likely to be correct - that's because we assume that the encryption is deterministic and so if the keys and the plaintext match, the ciphertext will as well.  Obviously, using more keys means that there are more targets the attacker can stumble into.

Deterministic stream ciphers, and plaintext with known linear relations.

Here, we assume we don't know the plaintext, however we do know certain linear relations between the bits of the plaintext; for example, we may know that the parity of each byte is even.  We also assume that the cipher works by generating a keystream (as a function of the key), and then exclusive-or the keystream with the plaintext to form the ciphertext.

So, what the attacker can do is examine each ciphertext; by assuming that the linear relationships hold in the original plaintext, he can evaluate the corresponding linear functions on the keystream; in the example, he can compute the parity of each byte of the keystream.

Then, he can pick random keys, and generate the corresponding keystream (here, we assume that this is determanistic).  Then, he can compute the linear function of that keystream (in the example, the parity of each byte), and see if it matches one of the keystreams that correspond to the known ciphertexts.

Like the first example, having more targets makes it more likely that the attacker will guess the correct key.

(Also, if you think that the example of "parity of each byte is even" is contrived, a more realistic example is "the msbit of each byte is 0").

Deterministic RSA encryption

If the encrypt the exact same message (without padding, or using determanistic padding) to $n$ different keys, and $n \ge e$ (where $e$ is the common public exponent), then it's easy to recover the message.  This is typically used as an example why you need to add randomness to your RSA encryption, even if you don't care about plaintext guessing attacks.

The above are three examples where encrypting with multiple keys can reduce security; in other cases (such as CBC-mode encryption), there is no obvious way to use multiple ciphertexts.

Now, the obvious thing about all three examples are that they are deterministic encryption; it would appear to be wise to add randomness if you are encrypting with multiple keys.


Why are collision attacks important when talking about MAC schemes? I'm reading Ferguson, Schneier, and Kouno's Cryptography Engineering, and it has a section on MACs. It discusses different types of MACs, but it seems to claim that to acheive 128-bit level security, you need a 256-bit MAC due to the birthday attack.

Why is this the case? Why are collision attacks a concern in MACs? I think that to break a MAC, you need a preimage attack to guess the plaintext, or a second-preimage attack to forge messages. In these cases, the birthday attack is irrelevant since it only finds some random collision, which may not be relevant to the data stream being attacked.

What am I missing? It seems that in general 128-bit MACs are much more popular (GCM and CCM and all those fancy AEAD modes have 128-bit authentication tags); surely they can't have only 64 bits of security? Is Cryptography Engineering simply paranoid?

The attack outlined by Drlecter is valid for any deterministic MACs (that is: with the MAC a function of message and key) with an iterated structure and an $n$-bit state. It relies on internal state collisions, expected to occur after about $2^{n/2}$ messages (the birthday bound), that can allow forgery once discovered. I'll illustrate this in the case of CBC-MAC with a 64-bit block cipher (e.g. 3DES) operating on fixed-size 3-block messages (24-byte) with 8-byte MAC (the full block cipher width).

The adversary asks for the MAC of $2^{33}$ messages with random first two blocks and the last block fixed. It is expected that a collision occurs, and the adversary then has $(M_0||M_1||M_2)$ and $(M'_0||M'_1||M_2)$ having the same MAC, with $M_0\ne M'_0$. So far, this is not a break. But notice that, with certainty, the collision has occurred after the second block, and continued after the third.

Now, for any last block $M'_2$, $(M_0||M_1||M'_2)$ and $(M'_0||M'_1||M'_2)$ collide with certainty. That allows the adversary to predict the MAC of one of these messages by querying for the MAC of the other, which is a break.

Thus a deterministic MAC with $n$ bit internal state (and output, but in itself truncating the output does not help much), after $q$ queries with the same key, has become unsafe with odds about $q^2/2^{n+1}$, for $1\ll q\ll2^{n/2}$. E.g. after $2^{60}$ queries, HMAC-SHA1 has odds $2^{-41}$ to be vulnerable.

Note: This attack (or any generic attack with similar result that I am aware of) does NOT in general apply to iterated MACs with an $n$-bit output. E.g. HMAC-MD5 or CBC-MAC-AES truncated to $64$-bit are not awfully vulnerable to this attack; after $2^{40}$ queries odds that the attack works are $2^{-49}$.


Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group? I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If I know $\phi(n)$ I can calculate $p$ and $q$. I ask myself what is if I know $e$ and $d$ (and $m$ and $n$) with $m^{d \cdot e\ \bmod\ \phi(n)}\ \bmod\ n$. Is it possible to calculate $\phi$ (and then $p$ and $q$)?

The relationship between recovering the decryption exponent $d$ and factoring the RSA modulus $n=pq$ is a classical question in cryptography. There are three useful answers:

The first answer deals with a slightly different question but is useful to gain some insight into the problem. Assume that we given a bit more than $e$ and $d$, more precisely that someone gives up $\phi(n)$ [This is more because $e$ and $d$ only gives us a multiple of $\phi(n)$]. Then, we can compute $s=n+1-\phi(n)=p+q$. As a consequence, we know both the sum ($s$) and the product ($n$) of $p$ and $q$. Thus, $p$ and $q$ are the roots of $X^2-sX+n$.
EDIT I forgot to mention that if you are using safe primes and small public exponent such as $65537$, then by removing small factors of $ed-1$, you obtain $p'q'$. Since $\phi(n)=4p'q'$, you can thus use this direct method.
EDIT 2 For more details about this method, see the related question: Why is it important that phi(n) is kept a secret, in RSA?
The second answer is the classical one, it shows a probabilistic algorithm that factors $n$ given an arbitrary multiple of $\phi(n)$, such as $ed-1$. See http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect14-c.pdf for detailed examples. The basic idea is to rewrite $ed-1$ as $2^t O$, where $O$ is odd. Then take a random element $w$ modulo $n$. We know that $w^\phi{n}\equiv 1 \pmod{n}$, thus $(w^{O})^{2^t}\equiv 1 \pmod{n}$. Compute $w^O$, then (unless it is equal to $1$) square it repeateadly until you reach $1$. If the number $\ell$ that appears before $1$ is not $n-1$, you obtain a non trivial factor of $n$ as $gcd(n,\ell-1)$. If it does not work, try again with a different $w$.
EDIT 3: Additional information about this reduction. In fact, this attack is stronger than that: it still work if we are given a multiple $M$ of $lcm(p-1,q-1)$. Moreover, it even works when $M$ is a multiple of either $(p-1)$ or $(q-1)$.
The most recent answer is that the reduction can be made deterministic using Coppersmith's smooth root algorithm. This was showed by Jean-Sébastien Coron and Alexander May in http://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/springer_joc.pdf (see also http://www.iacr.org/archive/crypto2004/31520213/det.pdf). This solution puts a few additional restriction on $p$, $q$, $e$ and $d$. Namely, $p$ and $q$ must have the same bitsizes and $ed$ should be smaller than $n^2$. This last condition is true when $e$ and $d$ are reduced modulo $\phi{n}$ but may become false for a variant of RSA that would use values of $e$ and/or $d$ not fully reduced.


Is order of Correlation Immunity of AES S_box Zero? I am working on AES S_box and trying to find out its properties like Correlation Immunity, Balancedness, Algebraic Degree, ANF form etc.

These Papers 1, 2 give a nice definitions to above said terms.

Also this very famous paper by T. Siegenthaler proved a fundamental relation between the number of variables 'n', algebraic  degree 'd' and order of correlation immunity 'm' of a Boolean
function : $$m+d <= n$$

Moreover, if the function is balanced then $$m+ d <= n − 1$$

I used this python script to find the ANF form and the Algebraic Degree comes out to be 7 i.e d=7 and we know for AES S_box n equals to 8 and its balanced function.

So putting all this data in that formula gives m=0 i.e. order of correlation immunity be zero.

Is this the right Correlation Immunity? or I am doing something wrong. Those who have  worked in this field kindly help.

The Siegenthaler result is for boolean functions, i.e., $f:F_2^n\rightarrow F_2$, while you are considering vectorial boolean functions $$f:F_2^n\rightarrow F_2^n$$ so you can't apply it. The results in this area are quite technical. Some overview:

You could certainly compute resilience (hence correlation immmunity for AES Sbox) by using the definition that the resilience of a vectorial boolean function $$S:F_2^n\rightarrow F_2^n$$ is the minimum resilience of the boolean functions as $b$ ranges over the nonzero vectors in $F_2^n.$ So $$\min\{ \rho(b\cdot S(x)): b \in {F_2^n},b\neq \mathbf{0}\},$$ where $\rho(\cdot)$ denotes resilience of a boolean function. So you need to check $255$ boolean functions, since $n=8.$
There are some constructions in this area, I suggest you look at the draft of a chapter by Claude Carlet on vectorial boolean functions (especially the last section) available at his homepage. You may also find his chapter on boolean functions interesting, in terms of more basic definitions.

Edit: To clarify 1, let the output bits be $S_i(x)$ for $i=1,\ldots,8.$ Compute the correlation immunity of each nonzero bitwise linear combination of these functions, such as those of weight 1: $$S_1(x),S_2(x),\ldots,S_8(x),$$ weight 2:
$$S_1(x)+S_2(x),S_1(x)+S_3(x),\ldots,S_7(x)+S_8(x),$$
up to weight 8. This will give you 255 functions. The minimum correlation immunity of this collection of 255 functions is the correlation immunity of the AES Sbox.

Finally the correlation immunity of a boolean function is equal to the largest hamming weight $w$ for which all hadamard coefficients $\hat{f}(\lambda)$ for $\lambda$ with weight $1,2,\ldots,w$ are all zero.


Understanding Encryption length calculation and rounds I am trying to learn about password encryption by creating a simple password hashing algorithm, although many online articles did warn "Do not create your own algorithm".

I discovered that most of the encryption outputs are represented in bits instead of characters. Initially, I misunderstood this, how bits should be used instead of characters--resulting in my creation of an algorithm with a 1024-character output.

Why is encryption always represented in bits instead of characters? If I encrypt a color hexadecimal value (e.g. red with hex value ff0000), and at the end my output still contains value 0-9,a-f with 128 characters in total length, this will be represented as 512 bits since hexadecimal only uses 4 bits, as 512bits/4=128 characters. Have I understood this correctly?

Do the rounds in encryption mean the same thing as the number of iterations of my encryption process (e.g. transposition, mirroring, etc.)? And how should I determine the number of rounds that I should use to make my algorithm strong against attack?

Computers operate on bits and bytes internally. They do not operate on (hexadecimal) characters. Characters are for human consumption.

Hexadecimals use only 4 bits out of a possible 8 in each byte, assuming 8 bit ASCII or compatible encoding. To perform any calculation such as bit shifting, addition or modular multiplication, you'd first have to convert the characters to bits. So that's not something you would perform internally to your hash function. Only if you want to make your output compatible for human readable text do you need to convert to hexadecimals (or base 64 or any other encoding of binary in text).

A color consists of 3 bytes in the common RGB scheme. That they are represented as three concatenated hexadecimal bytes is again only for human consumption. If you look at the contents of a bitmap file (.bmp) then certainly the dots / pixels are not present as hexadecimal characters. They are bits and bytes.

A block cipher and secure hash (not password hash) uses a certain number of rounds to be secure. How many rounds depends on the complexity of the inner function; some algorithms have a lot of simple rounds and some have fewer complex rounds. You probably want to have at least some 30% of headroom against the best known attacks to your function (i.e. if 7 out of 10 rounds are broken then you'd consider your function secure, if 9 out of 10 are broken then you're living too close to the knife's edge).

Yes, the number of iterations is similar to the number of rounds in functionality. However, commonly each iteration in a password hash would already create a secure result if the input password has enough entropy. That is, you would at least not be able to reverse the function and gain information about the input. Instead, the number of iterations should be as large as possible so that an adversary has to perform a lot of work (the work factor) to brute force a large amount of password hashes.


What is ANSI X.923 padding standard? Wikipedia defines ANSI X.923 padding as follows:

  In ANSI X.923 bytes filled with zeros are padded and the last byte
  defines the padding boundaries or the number of padded bytes.

  Example: In the following example the block size is 8 bytes, and
  padding is required for 4 bytes (in hexadecimal format)

  ... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |

So far so good.

Java Bouncycastle provider supports X932Padding, but it does it differently; instead of filling the unused bytes with zeros it fills them with random bytes.

I've got interested and started to search for ANSI X.923 official standard in internet and did not find it; instead I've found ANSI X9.23 description, and it says The standard defines that any other added bytes, or pad characters, be random.

So Bouncycastle implementation follows ANSI X9.23.

The question is : does the ANSI X.923 standard as it is defined in Wikipedia really exist?

IBM described the exact padding with random bytes as in your message as ANSI X9.23.

ANSI X9.23 is a withdrawn standard called "X9.23-1988 (Financial Institution Encryption of Wholesale Financial Messages" from ASC X9 (Accredited Standards Committee X9) which is part of ANSI (American National Standards Institute).

It's very old, it may be that you could only order a paper version before it was withdrawn.

That means that:

the padding X.923 does not exist, it is just X9.23 with the dot at the wrong location;
the padding does exist and the Bouncy Castle padding generated during encryption is correct.

Bouncy Castle also allows you to not specify a random number generator in which case zero valued bytes are used instead. You can do this by not calling the init method, or by calling it with null instead of a SecureRandom instance. That's not an option that I see anywhere mentioned for this standard.

The X9.23 padding on Wikipedia is a relatively new addition by an author with just an IP address. My guess is that the author simply used the Bouncy Castle provider and specified "X923PADDING" which (incorrectly) doesn't call the init method and therefore generates zero bytes. And the name lacks the dot, of course.

Notes:

Obviously you should not use this padding for new protocols; in general you should try and avoid block cipher modes that require padding all together.
You should make sure that the padding byte has a value between 1 and the block size. Especially in languages with pointer arithmatic / unbounded arrays accepting values such as negative values for unpadding can be pretty dangerous.
Ciphertext should of course be authenticated before it is being deciphered and - where required - unpadded.


Have any PAKE extensions been added to TLS 1.3? In TLS 1.2, there was TLS-SRP (RFC 5054,) which provided a password-authenticated key exchange (PAKE) protocol for use with TLS. However, it apparently relied on handshake messages that have been removed from TLS 1.3 and, thus, is not applicable to TLS 1.3. TLS 1.3 does still support the PSK-DHE handshake, but it doesn't provide PAKE properties since it allows offline brute-force attacks. It appears that there was a proposal to add a PAKE extension for TLS 1.3 back in 2018, but the draft appears to have expired and I haven't seen why it was allowed to expire or if anything further came of it.
Has anything been done since then to add PAKE support to TLS 1.3? Are there any active proposals?

Has anything been done since then to add PAKE support to TLS 1.3? Are there any active proposals?

No, nothing has been done, and there are no active drafts.
One possible reason for this (I don't know if this is the reason; it sounds plausible to me) is that the TLS working group is waiting for the CFRG [1] to complete its study of PAKEs; the CFRG is mostly done; they have selected OPAQUE as the recommendation if you need an asymmetric PAKE (the server doesn't need to know, which fits how TLS would use it) [2], however just selecting the winner is not sufficient - they need to put together an RFC that explains exactly how to use it (and how to avoid various subtle pitfalls).
Once the CFRG has put together such an RFC, I would expect that a proposal to use it within TLS will be submitted (of course, you are welcome to submit such a proposal)
[1] The Crypto Forum Research Group; that's a group whose purpose is to make recommendations about cryptography to the various IETF working groups
[2] And the winner in the symmetric case would be CPACE; however that is less likely to be used in TLS, as it requires the server to have a copy of the password


Removing Padded Value in Decrypted Message How to remove padded value in Decrypted Message?

I am using AES Algorithm.

Let's take this as the decrypted message:

"abcdefghijklmn  "

There is a 2 space in that decrypted message which is equivalent to 0x00.
how can I removed that value? during decryption to show the exact message before it was encrypted.

I am using ECB Mode, I know that ECB mode is not secured, but I only want to know how to remove padded value in my decrypted message.

How you remove padding after decryption depends on how padding was added before encryption.

Typically, we design padding methods so that it is easy to figure out exactly how much padding was added; see This article for an overview.

From your question, it sounds like the encryptor is doing zero padding (that is, adding zero bytes until the next block boundary); if you can assume that the message will never end in a zero byte, then it is easy to remove.  If you can't make that assumption, it sounds like you may need to switch to another padding method; the one in RFC5652 is one common method.


what is the maximum size of the payload data when using ed25519 When using ed25519 what is the maximum size of the message/payload data?

From the specs:

  The Diffie-Hellman key exchange is then defined as follows: each party
  generates a random number 1 <= d < N (the private key), computes Q = d
  G (the public key). The parties exchange their public keys and compute
  the shared secret as Z = d Q_peer.

So once both parties have computed the shared secret, what is the maximum size of the message data that could be encrypted and therefore decrypted by the "secret"?

That depends really on which symmetric cipher and cipher mode is used. Basically, the strength provided by the secret is 128 bits, as indicated in the page you linked to.

Usually the secret is then converted into a key using a Key Derivation Function (KDF) or even into multiple keys, which will each have a security level of 128 bits (as long as the KDF is strong enough, but that's commonly the case).

After that it is up to the scheme used. Probably you don't want to go over $2^{128}$ blocks of encryption, but that's kind of nonsense in the first place.


Using public key cryptography with multiple recipients I have a message that I want to send to multiple recipients.
Can I encrypt the message separately with each of the recipient's public keys, then send the message thus encrypted to the respective recipient?
If an attacker obtains all the encrypted messages and knows that all of them have the same content but are encrypted with different keys, would that make the attack easier?
How about if the attacker manages to decrypt one of the messages, or obtains the plaintext by other means, would that compromise any of the other private keys?
Is there a form of asymmetric encryption that would work better than others in this scenario?

You did not specify the details of your method to analyze, however, the usual method is not purely based on the encryption with public-key cryptography, rather a hybrid cryptosystem, where the symmetric key is transferred with the public key cryptography and the key is used in the symmetric key cryptography.
With RSA
Let's say we want to send the message $m$ to $n$ parties each have $pub_i$ and $prv_i$ keys (use RSA with OAEP).
Now, generate a uniform random AES256 key $k$ and encrypt the message with AES-GCM,
$$(c,tag) = \operatorname{AES-GCM-Enc}(k,IV,m)$$
Now encrypt the $k$ for each person $$\bar k = \operatorname{RSA-OAEP-Enc}(pub_i,k)$$ and send each user $(\bar k, c, IV, tag)$. Now each user can individually get the key $k$ and decrypt the message.
The weakness is that an observer can see that you have sent the same message to all. To mitigate this, if necessary, use a different IVs per user. Note that this will increase the encryption time.
Other candidates
RSA-KEM
The above was direct usage of the RSA. Normally one can go for RSA-KEM (in short below, full detail here)

Generate a random $r \in [1,n-1]$ and use HKDF to derive a key.
Encrypt the message with AES-GCM by using the derived key
send the $r$ with textbook-RSA together with the $(c,tag)$

NaCL
NaCl has existing solutions for this; the authenticated encryption
Integrated Encryption Scheme (IES)
Integrated Encryption Scheme (IES) has multiplicative and an elliptic curve version, too.
In the Elliptic curve version ECIES, first, there are agreements on

the elliptic curve parameters $(q,n,b,G,n,h)$
Key Derivation Function (KDF)
Message authentication code like HMAC-SHA256 ( or directly use AES-GCM or ChaCha20-Poly1305)
each user has $x_i$ as private key and the public key $P_i = [x_i]G$

Then the message can be sent as

The sender generates a random integer $r \in [1,n-1]$ and set $R = [r]G$

Let $P=(x(P),y(P)) = [r]P_i$ and make sure that $P \neq \mathcal{O}$

Let $S = x(P)$

Derive the encryption AES256 key$$k = \operatorname{HKDF}(S)$$

Encrypt with AES-GCM or ChaCha20Poly1305.
$$(c,tag) = \operatorname{AES-GCM-Enc}(k,IV,m)$$

Send $(R,c,IV,tag)$

On the decryption side

Calculate $P = [x_i]R$ due to $$P = [x_i]R=[x_i r]G =[r x_i] G = [r]P_i $$ as prepared
Let $S = x(P)$
Derive the encryption AES256 key$$k = \operatorname{HKDF}(S)$$
Decrypt $$(m,\perp) = \operatorname{AES-GCM-Dec}(k,IV,c,tag)$$Never accept an incorrect tag, halt $(\perp)$?

WhatsApp
WhatsApp uses a similar idea.

Note: If possible, I would go for the NaCL


Using AWS KMS to manage secret keys For my use case, I need to maintain a secret key with the client to generate and verify HMAC for requests.

We can have multiple clients and we can not make assumptions such as a client's server will always reside in EC2.

I am considering envelop encryption for our secret keys using AWS KMS.
I have the following concerns:

Secret key will be transferred over the wire as plain text to be encrypted and after decryption by KMS, is this a safe practice?
We will need to store AWS credentials in plain text on servers (our server as well as client's) to call KMS, how is it better than storing the secret key itself? (Given that we could share the secret key once, say in a registration successful email)

AWS is complicated, and most of the details are not in scope for this site.

  We will need to store AWS credentials in plain text on servers (our server as well as client's) to call KMS, how is it better than storing the secret key itself? (Given that we could share the secret key once, say in a registration successful email)

You said clients might not be on EC2, which I interpret to imply that your servers will be.  AWS is designed so that EC2 instances can authenticate with services like KMS without you having to store secrets in them—rather, EC2 can issue ephemeral credentials to your instances when it creates them.

That doesn't however by itself solve how to make sure that your EC2 instances and your clients will be able to share a secret key, or whether that's a good idea in the first place for your problem space. I think you need to find an AWS consultant and possibly a cryptographic engineer.

  Secret key will be transferred over the wire as plain text to be encrypted and after decryption by KMS, is this a safe practice?

The connection to KMS is encrypted.


Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey Edit

Does the state register (the LFSR) always have to remain with 16 bits (I'm assuming yes).

If so, are we shifting the register right by one (lfsr>>1) and inserting the output bit onto the left-most bit (lfsr>>1 | bit<<15) which allows us to wraparound within the same 16-bit address space.

So with this in mind, how does one generate the continuous keystream given:

seed: 1100101001110101

taps: 3, 12, 14, 15

Assuming you are given the following information:

Seed: 1100101001110101

Key Fragment: 000100011110101100001101101111101

And the following ciphertext/encrypted stream: 10101011000000010010110011001100101000010101010101010111101111110111010000010011

I am seemingly unable to decrypt the entire text into some ASCII values (UTF-8 decoded). I initially wrote a Berlekamp-Massey implementation and an online calculator to grab the tap positions of the above key fragment, which returned the following polynomial:

$$x^{15} + x^{14}+x^{12}+x^{3}+1$$

Fibonacci LFSR implemented in Rust:

fn next(&mut self) -> Option<(u16, u16)> {
    self.bit = ((self.lfsr >> self.taps[0]) ^ (self.lfsr >> self.taps[1]) ^
                (self.lfsr >> self.taps[2]) ^ (self.lfsr >> self.taps[3])) & 1;

    self.lfsr = (self.lfsr >> 1) | (self.bit << 15);

    if self.lfsr != self.seed {
        Some((self.bit, self.lfsr))
    } else {
        None
    }
}

The key fragment never appears in the generated key stream, indicating something probably went wrong.
The decrypted cipher doesn't map to ASCII values, just cryptic UTF-8 symbols.

The Berlekamp-Massey implementation is based off of the following whitepaper - https://www.osti.gov/servlets/purl/12658

And the full code can be found here - https://gist.github.com/JuxhinDB/ef8dac92b5af5de2e365d326b8dbc410

TL;DR:
If you have a similar question, then use the online Berlakamp-Massey algorithm to get the minimal polynomial by providing the given keystream, then get the C++ code from github and then replace your tap positions, seed, and ciphertext and then compile and run.

The answer is attraction
How to get it
What is given: We have given the following information;

Key fragment
seed
ciphertext

Attack idea: The key fragment is given to calculate the shortest LFSR that outputs the given key fragment. Once you get the taps, initialize the LFSR with the seed then decrypt the ciphertext stream.
Steps in details;

Use Berlakamp-Massay algorithm to find a shortest LFSR (need not to be unique). An online version is used.

The output is given as $x^{16} + x^{12} + x^3 + x^1 + 1$

As noted on the online site the size of the LFSR is 16 and the tap positions are
0,1,3,12
  xxxxxxxxxxxxxxxx <-|
  || |       |       |
  ++-+-------+-------|
  01 3       12

Initialize the LSFR of size 16 with the seed and this tap positions. Run the LFSR and get the keystream;
11001010011101010101100010111110110000000011011000100011110101100001101101111101

X-or the keystream with the ciphertext

Convert the plaintext to ASCII to get
attraction

note 1: if you x-or the 16-bit seed with the ciphertext you will get the at. This has a very low probability to contain two letters from the English Alphabet. If we assume that only small English letters are used then the probability is $26^2/256^2 \approx 1.031\%$. This was the actual clue int the question. And, normally, real stream ciphers don't start immediately form the initialization. They step for a certain amount from the beginning.
note 2: A sample C++ code can be found in the github.


Advanced Composition (Differential Privacy) I have a problem understanding the proof of the corollary of Advanced Composition
Theorem Advanced Composition:
For all $\varepsilon,\delta,\delta' \geq 0$ the class of $(\varepsilon,\delta)$-differentially private mechanisms satisfies $(\varepsilon',k\delta+\delta')$-differential privacy under $k $-fold adaptive composition for:
\begin{equation*}
    \varepsilon'= \sqrt{2k\ln(1/\delta')}\varepsilon+k\varepsilon(e^\varepsilon-1)
\end{equation*}
Corollary
Given target privacy parameters $0<\varepsilon'<1$ and $\delta'>0$, to ensure $(\varepsilon',k\delta+\delta')$ cumulative privacy loss over $k$ mechanisms, it suffices that each mechanism is $(\varepsilon,\delta)$-differentially private, where
\begin{equation*}
    \varepsilon=\frac{\varepsilon'}{2\sqrt{2k \ ln(1/\delta')}}
\end{equation*}
Proof:
The theorem of Advanced Composition tells us the composition will be $(\varepsilon^*,k\delta+\delta')$ for all $\delta'$, where $\varepsilon^*=\sqrt{2k \ln(1/\delta')}\cdot \varepsilon+k\varepsilon^2$. When $\varepsilon'<1$ we have that $\varepsilon^*<\varepsilon'$.

I don't see clearly the connections between the proof and the corollary. I tried using the quadratic formula. I think it, and don't see how they get the $\varepsilon$ from the corollary.

Turning arcynia's comment into an answer so this question can be marked as fixed: « The very next paragraph of the book explains this: "Note that the above corollary gives a rough guide for how to set $\varepsilon$ to get desired privacy parameters under composition. When one cares about optimizing constants (which one does when dealing with actual implementations), $\varepsilon$ can be set more tightly by appealing directly to the composition theorem." That is to say, this value for epsilon does not represent anywhere near a calculated optimal value, but just a fairly good rough guide. »


Can tweaking a cipher have the same or similar effect as changing the key? If we encrypt a message $m$ with (say) $AES$ and key $k$ we get ciphertext $c$.
And if we encrypt the same message $m$ but with $k^*$ we get ciphertext $c^*$:

1) $AES[E_k(m)] = c$ and $AES[E_{k^*}(m)] = c^*$

But what if we were to tweak $AES$ insted of changing the key? For example, a simple tweak might be to change the ShiftRow from right shifts of $0,1,2,3$ to (say) right shifts of $1,3,0,2$. And perhaps unique shifts for each round of the $10$ rounds.

Then, if we encrypt a message $m$ with (say) $AES_{tweak1}$ and key $k$ we get ciphertext $C$. And if we encrypt the same message $m$ with $AES_{tweak2}$ and with the same key $k$, we get ciphertext $C^*$:

2)  $AES_{tweak1}[E_k(m)] = C$ and $AES_{tweak2}[E_{k}(m)] = C^*$

Since these ciphertexts in (2) are distinct is this the same or similar to changing the key, as in case (1)?

Let's assume sender and receiver can secretly exchange the tweaks.

Well it'll change the output for sure.  But it's not a great idea.  I don't know what exact arrangements you have in mind, so I'll think of my own along those lines and throw some numbers at you:

Possible number of 128 bit keys = 2^128 ~ 10^38

Possible number of ShiftRows tweaks = P(4!,10) ~ 10^13 -> 42 bits

So  better than I expected (42 bits) but still wholefully inadequate today.  However I'm not sure how you'd actually exchange the tweaks.  Little tables of shifts that you enter into a program that enters them into AES?  Clearly you can't use a password + standard key derivation function.

I'm always messing around primitives to create weird stuff.  But one thing that I've learned from this forum is not to mess with their internals.  They are carefully designed (some might say evolved over time) to be secure and efficient.  By tweaking them you can unwittingly fall foul of the law of unintended consequences.  What if a pattern is created?  Or some form of weak shifts?  Recall totally unforeseen RC4 weak states.  I'm not aware of any crypt-analysis of AES with your ShiftRow arrangement.  How do you know it's secure, just because you can't break it?

So in summary it's not like changing the key to standard AES as that's how it's meant to be used.  You might enter a particular ShiftRow permutation and just break the thing security wise.


AES-256 example code encrypting multiple subsections of plaintext with the same initialization vector I have been dabbling a bit into encryption in C++ using Brian Gladman's implementation found here:

https://github.com/BrianGladman/AES

I also found some example code that uses this library found here:

http://forums.devshed.com/programming-42/aes-encrypt-decrypt-687368.html

The relevant bits of code are as follows:

void encrypt(const char *fileIn, const char *fileOut,
    const unsigned char *key) {
    ...
    /* pick a random initialisation vector */
    for(i = 0; i < 16; ++i)
        iv[i] = rand() & 0xFF;
    fwrite(iv, 1, 16, outFile);

    aes_encrypt_key256(key, ctx);
    while((i = fread(inBuffer, 1, sizeof(inBuffer), inFile)) > 0) {
        aes_ofb_crypt(inBuffer, outBuffer, i, iv, ctx);
        fwrite(outBuffer, 1, i, outFile);
    }
    ...
}

void decrypt(const char *fileIn, const char *fileOut,
const unsigned char *key) {
    ...
    /* read initialization vector from file */
    if(fread(iv, 1, 16, inFile) < 16) {
        ...
        return; /* error: file doesn't even contain an initialisation vector */
    }

    aes_encrypt_key256(key, ctx);
    while((i = fread(inBuffer, 1, sizeof(inBuffer), inFile)) > 0) {
        aes_ofb_crypt(inBuffer, outBuffer, i, iv, ctx);
        fwrite(outBuffer, 1, i, outFile);
    }
    ...
}

However, after reading through the last answer on:

Why is AES resistant to known-plaintext attacks?

It seems like that chunking the input text and encrypting each chunk using the same initialization vector is a bad idea.  I just wanted to ask if this implementation is flawed from a security perspective or is there a valid reason for encrypting each chunk of text with the same initialization vector?

In addition, are there compelling reasons for chunking the plaintext in this way to begin with (where each chunk has its own initialization vector, that is)?

Thanks in advance for any responses.

It seems like that chunking the input text and encrypting each chunk using the same initialization vector is a bad idea

You are quite right to be concerned. It wouldn't only be a bad idea; it would be an absolutely dreadful one.  With OFB mode, reusing an IV would cause the same bitpattern to be exclusive-or'ed with the plaintext to form the ciphertext; hence if the attacker takes the two ciphertexts with the same IV and exclusive-or's them, they'll get the two plaintexts exclusive-or'ed together.  From that, it is often not that difficult to recover the original plaintexts (as real plaintexts often have enough redundancy to allow this).

However, that's not what's happening here.

As a part of its processing, aes_ofb_crypt updates the IV it was passed; hence calling it multiple times will cause it to use a different IV each time.  Hence, this problem is avoided (and so this code is safe).


A commonly used way to encode RSA keys is DER which derives semantic meaning via ASN.1. You can find more detail in RFC3447. The ASN.1 syntax for a DER-encoded string looks as follows:

  Version ::= INTEGER { two-prime(0), multi(1) }
      (CONSTRAINED BY
      {-- version must be multi if otherPrimeInfos present --})

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

A sample private-key using the encoding and syntax above would look as follows:

-----BEGIN RSA PRIVATE KEY-----
MIGGAgEAAhkAr6M0MwwZb+PmNOex7pFe5IDLe+eKEhazAgMBAAECGBpkc9uX3dqq
bFVW224yqOR0m8LyV+x2wQINANs9bxnc7ZdljRmlHwINAM0WMid0p2sbmMOn7QIN
AMocs4yTOFFG5DJNHwIMOLmt76ndcMu2Sk/VAgwpTp5DBMk2FLZKfaY=
-----END RSA PRIVATE KEY-----

Final note: You've posted your private key online ... which means that you shouldn't use it anymore.


The strength of ECDH public keys with small order I am trying to get my head around the methods involved in ECDH and am confused by the public keys that are used. Alice picks a random number A from 1 to P - 1 and then computes A⋅g (g being the publicly agreed generator, with a high order) using point addition and multiplication. She then publishes this value. In order to arrive at a shared secret, Bob must then also pick a random number B and compute B⋅(A⋅g).

Now, the shared secret can only be one of the points which can be generated from A⋅g through point addition and multiplication and, as such, if A⋅g has a low order surely there are very few potential results of Bob's calculation of the shared secret. Because an attacker would have access to A⋅g and the parameters of the curve (as they are publicly agreed) would they not be able to discern whether Alice's public key had a low order? If this was the case would a brute force attack not be sufficient to discover the shared secret?

There must be a mistake in my reasoning somewhere and I just can't see it, else are the random numbers re-computed if A⋅g has a low order to avoid this very attack?

Thanks for the help.

$g$ is a generator and is of order $P$.  Lagrange's theorem says that the order of an element in a group $\mathbb{G}$ divides the order of the group.

In your case, one has $\mathbb{G} = \langle g \rangle$.  Therefore, the order of an element $a = Ag \in \mathbb{G}$ is a divisor of $P$.  If $P$ is a prime, its two divisors are $P$ and $1$.  Hence, either $a$ is of order $P$, either $a$ is of order $1$ (in the latter case, $a$ is the neutral element ---the point at infinity on an elliptic curve given by a Weierstrass equation).


How to prove that a encryption scheme is not IND-CPA secure I am trying to construct a proof that a scheme is not CPA-secure. In IND-CPA experiment, can the adversary generate a key(that may not be real secret key) and compute Enc(key, message)? Does the adversary knows the encryption scheme in IND-CPA experiment?

I need this as I want to prove that if a scheme B1 is not CPA-secure, a scheme B2 is not CPA-secure by the following logic:
There exists an adversary A that can win IND-CPA experiment for scheme B1.
Then I construct an adversary A' with the help of A to win IND-CPA experiment for scheme B2.
But A' has to be able to compute Enc(key, message) for some key. I am unsure whether I can do so.

In IND-CPA experiment, can the adversary generate a key (that may not be real secret key) and compute Enc(key, message)?

Yes, for message available to the adversary per the rules of the game. The adversary is always assumed to be able to use as a subprogram the algorithm under attack, or any part of it (e.g. encryption, or decryption, or key generation as is the case here; or any deterministic internal block, such as a hash including when modeled as a random oracle). That's per Kerckhoffs's principle. The computation is still counted as work performed by the adversary.

The random inputs and the outputs of any internal TRNG of the scheme under attack are assumed to be supplied to the adversary only inasmuch as prescribed by the scheme (e.g. IV for encryption; that's uncommon for key generation). The adversary has unlimited randomness available (e.g. to generate new keys, collisions), except if it is explicitly specified to be deterministic.


Available programs that can verify the working of a simple substitution cipher Is there any tool available that can test whether a simple substitution cipher is working.
I will put my scenario in detail. Lets say I built a simple substitution cipher that maps 8 bit data to 16 bit encrypted cipher using an 8 bit key. I need to verify whether the substitution cipher is actually unique for all possible permutations of 8 bit data and 8 bit keys with my algorithm.

Before you guys eat me alive with 'You think you can build a superior cipher?' questions, this is not a high security application but a simple app where sending plain data is not preferred. Existing ciphers like columnar transposition and caesar cipher were not an option considering user experience and ease of implementation. You can assume it is just simple XOR.

I just want to verify whether the substitution is happening correctly or not. If I need to manually write a program that can verify this, can anyone give me a brief detail about how I should start?

Regarding the test of unicity

You could just script the test in Python (or any other language, really). The language in which you already implemented your cipher might be a good choice otherwise.

Then, given the size you are talking about (256 possibilities of 16bits = 4Ko), you can basically just generate all the results in a 256-array, and check the unicity of each element in your array.

Regarding your cipher

I've got a pretty hard time figuring the security level of your application. With a basic substitution over basically each character (8bit), your ciphertext is extremely vulnerable even with not-so-long messages, and especially if your data/protocol/application has any kind of predictable headers and such. It's not clear which kind of threat you want to protect the data from.


Is it possible to prove that I have half a key to decrypt file, to someone who has other half, without disclosing my part? Is it possible to prove that I have half a key to decrypt file, to someone who has other half, without disclosing my part?
Or better yet, could you suggest a place where I can read about solved and unsolvable practical cryptographic problems like this one?

This is similar to problems in Multi-Party Computation, but in this case I don't know how its possible if there is no trusted third party, and no corollary data accompanying the secret keys.

However if you relax the scenario, and allow the distributor to convey an extra piece of information to both parties, then this can be achieved. Have the distributor distribute a second piece of information to both parties, for this example let it be Hash(First Half) XOR Hash(Second Half)

So both parties know the hash of their half, and the XOR of the hashes of both halves. They can easily figure out the hash of the other parties data. So effectively, they both have a password which they can authenticate each other with. So then use a secure verification protocol that isn't subject to replay attacks (perhaps Password-authenticated key agreement algorithms such as SPEKE) Then they can both verify each other, and that they knew the Hash of their block of half of the key, which we now assume means that they knew that data.


Sigma proofs for Pedersen commitments arithmetic under different bases I was wondering if it's possible to prove an equality of openings between $3$ Pedersen commitments $P\cdot Q$ and $R$ when $P, Q, R$ have different commitment keys.
Suppose that commitment $R$ commits to $a+b$ and $P$ and $Q$ commit to $a$ and $b$ respectively. How can we prove, that $P$ and $Q$ combined commit to the same value as $R$ if we don't know relation betwen $(g_1, h_1)$ and $(g_2,h_2)$?
$P = g_1^ah_1^{r_1}$, $Q = g_2^b h_2^{r_2}$ and $R = g_3^{a+b}h_3^{r_3}$.
LegoSNARKs does something similar ($CP_{had}$), but I was curious if there is a solution with sigma protocols.

This is certainly possible using only standard Sigma-protocols and compose them together. But first, let's introduce the used standard Sigma-protocol building blocks:

Equality of committed values in two Pedersen commitments

Given Pedersen commitments $P=g_1^a h_1^{r_1} $ and $P'=g_2^{a'} h_2^{r_2} $, one can show in zero-knowledge using a Sigma-protocol that $a=a'$. Note, that all generators could potentially be different in the statement.

Equality of opening of two Pedersen commitments

Given Pedersen commitments $P=g_1^a h_1^{b} $ and $P'=g_2^{a'} h_2^{b'} $, one can show in zero-knowledge using a Sigma-protocol that $a=a'\land b=b'$. Note, that all generators could potentially be different in the statement.

Proving the conjunction of different statements using Sigma-protocols

Given several statements $\{\mathit{stmt_i}\}^{n}_{i=1}$, it is possible to prove their conjunction, i.e. $\wedge^{n}_{i=1} \mathit{stmt_i}$. In this case, for every statement the verifier samples the very same challenge value.
For a more thorough treatment on these building blocks, please refer to this post.
Now, it should be straightforward to devise a Sigma-protocol for your statement. Let's use the notation introduced in the question. First, prover computes $P'=g_3^a h_3^{r_1}$ and shows the equivalence of openings of $P'$ with $P$. It does the same for $Q'=g_3^b h_3^{r_2}$ and $Q$. Finally, prover can show the equality of committed values for the point $P'*Q'=g_3^{a+b} h_3^{r_1+r_2}$ and $R=g_3^{a+b} h_3^{r_3}$. The conjunction of these statements can also be easily proven by sampling the same challenge value for all the constituting Sigma-protocols.