Parameters for ring-LWE I see on eprint that there are many papers suggesting ways to compute parameters for LWE. How can those be used to compute parameters for ring-LWE (assuming that known algorithms solving LWE are the best for solving ring-LWE)?

Specifically, consider the ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$. How can an R-LWE instance $(a, as+e)$ in that ring be transformed into an LWE instance $(A, As+e)$? I am missing in particular how to get $m > n$ linear equations from what appear to be only $n$ linear constraints in the original system.

As mentioned by Peikert in [Pei16]:

*) Ring-LWE is parametrized by a ring $R$ of degree $n$ over $\mathbb{Z}$, a positive integer modulus $q$ defining the quotient ring $R_q=R/qR$, and an error distribution $\mathcal{X}$ over $R$.

**) Left-multiplication by any fixed $a\in R_q$ is a $\mathbb{Z}$-linear function from $R$ to $R_q$, so it can be represented by a square matrix $\mathbf{A}_a \in \mathbb{Z}_q^{n \times n}$, which maps $\mathbb{Z}^n$ to $\mathbb{Z}_q^n$.

For example, for $R=\mathbb{Z}[X]/(X^3+1)$ and $R_5=\mathbb{Z}_5[X]/(X^3+1)$, fix $a=3+2X+4X^2 \in R_5$. For $z=1+10X^2 \in R$, we have:
$$
a.z = 4X^2+2X+3 \in R_5
$$
Now, consider the matrix representation of $a$ and $z$:
$$
\mathbf{A}=\begin{bmatrix}
3 & -4 & -2\\
2 & 3 & -4 \\
4 & 2 & 3
\end{bmatrix} = \begin{bmatrix}
3 & 1 & 3\\
2 & 3 & 1 \\
4 & 2 & 3
\end{bmatrix} \in \mathbb{Z}_5^3
\qquad ; \qquad \mathbf{z}=\begin{bmatrix}
1\\
0 \\
10
\end{bmatrix}$$
We have:
$$
\mathbf{A.z}=\begin{bmatrix}
3 & 1 & 3\\
2 & 3 & 1 \\
4 & 2 & 3
\end{bmatrix}\begin{bmatrix}
1\\
0 \\
10
\end{bmatrix}=\begin{bmatrix}
33\\
12 \\
34
\end{bmatrix}=\begin{bmatrix}
3\\
2 \\
4
\end{bmatrix} \in \mathbb{Z}_5^3
$$
which is the matrix representation of $a.z$.

Now from these results, it is easy to see that each random element $a\in R_q$ corresponds to $n$ $\textit{related}$ (non-independent) vectors $\mathbf{a}\in \mathbb{Z}_q^n$, where $n$ is the degree of the ring $R$ over $\mathbb{Z}$.


What are the possible cryptographic implications of Zhang's proof of the Twin Prime Conjecture? Earlier this year, Yitang Zhang published a proof of a weakened form of the Twin Prime Conjecture. I'm wondering if any of the new mathematical machinery he developed has uses in cryptography or could be adapted for future use in the field.

There are no known applications or implications to cryptography of that mathematical machinery.  I've not seen any suggestion that the machinery would plausibly have implications for cryptography.  The twin primes problem doesn't have any obvious connection to any hardness assumption or problem in cryptography.

(Yes, both Zhang's proof and cryptography have something to do with prime numbers, but that is extremely thin. Much of number theory can say it is somehow related to prime numbers, but only a small fraction of number theory has had applications to cryptography. It'd be like assuming that recent improvements in building fast sailboats for the America's Cup has implications for the possible future availability of an immortality potion, since they both involve fluids.)

In other words, this is about as close to a "No" answer as one is likely to be able to give, given the nature of the question (which makes it very unlikely that you are going to get a definite, resounding no).

Here are some surveys of the mathematics of this result and related results, if you want to take a look for yourself:

https://gilkalai.wordpress.com/2013/09/20/polymath-8-a-success/
http://arxiv.org/pdf/math/0605696v1
https://terrytao.wordpress.com/2013/06/30/bounded-gaps-between-primes-polymath8-a-progress-report/


Is this design of client side encryption secure? I want to build a secure file storage web application. Users should be sure that server doesn't know how to decrypt files so encryption should take place at client side (i.e. in Javascript) and TLS will be used. Also public key cryptography is required as users should have possibility to send files to each other.

I plan to have encryption process like this:

SymmetricKeyAlgo(file, AssymetricPublicKey)

And decryption is:

SymmetricKeyAlgo(encFile, AssymetricPublicKey(EncryptedAssymetricPrivateKey, SlowS2K(password)))

where AssymetricPublicKey, encFile, EncryptedAssymetricPrivateKey are stored at server and all computations (encryption, decryption, hashing) are performed at client.

Output of AssymetricPublicKey(EncryptedAssymetricPrivateKey, SlowS2K(password)) has a prefix that is used to check whether password is valid. Prefix is fixed and is the same for all messages. It's truncated before supplying output to SymmetricKeyAlgo.

It seems that similar scheme is used by OpenPGP.

I know that there are existing OpenPGP implementations in Javascript but they are very large and not widely-used. I feel that it will be better to use more trustworthy cryptographic primitives supplied by SJCL (AES, PKDF2, key generation). But I haven't found trustworthy asymmetric encryption library.

Is this design right? Or should I use full OpenPGP for my purposes? Is there anything else I should think about?

Edit: Public keys aren't secret and can be sent to anyone. Every user has unique username. When Bob wants to send file to Alice, he sends Alice's username to server, server maps this username to public key and returns it to client. Thus Mallory can't trick Bob to send file to her instead of Alice.

It sounds like you're trying to set up a "host-proof" system.
( How can one share information using the 'host-proof' paradigm? ; Encryption scheme for social-network-like data sharing data via untrusted server? ; host-proof etc. ).
Sounds like a fascinating problem.

I'm assuming you're trying to set things up so that no data is stored on the client -- not even encrypted.
(That makes things much more difficult, compared to storing the user's private key on the user's client).

encrypted public keys

All the asymmetric systems I've been involved in are careful to generate the private key inside one box and never, ever let that key outside the box, even in encrypted form.

So I'm a little uncomfortable with storing the (encrypted) private key on the server.
However, I'm almost convinced that is excessive paranoia -- several people I respect seem to think it's OK to let a encrypted form of that private key outside the box -- a private key encrypted using a well-vetted algorithm such as AES, encrypted using a key generated from some key-stretching KDF (S2K) such as scrypt or PKDF2, giving the KDF a long passphrase. (Perhaps What is the harm if I publish an encrypted RSA private key publicly? is a better place to talk about encrypted private keys, and How can one securely generate an asymmetric key pair from a short passphrase? is a better place for comparing "encrypted private keys" to the various other ways of obtaining a private key from a passphrase).

message authentication

You may want to add some sort of message authentication code (MAC) or digital signature to the data.
After you do that, there's really no need for another process to check whether the password (or the key generated from it) is valid (see Sending KCV (key check value) with cipher text , Can I determine if a user has the wrong symmetric encryption key? ).

So your server blindly sends (encrypted) files to any person who requests them?
Then the local client does the check to see if the password(s) that person has are valid are performed locally?
I suspect there may be a better way of handling this.
Perhaps some sort of zero-knowledge challenge-response protocol?

protocol

So when Bob wants to send a message to Alice,

Bob types up his message on his own local machine.
Bob somehow obtains that Alice's public encryption key. (This can be a tricky -- how do you keep Charley from tricking Bob into using Charley's public encryption key?).
Bob encrypts his message with Alice's public encryption key (locally), and then sends the encrypted file to your server
Later, Alice pulls a bunch of files from your server:

her encrypted private key
the file Bob posted
some client code. (This is the really tricky bit -- is there any way for Alice to confirm that this code hasn't been maliciously modified, either modified in-flight while it's being transferred from your host to Alice's machine, or worse -- modified by some malicious attacker who has compromised your host?)

(optional) Alice unplugs her local machine from the Internet
Alice types in her passphrase on her local machine into your client code.
The client code runs Alice's passphrase through a slow KDF to get a (symmetric) key, then uses that (symmetric) key to decrypt her private key, and then uses that private key to decrypt Bob's file. (Typically there's yet another file-specific symmetric key involved in that decryption).
Finally, Alice reads the message Bob typed.

other things to think about

Rather than writing new crypto code from scratch,
you might consider using code that other people have already written, debugged, and vetted for security flaws. a b c d

You seem to think that PKDF2 and AES is better than whatever algorithms were around when OpenPGP was standardized.
Rather than completely writing an entirely new system from scratch,
perhaps it would be better to incrementally improve some OpenPGP implementation
so it supports PKDF2 and other things you feel are important.
Most open-source software writers would be happy to receive your improvements.
OpenPGP files generated according to the latest standards (RFC4880)
already support AES.

You might also think about what people at the security stackexchange say about JavaScript. Often they mention "Javascript Cryptography Considered Harmful".

Perhaps you might find convergent encryption ( convergent-encryption ) interesting.


When did Kerckhoffs's principle become fully accepted in design and practice of modern ciphers? Kerckhoffs's principle is named after a publication over 130 years old. Yet it is still something that is commonly misunderstood and challenged by newcomers to cryptography. This question from Open Source Stack Exchange seems typical, and one answer to it implies that at some point, cryptographers in general "got it" and it has become a cornerstone of modern cipher design.

This seemed interesting to me - was the principle for Kerckhoffs's original paper (originally design principle 2 from a list of 6 according to Wikipedia) broadly accepted from the moment of publishing, or has it taken time, specific events and/or the failure of many electronic designs before attaining its current importance?

I searched for "violations of Kerckhoffs's principle" and found a few modern examples (e.g. MiFare being hacked), where essentially the cipher was weak - and easily understood to be weak at the time it was made - but kept secret in the vain hope that reverse-engineering it would be too much of a challenge. However, I didn't find anything I could relate to history such as a series of "secret" ciphers failing badly in the 1990s for instance. So I'm starting to think the principle really has been well-understood ever since it was published, just not followed in practice by some institutions that should have known better had they asked any cryptanalyst. Therefore one way re-framing my question might be "Has there ever been a time in modern (computer-based) cryptographic practice where Kerckhoffs's principle was not considered as important as it is today?"

I tried to use Google ngrams to get a sense of when terms may have become popular, and didn't notice any spiking, but a steady rise in term frequency for e.g. "security through obscurity" from 1970's to present day. Does that point to use of Kerckhoff's principle as a norm (or even just as a label), due to increased academic study of cryptography? This has been suggested in comments. Is there better evidence for that than my ad-hoc searching?

As I noted in another answer, Auguste Kerckhoffs published his principles in the scientific/academic journal “Journal des sciences militaires, vol. IX, pp. 5–38 in his article "II. DESIDERATA DE LA CRYPTOGRAPHIE MILITAIRE.", Jan. 1883.

So, when you ask since when academics and cryptographers “might” have been accepting (and even applying) those rules, the answer would be: Since the publication of those principles in a scientific journal in 1883, while they gradually gained importance and acceptance during the past 132 years.

Yet, that might be a bit too short and easy as an answer… so let’s dive into some more detail.

From my personal point of view, the statement

  …at some point, cryptographers in general "got it"…

is wrong for two reasons:

As with most innovations and/or publications, “general acceptance” is something which is hard to pin-point. When it comes to Kerckhoffs principles, this is something that happened over time.

It should be remembered that Kerckhoffs was a Dutch linguist, cryptographer, and professor of languages at the École des Hautes Études Commerciales in Paris at the beginning of the 19th century.

Back in his days, “education” was not accessible as it is today and not many of his (more commercially interested) students focussed on cryptography. One could almost say that, generally, people didn’t care about cryptography in a way we do today. So – at first – Kerckhoffs principles were more of military and (limited) academical interest, but not general interest.

There was no point in time where cryptographers suddenly “got it”.

What can be observed is that – while time progressed – people who were involved with cryptography slowly but steadily started to recognize the importance of Kerckhoffs publication.

What can also be observed, is how – at the same time – the cryptographic community slowly shifted from a minority of military strategists and academically interested people, to a rather broad, general public (as we nowadays call it).

Yet, all that spans the past 132 years!

For example: when you dive into crypto-history, you will discover that there are examples of WWI cryptography that actively respected most of his principles.

Same goes for WWII cryptography… even though the most famous WWII crypto device – the Enigma – is a prime counter-example which shows what happens if you ignore Kerckhoffs advice. Nevertheless, we shouldn’t ignore the influence of both world wars in this context.

Also, factors like the electronic revolution, up to the invention of a world wide network we now call “the internet”, definitely added to the general acceptance of some of Kerckhoffs principles (especially, the 2nd one).

No matter which individual influence we pick, they all point at a simple fact: there was no “ugh, Kerckhoffs was correct so let’s all follow his principle(s)” moment in history. Instead, there were several independent points in history which added to the acceptance of his publication and the general acknowledgement of his (eg) 2nd principle.
Let’s talk about the term “cryptographers” in general.

Generally talking about “cryptographers” in this context is pretty misleading, if not wrong all together. The reason is simple: it lacks specific definition. Over 100 years ago, you would be talking about academics and the military. Today, you could be talking about an amateur cryptographer without academic or military background.

We shouldn’t forget that nowadays, everyone can fire up a random search engine and learn about cryptography. 132 years ago, it was not common for “average Joe” to even be able to read.

Also – today, an interested amateur could use his computer at home to find (eg) bias in a cipher like RC4. But you can’t simply compare that to 100 years ago.

Expecting early-1900 “average Joe” to look at (and understand) cryptography is something which can not be expected or even generalized. That evolved just like the knowledge and study of Kerckhoffs principles: during a 132-year timespan, where ideas like “education for everyone” were given birth to.

TL;DR

Wrapping it up: there is no one-time-event that would mark a point where Kerckhoffs principles suddenly got accepted by most cryptographers. At least, history does not show any related ”Eureka” moment.

The knowledge and acceptance of Kerckhoffs’ principles goes hand-in-hand with the (not only academic) study of cryptography; which grew over time thanks to evolving technologies (reaching one of its many highs in the 1970’) and the general progress of modern civilisation during the past 132 years.

I’ld say that – in the broadest sense of possible interpretation – your

  So I'm starting to think the principle really has been well-understood ever since it was published, just not followed in practice by some institutions that should have known better had they asked any cryptanalyst.

is a close-to-correct[*] conclusion.

[*] The reason I wrote “close-to-correct“ is that I personally would’ve avoided using terms like “institutions”. There were ample times where there was no institution, but rather some country’s military, involved. Also, 132 years is a rather long timespan, during which (eg) the job-description “cryptanalyst” didn’t always exist.


Security properties of an encryption scheme built from a PRP and a PRG Note: This was my in-class problem last week and potentially will be on the exam tomorrow. Thus, I want to reconfirm my thoughts so that I'll be ready to face this type of question (if appear) tomorrow.
Question:

Assume I have an encryption where the key is computed using a PRP $P$ and the message is computed using a PRG $G$ so that
$$E(k,m) = ( P(k,r) , G(r) \oplus m )$$
(also given) $k \in K = X = Y = \{0,1\}^n$ and $m \in M = \{0,1\}^{2n}$
$P$ is the PRP, $G$ is the PRG, and $k$ and $m$ are the key and the message belonging to the keyspace $K$ and message space $M$ respectively, and $r$ is a random bitstring.

My thoughts:
First, I say that $E(k,m)$ is not perfectly secure because $|M| > |K|$.
Second, I can argue that $E(k,m)$ is indistinguishable because the message is generated by a PRG (assuming that the seed is independent & uniformly distributed).
Third, I claim that $E(k,m)$ is CPA-Secure too because the PRG makes the message non-deterministic.
Fourth, I think $E(k,m)$ is CCA-Secure too, right?
Please feel free to correct me, I don't mind criticism. I think some of my thoughts are still wrong. I just want to feel ready for the exam.

Fourth, I think $E(k,m)$ is CCA-Secure too, right?

Consider this: what if an attacker takes a valid ciphertext $E(k,m) = ( P(k,r) , G(r) \oplus m )$ and flips a bit, so that it is $P(k, r), G(r) \oplus m \oplus 1$.  What would happen if you gave this altered ciphertext to the decryptor?


Why aren't Complex number fields used in cryptography? Most of the cryptography is limited to use of real integer fields. Complex numbers are seldom used. Is there any reason for it? Wouldn't complex numbers provide more structure?

If there is already some work on this area, I would be happy to learn about it.

Why aren't complex number fields used in cryptography?

If you mean fields of the form $k[i]/(i^2 + 1)$ where $i^2 + 1$ is irreducible over the base field $k$, well, they are!  FourQ is a twisted Edwards curve $-x^2 + y^2 = 1 + d x^2 y^2$ over the quadratic extension field $\mathbb F_{p^2} = \mathbb F_p[i]/(i^2 + 1)$ of Mersenne prime characteristic $p = 2^{127} - 1$, where $$d = 25317048443780598345676279555970305165i + 4205857648805777768770$$ is nonsquare.  FourQ is appealing because it takes advantage of cheap arithmetic modulo a Mersenne prime on a curve together with a cheap endomorphism.  The coordinate field is in a sense the ‘complex’ extension of $\mathbb F_{2^{127} - 1}$ arising by adjoining a square root of $-1$.

(FourQ is not universally appealing: it has a relatively high cofactor, $8\cdot7^2 = 392$, and it does not provide modern standards of twist security, so it's not a drop-in replacement for X25519 or Ed25519.  But it is implemented in practice by Microsoft's FourQlib and probably deployed somewhere.)


What is the benefit of applying the tweak a second time using XTS? I tried to understand the inner working of XTS. What I understood is that it is applying  the tweak two times: once on the plaintext and once on the output.

What is the benefit of applying the tweak on the cipher text also?

XTS works by encrypting each plaintext block with XEX, and specifies which tweak to use.
The benefit of applying the tweak to the blockcipher output is that it makes XEX secure against chosen-ciphertext attacks.

If T is the tweak and E is the underlying blockcipher, we could consider a variant of XEX without the second application of the tweak: $\mathsf{XEX}_\mathsf{weak}(T, X) = E(h(T) \oplus X)$ (where $h$ is the keyed function used to "hash" the tweak and $E$ is the blockcipher). Then decryption would be $\mathsf{XEX}_\mathsf{weak}^{-1}(T, Y) = E^{-1}(Y) \oplus h(T)$. But this would imply that for any T, Y, and Y', $\mathsf{XEX}_\mathsf{weak}^{-1}(T, Y') \oplus \mathsf{XEX}_\mathsf{weak}^{-1}(T, Y) = E^{-1}(Y) \oplus E^{-1}(Y)$ --- the $h(T)$ terms cancel out because of the way XOR works. This is a problem because the right-hand side doesn't depend on the tweak; tweakable ciphers should look like a family of unrelated random permutations, one permutation for each tweak, but the above equality is structural and predictable.

So if an attacker were to change the first two blocks of each sector to Y and Y', he could guarantee that the corresponding two plaintext blocks would always XOR to the same constant. It's hard to see how this would result in a practical attack (although I'm sure someone imaginative could find a contrived example). That being said, in crypto we generally try to avoid saying things like, "Oh, that'll never matter" and instead try to make algorithms that remain secure regardless of context. Plus, you can't be sure you've found all the attacks unless you prove that none exist. Applying the second tweak lets us prove that there are no efficient chosen-ciphertext or chosen-plaintext attacks against XEX.


Using Pollard's lambda in a key-recovery attack on DH I've become interested in writing an exploit for the OpenSSL vulnerability here (CVE-2016-0701). Running through the bullets describing the attack, I can follow up to the last bullet point.

Reviewing the referenced paper, Key Recovery Attack on DH Small subgroups, I find myself in a similar position.

The Chinese Remainder Theorem, according to Wikipedia, will return me an 'x'. If I have read the reference paper correctly, this will either be the whole of the secret 'x' if x is short enough, or it will be 'bits of x'.

Both the blog and paper seem to hand wave through "and then you can use Pollard's Lambda to recover the rest". The Wikipedia for Pollards Lambda describes it as finding the x in g^x = y, with a given g and y.

I've eventually researched this down to a further paper, as per page 338 of "On Diffie Hellman Key Agreement with Short Exponents", image below:

I can somewhat see the 'g' value required based on this, but it simply tells a user to "calculate y*", a calculation which itself appears to require several unknown values.

This could well be an issue of how I'm reading things, as I'm much better notation seen in code than in maths.

If someone could assist with what values are meant to come out of CRT and be be fed into the Pollard's Lambda function (of which there are several implementations floating around), it would be appreciated.

it simply tells a user to "calculate $y^*$", a calculation which itself appears to require several unknown values

Nope, it has $y^* = y / g^V$, where at this point, you know $y$, $g$ and $V$.

The original discrete log problem was given as $y = g^x$, and so you were given $y$ and $g$

In addition, $V = x \bmod z$, where $z$ is a smooth factor of $n$ (the group order, which the algorithm assumes you know). You can find the value of $V$ by taking the group order $n$, doing a partial factorization to obtain $z$ (even if it is infeasible to complete factor $n$, it's easy to find the small factors of $n$), and then by solving the Discrete Log problem $y' = g'^V$, where $g' = g^{n/z}$ and $y' = y^{n/z}$.  This particular Discrete Log problem can easily be solved by the Pohlig-Hellman algorithm, as $g'$ is in a subgroup of order $z$, which is smooth.


Counter Mode in Advanced Encryption Standard(AES) Algorithm In Advanced Encryption Standard, if I used "Counter Mode", how should I handle the nonce? Should I divide the nonce value into two? For example: I have 128-bit of nonce, should I divide it so I get two parts with 64-bit each?

The first 64-bit is my chosen nonce value (for example a0a1a2a3a4a5a6a7) and the second 64-bit is the counter (for example 0000000000000001). Is this correct?

In the sequence of the counter, does it work like the following?

0000000000000001,
0000000000000002,
...
000000000000000f,
0000000000000010,
0000000000000011,
...
00000000000000ff

And… after 00000000000000ff, what is the next counter value? Is it 000000000000ff00, followed up like this?

000000000000ff01
000000000000ff02
000000000000ff03
000000000000ff04

Yes, that's correct assuming you have, say:

0x347ABCD98....000000001
       |             |
       |             --- Counter (64-bit width)
       |
       ----------------- 64-bit nonce prefix

What you're trying to do is ensure that each 128-bit AES block is xor'd with a different value.

The reason for this is that, if you take typical AES, you have a key schedule which expands your key size to a longer stream that appears random. However, should your data repeat and the values of the key schedule repeat, you'll effectively begin to see patterns.

Using a unique counter essentially attempts to ensure that no plaintext blocks ever repeat for the same key - taking any two plaintext blocks and xoring them with an ever increasing value guarantees that. The block cipher primitive guarantees your secrecy, so the result should be a stronger than ECB cipher.

There are two obvious caveats to what I've just said, however:

Each IV must be unique per key. If it isn't, then you run the chance of generating patterns over a sufficiently large collection of ciphertexts. See this answer.
Each nonce (generated from the IV + counter) must be unique.

With a 64-bit split in the field, you effectively give yourself $2^{64}$ possible uses of a key and a maximum stream length of $2^{64}$ 128-bit (that's $2^{64}*16$ bytes) blocks - which when you work this out should be more than enough storage space and key uses

The split I'm talking about here is actually in general hypothetical. If you're only ever using the key once, you could use the entire space.


Is PKCS #1 v1.5 RSA encryption padding secure under these conditions? The PKCS #1 v1.5 padding scheme for RSA has been proven to have some weakness when used with TLS for example.

My question is: is it still secure under the following conditions?

Alice sends a message to Bob encrypted with RSA using PKCS #1 v1.5 padding scheme.
If Bob figures out that the message is correct, he will send an answering message back to Alice, otherwise, he will discard the message and won't send anything to Alice. Alice cannot know if Bob accepted the message nor how much it took to bob to decrypt it (and this makes timing attacks impossibile) because Bob may decrypt it after one day, one week or one year.

Though Bob may potentially delay his response by one year or more, the attacker may probably assume that, in practice, Bob will respond rather promptly. Thus, an active attacker can infer from Bob's response, or lack thereof, whether decryption occurred or not. This is a setup where Bleichenbacher's attack seems to apply.

However, one must take the fine print into account: Bleichenbacher's attack works by knowing whether, upon decryption, Bob found a seemingly correct padding, i.e. one that begins with the two bytes 0x00 0x02. When Bob finds that padding, he will then extract the "message" by removing the leading non-zero bytes (after the 0x02), which are supposed to be random padding bytes, as per PKCS#1 specification. In the case of Bleichenbacher's attack, the message will then be random junk.

If your setup is exactly the following:

Bob decrypts the incoming sequences of bytes with the RSA modular exponentiation;
if the exponentiation result does not begin with 0x00 0x02, Bob does not respond;
otherwise, Bob always respond, possibly with a "Alice, you sent me random junk";

Then Bleichenbacher's attack applies.

However, if Bob does the following:

Bob decrypts the incoming sequences of bytes with the RSA modular exponentiation;
if the exponentiation result does not begin with 0x00 0x02, Bob does not respond;
if the message, after padding removal, does not make any sense, then Bob does not respond;
otherwise, Bob always responds;

Then Bleichenbacher's attack may be thwarted, or not, depending on the exact notion of "make sense". For instance, if Bob expects each message to have the format m||SHA-1(m) (concatenation of the message itself and its hash with SHA-1), and won't respond if the hash does not match, then Bleichenbacher's attack won't be feasible.

Note that I do not claim that PKCS#1 v1.5 is secure. To my knowledge, we have no proof of security of PKCS#1 except the usual criterion: the scheme has been widely used from quite some time, and Bleichenbacher's attack is the best attack that has been found. So far.


Decrypting messages crypted with one time pad (used more than once) I have a stream cipher with a key (that is unknown to me) that is used more than once. Messages are ciphered in this way:

ciphered_message = message XOR key

Let's assume that I have 23 messages (all ciphered with same key) and
the original messages contain only upper and lower case letters and spaces.

I've understood that if you xor a space with a space the result is zero, and if you do Letter uppercase xor Space = Letter lowercase (and vice-versa).

I have to get the original messages (at least a part...). How can I do that?
I have to use frequency analysis, right?
I'm trying to write some code but I'm stuck!

import binascii

def xor(a, b):
    return bytes(x ^ y for (x, y) in zip(a, b))

def read_msgs(input_filename):
    try:
        with open(input_filename) as f:
            rawmsgs = f.read().splitlines()
    except Exception as e:
        raise Exception("Cannot read {}, error={}".format(input_filename, e))

    return [ binascii.unhexlify(m) for m in rawmsgs ] # each message is an array of byte

def xor_all_msgs( messages ): # return a matrix, first row is the first message xored with the others
    ret= []

    for current_msg in messages: # xor message "current_msg" with the others
        xor_with_current= [ xor(current_msg, other_msg) for other_msg in messages if current_msg is not other_msg ]
        ret.append(xor_with_current)

    return ret

def xor_is_space( c ):
    return (ord('a') <= c <= ord('z')) or (ord('A') <= c <= ord('Z'))

def main():
    msgs= read_msgs("ciphertexts.txt")
    xor_all_msgs(msgs)

if __name__ == "__main__":
    main()

First of all, there is nothing really special about spaces. It is a fact of how the ascii encoding is put together that e.g. chr(ord('a') ^ ord(' ')) = 'A' and vice versa. Your code should just xor things together and not try to do anything special if the key character is a space.

4 important properties of xor are:

1) a xor 0 = a
2) a xor b = b xor a
3) a xor a = 0
4) a xor (b xor c) = (a xor b) xor c

(i.e. xor gives rise to an Abelian group where every element is its own inverse).

This implies that if a and b are both encrypted by the same k, to get cipher texts a xor k and b xor k, then if you xor the two cipher texts together you get:

(a xor k ) xor (b xor k) = (a xor b) xor (k xor k)
                         = (a xor b) xor 0
                         = a xor b

k drops out leaving you with a encrypted by b.

Now -- if you have 23 ciphertexts, xor the last 22 with the first one. The result is now 22 new ciphertexts encrypted with the same key (where the first albeit unkown plaintext is the common key). At first this seems pointless -- but note now that the key is far from random whereas the original key was likely to be random. You are assuming something about the alphabet the first message is written in and are hoping that it should have a reasonably common frequency profile.

What you can do is the following -- and this can be automated in Python: For each character position in message 1, pick the character in 'a'-'z','A'-'Z',' ' which renders the statistical profile of the characters at that position in the remaining 22 cipher texts as close to English as possible. As a simple expedient, pick the character which maximizes the count of the 4 or 5 most common letters in the English language (or whatever natural language is being used). This gives you a tentative decryption of message 1. It is almost certainly wrong -- but there should be more than enough for you to guess most of the words in it -- and you have 22 ways to verify each guess. Further more, as more and more words in message 1 fall into place, you start getting trial decryptions of the remaining 22 messages, including words that you can guess and that shed light on any portions of the first message that are still known. Once the dominoes start falling, they should fall quite rapidly.

One possible use of the observation concerning spaces is that, since lower case letters are much more common that upper case letters, if after you get your 22 messages encrypted with the first one, if you see any position in which the overwhelming majority of the 22 characters in that position are upper case, it is somewhat likely that the corresponding position in the first message is a blank, which could help you guess where the word boundaries in the first message is. Also -- I have been assuming that all messages are the same length. Obviously things are slightly more complicated if the messages are of variable length, though these sorts of idea will still work (though the longest message would likely have a tail which in incapable of decryption).


Safe generation of $k$ points on a curve such that the mutual discrete logs are hard? I have a multiplicative group $G$ of prime order $p$ implemented using a twisted Edwards curve (similar to Ed25519).

I want to compute a set of $k$ distinct points $P_1,...,P_k$ that generate $G$, such that the mutual discrete logarithms of these points are hard to compute. I.e., for any distinct $P_i,P_j\in \{P_1,...,P_k\}$ it should be hard to find $s$ such that $P_i=s\cdot P_j$.

To obtain such a point $P_i$, I do the following steps:

I select $y$,
I use $y$ to compute $x$,
I verify if $(x,y)$ is on the curve,
I verify if the order of $(x,y)$ is $p$.

If $(x,y)$ is not valid, I retry with a different $y$. I repeat this process until I have found my $k$ points.

My question:

Can I generate the points by simply increasing $y$ (e.g., $y=3,4,5,...$) or will this affect the security if the $y$ coordinates of all my points are in a very small range?

It would be more confidence-inspiring to choose a hash-to-curve method and pass consecutive integers through that.  There is a current (2019-05-16) internet-draft surveying hash-to-curve techniques with references, draft-irtf-cfrg-hash-to-curve.  The most popular method for Ed25519 is Elligator 2.  Since invertibility is not required for your application, you could also just use the hash-and-pray technique: for each $i$, find the smallest $j$ such that $H(i) + j$ is an $x$ coordinate on the curve, where $H(x)$ is (say) $\operatorname{SHAKE128-512}(x) \bmod{2^{255} - 19}$.


Is packing an executable just like encrypting it? What's the difference between encrypting a file and packing it?

Can I encrypt a file that is already packed? Can I pack a file that is already encrypted, or does packing already do both?

If I pack a .exe file will it be considered as encrypted?

No, packing an executable is not just like encrypting it. The difference is that to use an encrypted executable, a secret key/passphrase is necessary, beyond the method/program to do the decryption (typically public, sometime embedded). By contrast, no key is required to run a packed executable, and how to use it often reduces to: just run it as usual; a clever piece of built-in code (a self-decompressing header) will do the rest.

Yes, you can (and it is common to) encrypt a file that is already packed/compressed, including an executable, including a self-decompressing executable, perhaps even producing a self-decrypting-then-decompressing executable; however the latter is not recommendable: it works in a world of fairy where executable file format is clearly defined, is respected by the self-decompressing header, and does not trigger a bug in the self-decrypting header.

There's nothing to prevent you from trying to pack/compress a file that is already encrypted (except if you want the result directly executable and the fairy did not bless, see above). However, that will often increase the size. There are exceptions: for example, if the encryption used ASCII armor, and the packing does not, there will likely be a moderate size gain.

Some programs pack/compress, some encrypt, some do both in one use (these are typically encryption programs happening to use compression; e.g. PGP/GPG). That's true both for general files, and when it comes to executables that remain directly executable (typically, after entering a passphrase/key if encryption was performed).

From the standpoint of cryptography, packing/compression is not encryption. A virus checker, security auditor, or perhaps customs officer, might nevertheless treat a packed file or executable as if it was encrypted, on the grounds that it is not as easily amenable to scrutiny as if it was not packed, or just as the result of some poor choice.


Do reversible black box obfuscators exist? We shall say that an obfuscator $\mathcal{O}$ is a reversible black box obfuscator if for each reversible program $P$ the obfuscated program $\mathcal{O}(P)$ is still reversible but does not reveal any more information than an oracle that computes $x\mapsto P(x)$ along with an oracle that computes $x\mapsto P^{-1}(x)$. It is well-known that black box obfuscators do not exist. Do reversible black box obfuscators exist?

By "reversible program" I assume you mean an injective function.

The answer to your question is no, there is no black-box obfuscator for the set of injective functions.

The idea is to make an unobfuscatable function invertible using the Feistel trick. More formally, if $g: \{0,1\}^n \to \{0,1\}^n$ define $Feistel_g : \{0,1\}^{2n} \to \{0,1\}^{2n}$ as

$$Feistel_g(x,y) = (x, g(x) \oplus y).$$

$Feistel_g$ is invertible regardless of $g$ (and a similar thing works when the input/output lengths of $g$ are different).

Let $\mathcal{G}$ be the unobfuscatable function family from the Barak et al paper. Then define

$$Feistel_\mathcal{G} = \{ Feistel_g \mid g \in \mathcal{G} \}$$

Then this family consists of only invertible functions. Furthermore it is black-box unobfuscatable because black-box access to $g$ can be simulated given black-box access to $Feistel_g$ (and vice-versa). And oracle access to  $(Feistel_g)^{-1}$ is redundant since $Feistel_g$ is its own inverse.


Generate RSA-2048 private key for a VERY fast decryption (don't care if it will be unsecure) Given public standard RSA exponent e = 65537,
is there any (d, n) pairs so that RSA decryption becomes a trivial operation?

The modulus n must be no less than 2048-bit. The goal is to get a real certificate for some internal server that must send same data both via http and https. Certificate authorities will check modulus length. But some of them can possibly accept other e values so it can be a viable option too.

Note: security is not a factor at all, only simplicity\speed matters (trivial complexity will be an ideal).


difference between soundness in ZKPoK and special soundness for sigma proofs What is the difference between
soundness in ZKPoK and
special soundness for sigma proofs?

Soundness usually means "you can't prove a false statement". There are different ways to formalise this but usually the probability of an efficient algorithm coming up with a false statement and a proof that verifies is negligible in some parameter (such as the length of the statement). Soundness can be defined for any proof scheme, including ones that are not sigma protocols.

Special soundness is a particular property of sigma protocols. It implies soundness (the chance of making a false proof is at most the inverse of the size of the challenge space) but it implies a lot more, as it can be used to show that sigma protocols are proofs of knowledge.


Distributed integer factorization? I'm looking around for publicly published work on factorization of large numbers using distributed systems of any kind. So far I've come across the PDF "Mapreduce for integer factorization" by Javier Tordable" which looks like an interesting read.

Are there any papers in particular that I should be reading?

Last year the paper Factoring as a Service was published, where Amazon EC2 is used to factorize a 512bit RSA modulus in just four hours for $75.
As far as I know, that is currently the fastest/cheapest approach actually used.


Can AES ans SHA-2 algorithms be implemented in parallel? As I understood AES GCM mode of operation gets good performance result because parallel execution of both encryption and hashing part.

Why AES and SHA-2 computation cannot be pipelined ?

They can be computed in parallel.

But what would still make AES-GCM faster than AES-SHA2 is GCM itself.

GCM is a universal hash function: it can be very fast, especially on CPUs supporting carry-less multiplications.
But it doesn't satisfy the same properties as a hash function such as SHA2. In particular, not encrypting its output would have catastrophic implications. It's fast because it is a simple and specialized function.

Even with Intel and ARM SHA extensions, I doubt it would be faster than GCM.

With AESNI and CLMUL, AES-GCM is about 0.65 cpb. SHA256 alone using Intel extension is about 3.8 cpb.


Is it reasonable to assure that p-1 and q-1 aren't smooth? I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question:

How complicated is it to check whether $p-1$ is smooth? (And how is it done?)

Knowing the complexity of finding out, is it reasonable to actually check?
For instance, does OpenSSL perform this check?

I assume that the chance of hitting smooth $p-1$ among $512$-bit primes (for RSA1024) is pretty low to begin with. Is it?

Checking for smoothness can be computationally expensive, depending on the size of the "small" primes (there is no "natural" definition of "small", one has to define an arbitrary limit). Also, it is not really useful.

The need for non-smooth integers comes from the $p-1$ factorization method. Let $n = pq$ be a RSA modulus that we wish to factor. Now suppose that $x$ is an integer which is a multiple of $p-1$, but not $q-1$. For an integer $v$ relatively prime to $n$ (e.g. $v = 2$), this means that $v^x = 1 \mod p$ but $v^x \neq 1 \mod q$. By the Chinese Remainder Theorem, this implies that $w = v^x - 1 \mod n$ is a multiple of $p$ but not of $q$. A simple GCD computation between $w$ and $n$ then reveals $p$, a prime factor of $n$.

So the $p-1$ factorization method is about assuming that $p$ (or $q$) is such that $p-1$ is $B$-smooth for some limit $B$. Then things go thus:

Set $w \leftarrow 2$.
For all primes $r$ lower than $B$, compute $w \leftarrow w^{r^{z_r}} \mod n$, where $z_r = \lfloor \frac{\log B}{\log r} \rfloor$.
Compute the GCD of $w$ and $n$.

One way to see this method is the following: when we compute modulo $n$, by the CRT, we are actually computing modulo $p$ and modulo $q$ simultaneously. We do multiplications, so we work with two multiplicative groups, the non-zero integers modulo $p$ and the non-zero integers modulo $q$. The goal of the attacker is to find a multiple of the order of one of these two groups. The two groups have orders $p-1$ and $q-1$, respectively. If one of these two orders is $B$-smooth, the algorithm above will work with high probability (there are a few pathological cases where this does not work, due to the condition on $z_r$, but success probability is close to $1-(1/B)$).

This explains the prohibition against smooth $p-1$ and $q-1$. Note, though, that this depends on $B$: $B$ represents the effort that the attacker is ready to invest in the computation. A larger $B$ implies a more expensive attack, but also a more expensive test of non-smoothness, because the best known method for testing $B$-smoothness is trying to divide by all primes lower than $B$: this is somewhat faster than running the $p-1$ factorization method, but not by much. So to defeat an attacker ready to invest one month worth of computation with a dozen PC, we have to do ourselves a check which will take several hours one one PC.

Checking for smoothness is not useful because of the Elliptic Curve Method. ECM is an extension of the $p-1$ method. We again compute things modulo $n$, so that we are working, through the CRT, with two groups, one using integers modulo $p$, the other modulo $q$; and we still hope to hit a $x$ which is multiple of the order of one of the groups.

The groups, in ECM, are randomly chosen elliptic curves. The group law (usually denoted with an addition sign, but that's purely conventional) is weird but can be computed reasonably efficiently through a handful of operations modulo $n$. The interesting point is that when working with integers modulo $p$ (a prime), the order of an elliptic curve modulo $p$ is an integer $f = p+1-t$ where $t$ is called the "trace" and Hasse's theorem states that $|t| \leq 2\sqrt{p}$. So the order of a curve modulo $p$ is "close" to $p$, but still lies in a relatively large range surrounding $p$, and it so happens that a randomly chosen elliptic curve will have an order distributed fairly uniformly in that range.

So the ECM method works by selecting a random curve modulo $n$ (which implicitly selects two random sub-curves, one modulo $p$ and one modulo $q$), assuming that the order of one of these curves is $B$-smooth, and running the same algorithm than for the $p-1$ method, except that we use curve point additions instead of multiplications. If the algorithm fails (the final GCD yields 1), then we can start again with a new random curve.

The ECM method works as long as a randomly selected integer in the range around $p$ (of size $4\sqrt{p}$) has a non-negligible probability of being $B$-smooth from some value $B$ such that the "for all primes lower than $B$" step is computationally feasible. In other words, the RSA modulus will be secure only if the probability of a random integer of the size of $p$ (half the target size of the modulus) of being $B$-smooth is low enough.

Thus, due to ECM, we already rely on the non-smoothness of a random integer. It thus makes little sense to spend CPU cycles on checking $p-1$ specifically: even if we carefully avoid $p$ such that $p-1$ is $B$-smooth, this gains nothing about the probability of a random integer of the size of $p$ to be $B$-smooth. We still need that probability to be negligible, which is achieved by using large enough primes.

Probability of smoothness can be estimated with the de Bruijn function. But, given the discussion above, it is more practical to look at factorization records with ECM. Efficiency of ECM largely depends on the size of the smallest prime factor of the attacked integer -- that's the factor which the ECM finds. The largest factor ever found through ECM is close to $1.8*10^{73}$, i.e. a 244-bit integer. We can thus estimate that 244-bit integers have a probability of smoothness which is high enough for the ECM to work, but larger integers do not. For a 1024-bit RSA key, we use 512-bit prime factors, more than twice that record size. So we can say with some confidence that a random 512-bit integer is sufficiently non-smooth with overwhelming probability, thus "secure enough" for RSA. No need to test.


SSL certificate / SSL configuration - FIPS-197 compliance What does it mean when we talk about FIPS-197 compliance in the context of SSL certificates, their deployment and usage ?

I am almost certain that the FIPS-197 compliance in the context of SSL configuration is not about how the certificate is generated and signed but rather about how the web server / application server(Eg: Jetty / Apache / Nginx / JBOSS etc) are configured. By configured, I mean to say - the SSL / TLS version that is being used and specifically the CipherSuites that are in the allowed list and their order.

This document has the recommended CipherSuites. My understanding says that if we ensure that the client and Server negotiate a CipherSuite that uses AES for confidentiality (Eg: TLS_RSA_WITH_AES_128_CBC_SHA, TLS_RSA_WITH_AES_256_CBC_SHA) then SSL configuration is FIPS-197 compliant. Is my understanding correct ?

OR Is there anything required during the certificate generation process as well to ensure compliance with FIPS-197.

I am kind of confident about my understanding but just want to be sure.

FIPS 197 is the AES specification. An implementation complies with it if, and only if, it correctly implements the AES algorithm. The standard applies only to implementations of AES; it doesn't apply to certificates, or TLS server configurations, or computer systems in general. In particular, since it only applies to implementations of AES, it doesn't actually require that you use AES at any point in your system. Other FIPS apply to broader things (e.g. FIPS 140-2 applies to cryptographic modules) and do specify acceptable algorithms to use, but the algorithm specification itself just tells you how the algorithm works.

Unlike FIPS 140-2, FIPS 197 compliance isn't a big deal. It just means whoever coded the AES implementation did it correctly; it doesn't even mean they did so securely.


Question about use of IV in this cipher Main cipher objective : Generate a keyed CSPRN stream, that does not expose useful information about the state of the CSPRNG, and xor this with the plaintext. To prevent an attacked who could somehow recover state or key information from one ciphertext from using this on other ciphertexts, a "random section", here called an IV, is appended to the original key, before it is scheduled (hashed into the state of the CSPRNG).

The question concerns one final part of the algorithm not mentioned above : to transmit this "once generated" IV, it is encrypted with the original key (after scheduling the original key into the state of the CSPRNG), and appended to the output. How secure is this formulation ? Where original key is used 1 time to encrypt the random IV, and a novel key formed from original key + unencrypted IV is used 1 time to encrypt plaintext ?

As a list of instructions, the use of the IV proceeds like this :

Generate 37 random 32 bit integers
Pack these into bytes
Using the user key (which has been scheduled), encrypt these bytes, so the IV can be saved to file
Concatenate the original (unscheduled) user key with the unencrypted IV bytes
Reschedule this key, to give the final state of the stream generator before encryption

The encryption combination function is symmetric, just xor.

Different modes of operation have different requirements. For example, the IV for CBC mode should be generated with a CSPRNG, where as the IV for CTR mode just needs to be unique for each encryption.  In terms of cryptography, the 'random' functions found in many languages are more predictable than you might imagine.

That being said, there's absolutely no need to encrypt your IV.  It doesn't need to be secret, and can be transmitted/stored as clear text.

Encrypting the IV might add some level of security, but if you plan to do that then you should use a key which is independent of the key used for the initial encryption.  Independent not only means unique, it also means that it's derived from a different source (which can make things unnecessarily complicated).


Is it possible to make time-locked encrytion algorithm? I'm not sure if what I'm asking is even a valid question but here goes.

Would it be possible to add a mechanism to an encryption algorithm that would mean it had to be a certain time of the day or a certain day of the year for the encryption to be able to be decrypted.

To Clarify, It should only be decryptable at a certain time eg

4th February or
11.23 am
or between 1 and 2 pm

working in a similar way to a time clock on a bank safe.

Obviously this would require encrypted access to an internet timeserver to ensure an unspoofed time signal.

Does this make an sense?
Would it be possible?
What would the mechanism be?

I asked this on stackexchange.com but this seems a better place.

Cryptographic algorithms are not time-aware, so you require a time-aware third-party to accomplish this. The third-party also needs access to a secure time source (like an on-site atomic clock or a secure connection to an offshore one)

The precise implementation and protocol depends on your usecase, but as an example you could have a server that does two things:

accepts inputs that include a message to timelock and a "release date"
allows requests to obtain the message only once the message's release date is passed

For the first case, the server would generate a random symmetric key of sufficient length, encrypt the message with it, hash the encrypted message and add the key + the hash + the release date in some database. The server then returns the hash that serves as an identifier for the message that was just timelocked. It can also return the encrypted message, if needed (presumably, the entity submitting the message destroys his plaintext copy after as he is the one wishing to timelock it).

Then, in the second case, the client sends the identifier to the server. The server looks it up, and checks the release date. If it isn't passed yet, the server denies and bails, however if it is, the server simply returns the correct encryption key (and the plaintext message if desired).

That's just one example of a very basic timelock service (you can elaborate by using public-key crypto to enhance various aspects of the service, for instance).

Your question is quite broad, perhaps you should add more detail.


Choosing good entropy $g$ and $p$ for a classic Diffie-Hellman Key exchange When selecting $g$ and $p$ for the Diffie-Hellman modular exponentiation:

  $ s= g^x \bmod p $

Which pairs of $g$ and $p$ are considered good nowadays, are recommended by bibliography?

What I try to do is to write a simple Python script that chain calculates Diffie-Hellman Modular exponentiation:

def dh_public(secret):
    g=5;p=23 //@todo select better values

    return g**secret % p

For now, I have REALLY POORLY selected values but I want standardized and tested values for calculating a Diffie Hellman key exchange. As far as I know, both $g$ and $p$ should be primes.

The most commonly used values are in this RFC; it includes groups that range from 1536 to 8192 bits; the size 2048 is actually the most common.

The properties of these groups include:

The modulus is chosen using a 'nothing up my sleeve' method (and hence is unlikely to be specifically chosen to be especially vulnerable)
The modulus has the high 32 bits and the low 32 bits all set; this can be useful for some modmul algorithms
It has $g=2$; this can make the initial computation of $g^x \bmod p$ rather more efficient
The order of the subgroup generated by $g$ is a prime of size $(p-1)/2$; a size which is quite sufficient for security

DannyNiu's reference to the IANA TLS groups (actually, the groups 256-260; the others are various elliptic curves which aren't what you are asking about) are another set; they're actually generated using the same procedure (and share the above properties), but are deliberately slightly different (to avoid potential factor-based style attacks against the original group)


Can frequency attack be successful on Vigenère cipher? Here is my question when learning Vigenère cipher, can we perform frequency analysis attack toward this cipher?

My first impression is no, because each column of its matrix has exactly 26 English letters. But I also know that this cipher is not secure. So, my question is, whether and how we can perform frequency attack towards this cipher?

Yes, Vigenère cipher is vulnerable to frequency analysis.

BUT! It requires some pre-processing first.

I propose to walk us through a small example of how frequency analysis can help decrypting Vigenère cipher in order to get a better idea of the process.

Firstly, it is important to notice that if you were to choose a key length of 1, then Vigenère cipher becomes Caesar cipher, which is one of the best examples of ciphers sensitive to frequency analysis!

Let us consider the following ciphertext encrypted using Vigenère:

  Vyc qxgv gpdzfcdq pks yigimsp jm iaov tmbiivzlv foeygcxg erl exfhfpb mvgd ojbqmcw pgr uf rwth jlkpg pgzlvl qce scwstjrpgr vycb vzgrpar. O rimvkoodcg bg kucpeza rl tlgcpghm kjf udkyu ngia htrbxmwqeya tsukftmwe rls ewvvppkm hfpbl ou ncae ou dyiasorrxvon tmcvsrkq, ih qqdkjgwerrt mvg nyn mvck yc tzifpxmvo nmgdg ceb ih qqetxgqg r pttrgi rwth vyc gxgwcrh pwnc zt vcticrm.

If we were to perform a simple frequency analysis on it, we do not get really insightful information:

letter  occurrences  %
G           25      8.2%
R           21      6.89%
C           20      6.56%
V           19      6.23%
P           17      5.57%
T           16      5.25%
M           16      5.25%
I           13      4.26%
E           12      3.93%
O           11      3.61%
K           11      3.61%
Q           11      3.61%
W           10      3.28%
Y           10      3.28%
L           9       2.95%
F           9       2.95%
H           9       2.95%
D           8       2.62%
B           8       2.62%
X           8       2.62%
S           8       2.62%
Z           7       2.3%
A           7       2.3%
U           7       2.3%
N           7       2.3%
J           6       1.97%

On a total of 305 characters (not counting punctuation marks), we can see the raw frequency analysis is not helping on first sight, as it's far from matching English's frequency.

But, if we study the n-grams appearing in that ciphertext, we can notably see the following occurrences:

n-gram    occur.  positions
RWTH        2       74,278
HFPB        2       54,186
IHQQ        2       219,261
VYC         3       0,102,282
MV          5       58,116,232,238,250

Now, the positions of these repetitions is important, let us take a look at the distance between any two of them:

n-gram    positions     distances
RWTH        74,278      278-74= 204
HFPB        54,186          132
IHQQ        219,261         42
VYC         0,102,282       102, 180
MV    58,116,232,238,250    58, 16, 6, 12

Now, if we are to look at each of these distances, we can see that among all the common divisors there are between any two distances, the most common one is 6:
$\gcd(12, 42, 102, 132, 180, 204) = 6$

This allows us to infer the size of the key could probably be 6.

From there, we just need to split it into 6 columns (I mean in Python it would be [trimmed[i::6] for i in range(6)]) and consider each column as a single string encrypted using Caesar cipher! We thus get:

Vvcypvveehgmujgctvgrokacjutquevhuuonrqegciocqggvwnt
ygdijtzyrfdcflzejyridurpfnrekrvfndrtkdrnkfneeriycci
cpqgmmlglpowrklsrcpmcclgugbyflppcyrmqkryypmbtprcrzc
qdpiibvcebjpwpvcpbavgpthdixatspbaixcijtncxgixtwghtr
xzkmaifxxmbgtglwgvrkbelmkamtmekleavvhgmmtmdhgttxpvm
gfssoiogfvqrhpqsrzOogzgkyhwswwmoososqwvvzvgqqrhgwc

And now we can again perform a frequency analysis like we would for any Caesar cipher, but this time on each string independently:
Vvcypvveehgmujgctvgrokacjutquevhuuonrqegciocqggvwnt gives:

let.   occ.  %
V       7   13.73%
G       6   11.76%
U       5   9.8%

And we know that in English the frequency table goes as follows:

let.  %
E   12.02
T   9.10
A   8.12
O   7.68

Which means that since the most common letters in the English alphabet are E, T A and O, we can assume they are very likely represented by the most common letters in the cipher too. (Sadly, this won't work here for all 6 Caesar ciphertexts we got, and some require a better frequency analysis using more advanced tools such as cross-entropy or chi-squared tests...)

So, let us find in Vigenère matrix which column is using V for E or for T, G for T (or for E),  and U,C or E for A!
We find that if V is used for E, we would be in the case where key would be R and then G would match P, and U would be the matches for D, which doesn't really fit our frequency table for English...
But if V is used for T, then we would be in the case where the key is C, and then the cleartext for G would effectively be E! Now this latter case seems way more plausible, so we have probably found the first letter of the key: C.
Notice that in practice, instead of performing such deduction, we would typically use the graphs of the frequency of each letter under every 26 possible keys to find which one is the closest to the English distribution. (Well, in fact we would probably be computing the cross entropy between the English frequency and the frequency we obtain from our ciphertext when it is decrypted as a Caesar cipher for each letter of the alphabet and we would retain the letter that has the smallest entropy as our best candidate.)

If we do the same for ygdijtzyrfdcflzejyridurpfnrekrvfndrtkdrnkfneeriycci, we can find that the most probable shift would be for index 17, that is the letter R. But here it is not trivially done by hand anymore and I've relied on the
cpqgmmlglpowrklsrcpmcclgugbyflppcyrmqkryypmbtprcrzc gives Y when analysed in turn by frequency like Caesar cipher.
qdpiibvcebjpwpvcpbavgpthdixatspbaixcijtncxgixtwghtr gives in turn P.
xzkmaifxxmbgtglwgvrkbelmkamtmekleavvhgmmtmdhgttxpvm gives T (with I also a possibility).
Finally gfssoiogfvqrhpqsrzOogzgkyhwswwmoososqwvvzvgqqrhgwc will be a bit more of a problem: frequency analysis tells us it could probably be S, E, N, D, C or O ... What a pain! (However, notice cross-entropy is the lowest for O)

However, since we've greatly reduced the number of candidates, we can simply try all of them until our ciphertext decrypts using Vigenere decryption to an English text.

And this finally works here with the CRYPTO keyword and gives the following plaintext:

  The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.

(A quote by D.Knuth)


How succeptible to accidental collision is the construct sha256(uuid4 + now) in Python? I need 32 byte pseudorandom sequences that denote unique filenames and am currently using this Python code:

import base64
import hashlib
from django.utils import timezone
from uuid import uuid4

def get_name():
    data = str(uuid4()) + str(timezone.now())
    hash = base64.b64encode(hashlib.sha256(
                  data.encode()).digest(), '-_'.encode()).decode()[:-1]

Do you think it's necessary to check if the generated sequence doesn't collide with any previously generated sequences or can I just skip the overhead of checking, trusting the function?

You can skip the test, unless you suspect that uuid4()) + str(timezone.now() (and the random value you may have added) is possibly not unique. The chances that SHA-256 itself accidentally introduces a collision is negligibly small.

There are no known attacks on SHA-256 that break the algorithm, other than length extension attacks. Those however don't seem to be an issue with your protocol.

So you mainly have to worry about an attacker messing with your input. The date won't add much entropy, so as a long as the underlying random generator(s) are secure, your scheme is likely secure as well.

Although it doesn't seem to  be an issue with your current scheme, you should make sure that the input to the hash function doesn't rely on the size of the input data. For instance, A | BC hashes to the save value as AB | C. In other words, you need a canonical method of encoding your data structure. Best to document this, otherwise you may mess up your scheme at a later date.


Entropy Rate of Bit String How to calculate "Entropy Rate" of a bit string?
Does "NIST Randomness Test Suite" provide any test to measure Entropy of an
entropy source?
How to check "biased-ness" of a bit string?

Thank you in advance.

There is no such thing as the "Entropy Rate" of a bit string. That's shorthand for the entropy rate of the process that created the bitstring. Thus what's to be analysed to determine this entropy rate is how the bit string was produced, not the bitstring itself.

If a bitstring 0000 was produced by four fair coin throws, the entropy rate of that process is 4 bit/bitstring, and the entropy rate of the process that created each bit of the bitstring is 1 (bit/bit). Knowing the bitstring is of no use in this determination.

If a bitstring 0101 was produced by starting with 0 then alternating, then the entropy rate is zero.
The "NIST Randomness Test Suite" accepts a bitstring as input and determines if the hypothesis that the bits in this bitstring have been created independently and uniformly at random is acceptable, or should be rejected as too improbable.

When the hypothesis is true, the tests most often accept the hypothesis, but occasionally reject it (modern versions output a p-value, that is the probability that the hypothesis is rejected even though it actually holds).
When the hypothesis is false, what the test concludes depends enormously on the actual process.

If the process is a CSPRNG initialized with a constant bitstring, its entropy rate is zero, but the tests conclude just like if the hypothesis was true (and the entropy rate was 1 bit/bit).
If the process is a natural source that behaves distinguishably from the hypothesis (for example, if each bit is determined by 20 fair coin throws and is 1 if there was at least 10 heads; which is a source of independent bits sizably biased towards 1), some tests in the suite are more likely to reject than they would be should the hypothesis hold; how likely depends on the source, and on which test.

To check the "biased-ness" of a bit string, first define "biased-ness" of a bit string; I know no acknowledged definition.

To test if a bitstring could be from a source of random independent bits with no bias, count how many bits it has, and how many are 1; then, armed with these two integers, use a (perhaps, one sided) chi-squared test. This will tell if the hypothesis can be rejected with confidence. The monobit test in the NIST Randomness Test Suite does that, restricted to long bitstrings.


How resistant are stream ciphers like Salsa20 or ChaCha in a post-quantum world? What kind of quantum computer would be required, if it is possible to break such ciphers?

There is no known quantum attack better than the generic Grover attack on Salsa20 and ChaCha, which is inconsequential because it would take $2^{128}$ sequential steps.  Even if parallelized $p$ ways to run in marginally less time, a factor of $\sqrt p$ improvement, it would cost more, also by a factor of $\sqrt p$, than the cost to run a quantum computer for $2^{128}$ steps.  Even if you were satisfied with breaking the first of $t$ targets for $t \ll p$, you would get only a $\sqrt[4] t$ cost reduction in the best known multi-target attack.

The same is true for AES key recovery, SHA-256 preimage search, etc.  More on quantum attacks on various kinds of hash functions.


Is it safe to convert a 256-bit nonce into a 192-bit nonce by SHA-256ing and then truncating it? I'd expect a 192-bit nonce derived from a 256-bit nonce by computing the SHA-256 hash and then truncating it to 24 bytes to behave like an approximately uniformly randomly generated 192-bit nonce and hence be good enough for using it e.g. as a nonce for XChaCha20-Poly1305 encryption. Is this correct? If yes, could maybe someone sketch the formal argument, and if no, explain the problem with this approach?

XChaCha20 requires a 192-bit nonce size. As a rule of Stream ciphers, the nonce should not be repeated under the same key.
Note that; Daniel J. Bernstein is pointed in the XSalsa20 article for Salsa20 which has 64-bit nonces.

There is a standard argument that a 64-bit nonce is long enough. Nonce
security does not mean unpredictability; it means uniqueness. Applications can
generate a nonce as a monotonic timestamp or simply a counter 1,2,3,...

and

There is also a standard counterargument. Counters might sound simple but
are sometimes mismanaged by applications, destroying security. Rather than
blaming the application for this failure, we can append random bits to the nonce,
adding protection that is likely to succeed even if the counter fails.

For Salsa20 using random nonce is not secure since the birthday bound on the collisions. One expects at least collision after $2^{32}$ random generation with 50% probability.
For XChaCha20 using random nonce is secure since the collision probability becomes nonnegligible (50%) if you can encrypt $2^{96}$ messages under the same key. Since it is not possible, you will change, you should, way earlier than that.

I'd expect a 196-bit nonce derived from a 256-bit nonce by computing the SHA-256 hash and then truncating it to 24 bytes to behave like an approximately uniformly randomly generated 196-bit nonce and hence be good enough for using it e.g. as a nonce for XChaCha20-Poly1305 encryption.

If the input to the SHA256 is a good random source then we expect the usual collision probability. Except it doesn't guarantee that there is no repeat, however, that is negligible.

(This was in the comments by OP) In the extreme case the input is just a counter.

Your proposition is similar to building a CTR mode encryption from hash function. As long as the hash function has pseudo randomness properties the construction will work (most modern hash functions have this property). It will work, too.
You have the same problem as mentioned by Bernstein, the mismanagement of the counter that usually occurs system failures. The system may start from a previously used counter that will regenerate the same SHA256 values and that is insecurity may be more than one nonce.
Generate the nonce like $$nonce = random \mathbin\| counter$$ is a better and safe way. Now, the mismanagement of the only counter is handled.
Or, generate the nonce like $$nonce = random \mathbin\| \operatorname{SHA256}(counter).$$


Peikert's framework for attacks on R-LWE: What "reduction modulo q" means? I am reading Peikert's paper [Pei16] about secure instantiating of R-LWE problem. In section 3.1, The author gives a new attack framework by using "reduction modulo an ideal divisor $\mathfrak{q}$ of the modulus $qR$".
I'm a little new to Algebraic number theory and so I did not understand this framework especially the following part:

"Let $\mathfrak{q} ⊆ R$ be an ideal divisor of $qR$, having norm $N(\mathfrak{q}) := |R/\mathfrak{q}|$, and let $ψ$ be a continuous error
distribution over $K_\mathbb{R}$. Given Ring-LWE samples
$(a_i, b_i = s · a_i + e_i) \in R_q × K_\mathbb{R}/qR$
where $a_i ← R_q$ and $e_i ← ψ$, we can reduce them modulo $\mathfrak{q}$ to obtain samples $(a'_i = a_i \mod \mathfrak{q} , b'_i = b_i \mod \mathfrak{q}) \in R/{\mathfrak{q}} × K_\mathbb{R}/\mathfrak{q}$"

What "reduction modulo $\mathfrak{q}$" means? Can anyone help clarify things for me? Giving an example would be perfect.

Recall that any ideal $I$ of $R$ is in particular an additive subgroup of $R$, and that the quotient $R/I$ is the collection of cosets $a + I = \{a + i : i \in I\}$ for each $a \in R$.  Two cosets $a+I, b+I$ are equal iff $a-b \in I$.  The map that sends $a \in R$ to $a + I \in R/I$ is called "reduction modulo $I$," and often written "$a \bmod I$."  The quotient $R/I$ is a ring via the induced ring operations from $R$ itself: $(a+I) + (b+I) = (a+b) + I$ and similarly for multiplication.

Now suppose we have some ideal divisor $J$ of $I$, i.e., $J \supseteq I$.  The "natural" or "reduction mod $J$" homomorphism from $R/I$ to $R/J$ simply sends $a+I$ to $a+J$.  This is well defined because if $a+I = b+I$, then $a+J=b+J$ because $a - b \in I \subseteq J$.  (You can easily check that this is both an additive and multiplicative homomorphism.)

In the present setting, we have $I=qR$ and an ideal divisor $J = \mathfrak{q} \supseteq I$.  For a Ring-LWE sample $(a_i, b_i = s \cdot a_i + e_i)$, we should view $a_i \in R/qR$ as the coset $a_i + qR$.  Reducing it modulo $\mathfrak{q}$ just means sending it to the coset $a'_i = a_i + \mathfrak{q} \in R/\mathfrak{q}$.  Similarly, we send the coset $b_i + qR$ to the coset \begin{equation} b'_i = b_i + \mathfrak{q} = (s \cdot a_i + e_i) + \mathfrak{q} = (s \cdot a'_i + e_i) + \mathfrak{q}. \end{equation}
Note that the last equation holds because $s \in R$, $\mathfrak{q}$ is an ideal, and $(a_i - a'_i) = \mathfrak{q}$, so $s \cdot (a_i - a'_i) \subseteq \mathfrak{q}$.

The upshot of all this is that we can transform "mod $qR$" Ring-LWE samples $(a_i, b_i)$ into "mod $\mathfrak{q}$" samples $(a'_i, b'_i)$.  However, as the paper notes, if the error distribution $\psi$ is very "smooth" modulo $\mathfrak{q}$---i.e., if $e + \mathfrak{q}$ is very close to uniform for $e \gets \psi$---then the resulting sample is useless: $(a'_i, b'_i)$ is just uniform junk, and it's impossible (information theoretically) to recover anything about $s$ from it.


detect the RSA public key from encrypted text we have a service who has a list of public keys got from clients (for example 1000 public keys. not too many)
service gets an encrypted message from one of clients. this message is encryped with a public key and defenitly service has that key.
can service find out which public key is used to encrype that data?
for more information (you can ignore it): service must broadcast data between all the clients (each one has a pair of RSA keys and service has their public keys). clients must send message to each other with no clue for tracking on service.
for example client A wants to send a message to client B. A encrypts the message with Bs public key and sends it to service. service broadcasts the message to all clients. but only one of the clients (it's B) can decrypt the message.

Maybe, but this approach depends on the distribution of the public key sizes.
Suppose that cm is the encrypted message, and ni is the modulus for customer i.

If cm >= ni, then customer i cannot be the recipient of this particular message.
if cm is significantly smaller then ni (16-32 bits or so, depending on how certain you want to be) then it is possible (but unlikely) to have been sent to customer i.

So if there is a variety of key sizes, this may allow you to narrow down the list of possible senders. For example, if customer X has a 4096-bit key and all the others have 3072-bit keys, identifying messages from customer X would be easy.
On the other hand, if everyone has a 3072-bit key, you may be able to narrow the list of senders down some, but you would still have a fairly large list remaining.
One possible countermeasure is to add random high-order padding bits to the message to make the padded message larger than any modulus. In other words, if the largest modulus is (decimal) 1000000, then 1234 might become 9351234, while 12345 might become 7412345.  Each recipient can remove high-order bits until the message is smaller than their modulus, then try decrypting the message.


Can I use a random number generator with seed for key derivation? I don't know a thing about cryptography so I'm judging by what I see in APIs docs.
I want to use ECDSA or ECDH in my project. And what I know so far about key derivation in this systems is that they:

generate a random private key $d$
then do some fancy stuff with it to get a public key $dG$

My question is: can I use a random number generator that works with seeds?

Like if we say thatrandom(seed) produces random numbers from set A.
And if
random(seed1) -> set A,
random(seed2) -> set B,
seed1 != seed2,
Then A != B or at least A is as far as possible from being equal to B

My question is: can I use a random number generator that works with seeds?

Yes.

All you need is a 256-bit uniform random secret, or a seed chosen by a process with 256 bits of min-entropy.  You can derive everything else from there using a key derivation function like HKDF-SHA256, which is—securitywise—just a kind of PRNG with a convenient API to name what the purpose of each derived key is so that you can reproduce the computation.

For example, you could ask a computer to generate for you a 20-word diceware phrase $p$.  You can convert it into a 256-bit effectively uniform random secret $k$ with $\operatorname{HKDF-Extract}(p)$; then, from $k$, you can derive:

an AES-GCM-256 key for notes in a private todo list with $k_1 = \operatorname{HKDF-Expand}(k, \text{‘todo list key 1’})$
an ECDSA key for a Bitcoin wallet with $d = \operatorname{HKDF-Expand}(k, \text{‘Bitcoin wallet, 2019-03-23’})$
an RSA key using a particular prime generation procedure with a particular choice of PRNG seeded with $s = \operatorname{HKDF-Expand}(k, \text{‘my RSA key seed’})$.  Of course, RSA key generation is rather slow!  So people don't usually do this.

There are two key points:

You must let a computer or fair dice rolls choose the phrase $p$ for you, and then commit it to memory.  Don't try to think of $p$ yourself first, because you are bad at thinking randomly.
The labels must all be distinct.  All bets are off if you use the same label for two different purposes.


Shamir Secret sharing - Can share generator keep x values secret? I'm wondering, in Shamir secret sharing, can generator of the shares, keep the x values which are used in evaluating the polynomial to obtain y values (i.e., the shares) secret, and whenever the original secret is needed, he retrieves the t shares and reconstructs the secret? In this setting the share holders should not be able to construct the secret even all of them collude. Is there any secure way of doing so?

Each share in Shamir-type secret-sharing schemes has two parts: the share value
$f(x_i)$ which is the value taken on by a certain polynomial $f(\cdot)$, and the share "location" $x_i$. The "dealer" who constructs the shares and hands them
out to individual shareholders is assumed to have handed out $(x_i, f(x_i))$
to the $i$-th share holder. In this scenario, any $k$ (or more) shareholders in a
$(k,n)$ scheme can get together and reconstruct the secret, and fewer than $k$
shareholders cannot reconstruct the secret.

If the dealer
hands out only $f(x_i)$ to the $i$-th share holder and merely makes a note
in his records that the $i$-th share holder's share location is $x_i$,
then only the dealer can reconstruct the secret when $k$ or more shareholders
make an application to the dealer; the $k$ shareholders cannot
reconstruct the secret by
themselves because while they all know their share values, they do not know the
location of those shares.  This scheme is, of course, fraught with danger in
case the dealer's list is lost or is corrupted in various ways: the secret
might be irretrievably lost.

See also this answer for
how enemies can attack a Shamir-type secret sharing scheme by tampering
with share values and by tampering with share locations, and how to
get around such problems.


AES256-GCM - can someone explain how to use it securely (ruby) I am looking into using AES256-GCM for encrypting some database fields. I know that for AES256-CBC, I need to generate a new IV for each encrypt, but I can use the same key. The IV can be openly stored alongside the ciphertext (ie, it can be public).

I started to read about GCM, but I don't quite understand some things. On this Stackexchange Thread, it is stated that:

GCM does not need an IV supplied.
Associated Tag is not necessary, but may improve security (example they gave is using a database id)

But Wikipedia states about GCM:

  GCM has been proven secure in the concrete security model.[13] It is secure when it is used with a block cipher mode of operation that is indistinguishable from a random permutation; however security depends on choosing a unique initialization vector for every encryption performed with the same key (see stream cipher attack).

Which implies that the IV still needs to be randomly generated and supplied for each encrypt with GCM, so why does the user in the stackexchange answer post say that we are not required to provide the IV?

Wikipedia also states:

  The authentication strength depends on the length of the authentication tag, as with all symmetric message authentication codes. However, the use of shorter authentication tags with GCM is discouraged. The bit-length of the tag, denoted t, is a security parameter. In general, it may be any one of the following five values: 128, 120, 112, 104, or 96.

In OP's post in that stackexchange thread, OP uses tag = cipher.auth_tag. Is this by default 96? If so, is there a way to change it? Are there significant performance issues in using 128 than 96?
Does both the Associated Tag (cipher.auth_data) and the Authentication Tag (cipher.auth_tag) need to be kept secret? Or can they be kept open like the IV?
Finally, can someone explain further what is meant by the Associated Tag? The example in the answer that was given in OP's thread was that we can use a database id to ensure that the data belongs to a certain database user. Let's say that a user has the following database fields:

User
- primary_id
- encrypted_email

And we want to encrypt the User's email before insertion. With User primary_id==10 (modifying OP's ruby code):

cipher = OpenSSL::Cipher::AES.new(128, :GCM)
cipher.encrypt
key = cipher.random_key
iv = cipher.random_iv
cipher.auth_data = "10"    # Using DB user's id!

encrypted = cipher.update(data) + cipher.final
tag = cipher.auth_tag

I replaced cipher.auth_data with the database user's primary_id. Is this correct?

Before answering your questions:
GCM is an authenticated encryption mode of operation, it is composed of two separate functions: one for encryption (AES-CTR) and one for authentication (GMAC).
It receives as input:

a Key
a unique IV
Data to be processed only with authentication (associated data)
Data to be processed by encryption and authentication

It outputs:

The encrypted data of input 4
An authentication TAG

The authentication TAG is an input to the decryption, if someone tampered with your associated data or with your encrypted data, GCM decryption will notice this and will not output any data (or return an error and you should discard the received data without processing it)

Now:

  Which implies that the IV still needs to be randomly generated and supplied for each encrypt with GCM, so why does the user in the
      StackExchange answer post say that we are not required to provide
      the IV?

GCM requires an IV, it is used both by AES-CTR and by AES-GMAC, so no matter what you are doing with GCM, you need to pass an IV.
It is required to be unique not necessarily random. Usually, implementations take a 96-bit IV and this is the recommended way to use GCM according to NIST.

  In OP's post in that StackExchange thread, OP uses tag = cipher.auth_tag. Is this by default 96? If so, is there a way to
      change it? Are there significant performance issues in using 128
      than 96?

By default, the authentication tag is 128 bit. You should provide the authentication TAG to the receiver of your message, so in some applications make sense to use a smaller tag. Keep in mind that the smaller tag you have, the more collisions you might get. If bandwidth is not an issue, use 128.

See also the detailed section on auth_tag([ tag_len ] → string here

  Does both the Associated Tag (cipher.auth_data) and the Authentication Tag (cipher.auth_tag) need to be kept secret? Or can they be kept open like the IV?

The associated data (incorrectly you wrote Associated Tag) is used for data to be publicly known. Examples are headers or destination address. So it's not required to be secret, but if need to encrypt everything, then set the associated data to "".
The authentication Tag is not required to be secret and in fact, it must be provided to the receiver unencrypted (like the IV).

  Finally, can someone explain further what is meant by the Associated Tag? The example in the answer that was given in OP's thread was that we can use a database id to ensure that the data belongs to a certain database user. Let's say that a user has the following database fields:

It looks like you confuse the authentication data and authentication tag.
The authentication data (or associated data) is something that you want to protect with authentication (if somebody modifies it you will know) but don't need to be encrypted. As stated above this is usually the case for headers which must be read by intermediate routers that can't decrypt the encrypted message.

The authentication Tag will depend upon the data you encrypt and on the associated data. So in decryption, you will need to process also the associated data or you will fail.

In your example, which is not very clear to me, you authenticate the primary id and the email and you encrypt the email. If you store in your DB both the IV and the TAG then you can decrypt the email if needed.
Without an authentication tag an attacker could copy the email of user1 to the email of user2, if he also copies the IVs, then when you will lookup for the email of user2 you will successfully decrypt the email of user1 without noticing anything.

Instead, if you also use a TAG and process as associated data the id of the corresponding user, then an attacker could not do the previous attack, because in decryption will we notice the associated data wasn't the one used in encryption and the operation will fail (you will know someone tampered with user2 data).


Collision likelihood from /dev/urandom for VMs using the same underlying hardware We have multiple virtual machines sharing the same physical hardware. We use /dev/urandom for session key generation. But a question comes up: if /dev/urandom utilizes metrics from the physical hardware for entropy, isn't there an increased risk of duplicates for VMs on shared hardware if calls are made at the same exact time?

There are at least two important things that can go wrong with VM randomness:

They could end up with the same "entropy" input and produce same/related numbers.
Someone with access to one VM could be able to predict the "random" inputs of another VM.

In a simple setup each VM has their own pool, they get initialized with saved values on startup and they make their own measurements that they feed into the pool. Only on first start (or two starts from a checkpoint), when they have constant initialization could they start off with identical numbers and be slow to gather enough entropy to diverge. (If you have a CPU with RDRAND/RDSEED this should never happen, since that is mixed into the pool frequently.)

The second issue is more difficult to gauge. Again, access to hardware random numbers avoids the issue, but theoretically the other VM could have influence on or be able to predict the "random" measurements otherwise.

It is common to use paravirtualization to handle the problem for good. By having the host generate independent random numbers for the guests, their random number generators will generate independent numbers.


Standard parameters for Boneh–Lynn–Shacham signature? The Boneh–Lynn–Shacham signature is (as far as I know) unrivaled in compactness, promising $b$-bit security for $2b$-bit signature (perhaps: asymptotically).

Are there standard parameters for BLS signature, (being?) defined by standard bodies, security authorities, or other recognized authority; or otherwise common/recommended?

In particular, is there something with a size recommendation, perhaps in ISO/IEC 15946-5: Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 5: Elliptic curve generation?

What does the state of the art ([BD 2019] I guess) implies about the size of BLS signature for $b$-bit security, for practical $b$ like 128?

Some references (now dated except the last two) :

[BLS 2004]: Dan Boneh, Ben Lynn, Hovav Shacham, Short Signatures from the Weil Pairing, in Journal of Cryptology, 2004 (originally [BLS2001] is proceedings of Asiacrypt 2001).

[BN 2005]: Paulo S. L. M. Barreto, Michael Naehrig, Pairing-Friendly Elliptic Curves of Prime Order, in proceedings of SAC 2005; slides.

[SSS 2006]: Mike Scott, Hovav Shacham, Terence Spies, P1363 presentation of 2006/10.

[NNS 2010]: Michael Naehrig, Ruben Niederhagen, Peter Schwabe, New software speed records for cryptographic pairings, in proceedings of Latincrypt 2010; software linked at referring page.

[ABLR 2013]: Diego F. Aranha, Paulo S. L. M. Barreto, Patrick Longa, Jefferson E. Ricardini, The Realm of the Pairings, in proceedings of SAC2013, with slides (reporting actual use since 2002).

[KB 2016]: Taechan Kim, Razvan Barbulescu, Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case, [KB16] in proceedings of Crypto 2016, originally [K 2015] of October 2015 and [B 2015] of November 2015.

[BD 2019]: Razvan Barbulescu, Sylvain  Duquesne, Updating key size estimations for pairings, in Journal of Cryptology, October 2019

Well, the Boneh-Lynn-Shacham "BLS" signature scheme is currently in the process of being standardized through an Internet Draft named "draft-irtf-cfrg-bls-signature-00" (a working document of the Internet Engineering Task Force "IETF"), which you can track here. It appears Algorand might be behind this process, along with Dan Boneh's own support.

As stated in there:

  There are two variants of the scheme:

  (minimizing signature size) Put signatures in G1 and public keys
     in G2, where G1/E1 has the more compact representation.  For
     instance, when instantiated with the pairing-friendly curve
     BLS12-381, this yields signature size of 48 bytes, whereas the
     ECDSA signature over curve25519 has a signature size of 64 byes.
  (minimizing public key size) Put public keys in G1 and signatures
     in G2.  This latter case comes up when we do signature
     aggregation, where most of the communication costs come from
     public keys.  This is particularly relevant in applications such
     as blockchains and compressing certificate chains, where the goal
     is to minimize the total size of multiple public keys and
     aggregated signatures.

While they do not (yet) specify explicit parameters that are to be used, they do refer to the Internet Draft "Pairing Friendly Curves", which in turn has multiple recommendations depending on the level of security you want to reach.
Regarding the above quote, it notably lists BLS12-381 in the recommendation to have 128 bits of security.

Also, when compared with ECDSA, they mention that (emphasize mine):

  The following comparison assumes BLS signatures with curve BLS12-381,
  targeting 128 bits security.
  [...]
     In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes
  for signatures; while BLS uses 96 bytes for public keys, and 48 bytes
  for signatures.  Alternatively, BLS can also be instantiated with 48
  bytes of public keys and 96 bytes of signatures.  BLS also allows for
  signature compression.  In other words, a single signature is
  sufficient to anthenticate multiple messages and public keys.

So it appears that the current "standard" is to have ~384 bits of signature to reach 128 bits of security, which means having $3b$ bits signatures for $b$ bits of security. (BN curves having "lost" favors, as Bristol said already and their current 128 bits contender being BN462.)

Also, notice this is a working document, and as such is not complete. For instance it is missing things that are yet to be added:

  TBA: additional discussion on this, e.g.  [Ristenpart-Yilek 06], and alternative mechanisms for securing aggregation against rogue key attacks, e.g.  [Boneh-Drijvers-Neven 18]; there, pre-processing public keys would speed up verification.

And the rogue key attack is typically something important to defend against in the case where we want to have aggregate signatures, which is one of the nice features of BLS.

Notice that in pairing based crypto we had to move significantly our security estimates within the last 3 years most notably because of the advances in the FFDLP (see [KB16]), with your latest reference [BD 2019], being the current state of the art regarding security estimates and recommendations.

So it might still take a while until the above-mentioned IETF draft is finished and becomes an actual "standard", but this is in process.


Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ satisfy universal hashing? I read in our university lecture on hashing that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow   V$ to satisfy the following universal hashing condition: for all $\forall x,y\in U$ so that $x≠y$, we have $Pr[h(x)=h(y)]≤\frac{1}{|V|}$
I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?
Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.

First note that the set of all functions $U\to V$ contains for every value $u\in U$ and every value $v\in V$ a function $f$ such that $f(u)=v$. Also note that if you fix a point $u\in U$ and take a random function from $U\to V$, $f(u)$ is uniformly distributed in $V$.
Now if you apply that, fix any two points $x\neq y,\quad x,y\in U$. Now choose $h$ randomly out of $U\to V$. Note that $h(x)$ is uniformly distributed and $h(y)$ is uniformly distributed. The probability for $h(x)$ and $h(y)$ to be equal now should be $1/|V|$ which implies the desired universality.

Given that the above might not be entirely clear, let's do an example:
$$U=\{1,2,3\}\quad V=\{1,2,3\}$$
Clearly there are 27 functions mapping from $U$ to $V$ and clearly there are 6 pairs of unequal values $(x,y)\in U\times U$ for which we need to check whether the probability holds.

$(x,y)=(1,2):$ There are three possible ways to map $1$: to either 1,2, or 3, let's denote the actual value $h(x)$ for the moment. There are also three possible values to map $2$ to: 1,2, or 3, let's denote the actual value as $h(y)$. Given that these two choices are independent, there are 9 cases here.

If $h(x)=1$ then the tested equation only holds if $h(y)=1$ as well which is a 1/3 chance
If $h(x)=2$ then the same argument as for $h(x)=1$ applies with $h(y)=2$
$h(x)=3$ goes analogously

Now counting the cases where the equation holds for $(x,y)=(1,2)$ we get $3/9\leq 1/3$ as demanded.
If we go through the other pairs as well, a very similar argument will ensue and we'll be getting $3/9$ for all of them. Therefore a random function from $U$ to $V$ satisfies universality.


A substitution based on a matrix vector product I choose at random an invertible square matrix A of size 128 in GF(2). I want to use this matrix as a substitution box. Is this a non linear transformation ?

I've seen that substitution boxes are the non linear parts of a block cipher algorithm, but the product between A and x is linear ? Not ? There is something that I don't understand.

Thank you.

We call an operation F linear if the following holds:

$F(X+Y) = F(X) + F(Y)$

for all $X, Y$ within the appropriate set, and for some group operator $+$.

Now, if we consider matrix multiplication by a fixed matrix $A$, we do have the identity:

$A \cdot (X+Y) = A \cdot X + A \cdot Y$

for arbitrary vectors $X$, $Y$, and where $+$ is vector addition.  Hence, matrix multiplication by any fixed matrix $A$ is linear.

When you are designing a block cipher, it is critically important that, for any group operator $+$, there be some component that is nonlinear with respect to that operator.  Hence, matrix multiplication is probably not an ideal selection.

You appear to have some understanding of this; so what are you confused about?


The difficulty of computing discrete logs I understand that in Diffie-Hellman it should be hard to compute $a$ given $g$ and $g^a$.

In computational Diffie-Hellman, it appears to be hard to compute $(g^{ab})$ from $g^a$ and $g^b$.

As for the field, please consider $\mathbb F_p^*$ for this question.

Is it also difficult to compute the discrete log $w$ of more trivial things, such as $g^w\equiv (g^a+1)^b\pmod p$? It may be assumed that $a,b,g$ and $p$ are given.

I will assume for simplicity that you're talking about the full multiplicative group of $F_p$ instead of a proper subgroup, thus there are no problems with $g^a+1$ (except when $g^a=p-1$ which can be trivially ruled out by comparing to $p$).

The quantity $\log_g(g^a+1)$ is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for characteristic 2, but can be defined here as well).

So let's define $Z(a)=\log_g(g^a-1)$ and note that it sets up a one-to-one correspondence between $a$ and $Z(a)$. Thus the difficulty of discrete logs is not really changed by introducing the kind of twist you ask about, in your reference to "trivial things".

I can't dig out the reference now, but there was a paper years ago by a French author, in a crypto related conference or journal, on whether precomputing Zech's logarithms on some subset of $F_p^{\ast}$ helped with discrete logarithms. The answer was, "not so much".