Are there any signatures based on matrix multiplication with noise? Are there any signatures based on matrix multiplication with noise? Representing the message as a matrix and multiplying with some randomness coming from another matrix such that the signature itself is a matrix?

There are two major families of signature schemes that bear some resemblance what you described.

Code-based signatures: Courtois–Finiasz–Sendrier, or CFS

The CFS family of signature schemes is based on code-based cryptography first introduced by Robert McEliece in 1978 and dualized by Niederreiter.  We work with binary linear codes, of length $n$ and rank $k$ correcting up to $t$ errors.

In the error-correcting code scenario, a sender with a $k$-bit message $m$ redundantly encodes it as an $n$-bit codeword $c$ from a $k$-dimensional subspace of all $n$-bit strings, and sends it along a noisy channel; the receiver, on receiving a possibly modified message $c' = c + e$, can uniquely recover $c$ as the codeword nearest to $c'$ as long as the error pattern $e$ has no more than $t$ bits set, i.e. as long as the Hamming weight of $e$ is at most $t$.

The generator matrix of a linear code is a $k$-by-$n$ matrix $G$ that that transforms $k$-bit messages to $n$-bit codewords: $c = G m$.  The parity-check matrix of a linear code is an $n$-by-$(n-k)$ matrix $K$ that transforms $n$-bit strings to $(n-k)$-bit syndromes.  An $n$-bit string is a codeword in the code if and only if its syndrome is zero: $K c = 0$, and $H c' = K\cdot(c + e) = K c + K e = K e$.  The syndrome decoding problem is to find $e$ given $K e$.  The premise of CFS signatures is that finding the noise given a syndrome given only the parity-check matrix $K$ seems to be difficult without additional information about the structure of the linear code.

Parameters.
Bit sizes $n$, $k$, $t$ for a family of binary linear codes, usually binary Goppa codes (other proposals like Reed–Solomon codes have been broken, although there are new candidates, e.g. Reed–Muller codes in the pqsigRM submission to NIST PQCRYPTO), and a random function $H\colon \{0,1\}^* \to \mathbb F_2^{n-k}$ from messages to syndromes.

Public keys.
Alice's public key is the parity-check matrix $K$ of a binary linear code of length $n$ and rank $k$ correcting up to $t$ errors.

Signatures.
A signature by Alice on a message $m$ is an error pattern $e \in \mathbb F_2^n$ such that $K e = H(m)$.  That is, a signature is the noise whose multiplication by a parity-check matrix yields a syndrome that is the hash of a message.

Private keys and signing.
Too complicated to fit in the margins of this crypto.se post; see McBits for a modern implementation strategy of CFS signatures and Niederreiter KEM, and Classic McEliece for a NIST PQCRYPTO submission based on it (but KEM-only, no signatures), which also have concrete parameter suggestions for reasonable post-quantum security levels.  (The pqsigRM submission to NIST PQCRYPTO may have some implementation ideas too, but its supporting documentation makes no mention of side channel attacks or constant-time algorithms, and a brief look at the code makes me suspicious.)

Lattice-based signatures

Let $q$ be a prime, and let $F$ be the field $\mathbb Z/q\mathbb Z$.  Fix a secret vector $s \in F^n$, a sample of uniform random vectors $a_i \in F^n$, and a sample of errors $e_i \in \mathbb Z$ with some distribution $\chi$

The computational learning with errors problem, introduced by Regev in 2005, is to find $s$ given the sample $(a_i, \langle a_i, s\rangle + e_i) \in F^n \times F$ with nonnegligible probability.

The decisional learning with errors problem is to distinguish it from $(a_i, v_i)$ for uniform random $v_i \in F$.  There are a few variants on the theme: for example, in the ring learning with errors problem, we replace the vector space $F^n$ by the ring $F/(x^n + 1)$ when $n$ is a power of two, or $F/(\Phi(x))$ for some polynomial $\Phi(x) \in F[x]$, which was introduced by Lyubashevsky, Peikert, and Regev in 2010 to admit much smaller parameters.

This is a sketch of the Lyubahsevsky's learning with errors signature scheme, derived from the same Fiat–Shamir transform used to derive Schnorr signatures, and on which newer systems such as the NIST PQCRYPTO submission qTESLA are based.

Parameters.
Field $F$; dimensions $n$, $m$, and $k$; bound $d$; bounded distribution $\chi$ on $\mathbb Z^m$; a standard $n$-by-$m$ matrix $A$ in $F$; and a random function $H\colon \{0,1\}^* \to \{-1,0,+1\}^k$ such that $\lVert H(M)\rVert_1$ is bounded.

Public keys.
Alice's public key is an $n$-by-$k$ matrix $T$ in $F$.

Signatures.
A signature by Alice on a message $\mu$ is a pair of $z \in \mathbb Z^m$ and $c \in \mathbb Z^k$ such that

$\lVert z\rVert^2 = \sum_i {z_i}^2$ is small, and
$c = H(\underline{A z_q - T c_q} \mathbin\Vert \mu)$, where $z_q$ and $c_q$ are the componentwise projections of $z$ and $c$ onto $F = \mathbb Z/q\mathbb Z$, and the underline is some canonical bit string encoding of $F$.

(For the technical details of what ‘small’ means, see the paper.)

Private key and signing.
Alice's private key is a secret $m$-by-$k$ matrix $S$ in $\mathbb Z$ whose elements are chosen uniformly at random from integers at most $d$ in absolute value.  Let $S_q$ be the componentwise projection of the matrix $S$ onto $F$.  Alice computes her public key by $T = A S_q$.  (With an appropriate transformation of $A$, this is not far from the form of the learning-with-errors problem.)

To sign a message $\mu$, Alice draws $y \in \mathbb Z^m$ from $\chi$,  computes $c = H(\underline{A y_q} \mathbin\Vert \mu)$ and $z = S c + y$, and, with some rejection sampling on $z$, reveals $(c, z)$.

This satisfies criterion (1) of signatures because of the bounds on $S$, $c = H(\cdots)$, and $y \sim \chi$.

This satisfies criterion (2) of signatures because $A z_q - T c_q = A S_q c_q + A y_q - A S_q c_q = A y_q$, so $c = H(\underline{A y_q} \mathbin\Vert \mu) = H(\underline{A z_q - T c_q} \mathbin\Vert \mu)$.

Filling in details is left as an exercise for a less tired ossifrage than this one, preferably when day is not breaking.


Regain 3DES ECB key, assuming I have both encrypted and decrypted text Let's assume I've encrypted some text with some 24-byte key using 3DES in ECB mode. Is it possible to regain the key if I have both encrypted and decrypted text? (Excluding bruteforce.)

It is not practically possible. There are several attacks that are slightly faster than bruteforcing $2^{112}$ key candidates, but this is only a small factor. In some sense, they are bruteforce-like, since they require $2^{113}$ smaller steps.


Are cryptographic hash functions perfect hash functions? For a cryptographic hash function and input values of shorter length than the hash function output, it's pretty obvious that there should be as few collisions as possible. But are there guaranteed to be none?

In other words, for a cryptographic hash function $H: x\to y, x \in \mathbb{N}, y \in [0,y_{max}]$, are there any $x_i \ne x_j$ with $x_i,x_j \le y_{max}$ so that $H(x_i) = H(x_j)$?

This seems to be a special case of Is every output of a hash function possible?, with the additional limitation of inputs to the space of possible outputs.

If there are any such collisions, wouldn't that mean that, due to the pigeonhole principle, there exists some possible output of the hash function that can never be reached by hashing another output, i.e.

$\exists y:H(x) \ne y$ for all $x, y \in [0,y_{max}]$?

Are common cryptographic hashes bijective when hashing a single block of the same size as the output? even mentions that some hash values are expected to be unreachable by all possible inputs, which would of course also imply the limited input range given above.

Are there any practical consequences of that property of hash functions? I'm thinking about things like the Bitcoin proof-of-work system that require collisions (or "close collisions", differing only by some amount from the target hash value) to be found. Any chance that finding such a collision (range) would be not only practically, but theoretically impossible?

If a hash function is a random oracle, which is about as perfect as can be expected for a hash function, then we actually expect a lot of collisions. If the hash function output is in a space of size $N$ (e.g. $N = 2^n$ for a "$n$-bit output") then collisions are expected, on average, when about $\sqrt{N}$ distinct inputs are hashed (see the birthday problem for more details).

If you want to feed the $2^n$ possible sequences of $n$ bits to a hash function $h$, which produces $n$-bit outputs, and such that no collision occurs at all, then $h$ must severely depart from the normal hash function model -- in a way, it must be quite imperfect. This calls for a pseudo-random permutation. Think of it as a block cipher which you can compute in the "encrypt" direction but not the "decrypt" direction.

I am not aware of good constructions for that. Some attempts include RSA: let $N$ be a RSA modulus of unknown factorization, and $e$ the public exponent; then $m \mapsto m^e \pmod N$ is a one-way permutation of the set of integers modulo $N$. But it is not completely "random looking" (it is one-way on average) and requires a big $N$. Other constructions can use elliptic curves, but still with some drawbacks and caveats.


Would the Secure Enclaves such as Keystone or Intel SGX obviate the need for cryptography Would the use of Secure Enclaves such as Keystone or Intel SGX obviate the need for cryptography? Rendering cryptography irrelevant in the decades ahead?

No, Secure Enclaves do not obviate the need for cryptography.

For a start, Secure Enclaves typically receive their input data integrity-protected or/and encrypted, which requires cryptography both within the enclave, and outside (perhaps in another enclave).

Even if we turn the question to "Would the use of Secure Enclaves obviate the need for unrelated cryptography", the answer is still no. Secure Enclaves aim at creating a virtual secure computer not under control of the person holding the enclave, and that does not match all use cases. Even in an Orwellian world where Secure Enclaves are the only form of secure data processing permitted, I bet both a master of that society, and any rebel, will want to use raw cryptography. And I see no practical way to prevent that, as long as programming remains a thing. We can do AES-256 or RSA-4096 in any computer language, including a spreadsheet.


How long random value is required in random masking method? I heard that random masking method requires a random number whose length is as long as a message to be sent, but I’m not sure that. So, I'd like to ask about that.

1. Boolean masking : $ x_i \oplus r_i$

Assume that a message is $ (x_7, x_6, \cdots , x_0)$ where $x_i$=0 or 1. Then, a random value of 8 bits is required! That is $(r_7, r_6, \cdots , r_0)$ where $r_i$=0 or 1 and the Boolean masking is $(x_7 \oplus r_7, x_6 \oplus r_6, \cdots , x_0 \oplus r_0)$

2. Arithmetic masking : $x + r$

Assume a message $x$ of 8 bits where $x \in \Bbb Z_{2^8}$. Then, a random value $r$ of 8 bits where $r \in \Bbb Z_{2^8}$ is required!

2-1. Arithmetic masking

Assume that the length of all message $x$ to be sent is 4 bits (that is, $0 \le x < 2^4$) where $x \in \Bbb Z_{2^8}$.

(Question 1) Is it possible to hide the message $x$ with random number $r$ of 4 bits using arithmetic masking method $x+r$ in $\Bbb Z_{2^8}$?

3. Multiplicative masking : $x*r$

Assume that the length of all message $x$ to be sent is 4 bits (that is, $0 \le x < 2^4$) where $x \in \Bbb Z_{2^8}$.

(Question 2) Is it possible to hide the message $x$ with random number $r$ of 4 bits using multiplicative masking method $x*r$ in $\Bbb Z_{2^8}$?

(Question 3) Where can I find the related references?

Thank you in advance.

Forget $s=8,$ let $s=2t$ and let $t$ be large. An answer of "yes" only means the masked quantity is uniformly distributed in some set which is brute force able if the set is small enough.

Question 1. No, the distribution of the secret plus the mask is not uniform, when the mask is uniformly chosen from $\{0,1,..,2^t-1\}.$ It is triangular. This assumes addition is mod $2^s.$

Edit: If in this question you mean the addition is mod $2^t$ with the secret from the integers mod $2^s,$ the answer is yes.

Question 2. No, and this is even worse since if you get a product divisible by $2^m$ where $m$ is the largest exponent with that property you leak a lot of information. Again this is because there is no modular reduction of the product, it being too small. Say product is 2, then either secret is 1 and mask is 2 or vice versa.

Even if you have wraparound multiplication mod $2^s$ is weak due to it being a ring with zero divisors.

2nd Edit after new comment by OP:

You won't get a uniform distribution. And the divisibility comments above still apply since in general there is no wraparound.  Except you get a wraparound to zero only if you multiply the largest $x$ and the largest $r$  obtaining $2^{512}$ which would wrap around to zero if you reduce mod $2^{512}$ (and this would leak those values).

On the other hand, you now have huge numbers, and brute forcing, even when knowing the divisibility, will take a very very long time, if not being out of reach.

Question 3. Integer arithmetic.

In general addition is better, use full length uniformly distributed masks.


How much does a successful Distinguishing Attack "break" the attacked stream cipher? I started reading about the most recent cryptanalysis of RC4 and it's variants. One of the papers I just finished reading ("Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers" by Alexander Maximov) handles Linear Distinguishing Attacks.

Now, I understand that a Linear Distinguishing Attack can be used to (simply said) differ cryptotext from real random data. I also understand this proves the related stream cipher to be cryptographically broken, because the successful attack can be used as a base for further attacks. Yet, I am not sure I fully understand the whole range of consequences of a successful Linear Distinguishing Attack.

Does a successful Linear Distinguishing Attack mean the attacked stream cipher is completely broken from a practical point of view?

The question popped up in my mind, because there might be scenarios where Alice and Bob can guarantee that Eve will never get her hands on any plaintext at all. If I'm not mistaking, when Eve does not have (enough) plaintext, Eve can't do a successful linear cryptanalysis. That again could imply that a successfully attacked cipher could be still be used "under certain conditions". Is that correct?

Yeah, I know. No sane person would actually implement a cryptographically broken cipher (like RC4) as long as there are safer alternatives (like AES256) available… so please think of the scenario as a theoretical one. I'm only using it at part of the question since it might help me to completely understand the full impact of a successful Linear Distinguishing Attack, what it practically means for attacked ciphers, and how much a successful Linear Distinguishing Attack actually breaks an attacked stream cipher.

In fact, I guess my question boils down to a more general question covering more than just linear distinguishing attacks… do all distinguishing attacks generally count as a complete break, from a practical perspective?

I would say a distinguishing attack should count as a break. Especially so if it is practical.

The reason for this is that if you can distinguish the key-stream from random, you invariably leak details about the plain-text.

For example, suppose somebody turned up a few terabyte disks encrypted with VMPC under the same key. It says in the paper that after approximately $2^{40}$ bytes the cipher can be distinguished from random. The bias in the underlying cipher might allow an attacker to work out whether the plain-text was written in Arabic or English.

That in itself is useful information to know about the plain-text and, to me at least, constitutes an unacceptable weakening of the cipher.


RSA - Is $e = d$ a problem? I'm working on small RSA project in university.
At this moment I have done this:

An array of prime numbers is generated from selected range.
$p$ and $q$ selected randomly from this array
$n$ calculated
$\phi(n)$ calculated
$e$ calculated
$d$ calculated

What do you think about $e$ and $d$ in that case?

$p = 29$
$q = 53$
$n = 1537$
$\phi(n) = 1456$
$e = 545$
$d = 545$

It would be disastrous if an RSA key generation procedure had a sizable probability to end with $e=d$, because in that case, the public key reveals the private key, which must be secret from a security perspective.
But $e=d$ is a symptom of a larger problem lying in steps 1 and 2 of the key generation procedure: RSA can only be secure if $p$ and $q$ are selected in a way such that factoring $n$ is hard, and that means $p$ and $q$ should be large primes. The modern baseline is $n$ of $2048$ bits, that is $617$ decimal digits, not $4$ decimal digits. For this, $p$ and $q$ are chosen randomly among a sizable subset of primes of about $309$ digits. There are over about $10^{305}$ such primes, thus generating them all then picking within that is infeasible. The right procedure is to directly generate $p$ and $q$.
With $p$ and $q$ random primes this large, and a random choice of $e$ such that $\gcd(e,\phi(n))=1$ (or a random choice of primes $p$ and $q$ with the only dependency on $e$ that $\gcd(e,p-1)=1$ and $\gcd(e,q-1)=1$, as is common practice), it's infinitesimally improbable that $d=e$, or more generally that one or a few re-encryption(s) lead to decryption. See these questions on the cycling attack.

There are RSA key generation procedures in FIPS 186-4 appendix B.3. Ignore the proposed $1024$-bit key size, which is obsolete. The proposed $2048$ is the baseline, $3072$ increasingly common, extending to $4096$-bit not unreasonable. These procedures differ from those used in the question by several points including:

Generating large primes $p$ and $q$ unpredictably in a prescribed interval $[2^{(k-1)/2},2^{k/2}]$, where $k$ is the desired bit size of $n$ (e.g. $3072$)
Requiring odd $e$ with $2^{16}<e<2^{256}$ (the lower because that acts as a safeguard against poor choices of RSA padding, the higher for interoperability and to make some other poor choices impossible)
Using $d=e^{-1}\bmod\lambda(n)$ (where $\lambda$ is the Carmichael function) rather than $d=e^{-1}\bmod\phi(n)$. Both are mathematically fine, but using $\lambda$ insures generating the smallest positive private exponent $d$ working for a given $(n,e)$.
Requiring a minimum size of $d$ (much larger than $2^{256}$, which incidentally insures $d>e$), more as a safeguard against errors than out of mathematical necessity.


Are there any cryptographic flaws in my webhook signing process? Out of band my services have exchanged secret keys. These secret keys are then used to prevent two things of the webhooks (HTTP calls triggered by Service A to Service B when an event occurs in Service A).

Webhook Spoofing
Webhook Replaying

The basic problems with webhooks involve the fact that, short of Client SSL Certificates, there's no way to know that the sender of the HTTP call is who we think they are. Because of these, a mechanism is needed to ensure that the webhook is not being spoofed and that it isn't being replayed. For this, I'm using a Nonce and HMAC-SHA256. The definition of the Signing process (and a Python example) follows:

Creating the Signature

Generate a Random UUID.
Add this UUID as the HTTP Request Header "x-webhook-nonce".
A new, empty string is created, henceforth known as the signing string.
In alphabetical order of the Header names, append the HTTP Request headers (names and values, in that order, in lower case) onto the signing string.
Base64 encode the request body. Append the resulting Base64 encoded string to the signing string.
Using HMAC SHA256, create the signature. The previously exchanged key is to be used as the key and the signing string as the value to be signed.
Take the resulting HMAC value and Base64 encode it. Create the HTTP Header “x-webhook-signature” with the resulting Base64 encoded HMAC string as the value.

Verifying the signature:

This process is almost the exact same as generating the signature with a few minor changes.
 1. Verifiers should not generate their own nonce, but use the one provided in the “x-webhook-nonce” header.
 2. Verifiers should first check and ensure that the nonce has not been used before. If it has, it should ignore the webhook.
 3. When arranging the headers for the signing string, do not add the “x-webhook-signature” header.
 4. Once you have generated a signing string, compare it to the included “x-webhook-signature” to ensure that the generated signature and the header value are the same. If they are, the request is valid. If not, ignore the webhook.

Generating Signature Example in Python:

signing_key = "SIGNING_KEY_FROM_SUBSCRIPTION"
nonce = uuid.uuid4()

body = "{\"url\": \"https://example.com/\"}"
headers =   { 'Content-Type': 'application/json',
    'Content-Length': 25,
    'Host': 'example.com',
    'x-webhook-nonce': nonce
}

to_sign = ""

for key in sorted(headers):
    if key != "x-webhook-signature":
        to_sign += key + headers[key]

to_sign += base64.b64encode(body)
signature = base64.b64encode(hmac.new(signing_key, to_sign, digestmod=hashlib.sha256).digest())
headers["x-webhook-signature"] = signature

So, after that large wall of text, does this solution correctly prevent against spoofing and replaying of webhooks?

I do not recommend inventing your own protocol for this.

Instead, I recommend using TLS client certificates.  They solve exactly your problem, and solve it well.  The TLS folks thought a lot about the security challenges involved in designing such a protocol, so you wouldn't have to.

You mention that you perceive the complexity of client certificates to be significant.  My sense is that the complexity of rolling your own is actually higher than just using an existing TLS library's support for client certs; and the chances of making a subtle security mistake are significantly higher when rolling your own.   Therefore, I do not recommend the direction you are taking of trying to design your own protocol: I recommend using a well-vetted existing mechanism (like TLS client certs) whenever you possibly can.


How can one validate with a public key a JWT signature generated with a private key? As I understand it, a JSON Web Token (JWT) consists of 3 parts:

the header, specifying the hashing algorithm to use for the signature;
the payload itself; and
the signature, which is a hash of the header and the payload using the specified hashing algorithm and a given secret.

The point of the signature is for the receiver to verify the integrity of the received JWT, that it has not been tampered with. This is done, presumably, by the receiver of the JWT reproducing the steps made by the JWT producer to create the signature, by hashing the header and the payload with the specified hashing algorithm and a given secret.

When the secret used by the JWT sender and receiver is one and the same (shared secret, symmetric key), I understand how this works. All the inputs are identical, so the hash will be identical, whether calculated by the sender or receiver.

My actual question, and what I don't understand, is how this works when the secrets used by the sender and receiver are different (asymmetric keys, public/private key pair). I.e. if the hash produced by the sender was generated using the secret key, and the hash produced by the receiver (for signature verification purposes) was produced by the corresponding public key.

How can two different secrets yield the same hash?

I received the following explanation from a separate source.

Send:    { object | encrypt(hash(object), private_key) }
Receive: { object | signature }
Verify:  hash(object) == decrypt(signature, public_key)

This explains what I was struggling to understand.

There are two processes at work here: not just hashing, but also encryption. The actual hashing itself needs no secret parameter, it takes in only the object to be hashed (the concatenation of header + payload in the case of JWT). The resulting hash itself is then the input to the encryption, the result of which forms the signature, which can then be decrypted by the recipient to retrieve the original hash for comparison against the recipient's own computed hash.

Thus, instead of the sender and recipient performing similar calculations, with different secrets, to arrive at the same hash value:

hash(object, private_key) == signature == hash(object, public_key)

we rather have the sender and recipient performing complementary calculations to arrive back at the original input

decrypt(encrypt(hash_value, private_key), public_key) == hash_value

This makes sense with how I understand public-private key encryption.


Distinguishing generators of RSA primes and moduli We are trying to distinguish two RSA prime generators:

Prime generator 1

draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$, until it is prime
output $p$.

Prime generator 2

draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$
while $p$ is composite, $p\gets p+1$
output $p$.

We can distinguish these generators from their output: the primes generated per 2 are on average farther away from the prime immediately below than are the primes generated per 1.

What advantage do we get from the above distinguisher?

Can we make a distinguisher with sizable advantage from the distribution of $p\bmod \mathtt{e221f97c30e94e1d}_{16}$ ? That 64-bit constant is the product of the odd primes to $53$. If yes, what's the advantage?

Now we derive two generators of RSA moduli, by multiplying two consecutive outputs of each of these prime generators. Can we make a distinguisher with sizable advantage, even though we can't factor the moduli? If yes, what's the advantage?

Motivation is recognizing if RSA keys are generated using this.

This has been examined before, for example in Fouque and Tibouchi (2001).  It's been brought up in a number of places in online forums as well, though not with any sort of resolution.

I agree with this statement from F/T: "Moreover, even for more common uses of prime number generation, like RSA key generation, it seems preferable to generate primes that are almost uniform, so as to avoid biases in the RSA moduli themselves, even if it is not immediately clear how such biases can help an adversary trying to factor the moduli."

It is very easy for people to fall into the "proof by failure of imagination" trap.  Well I can't think of any way to do it, so it's good.  There are a lot of areas in life where this is an efficient strategy, but cryptography should avoid this compromise where possible.  Just because we can't think of a way to exploit it now, why should we leave this very large bias when we know how to do much better with almost no loss of efficiency?

It's easy to implement PRIMEINC, and while just as easy to implement, TRIVIAL without optimizations is slower.  Effective optimizations of the latter require some thought, coding, and testing.  Most consumers honestly do not care (edit: they should, but evidence is that quality isn't a big priority until something obviously breaks).  Also I see most packages like the OP's referenced pycrypto are really simple -- finding a hundred lines of optimized random prime generation would be out of place there.  This does have the advantage of readability and debugging.  But we can do this both better (more uniformly) and faster if we want.

The provable prime generators don't have this same issue, but they do generate only a subset of the primes in the range.  Both Shawe-Taylor and Maurer spend a large portion of their papers going over the distribution and implications.


How is Encryption Actually Used in Public Networks at This Moment? Has anyone done a study, assembled a snapshot, of how encryption is actually being used on the Internet at this moment?

So many companies do traffic analysis, the usage share of operating systems, etc., and one imagines that national-level agencies do this too, perhaps in incredible detail, but does any open-source information exist that quantifies the use of cryptographic hashes, asymmetric and symmetric algorithms, cryptographic libraries, etc.--and the services they provide?

Reliable data is certainly available.

Such a study on current use could answer many interesting questions:

  How much global message and email traffic is being encrypted all the
  way through an ISP?  With what?  How much is GnuPG being used? What cryptographic primitives are actually in decline? What services-- confidentiality, integrity, non-repudiation,
  availability, non-availability (!), authentication-- are really being
  requested, and what is their usage share?

Does a detailed, open-source (or compromised) study of global encryption use exist?

In relation to email, Google reports regularly on the use of TLS on incoming/outgoing mails through its servers, which is significant sample size given the popularity of GMail. See below.

https://transparencyreport.google.com/safer-email/overview

You can examine the data in quite some detail to see TLS usage by domain, country etc.

They also see to have other reports on HTTPS usage etc. although I haven’t checked them out myself.


Is XTS always better than GCM? XTS is suitable for disk encryption while GCM doesn't.
Both require the same number of block encryption calls.
Both are parallel in encryption and decryption.
XTS is actually even faster in openssl implementation (openssl speed -evp aes-256-xts/gcm), not sure why.
Why even bother to use GCM instead of XTS?

You're trying to compare authenticated encryption with disk encryption. GCM is used to solve 2 security problems at once: encryption and authentication. GCM is designed such that only someone knowing the key can modify ciphertext without raising alarms. This requires additional data to use as an authentication tag.
XTS, on the other hand, only partially hold this property. The benefit of XTS, however, is you don't need to store additional data for an authentication tag. XTS also has (some) resistance to tampering, since any change made to the ciphertext yields random and meaningless plaintext. However, this is not considered sufficient for authentication, since an attacker can still make changes without the changes being noticed. This is undesirable in any case where an attacker may intercept encrypted communication (ex. network protocols).
For full-disk encryption (FDE) authenticated encryption becomes impractical, since you would need to store a lot of extra data to verify integrity (with a mode like GCM). Unless you have so much disk space you don't mind losing half of it, this isn't a reasonable option. You could also store a separate hash (HMAC) but this still requires reading the entire contents of the disk to verify (which takes a long time), and will likely cause the hashes to mismatch simply due to normal wear and tear on the drive... Effectively creating a game of Russian Roulette; except instead of getting shot you lose data.
As such, unauthenticated encryption becomes the only rational way to encrypt an entire drive. Since an attacker cannot control the result of changes in XTS it's better than modes like CBC (where an attacker can rewrite the drive to whatever they want simply by being decently clever) or CTR (where cleverness isn't even a prerequisite to tamper with data), and XTS isn't vulnerable to statistical analysis like ECB. Therefore it's a not-ridiculous trade-off for cases where authentication can't be reasonably performed.


Understanding Genkin-Pipman-Tromer's ground potential, side channel attack on RSA I'm pretty sure that by now folks might have come across this research from Genkin-Pipman-Tromer (GPT) on extracting the RSA key used by GnuPG (GPG) just by measuring the ground potential. I'm going to call it the GPT attack on GPG for short. I have done work on extracting informational content of a processor core by studying it's high frequency current draw at power supply source but this is cool because it's a low frequency analysis (i.e. easier to perform).

Their work is at http://www.tau.ac.il/~tromer/handsoff/ and I got lost at Q13, where they point to the frequency components as an indicator of when the exponentiation with the secret primes p and q happen. The spectrograph is sideways (time is vertical and frequency is horizontal) and the 12 yellow arrows show 12 RSA decryption captures where the algorithm switches from the exponentiation of p to the exponentiation of q. I get that.

But then the question (Q14) they immediately have a lovely analog wave showing the final private key bytes (basically p and q)! Here it is:

I recall that a 0 bit in the base to be exponentiated, simplifies the modular exponentiation but that still doesn't explain the jump to the final image showing the secret bits in all their glory.

Question: How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits? I expect that jump is highly dependent on GnuPG's RSA implementation. If you can supplement with the math (informal math ok), bonus points!

PS: Yes, I know they did similar low frequency analysis with the spectrum of acoustic signals emanating from the decrypting chassis. I also suspect this might be due to RSA being partially homomorphic ...

How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits?

Actually, they're jumping to secret bits; however those aren't the secret bits you're thinking of.

The bits displayed above are not the actual bits of $p$ and $q$.  Instead, those are the bits from the secret exponent; because GnuPG uses CRT (and apparently binary exponentiation), those bits are of $d_q = d \bmod p-1$ and $d_q = d \bmod q-1$ (where $d$ is the private exponent).

With the CRT optimization of RSA, we take our message $M$, and divide it into $M_p = M \bmod p$ and $M_q = M \bmod q$.  We then compute $C_p = M_p ^{d_p} \bmod p$ and $C_q = M_q ^{d_q} \bmod q$ separately, and then recompute $C_p$ and $C_q$.  This attack looks at the computation of $M_p ^{d_p} \bmod p$ and $M_q ^{d_q} \bmod q$, and attempts to recover $d_p$ and $d_q$

So, what good are those bits?  Well, those are as good as the actual values $p$ and $q$; with the knowledge of those values (actually, we only need one of the two), and the public key, we can factor.

The actual technique to factor using $d_p$ does use some simple number theory; I'll sketch it out for you: with your known value $d_p = d \bmod p-1$ and the public exponent $e$; because of how RSA works, we have the property that $x^{e \cdot d_p} = x \pmod p$ (for any $x$), while no such relation holds $\pmod q$.  So, what you do is select a random value $r$, and compute $r^{e \cdot d_p} - r \bmod n$.  This value is 0 mod p, and (with high probability) nonzero mod q; hence doing a simple gcd with that value and $n$ gives you the value $p$

  I expect that jump is highly dependent on GnuPG's RSA implementation.

Yes; this sort of attack won't work with more recent implementations (such as OpenSSL), which disguise these sorts of simple side channel attacks.


What is the last value in a cipher suite? I understand that a cipher suite should contain the MAC algorithm at the end.

So ECDHE-RSA-AES128-SHA256 should use SHA256 in HMAC for the MAC.

But what about the PRF? From the RFC this is what I understand: new cipher suites need to include the PRF at the end. The only "new" cipher suites I can think of is AES-GCM: ECDHE-ECDSA-AES128-GCM-SHA256 and here if I understand correctly, since no MAC is used SHA256 refers to the PRF p_SHA256?

I'm confused

HMAC is the underlying primitive used to construct the PRF. The cryptographic hash is used to construct the HMAC.

It is (at least) used to derive the session keys. The only thing that changes is that records that transport the data do not rely on the HMAC function anymore.

The PRF (and therefore the underlying HMAC) has one configuration parameter: the underlying hash function. This is what is specified at the end of the ciphersuite.


Is it better to encrypt before compression or vice versa? Is it better to encrypt a plain text file before compression, or vice versa?

Neither:

Encrypting first and then compressing does not work.
Compressing first can leak information about plaintext content through the ciphertext length, as poncho mentioned in comments to another answer.

Specifically, compression allows an attacker who can control parts of the message that is encrypted to reveal things about the other, secret parts, like cookies in the case of web traffic. It is most dangerous in a live protocol like TLS. Some forms of compression (e.g. truly constant bitrate lossy video/audio compression) may be immune to such attacks (but even then there might be side channel attacks due to the compression).

In most cases you should just encrypt the uncompressed data and be done with it.

Data storage and transmission is usually cheap enough. If you cannot live without compression, you must do it first, but then you have to really know what you are doing and likely accept at least some loss of security.


Hash function from narrower block cipher operated in CBC-encryption mode? I am trying to build a public hash function (thus collision-resistant and preimage-resistant, and more generally behaving like a random oracle), with input a message $M$ of fixed size $|M|=m\cdot b$ bits, and output the hash $H(M)$ of fixed size $|H(M)|=h\cdot b$ bits, using as the single primitive a $b$-bit block cipher with key of $k\cdot b$ bits, operated in CBC-encryption mode.

One of the motivation of the construction is to maintain the confidentiality of the message under DPA attacks, assuming that the implementation of the cipher in CBC-encryption mode is DPA-protected. I thus require that all message-dependent data is manipulated using the $P$ and $K$ inputs of that trusted primitive:
$$F(K,IV,s,P)\to C\text{ with }|K|=k\cdot b,|IV|=b,s>0,|P|=|C|=s\cdot b,$$
$$C[0]=\text{ENC}_K(P[0]\oplus IV), C[j]=\text{ENC}_K(P[j]\oplus C_{j-1})\mathsf{\text{  if }}1\le j<s.$$

I would like security beyond that of the underlying block cipher by a security parameter $q$, with an argument that any attack requires $2^{b\cdot q}$ queries to an encryption or decryption oracle implementing $\text{ENC}$ and the corresponding decryption, for some suitable definition of security/attack which, uh, is part of the question (in particular it seems necessary to restrict the amount of memory usable by the attacker, including but not limited to as a cache for the oracle). Performance is secondary (one envisioned application is a slow KDF), a security argument (or better proof) is a must, simplicity matters.

Assume there is enough memory for the whole message, and then some. Assume at least $\min(b,k\cdot\lceil b/2\rceil)$ bits of the block cipher's key are effective (which rules out simple-DES). A typical setup could be 3DES thus $b=64$, $k=3$, and $m=64$ ($4096$-bit input), $h=8$ ($512$-bit output), $q=4$ (security of $2^{256}$ block cipher queries or memory accesses). Assume $m\ge h>1$, and if that helps assume $m\gg h$ or/and $h\gg k$ or/and $k=1$ (e.g. AES-128, ignoring attacks marginally reducing its effective key size).

What appropriate definition(s) of security are applicable?
I apologize for late realization that this is an issue, and corresponding introduction of security parameter $q$. I now think I want a collision-resistant Universal One-Way Hash Function family per this terminology.

Is there some standard construction that fits?My review of the existing found a few hashes made from block ciphers, but suitable for $h\le2$ only, not neatly constructible from my primitive when $h>1$, and aiming at efficiency rather than a strong security argument.

If nothing standard exists, my simplest candidate is the following CBC-HASH:

assume an arbitrary public parameter $P$ of $p\ge k$ blocks which right $k$ blocks are suitable as an initial key for the cipher ($P$ parameterize the UOWHF family; in the simplest/original setup, $p=k$);
append $P$ to message $M$ forming $X_0$ of $m+p$ blocks $X_0[j]$, that is $M[j]\to X_0[j]\mathsf{\text{  if }}0\le j<m, K[j]\to X_0[m+j]\mathsf{\text{  if }}0\le j<p$;
repeat for $n$ rounds, numbered $r$ from $0$ to $n-1$:

set $K_r$ as the right $k$ blocks of $X_r$, that is $X_r[m+p-k+j]\to K_r[j]\mathsf{\text{  if }}0\le j<k$;
CBC-encipher $X_r$ using key $K_r$ and the $b$-bit big-endian representation of $r$ as $IV$, giving $X_{r+1}$, that is $F(K_r,(r)_b,m+p,X_r)\to X_{r+1}$;

set output $H=H(M)$ as the right $h$ blocks of the left $m$ blocks of $X_n$, that is $X_r[m-h+j]\to H[j]\mathsf{\text{  if }}0\le j<h$.

Now I am wondering how the number of rounds $n$ and the size $p$ of the initial padding shall be chosen from $q$, $h$, $m$, $k$ (perhaps $b$), and the limits on parameters for a security argument.

Can you justify, prove, improve, break, or fix CBC-HASH?The scheme now incorporates parameter $p$ controlling the size of the UOWHF family. I retract an earlier guess on $n$ made without even a clear security definition. I hereby vow to stop modifying this question except for fixing obvious typos; any addition will be an answer.

If the motivation is to rely on a DPA protected implementation of a block cipher, hash function constructions based on a block cipher (think of Davies-Meyer for instance with say Rijndael at 256-bit plaintext) could be used.
Alternatively, the issue of using small input size compression function to built secure hash functions with larger output size has been investigated in e.g. Nandi, INDOCRYPT 2005; Hirose, FSE 2006; Peyrin et al., Asiacrypt 2006 and following work, but is not entirely settled.

From an efficiency point of view, CBC-HASH is going to be at least $n$ times slower than any other hash function in the wild. (And practical security is always a balance between practicality, that is resources, and security.) In addition, the hash cannot be computed on the fly: one has to make $n$ passes over the message which is cumbersome in many scenarii (think embedded devices for instance).

Case $n=1$. Assuming the underlying block cipher is denoted by $E$, take whatever you want for the message blocks $M_i=N_i$, $l>i>1$ for some big $l$ and:

$M_0=0$ and $M_1=E_K(R)$,
$N_0=R$ and $N_1=E_K(0)$.

for some $R\neq 0$ if $IV=0$ and $R=IV$ otherwise.
Then, note that the hash output is the same, so that you have a collision for $M$ and $N$. This is possible because $K$ and $IV$ are known values.

Case $n=2$. Choose some index $\xi$ and choose the message blocks $M_1$, ..., $M_\xi$ and $N_1$, ..., $N_\xi$ randomly and choose the remaining message blocks so that $M_i=N_i$, $i=\xi+1, ..., l$. Then, use the trick above to ensure the key for the next round is identical for both messages (i.e. create a collision at stage $\xi$ during the first pass instead of at the beginning). Then, wait for a collision to happen in the 2-nd round at block $\xi$. It happens with probability
${2^{block\_size/2}}$ for a primitive $E$ with block size $block\_size$. This appears to be possible as the first message blocks are randomly chosen.

Case $n>2$. This procedure can be followed up to any round $n$ with complexity $2^{block\_size*{n-1\over2}}$.

Example.
With the 3DES as $E$ and an hash output size of 512 bits, this leads to a collision attack for CBC-HASH with 8 rounds that has complexity $2^{32\cdot 7}$ instead of the $2^{32*8}$ of the birthday paradox.

I am more generally concerned about the small "bandwidth" issue due to the use of an underlying CBC with a block cipher of small output size.


Zero-knowledge proof for committing a choice? Let's say there are 100 choices (which are publicly known), each represented as a different string, and today you have to choose one of them. You need not reveal what that choice is right now, though. One thing you could do is take your choice, append a bunch of entropy at the end, and publish your signature of the resulting string. Later, to prove that you made a valid choice, you can publish the string, proving that you had decided on that choice by the time you published the signature.

However, this still requires you to ultimately reveal your choice in order for others to verify that you did indeed select one of the 100 choices and didn't try to pass off some garbage string. Is there a zero-knowledge protocol, such that you can let others verify that you indeed chose one of the 100 choices without leaking any information? That is, we want the advantage of an adversary trying to guess your choice to be still only 1/100. If not possible, anything under 1 (which would result from directly revealing your choice) would nonetheless be an improvement.

Below is one possibility, but for a large set of values not a really efficient one as the work and the size is linear in the number of values. I additionally added a variant where the work and proof size is constant.

Standard OR Proof

Say we are working in a cyclic multiplicative group $G$ of prime order $p$ with generators $g$ and $h$ (such that the discrete logarithm between $g$ and $h$ is unknown to the users) and I assume that the values on the list (values $v_i$'s) are elements of $Z_p^*$ (e.g., by hashing the choices if they have a larger representation than values in $Z_p^*$ using a secure hash function).

You could publish an authentic list $(v_1,\ldots,v_{100})$ so everyone can check that these choices are indeed the possible choices or just give it to your users if you want to be the only one verifying the choices of the users.

Then, if a user chooses one out of the 100 possibilities, say $v_i$, the user computes an unconditionally hiding commitment to one of your choices (such that even knowning the 100 choices one cannot figure out which value is hidden in the commitment) as $H=g^{v_i}h^r$ for random $r\in Z_p^*$ (here by using a Pedersen commitment). In addition to $H$ the user publishes a non-interactive honest-verifier zero-knowledge proof of knowledge $\pi$ that the value in his commitment $H$ is equal to one of the values in the list. More precisely, with $\pi$ one proves the statement $$PoK\{(\beta):H=g^{v_1}h^\beta \vee H=g^{v_2}h^\beta \vee \ldots \vee H=g^{v_{100}}h^\beta\}$$ where this is a standard OR composition of discrete logarithm proofs and made non-interactive using the Fiat-Shamir heuristic.

So the user publishes the pair $(H,\pi)$ which convinces any verifier that the prover knows a secret value $r$ (the value $\beta$ in the proof, which is not revaled) such that his commitment $H$ is a commitment to one of the values $(v_1,\ldots,v_{100})$ without revealing which one.

If the user later on wants to open the commitment (reveal the choice) he publishes $(v_i,r)$ and everyone can check whether $H=g^{v_i}h^r$.

Efficient Set Membership Proof

In the above proof, the cost for the prover is $O(n)$ where $n$ is the cardinality of the set of values. You could also use the approach in this paper, which requires the publisher of the list to compute a (Boneh-Boyen) signature to each of the values of the list, i.e., costs of $O(n)$, but the cost for the proof is only $O(1)$, i.e., the prover computes a commitment and proves that he knows a value that has been signed, which can be efficiently done when using Boneh-Boyen signatures. The proof can also be made non-interactive using the Fiat-Shamir heuristic.


Secret-suffix MD5 as secure PRF (not MAC) In standard secret-suffix fashion, assume we compute the PRF of some message $m$ as $MD5(x || k)$. Preneel and Van Oorschot showed in [1] that this secret-suffix method is unsatisfactory for constructing a secure MAC. (Particularly because MD5 is not collision resistant and therefore the scheme is susceptible to forgeries.) But does that also mean this is not a secure PRF?

[1] http://people.scs.carleton.ca/~paulv/papers/Crypto95.pdf

The collision resistance of MD5 is fully broken, for 2 rounds, or even just 1 round. If follows that we can exhibit distinct 1024-bit or even 512-bit  $x_0$, $x_1$ such that for any $k$, $\operatorname{MD5}(x_0||k)=\operatorname{MD5}(x_1||k)$.

This allows to make a near-perfect distinguisher between the PRF (family) parametrized by $k$: $x\to\operatorname{MD5}(x||k)$, and a random oracle; thus breaking that PRF.


Where was the stand-alone model for simulation-based MPC proposed first? The stand-alone model and the UC model for simulation-based proofs in multiparty computation differ in the guarantees that they provide: The stand-alone model provides security under sequential composition whereas the UC model provides security under concurrent composition.

It is typically cited that the UC model originated in a paper by Ran Canetti at FOCS 2001. However, I can't find such citation for the stand-alone model.

  Which work(s) introduced the stand-alone model?

As far as I understand, MPC in the 80s and 90s was not as formal as it is today, and perhaps this model was used but not formally defined. However, I still would like to know where and when the term was coined, and which works used the concept first (without perhaps naming it).

The standard (stand-alone) definitions were developed over many years, including the original GMW, Beaver, Goldwasser-Levin, and Micali-Rogaway. However, the standard definition used today is by Canetti, and was published in the Journal of Cryptology in 2000. That paper also proved the modular sequential composition theorem. Here is a link to that paper: https://eprint.iacr.org/1998/018.

It is worth nothing that the above paper actually only deals with the honest majority setting. However, the changes needed for a dishonest majority are minor and straightforward, and make no difference to the proof of the modular sequential composition theorem.


How to prove I know an x without revealing x or f(x)? Suppose a set of $u_1, u_2, ..., u_N$ users each knows an associated secret $x_1, x_2, ..., x_N$ they do not wish to reveal.  We have a public $f(x)$ such as the discrete logarithm $f(x)=g^x\,\mathrm{mod}\,p$, which produces a set of publicly available values $v = \lbrace f(x_1), f(x_2), ..., f(x_N) \rbrace$ used for verification.  Is there a way for any given $u_i$ to prove that they are in possession of $x_i$ such that $f(x_i) \in v$, without revealing which $f(x_i)$ (or $x_i$), as a means of providing anonymity?  The usual ZKP requires that $x_i$ and $f(x_i)$ are publicly associated.

There is a technique called set membership proof. I am not an expert in this area, but it seems closely related. See the excerpts below:

  Given a set $\Phi=\{\varphi_1,\ldots,\varphi_n\}$ and a commitment $C,$ a typical approach to
  the set membership problem is to use a zero-knowledge proof of the form:

“$C$ is a commitment to the element $\varphi_1$ OR $\ldots$ OR it is a commitment to $\varphi_n$.”

  Even though there exist efficient algebraic $\Sigma$ (Sigma) protocols for handling a single such OR clause, such a proof still has length which is proportional to $n$.
  In many practical situations, the set $\Phi$ is often specified in advance by the verifying party. In other words, $\Phi$ can be considered a common input to both Prover and Verifier, and thus we might ask whether it is possible to prove a commitment is a commitment to an element of $\phi$ without having to explicitly list $\Phi$ in the proof.

The paper Camenisch et al with the above passage is available here, so start by looking at algebraic $\Sigma$ protocols if your $n$ is small, or to their techniques if it is large.


ECC: application of multiple multiplicative inverses I've recently read about "Montgomery trick" on Application of Montgomery's Trick to Scalar Multiplication by Pradeep Kumar Mishra and Palash Sarkar which provides a way to compute several multiplicative inverses at once using this technique:
if x = 1/(ab), then 1/a = xb and 1/b = xa

I've also analyzed various algorithms for computing multiplicative inverse on Modular Inverse Algorithms without Multiplications by Laszlo Hars.
At the top of the page 12 they briefly mention:

Still, in case of elliptic curve cryptography the most straightforward
(affine)   point representation and implementation of the point
addition is the best (the projective, Jacobian and Chudnovsky-Jacobian
coordinates are slower, see [8]).
T

Of course, projective coordinates usually using delayed inverse, but more multiplications per point addition.
Affine coordinates need less total operations, but inverse is calculated at every point addition instead of once at the end.
As I understand, Montgomery trick can eliminate a computation of inverse at every step.
However, I struggle to understand how to apply this technique.
Let's say I have 4 points in affine coordinates on some weierstrass curve.
Affine addition formula requires an inverse of X-coordinate difference between two points. Which means that I can't add all 4 points together with only one inversion.
I could do P1+P2 and P3+P4 with one inversion, but then I need to add P1,2 together with P3,4, which means that another inversion is needed. So at the end it is slower than using projective coordinates, if inverse cost compared to multiplication is high.
I understand how to apply "Mongomery trick" to a case where we calculate a bunch of independent scalar multiplications at once, and then convert all resulting points to affine system using only one inverse. But I don't understand how to use it in a single multiplication which consists of many additions, and if this even possible at all.

Your analysis is pretty much on point. The cost of batch inversion is only justified if we have a computation involving a relatively large number of simultaneous point additions. In a project I work on, we set a threshold of 70 additions based on our benchmarks. Our code is here if you're interested.
To generalize your example a bit, a single summation involving $n$ points could be reduced to one involving $\lceil n/2 \rceil$ points by simultaneously adding pairs of points. So we would need a rather large summation (140 terms in our case), or several simultaneous summations, to justify the cost of inversion. Even then, we would eventually fall back to projective formulas after this reduction shrinks the problem size below our threshold.
In practice, the cost of inversion isn't likely to be justified for single multiplication problems, at least assuming ~256 bit scalars. The affine formulas are quite useful in the multi-scalar setting, though. We use a multi-scalar variant of Yao's method, which involves computing a summation of precomputed points for each digit in $1 \dots 2^w - 1$. Not only are these summations potentially large, they are also independent of one another, so the whole first (and most expensive) phase of the algorithm can be viewed as $2^w - 1$ simultaneous summations.


How does bit-wise operation work for encrypting grayscale images? How does bit-wise operation work for encrypting grayscale images?

In my Khan Academy course they encrypt an image with bitwise_and, bitwise_or and bitwise_xor. I have tried, without success, to replicate their results.

The Khan Academy write-up: https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-and-the-one-time-pad

My results: https://imgur.com/a/ltvj5os

The way I did the operation is this (Python code):

def get_bitwise_image(image, key, op):

    and_image = []
    row=0
    col=0
    while row < len(image):
        new_row = []
        col = 0
        while col < len(image[row]):
            # a bitwise and between say 243 and 1 is bitwise and between 2 intergers and not binaries. So, their constituent bits and and-ed together
            # ex: 1 => 00000001 and 243 => 11110011
            # 00000001
            # 11110011
            # --------
            # 00000001 => 1
            if op == 'and':
                new_row.append(image[row, col] & key[row, col])
            elif op == 'or':
                new_row.append(image[row, col] | key[row, col])
            else:
                new_row.append(image[row, col] ^ key[row, col])
            col += 1
        and_image.append(new_row)
        row+=1
    return and_image

My second image is grayscale with values 0-255, and my key is a matrix of the same dimensions as an image with random 1s and 0s.

Key is defined as: key = numpy.random.randint(0, 2, image.shape)

Why is the Khan Academy's result completely different from mine? How are grayscale images encrypted with bit-wise operations?

I have solved it.

The main reason was that I'm supposed to use LOGICAL operations instead of BITWISE operations.

The new results: https://imgur.com/a/NLa5Q8J

my function:

def logical_xor(message, key, op):
    message = np.asarray(message)
    key = np.asarray(key)
    new_image = []
    row=0
    col=0
    while row < len(message):
        new_row = []
        col = 0
        while col < len(message[row]):
            if op == 'and':
                new_row.append(message[row, col] and key[row, col]) # and instead of &
            elif op == 'or':
                new_row.append(message[row, col] or key[row, col])
            else:
                new_row.append(message[row, col] !=  key[row, col]) # xor
            col += 1
        new_image.append(new_row)
        row+=1
    return new_image

but before using this function, I had to do this:

from PIL import Image
m = Image.open("test_image.jpg") # message
m = m.convert("1") # converts to boolean?


AES s-box – How do I calculate the inverse of this field equation? I want to implement AES algorithm,instead of LUT based S-box, but I’m stuck at point creating "Inverse of equation" during implementation.

In creation of S-box I am using the following steps:

($a_7a_6a_5a_4a_3a_2a_1a_0$) bits converting in to field equation.
Calculating the inverse of the field equation modulo($x^8 + x^4 + x^3 + x + 1$).
Doing the affine transformation.
Return the 8 bits.

In these steps I did not find a way to calculate inverse of the field equation.

Can anyone help me in calculating inverse of equation in Galios field mod($x^8 + x^4 + x^3 + x + 1$)?

In a finite field, there are basically two main algorithms to compute an inverse:

The Extended Euclidean Algorithm, also known as as "extended GCD". There is a variant called Binary GCD. In a finite field of characteristic 2, where addition is bitwise XOR, the binary GCD is easier to implement.
Fermat's little theorem, which is easily generalized: if the field order is $n$ (in your case, $n = 2^8 = 256$), then the inverse of $x$ is $x^{n-2}$, because $x x^{n-2} = x^{n-1} = 1$. This holds because in a field of order $n$, the invertible elements are a multiplicative group of order $n-1$, thus exponentiation by $n-1$ must yield the multiplicative neutral element $1$.

If you already have a multiplication function (mul()), then the exponentiation can be done in relatively few calls to that function. For instance:

static inline unsigned
invPow(unsigned x)
{
        unsigned x2 = mul(x, x);
        unsigned x3 = mul(x, x2);
        unsigned x6 = mul(x3, x3);
        unsigned x12 = mul(x6, x6);
        unsigned x15 = mul(x12, x3);
        unsigned x30 = mul(x15, x15);
        unsigned x60 = mul(x30, x30);
        unsigned x120 = mul(x60, x60);
        unsigned x126 = mul(x120, x6);
        unsigned x127 = mul(x126, x);
        unsigned x254 = mul(x127, x127);
        return x254;
}

In this C function, variables are named out of their contents: x60 contains $x^{60}$. Also note that invPow() returns $0$ for an input of $0$: zero does not have any inverse, but the AES specification formally says that when computing that operation, we use zero as its own "inverse".

Now this will hardly be efficient. You could first precompute a table of inverses, but that would be a look-up table, that you want to avoid.

An optimization is to use a tower of fields: the finite field of size $256$ can be defined as an extension of degree $2$ over the finite field of size $16$. This was described in a succinct note by Rijmen, and allows computing inverses in $\mathbb{F}_{256}$ by doing the relatively simpler task of computing inverses in $\mathbb{F}_{16}$. If you go down that road, you will want to read this article by Boyar and Peralta, who describe the currently best known implementation of the AES S-box in terms of logic gates.

Going down to logic gates is expensive in software, since this means doing more than a hundred boolean operations for each S-box invocation. However, such techniques offer considerable speed-ups if used with bitslicing, especially on machines with large registers. The Käsper-Schwabe implementation is well-known, using 128-bit SSE2 registers. Other similar implementations, using only 32-bit or 64-bit registers, can be found in BearSSL (which also handles the case of the reverse S-box, which is needed for decryption with AES/CBC; the Käsper-Schwabe code supports only the forward S-box, since they target only AES/CTR).


How to decode a (Vigenère?) substitution cipher? I am trying to decode a message that I suspect has been encrypted with a Vigenère cipher:

  Utl zluuocp zsc rvzu hbcp ztvibfz vrabzz utl ilry. Utlal flal cb fbaiz, qszu zbsciz. Utvu cllihl vhzb dvil v zhbf roarsou vabsci vci vabsci vci vabsci, hoyl v zeli-se rhbry. Qvry rhbzli toz lglz uoptuhg oc kaszuavuobc. Vavwlhhv rhscp ub utl avohocp ub dvocuvoc tla wvhvcrl. Qvry tskkli vci dbjli ubfvai utl wbf ftlal Vavwlhhv zubbi zuvaocp bsu bjla utl wbfzeaou. Vavwlhhv ztojlali vz utl pabse dbjli bc ub utl utabcl. Vavwlhhv, utl toz koazu dvul vci v kbadla wvadvoi bc Ubauspv, hvsptli. Ztl hvg zeavfhli oc v fvg utvu dvil tla hbby hoyl v hode avp ibhh. Utl brlvc fvz zuohh vci zohlcu vpvoc, utl bchg zbsciz tlvai flal utl ralvyocp wbvaiz vci utl zhve bk utl fvjlz vpvoczu ouz tshh. Vavwlhhv tvi zluuhli bcub utl ilry, zouuocp rabzz-hlppli fout tla wvry vpvoczu utl kbaldvzu. Utbzl ufb alvhhg val v evoa bk lxrlhhlcu zvohbaz. Sebc iozrbjlaocp utl laaba Zohjla tvi dvil, Hbsoz nsoryhg tvi utl rbby-rsd zsaplbc-rsd-eoavul ubzzli bjlawbvai. Vci kva corla ub wl vu zlv utvc zravdwhocp kba v raszu oc utl abspt-vci-usdwhl ubfc bk Ubauspv. Qvry utalf toz tlvi wvry vci kbaut jobhlcuhg, uagocp ub ztvyl utl zbsci bsu. Tl rabzzli ub utl avoh ub wluula zll toz dvulz. Tl zusry utl zubcl oc toz ebrylu vz v zflhhocp fvjl tllhli utl ilry. Qvry klhu vz utbspt utl zbcp flal vc lcuoug utvu tvi qszu fbsci ouz fvg vrabzz utl ilry vci fvz cbf tlviocp wvry bsu bjla utl fvula. Vavwlhhv ztojlali vz utl pabse dbjli bc ub utl utabcl. Utoz fvz dsrt wluula utvc uavjlhocp vz v zubfvfvg, vz tl tvi wlkbal. Ou fvz hoyl v zbcp, wsu cbu lxvruhg. Qvry vci utl ralf ilklvuli utl cbubaobsz Rveuvoc Ubaalcuz, ftbzl vcpla fvz ulaaowhl. Qvry nsoryhg qsdeli bsu bk utl fvg, ubeehocp ocub Koumfohhovd. Ftohl tl fvz ealevali kba vcbutla wvuuhl, utlg flal zhvry vci alhvxli. Kvocu ztvibfz flal rvzu sebc utl ozhvci wlhbf: tspl, whvry zvohocp ztoez, zlv dbczulaz, vci butla utocpz utvu tvsculi utl doicoptu fvulaz zlldli ub rvzrvil bjla utl tohhz. Vci utlc, utvu butla zbsci vpvoc -- utl wlvsuoksh, tvscuocp, hbjlhg, dviilcocp zbsci. Koumfohhovd pbu se kabd utl cbf-zhoeelag ilry dbal zhbfhg vci rvalkshhg. Ljlag uodl tl gvcyli ou bcl fvg, ou gvcyli ouzlhk wvry utl butla. Tl cllili ub hoptu utl hvculacz. Vz zbbc vz tl rbshi, tl fbshi koci v doaaba. Koumfohhovd pbu se kabd utl cbf-zhoeelag ilry dbal zhbfhg vci rvalkshhg. Qvry ubby oc v ille walvut, vci utl zvhu voa kohhli tod fout v tveeg kllhocp bk vijlcusal. Qvry tbozuli todzlhk se bcub utl wbf vci zfscp toz hlpz vabsci zb utvu utlg ivcphli bc loutla zoil bk utl wbfzeaou--utl hbcp ebhl utvu lxulcili bsu bjla utl fvula. Tl utbsptu ou doptu dvyl v corl eolrl bk qlflhag: dvgwl v clryhvrl ba zbdlutocp. Kvocu ztvibfz flal rvzu sebc utl ozhvci wlhbf: tspl, whvry zvohocp ztoez, zlv dbczulaz, vci butla utocpz utvu tvsculi utl doicoptu fvulaz zlldli ub rvzrvil bjla utl tohhz. Vavwlhhv, utl toz koazu dvul vci v kbadla wvadvoi bc Ubauspv, hvsptli. Utl ralf veelvali ub wl pluuocp wvry ub ouz cbadvh zlhk, vci utlc, zsiilchg, utl zbsci ocralvzli dvaylihg. Qvry fbshi tvjl utbsptu utlg tvi wllc dgzuorvhhg usacli ocub zuvuslz ok utlg flal cbu lvrt vwzlcuhg, hvcpsbabszhg, vci zohlcuhg rbcuocsocp utloa vruojouolz. Utl gbscp zvohba fvz dvyocp viqszudlcuz ub utl vzuabhvwl.

However, even after watching YouTube tutorials and reading from different websites, it still doesn't make sense to me like the Caesar cipher does. I do understand that the Vigenère cipher alternates between multiple Caesar ciphers, but I just don't understand how to decrypt it with no hints.

Could someone give me some kind of a step by step method for breaking ciphers like this?

This is, in fact, not a Vigenère cipher.

One clue to this is the fact that the ciphertext (which, conveniently, includes unenciphered word breaks) contains lots of repeated words like UTL, VCI, V, UB and QVRY that would be very unlikely to occur by chance in the output of a polyalphabetic cipher like Vigenère.

Another clue can be obtained by examining the letter frequency distribution of the ciphertext: while the letters of the alphabet have obviously been scrambled, sorting the letters by their frequency reveals a very similar distribution as unencrypted English text:

L: 305 #############################################################
V: 248 ##################################################
U: 246 #################################################
B: 175 ###################################
Z: 160 ################################
T: 158 ################################
C: 154 ###############################
A: 142 ############################
O: 140 ############################
H: 131 ##########################
I: 121 ########################
S:  77 ###############
R:  72 ##############
F:  63 #############
P:  63 #############
D:  49 ##########
Y:  42 ########
G:  41 ########
W:  41 ########
K:  39 ########
E:  37 #######
J:  22 ####
Q:  14 ###
X:   4 #
M:   3 #
N:   2

Both of these clues suggest that we're probably dealing with a basic monoalphabetic substitution cipher.

So, how do we break a cipher like this?

One way to get started is to guess that the three most common letters in the ciphertext (L, V and U) most likely correspond to the three most common English letters (E, T and A) in some order.

One of those letters, V, occurs several times in the ciphertext as a single-letter word (in fact, it's the only letter that occurs so).  The most common single-letter word in English is the indefinite article "a", so we might guess that the ciphertext letter V probably corresponds to the plaintext letter A.

Meanwhile, the other two most common letters, L and U, occur together in the most common word in the ciphertext, UTL.  As the most common word in English is the definite article "the", and as we've already guessed that L and U probably correspond to E and T (since V is A), it seems very likely that UTL in fact means "the".

This already gives us the following partial cipher alphabet:

plaintext:   abcdefghijklmnopqrstuvwxyz
ciphertext:  V   L  T           U

We might even go out on a limb, and guess that the very common three-letter ciphertext word VCI, which starts with the known plaintext letter A, might correspond to the common three-letter conjunction "and".  But at this point, it's probably a good idea to just try to decode some of the ciphertext using the partial alphabet we've guessed, just to see if it looks reasonable.  Doing this, we get something like:

  the ZettOnP ZSn RaZt HBnP ZhadBFZ aRABZZ the deRY. theAe FeAe nB FBAdZ, QSZt ZBSndZ. that needHe aHZB Dade a ZHBF ROARSOt aABSnd and aABSnd and aABSnd, ...

(Here, the uppercase letters are still undecrypted, while the lowercase ones have been decrypted according to our partial cipher alphabet.)

At this point, we can just start guessing at the partially decrypted words.  For example, "theAe" is probably "there", so A would be R, and "needHe" might be "needle", making H correspond to L, and so on.

Continuing in this manner (and occasionally checking to see if the resulting partial decryption still makes sense), it should be possible to work out the complete cipher alphabet.  I'll leave completing this task as an exercise, since that's what this is presumably meant to be.  I did verify, though, that it is indeed possible to decrypt the entire message in this manner, and that the guesses I've made above for the decryptions of various ciphertext letters are, in fact, correct.  (Note that this will not always be the case in general; sometimes, you do need to backtrack and try different guesses if it turns out that the decrypted message makes no sense after all.)


Is AES-CBC mode not secure against chosen cipher-text attacks even if the IV is not predictable? I've seen questions where people have asked if AES-CBC mode is vulnerable to chosen cipher-text attacks if the IV is predictable.

But is it guaranteed to be secure against chosen cipher text attacks if the IV is not predictable?

No, unpredictable IV won't solve the problem (cihpertext is malleable).

One example to demonstrate the insecurity:

in the CCA game, the adversary sends $m_0,m_1$ to the challenger, and  receive back the ciphertext $c=(r,s)=(r, E_k(r\oplus m_b)$), where $r$ is the random IV.

Then the adversary sends $c'=(r\oplus t,s)$ where $t$ is a random string.

The oracle will decrypts becausee $c'\ne c$, and the adversary now gets
$$
D_k(s)\oplus r\oplus t = D_{k}(E_k(r\oplus m_b))\oplus r\oplus t=m_b\oplus t
$$

The adversary then compute $m_b\oplus t \oplus t =m_b$ and can decide $b$ by comparing the result with the messages it sent.

One way to obtain CCA security is to use a message authentication code and the encrypt-then-mac procedure (authenticated encryption).


XTEA brute force 128 bits key, 64 rounds Is my calculation correct that to bruteforce XTEA with 128 bit key:

https://www.wolframalpha.com/input/?i=number+of+4-permutations+of+4,294,967,295+objects

Would require that many permutations?

Are there any attacks known to bruteforce it or decrypt? Especially in context of RKE (Remote Key Entry)

Thanks,

A 128-bit key contains 2128 possible combinations. Guessing the correct key in an exhaustive search will occur after approximately half that. This is true regardless of what cipher is used. Note that some ciphers are vulnerable to cryptanalysis which creates "shortcuts" to discovering the key. There are no known key recovery attacks against XTEA which can recover the key faster than an exhaustive search, though.


Are common cryptographic hashes bijective when hashing a single block of the same size as the output? It's been said that CRC-64 is bijective for a 64-bit block.

It the corresponding statement true for typical cryptographic hashes, like MD5, SHA-1, SHA-2 or SHA-3?

For example, would SHA-512 be bijective when hashing a single 512 bit block?

It would be very freakish if it turned out to be true. It is not an expected property of SHA-512 to have such bijectivity. It would be worrisome, even, because that's a kind of structure that should not appear in a proper cryptographic hash function.

Actually proving that SHA-512, for 512-bit blocks, is not bijective, would already be a kind of a problem. We do not expect to be able to prove such things without breaking the function.

One "simple" way to prove this would be a single collision (on short inputs), which in theory could be found by chance. But for finding such, we expect to have to calculate about $2^{256}$ hashes (and store/compare them to the other values) to have a non-neglible probability to find a collision.

For example, if I have one zettabyte of fast accessible storage (which would be more than half of humanity's currently stored data), I can store about $2^{62}$ SHA-512 hashes. The probability that between these is at least one duplicate would be about $2^{-389} \approx 10^{-117}$. If every human (around $2^{33}$ in some years) repeats this experiment about once a week (i.e. $2^6$ times a year) with $2^{62}$ new hashes, humanity each year has a chance of $2^{-351}$ of finding a collision. Assuming that humanity  will work on this for 10 times as long as the universe already existed (i.e. 130 billions of years), we get a chance of $2^{-314} \approx 10^{-94}$. For comparison, the probability that a ticket wins the main prize in the German weekly lottery (6/49) is around $2^{-27}$, so the probability that humanity will ever find a collision (in the scenario outlined above) is lower than the probability of me winning the main prize each week, for 11 weeks in sequence (with one ticket per week).

So we can expect collisions to stay hidden until the end of times.


Stronger security definition of PRG By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0\mathbin\|x)=0\mathbin\|G(x)$ and $G'(1\mathbin\|x)=1\mathbin\|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.

This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.

Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?

Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.

There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.


Simulation-based proofs - advice tape of reduction algorithm I am currently reading Yehuda Lindell's amazing tutorial on simulation proof technique and trying to write my own proof for the first time. In page 4 of this tutorial it is mentioned that

  [...] The value $a$ must therefore be written on the advice tape of the reduction algorithm.

and I also knew that $a$ in context of secure computation represents the parties' inputs (as prof. Lindell said in page 3 of the tutorial).

For proving security of oblivious transfer in semi-honest case (page 13), reduction algorithm $A$ is given $\sigma , b_\sigma$ on its advice tape. Could I also give $b_{1-\sigma}$ (other party's input) to $A$ on its advice tape if needed (which is in my case)?

Yes.

We work under the assumption that the protocol is not secure, which means that for infinitely many $n$, there is a pair of inputs $(x,y)$ on which the simulation fails (i.e., when the inputs are $x$ and $y$ the view generated by the simulator for at least one of the parties can be distinguished from a real one). Thus, when running on security parameter $n$, all non-uniform algorithms can be given $(x,y)$ as advice.

By the way, the reason why adversaries are only given $\sigma$ and $b_\sigma$ in this case (instead of $\sigma$ and $(b_\sigma,b_{1-\sigma})$) is that the given simulator always succeeds when $b_{1-\sigma} = 0$, so since we give an input pair where the simulator fails, it must be that $b_{1-\sigma} = 1$ and there is no need to give it explicitly.


Is this EAX extension weakening the (provable) security of EAX? I would like to insert a key deriving function into EAX mode, in order to hamper brute-force attacks for a key-size restricted cipher (56 bits). The modification inserts an identical multi-block pattern $S$ behind the corresponding tweaks:

Original: $OMAC(T||...)$ where the 128-bit tweak $T$ is either 0, 1, 2.

Modification: $OMAC(T||S||...)$

The state of the MAC behind $S$ is different for disjunct tweaks, because the MAC's state behind $S$ can be decrypted back to the original tweak, and identical states would yield identical tweaks.

Is this EAX extension weakening the (provable) security of EAX?

So you want to use EAX with a block cipher with a 56-bit key. Presumably, this is for a good reason.

Your idea is to include a (long!) fixed string in the OMAC to slow down nonce creation. Since the attacker must know the nonce to test if a key is correct, this should also slow down a brute force attack.

Instead of modifying EAX, you could use EAX in a slightly different way: Always prefix the EAX nonce by S, and always prefix the associated data by S. This seems to be equivalent in operation to your proposed modification. I don't think the EAX security proof covers this specific case, but I wouldn't be surprised if it could be adapted to this case. (Probably, you could argue that a random-looking function remains random-looking even when its inputs are restricted.) Which means that this should be ok.

You should note that including S in the associated data doesn't hinder the attacker, only the users of the system. So probably, S should only be included with the EAX nonce.

PS. You need a really good reason to use a 56-bit block cipher today.


How to sign a message using RSA? Assuming I already have a D, P, Q, etc of an RSA key: How do I now sign a message? If it matters – the message is around 100 bits.

I don't know much about cryptography, but I can get these numbers generated by a computer. Unfortunately, in my scenario – I can't use the built-in functions to use these numbers.

IMO implementing RSA yourself is a bad idea. While textbook signing is pretty easy, if you have access to a BigInteger class, you also need to get the padding right. In some use-cases timing attacks are also a problem.

But if you want to go that route, PKCS #1 is the standard you need to implement. It details how the padding should look like.

The text-book RSA signing operation is pretty easy, in principle. Just calculate $m^d \mod n$. Unfortunately without correct use of hashing and padding it's very insecure i.e. you can't use the actual message as $m$, but the padded hash of the message.

I'd look into mono's crypto code. They have purely managed implementations of most .net crypto classes. These should work even if you don't have access to the built in classes.

A few interesting looking classes:

All classes related to RSA in System.Security.Cryptography
RSAManaged

They use the MIT X11 license, which is a permissive open source license.


Is an efficient integer factorisation algorithm a threat to security anymore? Nowadays, private key systems like AES have replaced RSA. Even for digital signatures, people mostly use ECC, so even if an efficient integer factorization algorithm is made, would it be a threat to digital security anymore? Or is this danger just an idea in the past?

AES is a secret-key cryptosystem, and as such can't replace a public-key cryptosystem like RSA, or an ECC-based one.
Examine how the certificate of a web server is signed and you'll see RSA is far from dead, and actually remains king when it comes to static signature of certificates, for excellent reasons. If you look at the present server, not only the certificate is RSA-signed, but the key signed is actually RSA.
Thus yes, an integer factorization algorithm faster than GNFS for balanced biprimes would be a big deal. If it makes factoring a 1984-bit (or even 1536-bit) RSA modulus borderline feasible for well-funded adversaries, or factoring a 1024-bit RSA modulus feasible for more casual hackers, it could be a threat to the current IT infrastructure. 2048-bit RSA is extensively used, or 1984-bit when 255 bytes is a sound barrier, 1536-bit on occasions, and 1024-bit in legacy systems including some door locks (but it's easy to kick these open or sneak in).
I'm far from ruling out we'll see the RSA-1024 (former) challenge openly factored in the next 5 years, or that this size is already factored covertly. I'm ready to bet we'll get there unless a global disaster strikes, and that it won't first be with a quantum computer.

Addition: when RSA is used for encryption, factorization of the public key remains a threat as long as the encrypted data remains of interest and did not leak. Thus even if Post-Quantum Crypto had a fast adoption rate (contrary to human nature of not changing what works unless that's indispensable within a defined time frame), factoring RSA moduli will remain of practical interest decades after.


How can I implement the elliptic curve MOV attack myself? I understand and have implemented elliptic curve signatures in Python without the use of libraries like Sage, and would like to implement the MOV attack against certain weak types of elliptic curves.

Even though I understand the mathematical notation and terms of group theory, I'm a programmer by trade, not a mathematician or cryptographer.  When I read descriptions of the MOV attack, though, I'm completely lost.  The notation and terms are way beyond anything I understand, so I have no idea how to implement MOV.

I understand what $F_p$ and $F_{p^k}$ are about.  I also understand that the idea is to make a function $e()$ of domain $F_p$ and range $F_{p^k}$ in such a way that sets up $x^y = z \pmod {p^k}$, where $y$ happens to be the scalar by which your generator point was point-multiplied.  Then, since this is a traditional multiplication modulo a composite with known prime factorization group, you can do index calculus to get y instead of being limited to slower methods that work on elliptic curve groups.

But how the heck do I calculate this $e()$ function?  I don't understand these "torsion point" and "div() function" concepts at all, especially not in a way that would allow me to write Python code to implement them.

It is all pairings... this is a rather complex matter. I recommend reading Ben Lynn's PhD dissertation; it is about as nice an introductory text on pairings as you can get.

The definition is rather mind-twisting:

You first define divisors, which are rather formal objects. It is the free group of the curve points: for each curve point $P$, you define a divisor $(P)$, and then you add divisors together, so the complete form of a divisor is a linear combination: $\sum_{P\in E} a_P (P)$. This is a formal sum: all the linear combinations are deemed distinct from each other. In particular, $(P+Q)$ (the divisor associated with the point $P+Q$) is not the same as $(P)+(Q)$ (which is the sum of two elementary divisor, and is thus a divisor in its own right, but not associated with a curve point). Each $a_P$ is an integer (possibly negative).
Then you consider rational functions over the curve (these are functions $f = R_1(x,y)/R_2(x,y)$ where $R_1$ and $R_2$ are polynomials, and $(x,y)$ are the coordinates of curve points).
Then you establish a kind of bijection between divisors and rational functions. The function $f$ has zeros (roots of polynomial $R_1$) and poles (roots of polynomial $R_2$): you map $f$ to a divisor $\sum_{P\in E} a_P (P)$ such that:

if $P$ is a zero of multiplicity $n$ then $a_P = n$;
if $P$ is a pole of multiplicity $n'$ then $a_P = -n'$;
otherwise $a_P = 0$.

It so happens that to a given divisor corresponds a unique rational function $f$, up to a multiplicative constant. This is not completely surprising: we know that a polynomial can be rebuilt (up to a multiplicative constant) from knowledge of its roots: if polynomial $T$ has root $t_1$ with multiplicity $2$ and root $t_2$ with multiplicity $3$, then $T = \alpha (X-t_1)^2(X-t_2)^3$ for some constant $\alpha$. Here, this is extended to rational functions, which contain two polynomials, hence the zeros and the poles (our $f$ functions are over two variables $x$ and $y$ instead of one, but the same principle is at work here). We denote the divisor corresponding to function $f$ by $\operatorname{div}(f)$.
Then the really confusing part: for some reason, we begin to apply rational functions to divisors. It took me some time to understand this step. We define a new operation which takes a rational function $f$ and a divisor $D$, and computes $f(D)$. Then magic occurs: for two functions $f$ and $g$, we have $f(\operatorname{div}(g)) = g(\operatorname{div}(f))$ (the "Weil reciprocity").
Then we define the Weil pairing as a quotient of two such applications of functions on divisors. The quotient makes the multiplicative constants disappear, and the result is well-defined.

Then you want to compute the pairing. Mathematically, you would need to build two huge rational functions (the polynomials would have $2^{160}$ or so coefficients, so that's not feasible) and then apply these functions to some divisors (which are equally humongous). However, since we are just interested in the final application result, we can remove a lot of needless complexity, and that's Miller's algorithm.

All of this suppose that you start with a finite field $\mathbb{F}_q$ for some $q$ (a prime or a prime power), then do all computations in some extension field $\mathbb{F}_{q^k}$ for some $k$ called the embedding degree. Theory shows that if your points of interest have order $r$ (a prime number)(points of order $r$ are called $r$-torsion points), then the pairing remains trivial (you get $1$ at the end), until $k$ is "large enough": precisely, the $k$ value at which things get interesting is the smallest $k \geq 2$ such that $r$ divides $q^k-1$ (that the Balasubramanian-Koblitz theorem).

For normal curves, the embedding degree $k$ is ludicrously high (the same order of magnitude as $q$), so you would have to do computations with numbers too large to fit in your computer, or, for that matter, in the Universe taken as a whole. However, if the curve is so that $k$ is small, then the pairing can be computed, and the MOV attack reduces the problem of discrete logarithm on the curve to the problem of discrete logarithm in $\mathbb{F}_{q^k}$, which can be substantially simpler.

In particular, when $q$ is prime and equal to $3$ modulo $4$ and the curve is $Y^2 = X^3+aX$, then $k = 2$. If $q$ is a 256-bit integer, then the MOV attack turns discrete logarithm over a 256-bit curve (infeasible) into discrete logarithm in a 512-bit field (hard but feasible).

Implementing pairings is a deep exploration into non-trivial mathematics. It is enlightening, but daunting. For practical purposes it may be simpler to rely on some existing code, e.g. Ben Lynn's PBC library).

(I am writing all of this from memory, there could be some mistakes. Feel free to fix them.)


Mixing block cipher modes (AES) I'm trying to evaluate some changes to an existing codebase and one question that has come up is the block cipher mode. For legacy reasons we've been using AES in CBC mode, however it's unclear why this decision was made. I'd like to propose moving to GCM, but I'm unsure if this will affect decrypting the data we already have stored.

In general I'm curious if the block mode actually affects the cipher text or if for a given key AES(X) = Y for all block modes.

You cannot decrypt any ciphertext encrypted by CBC using GCM. GCM mode uses CTR mode internally. CTR mode only uses the block cipher only in the encryption direction, while CBC mode relies on AES decrypt. Thus it is impossible to use GCM to decrypt ciphertext encrypted using CBC. You need to use CBC decrypt to retrieve the plaintext.

Instead you should use some kind of protocol version to detect with scheme was used. Then you can distinguish between the ciphertexts and use CBC or GCM where required. Of course you may want to convert the CBC ciphertext to GCM ciphertext anyway - by decrypting and then encrypting the data again, preferably using a different key for GCM encryption.

Introducing a protocol version field is kind of tricky if you've just got the CBC encrypted ciphertext as the ciphertext is indistinguishable from random. That said, the output of CBC mode encryption is always a multiple of the block size (unless ciphertext stealing is used), so you could introduce a version number and make sure that the version, IV and GCM ciphertext are not a multiple of the block size. If you can store the protocol version elsewhere then this should be preferred.

If possible you should try and use a container format such as CMS or PGP instead of trying to invent your own protocol. There are also more lightweight protocols such as Fernet.


AES256 key entropy requirements Is this encryption method sensitive to weak keys? Is there any reference in the NIST on the AES key's entropy? (For example, must it have been generated from a TRNG?)

Can I safely use the Microsoft CAPI for key generation? (pseudorandom number generation)

Am I required to use true random number generation?

AES doesn't require uniformly distributed keys. However, if you have a key with less than 256 bits of entropy, then naturally your keyspace will be smaller than the maximum. Whether or not this is an issue depends on just how few bits you have. The only time a non-random key is bad for AES is when it's chosen very specifically to be harmful, in which case it can be used for a related key attack.

If your input is not uniformly distributed though, the standard technique is to pass it through a hash function like SHA-256 first, which compresses it to 256 uniformly-distributed bits. Or use a KDF.


Is there a feasible way to generate an RSA key manually the same way as it is for an ECC one? In elliptic curves, a private key is just a random number, and one relatively small compared to other crypto systems (256 bits for ECC vs 4096 bits for RSA for example).

Suppose I don't trust hardware random number generators (electronic ones) and I want an auditable way to generate a private key. For elliptic curves, it's feasible to flip a coin 256 times and annotate the results to form a 256 bits random number. You can switch that by an n-sided dice to speed up the process.

Now, for RSA, the key is not just simply a random number. It's a product of two random primes. I don't know the details of how these random primes are found. Are them generated by a random number? If so, how long is this number?

If this number is still long, do you know a feasible way to generate a 4096 bits RSA key manually?

PS: I know it'd take years to do the public key math manually from the private key in both cases. I just want to manually generate the key (in the case of ECC) or key seed (in the case of RSA), so I can plug into 2 completely different air gapped computers and see if the public keys match, which would be a very good signal.

You can pick a 1024-bit prime more or less uniformly at random by flipping only 256 coins.  But there's additional computational cost to it.  Here's a naive algorithm that is deterministic after the initial coin flips:

Flip 256 coins, yielding a bit string $s$.
Compute $p_0 = \operatorname{SHAKE128-1024}(s) \mathbin| 1$ and interpret it as an integer in little-endian bit order.  (The $\cdots \mathbin| 1$ forces it to be odd, saving you the wasted effort of testing a large even number for primality.)
Compute a primality certificate for $p_0$, such as a Pratt certificate (which requires computing the prime factorization of $p_0 - 1$) or a Pocklington–Lehmer certificate (which requires computing half the prime factorization of $p_0 - 1$, up to a composite factor below $\sqrt{p_0 - 1}$) or an Atkin–Goldwasser–Kilian–Morain elliptic curve primality proof certificate (which requires a ~512-bit prime, and doing some arithmetic on an elliptic curve).
If it turns out that $p_0$ is composite, then try again with $p_1 = p_0 \pm 2$, and so on.  If you hit $2^{1024}$ or $2^{1023}$, you probably made a mistake.

Generating an RSA key.
You can use the same 256-bit seed $s$ to pick both prime factors $p$ and $q$ of an RSA modulus $n$, e.g. by splitting the output of $\operatorname{SHAKE128-2048}(s)$ into two 1024-bit integers $p_0$ and $q_0$ instead of step (2).  You will also want to try again with the next candidate if you get $\gcd(e, \operatorname{lcm}(p - 1, q - 1)) \ne 1$, where $e$ is your favorite exponent, which ought to be 3 or 65537 unless you have eclectic taste in exponents.

Efficiency.
There are variations on the theme: you can use trial division to save some work, for instance, or use a fancier faster sequence of trials at small cost to uniformity of the distribution (but be careful or else you might have a billion-euro mistake on your hands).

Obviously, step (3) costs a lot more computation than generating an elliptic-curve scalar uniformly at random, even if you do the rejection sampling necessary to avoid the (negligible) modulo bias.  What's the exchange rate between computation and coin flips?

You can save a lot of computation by doing a fast probabilistic primality test first, like 128 independent Rabin tests, which gives reasonably high confidence that you found a prime, but this costs a lot more coin flips.

If you believe in the extended Riemann hypothesis, you could even avoid the additional coin flips and use a deterministic variant, the Miller test (paywall-free), which is named after the person who first republished the novel result of Russian mathematician М.М. Артюхов in English.  It might even perform better than finding an ECPP certificate.

Choice of prime vs. primality testing.
All this will take quite a lot of effort with the computational power of pen and paper.  But you could write a computer program to do everything past the coin flips in step (1), and feed that computer program the outcomes of your coin flips.  Even if it uses a probabilistic primality test, the choice of the prime will be (unless the primality test goes haywire) a deterministic function of the coin flip outcomes.

With a primality certificate, as a bonus you get a verifiable proof that it is prime, which you can independently verify in case a god with a cosmic ray gun angry at your computational arrogance decided to disrupt your faster-than-pen-and-paper computer.

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


What does this notation means $\mathbb{F}_{2^{-}}$? I have seen various papers to use this notation $\mathbb{F}_{2^{-}}$ to describe the diffusion layer. As for example the permutation in AES (MixColumns).
So, we have a field with order of 2, what does the minus sign means?

I have tried to search for the term in finite fields lectures and papers but none explained what it actually means.

Here are couple of references: (and generally i have seen it used when they discuss about the diffusion layer)

On sbox affine equivalent page2

Progress in Cryptology

The new codebreakers

You've been confused by the placement of the "-".

It's not $\mathbb F_{2^-}$ (Latex: $\mathbb F_{2^-}$), this does not exist. What was actually meant is $\mathbb F_2$-adjective (Latex: $\mathbb F_2$-adjective), where the hyphen binds the field and the adjective (eg "linear" or "affine") to bring more specific meaning to the adjective.

Example:

  [...]with an $\mathbb F_2$-affine permutation[...]

You would have read "with a permutation that is affine in $\mathbb F_{2^-}$" as opposed to the intended meaning of "with a permutation that is affine in $\mathbb F_2$".


How to express difficulty of breaking crypto when writing? When writing for both technical and non-technical readers I find my self naturally wanting to write things such as :

"..therefore it would be impossible to decrypt the data."

When trying to convey the real world difficulty in breaking AES for example.
My question is, what is the most succinct yet correct term for expressing this, both from a work effort perspective and a side-channel one?.
For a pure work effort perspective :

"Computationally infeasible"

Sounds good, but would not take into account side-channel type attacks.
Any appropriate term would need to be technically correct but strong enough so that non-technical readers understand the risk is extremely low.
Thanks

Your technical readers will gloss over the example. If you use this try to use fixed pitch for the large numbers.
The technical term is computationally infeasible. But as an example consider the two numbers:
 7,500,000,000,000,000,000
18,446,000,000,000,000,000

The first is 7.5x1018, the second number is somewhat less than 264.
The first number is a reasonable guess of the number of grains on sand on planet earth. The second is the number of different 64-bit numbers. Trying to check each one would take many very fast computers a very long time. But today, doing so is Giga-flippin’n hard but is still possible given a large budget. Please note that adding a single bit doubles the number of possible values.
The minimum key size for AES is 128 bits. That’s 3.4x1038 possible short keys.
There is some concern that quantum computers may someday be able to break AES if only minimum key sizes are used. AES is often used with 256-bit keys.


What is the idea behind hashing the QueryString in OAuth? In OAuth 1.0a and 2.0 using MAC Authorization, I need to generate a hash of all the QueryString Parameters, which requires normalization (alphabetical ordering) of them.

I'm trying to understand what this offers from a security perspective over just generating a hash of Secret Key + Nonce + Timestamp?

My guess is that the additional entropy makes it harder to brute force the secret key, but I'm not really sure if that is the case.

Does anyone know what QueryString hashing offers in terms of security on top of simpler hashing?

I asked @eranhammer on Twitter and the idea is to protect the URL from tampering.


MD-compliant hashes don't really accept arbitary length input, do they? When people talk about hash functions, they usually say that they accept arbitrary-length input, but if you actually look at the padding (eg MD-strengthening padding), you see it's like M100.000||length where length is the binary representation in bytes or bits. But what if the length is so large that you can't represent it in a single block?

Obviously you can get around this problem by just using the most significant bits, but doesn't this destroy the MD-compliant padding property (which you need in proofs of one-wayness and collision resistance etc, assuming properties of the compression function)?

It depends on the exact Merkle-Damgaard hash.

MD5 will literally take an arbitrary length; that's because the value placed in the padding is actually computed modulo $2^{64}$.

For SHA-1 and the SHA-2 hashes, yes, you are correct; there is an upper bound on the length of the preimages that could potentially be hashed; for SHA-1, SHA-224 and SHA-256, it's $2^{64}-1$ bits; for SHA-384, SHA-512, SHA-512/224 and SHA-512/256, it's $2^{128}-1$ bits.

On the other hand, for all practical purposes, these limits are effectively infinite.  For example, with SHA-1, the limit of $2^{64}-1$ bits, that's $2^{55}$ blocks; even if we were able to the compression function in 10nsec, that means it'd take us over 10 years to hash a single value that size.  It's unlikely that anyone would actually attempt that.