Why does using a prime-order subgroup in DLP improve security? Let's consider a discrete logarithm

  $\beta \equiv \alpha ^{x} \bmod \,\, p$

We can solve it using Pohlig-Hellman algorithm. And, if $p-1 = tq$ where $q$ is a large prime factor, we can avoid any leakages by choosing $\beta=a^{t}$.

This is what my professor said at lesson, however i don't succeed in understanding why it avoids any leakages. Can you explain to me why ? Also with calculations if it's possible

Probably what your professor meant is that you start with any group element $\alpha$, and then use $g := \alpha^t$ as the generator for a cryptosystem such as Schnorr signatures, as long as $g$ is not itself the identity.

Why?  If $g \ne 1$, then $g$ is guaranteed to have prime order $q$, because $g^q = (\alpha^t)^q = \alpha^{tq} = \alpha^{\phi(p)} = 1$, and since $q$ is prime there are no smaller orders possible for $g$ (just start over with a different $\alpha$ if it is).

Then when you choose a public key $\beta := g^x$ for secret $x$, you're guaranteed that $\log_\alpha \beta \equiv 0 \pmod t$.  (Of course, you could have equivalently chosen $\beta := \alpha^{tx}$, but precomputing $g$ may be cheaper.)

Now since the group generated by $g$ has prime order, Pohlig–Hellman has no advantage over any other DLOG algorithms.


How does openssl signature verification work? I would like to know how openssl verifies a digital signature? I know that it uses this command to verify a signature:

openssl dgst -sha256 -verify pkypem -signature signbin msgbin > result

What I want to know is, what openssl does exactly with the public key, the signature and the message before verification.

I'm also interested in the signature creation process.

It depends on the type of key, and (thus) signature.

If it is an RSA key, by default OpenSSL uses the original PKCS1 'block type 1' signature scheme, now retronymed RSASSA-PKCS1-v1_5 and currently defined in PKCS1v2.2. OpenSSL commandline also supports the RSASSA-PSS scheme (commonly just PSS) defined in the preceding section of PKCS1v2.2, with the dgst -sigopt option (online copy of man page) whose relevant values are actually documented in the pkeyutl man page.

If it is a DSA key, OpenSSL implements the algorithm as specified by the standard, FIPS186 currently at revision -4 and available at https://csrc.nist.gov/publications/fips (edited: usually, but download currently hangs presumably due to the government shutdown even though the webpage does display which initially fooled me); a shorter, less bureaucratic and more reliably available description is in Wikipedia. One minor point not stated in FIPS186, or Wikipedia, is that the signature value, which is mathematically a pair of integers, is concretely represented using ASN.1 (as a SEQUENCE of two INTEGERs). (In contrast PKCS1 for RSA defines the representation of the signature, which is mathematically an integer in $[2,n-1]$, using the I2OSP and OS2IP primitives, as bigendian (unsigned) binary with size equal to that required to represent the modulus.)

If it is an EC key, OpenSSL implements ECDSA as specified by X9.62, which costs money, but is also available in document SEC1 at http://www.secg.org (which ironically can't easily be accessed by https because it has a mismatched certificate!), and again in Wikipedia. Again the signature is mathematically a pair of integers, represented in ASN.1.

All of the above sources cover signing, aka signature generation or creation, as well as verifying for a given algorithm.

If it is a GOST key, OpenSSL may or may not work depending on version and build or packaging; this support has fluctuated. And if it works I'm not familiar with what it does, except that it is somehow like ECDSA.

Note that the 'raw' format used by openssl dgst -sign/verify, and openssl pkeyutl -sign/verify which skips the (data) hashing step (and for RSASSA-PKCS1v1_5, optionally the ASN.1 encode/decode step), is not used by most other software. Most actual signatures (for things like emails and code files and XML or JSON data, and certificates and CRLs and OCSPs and timestamps, as well as the signatures used in protocols like SSL/TLS and SSH) are represented in a form that adds metadata about the signature algorithm and a way to find the publickey for verification, and often to validate that key, and sometimes contain or are attached to the data signed as well.


Minkowski's theorem in lattice-based cryptography I am studying basic lattice-based cryptography. In the course given by O. Regev, on page number 7, there is Claim 1 and Corollary 2 (Minkowski's First Theorem), both of which are difficult for me to understand.

In Claim 1, how the volume of a ball with a of radius r is $vol(B(0,r)) \ge \left( \frac {2r}{\sqrt{n}} \right)^n$ ? (Specifically, how does the ball contain a hypercube of side length $\frac{2r}{\sqrt{n}}$) ?
In Corollary 2 (Minkowski's First Theorem), for any full-rank lattice $\Lambda$ of rank n, $\lambda_1(\Lambda) \le \sqrt{n} (<det \ \Lambda)^{\frac{1}{n}}$. How to prove this theorem ?

Try to draw a "hypercube" in $\mathbb{R}^2$ (i.e. a square) and in $\mathbb{R}^3$ (i.e. a regular cube), both centered at the origin and having side length equal to $\frac{2r}{\sqrt n}$...

Since they are centered at the origin, each side goes from $-\frac{r}{\sqrt n}$ to $\frac{r}{\sqrt n}$ (in its axis).

Now, the farthest points from the origin that belong to the hypercube are exactly the points of the corners and all the corners are at same distance from the origin. Since a sphere is symmetric, if one corner belongs to a sphere, all the corners belong to the sphere and, consequently, the whole hypercube is contained in the sphere.

The distance between the origin and the corner $c := \left(\frac{r}{\sqrt n }, \frac{r}{\sqrt n }, \cdots, \frac{r}{\sqrt n}\right) \in \mathbb{R}^n$ is given by

$$||c|| = \sqrt{\left(\frac{r}{\sqrt n}\right)^2 + \cdots + \left(\frac{r}{\sqrt n}\right)^2} = \sqrt{n \cdot \left(\frac{r}{\sqrt n}\right)^2} = r$$

Now, notice, by definition, the hypersphere $B(0, r)$ contains all points within distance $r$ to the origin, therefore, it contains the corners and then, the entire $n$-dimensional hypercube.

Since this hypercube is contained in $B(0, r)$, its volume cannot be greater than the volume of $B(0, r)$, and we know that the volume of a hypercube is the product of its sides' length, in this case,  $\prod_{i=1}^n \frac{2r}{\sqrt n} = \left( \frac{2r}{\sqrt n} \right) ^n$.

So, finally, $Vol(B(0, r)) \ge  \left( \frac{2r}{\sqrt n} \right)^n$.

To the corollary 2, you just have to use $r = \lambda_1$ in the above formula. Then, we get

$$\left( \frac{2\lambda_1}{\sqrt n} \right)^n \le Vol(B(0, \lambda_1))$$

and since $B(0, \lambda_1)$ has no nonzero lattice point (by the definition of $\lambda_1$), its volume can't be greater than $2^n \det(\Lambda)$ (by the contrapositive of theorem 9), then we get

$$Vol(B(0, \lambda_1)) \le  2^n \det(\Lambda)$$

  In this section we will talk about why the cube's side length is of $\frac{2r}{\sqrt{n}}$ in n-dimension

We first explain the 3-dimensional case and later extend things to n-dimensions.
Let us take the cube of side length $a$ inscribed in a ball of radius $r$ as shown below:

Now, the length of main diagonal of cube is $\sqrt{3}a$.
The length of the main diagonal of cube is the diameter of the Ball of radius r
$\Rightarrow \sqrt{3}a=2r$.
So, $a=\frac{2r}{\sqrt{3}}$ which is of the form $\frac{2r}{\sqrt{n}}$ for $n=3$

So, the result holds for $n=3$. Now, for the n-dimensional case see this question on Math.SE.

From the above post:

The length of the main diagonal of a cube is $\sqrt{n}a$ where $a$ is the length of each side of the cube.
Again, the length of main diagonal of cube is the diameter of the ball of radius $r$
$\Rightarrow \sqrt{n}a= 2r$
so, $a=\frac{2r}{\sqrt{n}}$  which is the value given by theorem.


Assistance Cracking Classical Cipher Below is the cipher text I am trying to break and as you can see its rather short which is why I am having so much trouble.

WOYFN ZCMSH VUVTG BFUTW ABTZP FHIMF TFOSU UXFQC HKVKG MPUUQ
MHRXI OVBRZ EPJYF KKVJW GEIOV HUKEB JUNSM THIMF TFKUB ULMMQX

What I know about this ciphertext:

Key is 6 characters long and repeats (Given by the person who encrypted it)
There is a single character missing from the start of the ciphertext! (Also given)
It uses a simple cipher I believe a vigenere cipher.
Friedman IC: 1.143 (kappa-plaintext: 0.4396) which is why i think its a vigenere cipher

I have spent many hours on this but to be honest im not very good at breaking these codes.

My problem that iv run into is that once I break the cipher into its sections they are all very short and hence frequency alaysis fails.

I would really appreciate if someone could either confirm or find the crypto system being used as well as any more information about how one would find the plaintext + key or better yet find the key itself and explain how you manage it with such a short piece of ciphertext

Edit: There was some debate as to the validity of this question so here is some more information from my attempts:

Streams:

?ZUUZFUKUXZKEKSFU IC = 3.6833 (kappa-plaintext: 1.4167)
WCVTPTXVUIEKIEMTL IC = 1.1471 (kappa-plaintext: 0.4412)
OMTWFFFKQOPVOBTFM IC = 2.1029 (kappa-plaintext: 0.8088)
YSGAHOQGMVJJVJHKM IC = 1.3382 (kappa-plaintext: 0.5147)
FHBBISCMHBYWHUIUQ IC = 1.5294 (kappa-plaintext: 0.5882)
NVFTMUHPRRFGUNMBX IC = 0.9559 (kappa-plaintext: 0.3676)

These numbers don't look good. they are almost all drastically off normal distribution for any language.

The main point to my question is:

Does Vigenere Seem like a reasonable fit (given those streams are correct)?
Is it possible to use that analysis in any way? I cant see how it can be effective with only 17 characters per stream. Most letters frequencies are 0.
What other ciphers are possible? How could I identify that they are in use?

I am happy to provide more information I am just not sure what else is useful.

I don't know the solution, but since you say you're only asking for hints, here's a few that occurred to me:

If this is a Vigenère cipher, the missing character at the beginning should not matter (much): if you encrypt a message with the key FOOBAR and drop the first letter of the output, you can decrypt the resulting ciphertext with the key OOBARF.
As ewanm89 notes, the obvious way to attack a Vigenère cipher, after you've determined the key length is $n$, is to write it with $n$ letters per row and attack each column as if it were a Caesar cipher.  There are automated tools for doing that, such as pygenere; they may not always give the correct answer for very short messages, but yours looks long enough that they should at least have a decent chance.
The most notable feature I see in your ciphertext is that the string HIMFTF occurs twice, at offsets 26 and 86.  That does strongly suggest that the key length may be a divisor of 60; alas, 60 has lots of small divisors (including 6, which you believe the key length to be), so that doesn't really give that much information.  It does at least rule out 7, 8 and 9 as likely key lengths.


How secure is ChaCha20? I want to implement a stream cipher to encrypt very sensitive data in my Python code. I heard about the ChaCha20 algorithm and the
PyCryptodome library
, but how secure is it ?

Aumasson et al. Showed that ChaCha6  can be attacked with time complexity $2^{139}$ and ChaCha7 with $2^{248}$.
Shi et al. gave an attack based on second-order differential with $2^{136}$ for ChaCha6 and $2^{246.5}$ for ChaCha7.
Maitra, chosen IV cryptoanalysis and the time complexity of the attack showed that it can be reduced to $2^{239}$ for ChaCha7.
Choudhuri and Maitra concluded ChaCha12 are
sufficient for 256-bit keys against differential cryptanalysis using a hybrid model of non-linear round functions and linear approximation...

\begin{array} {|l|l|}
\hline
Attack & Evaluation \\
\hline
\text{Differential Analysis }      &                    \text{No attack found}\\
\text{Rotational Cryptanalysis}     &                   \text{No attack found}\\
\text{Boomerang Attack}        &                        \text{No attack found}  \\
\text{Linear Cryptanalysis}      &                      \text{No attack found}\\
\text{Distinguishing Attack}     &                      \text{No attack found}\\
\text{Guess and Determine Analysis}       &             \text{No attack found}\\
\text{Time-Memory-Data Tradeoff Attack }   &            \text{Protected}\\
\text{Practically ChaCha Algebraic Attack}   &          \text{No attack found} \\
\text{Attacks on Initialization Process}    &           \text{No attack found}\\
\text{Single Power Analysis }           &               \text{Protected}\\
\text{Practically Difference Power Analysis }    &      \text{Protected Practically}\\
\text{Cache Timing Attack}         &                    \text{No attack found}\\
\text{Fault Injection Analysis }   &                    \text{Protected Practically}\\
\hline
\end{array}
The above table and results come from KDDI Research, Inc

simple power attack; though the rotation is vulnerable to power attack, they propose masking as a countermeasure.
differential power analysis; they demonstrated that adversary can get all keys except $k_1$ which can be found in $2^{32}$, proposed masking as a countermeasure.
Fault Injection Attack; they claim that the initial matrix $X$ or
matrix $X^{(20)}$ will be output if injection is performed on the addition.

A countermeasure against this sort of attacks is to separate variables; that is, distinct variables store the inputs and output of the addition. Consider an addition $z \leftarrow x+y$. The addition returns the initial value of variable z even if the addition is skipped. Thus, the adversary can get neither the value of variables $x$ and $y$. Algorithm 9 shows the implementation using countermeasure based on variable separation.
We should note that variable separation in source-code level does not work

They include all attacks upto 2017 in their document. I couldn't find one in 2018.


Are more complex algorithms easier to break with timing attacks? Is there a point where increasing the complexity of an encryption algorithm will make it easier to break using a timing attack?

Or is there no connection here at all?

Timing attacks rely on operations which do not always take the same time to execute, depending on the processed data. For instance, on a typical software platform (say, a PC) implementing SHA-256, all operations are 32-bit additions or rotations or bitwise combinations which take a constant time to execute, regardless of the actual operand values. SHA-256 is thus largely immune to timing attacks, because processing time, down to the nanosecond, depends only on the length of the input message, not on the values of the bits constituting the message. An attacker observing from the outside a SHA-256 computation would learn nothing about the hashed message, except possibly an estimate of the message length. On the other hand, a simple RSA implementation will leak information because the modular exponentiation incurs data-dependent and key-dependent costs (in a programmer's point of view, the code if full of "if" which operate on values computed from the input data and key).

"Complexity" of the algorithm is mostly irrelevant for that question. You can make a very complex algorithm out of operations which have no timing-related issue. Complexity is, in itself, a bad thing, since it makes analysis more complex (it is much harder to know whether the result is secure or not) and implies a higher implementation cost (in development time, and, often, in code size and execution speed).


What security guarantees do blockchains provide for data storage? When it's considered, like here

a project where a user needs to store a (small piece of data) on a blockchain

what does that really mean from a cryptographer's perspective? What security guarantees does it give? Things like availability (to which entity, under what condition and delay, with selection according to what criteria/tag), proof of origin (for one who finds that data), non-repudiation.
Is there a formal definition of a blockchain's expected properties, like we have for e.g. PRG, or a key exchange protocol?
Update: Emmanuelle Anceaume, Antonella del Pozzo,  Romaric Ludinard, Maria Potop-Butucaru, Sara Tucci-Piergiovanni's Blockchain Abstract Data Type attempt that. But it flies too high above my head. In retrospect I should have first asked: what's a blockchain, with a simple example?

Update: these NIST slides give a visual illustration of a minimalist blockchain:

They also make a basic but essential distinction between

Permissionless Blockchains, decentralized and often tied to cryptocurrencies.
Permissioned Blockchains, involving trusted participants or perhaps an authority.

What security guarantees does it give? Things like availability (to which entity, under what condition and delay, with selection according to what criteria/tag), proof of origin (for one who finds that data), non-repudiation.

In respect of data storage the blockchain itself (in a decentralised form) gives us very few guarantees.  When it is coupled with a cryptocurrency (eg. Ehtereum) then it isn't the blockchain that provides security primarily, but the cryptocurrency via the blockchain. In such cases it is the miners of the cryptocurrency that have a vested interest to keep your data.  And it costs money.
The blockchain is useful as a means to deliver something worthwhile.  Much like torrents if there is no one seeding, then it isn't a useful means of delivery.


Discrete Logarithm problem with selected order If the order of group ($p$)selected by attacker then discrete logarithm is still hard?

If the attacker can pick, say, an order $p=3$, then it's easy.
However, if the attacker is constrained to pick a large order, that may not be enough.  If the attacker is able to select a smooth group order, that is, an order $p$ which is the product of a multiset of small primes, then the discrete log problem is easy (using the Pohlig-Hellman algorithm).
Hence, unless the flexibility that the attacker is granted is more constrained than the question indicates, the answer is "no, the discrete log problem may be easy"


Order of an elliptic curve defined over a prime field I found the following algorithm to find the generator of an elliptic curve:

Find the order of the curve - N.
Choose any random point on the curve - P.
Find the order of that point - n.
Calculate co-factor - h=N/n.
Find the generator - G=h x P.

Here, let us assume the order of the generator G is n_g. It accounts to say n_g x G=O.
On replacing G from step 5, we can observe that n_g x (h x P)=O.
From this we see that n_g x h >= n_g which makes P a stronger generator with an higher order.

How should I counter this argument?

The fact that $n_g\cdot h\cdot P=\mathcal{O}$, does not mean that the order of $P$ is $n_g\cdot h$. It means that the order of $P$ divides $n_g\cdot h$, so it could simply be $n_g$.


Is it safe to reuse ECDH asymmetric keys for authentication? Alice, Bob, and Carol each generate ECDH keypairs.  Alice and Bob establish a communication channel and negotiate an AliceBob secret.

The question is:  Is it safe for Alice and/or Bob to reuse their keypairs to negotiate a new AliceCarol and/or BobCarol secret?

The intended use is authentication.  Each party can persistently store the others' public keys, and persistently store or deterministically recreate their own private keypair.  Each party could establish a new communication channel with another party at a later time, verify that the other party's current public key matches their previous public key, generate a random message M and send it to the other party.  The other party can then use the negotiated secret to HMAC sign M to generate M' and send M' back.  At this point, M' can be verified by the originating party re-calculating M' using the negotiated secret, thus validating the other party's identity.

Such keys are called static keys. Keys that are newly generated each time are called ephemeral keys. Note that you need to trust the public keys of the static key pairs to use them for authentication. This trust can be established by embedding the DH public keys in leaf certificates within an PKI.
Please note that there is an issue when static keys are used on both sides during common Diffie-Hellman key agreement: the generated secret will be static as well, as the whole scheme has now become deterministic. The solution for this is to send a nonce as well as a public key by one of the parties; this nonce can then be used during key establishment to create a unique secret key.
More information in chapter 6 of NIST SP 800-56A, specifically 6.3
Scheme Using No Ephemeral Key Pairs, C(0, 2) scheme.


ZKIP for Paillier public key correctness I'm using the Paillier cryptosystem in a protocol similar to mental poker. In the beginning of the protocol, each player generates a Paillier public key $(n,g)$.

Later in the protocol, a player may reveal any message encrypted by his public key (by revealing both the message and the randomizer used). The other players can easily verify that this message+randomizer does indeed encrypt to the original ciphertext. However, they might not be assured that this is the unique decryption of that ciphertext.

For this, it is necessary that after generating his public key, each player proves that this is a correct Paillier public key (ie. that $\gcd(\text{L}(g^\lambda \!\!\!\mod n^2), n) = 1$, or any equivalent statement).

The only way I can think of is the following:

prover generates $k$ public keys $K_1, \dots, K_k$
verifier chooses a random $i \in \{1, \dots, k\}$
prover reveals the private key for all public keys except $K_i$
verifier checks that the condition is satisfied for all revealed keys, and if so, assumes that $K_i$ is also a valid key

However, the probability of cheating only decreases linearly ($1/k$) with this scheme (as opposed to exponentially ($1/2^k$) using most ZKIPs), so it is not feasible to achieve a very high security level.

It might also be possible to prove the uniqueness of decryption directly (without proving the correctness of the key), e.g. by the verifier encrypting $k$ random messages, and the prover decrypting them and proving that the result is the same (this can be done in zero-knowledge using the homomorphic property). Unfortunately, I was unable to determine what the probability of unique decryption is with an invalid key, so the security level of such scheme is unknown.

Any ideas?

First, the awkwardness of ZKPs and distributed key generation in Paillier is the reason many protocols use exponential Elgamal for protocols like mental poker. It is additively homomorphic but has the drawback on only being able to decrypt a small message space. In your case, since users are opening their encryptions, it seems suitable. The whole protocol could be run under a common key that is shared among the users (in a distributed or threshold manner).

I don't know of a ZKP for well-formed keys in Paillier. This is just an initial thought. In the following Paillier variant (from Encyclopedia of Cryptography and Security):

It should suffice to prove $n$ is a well-formed RSA number (e.g., CM99) and prove knowledge of $\lambda$ given $y=(g^n)^\lambda$ for $y=1$ (e.g., knowledge of discrete logarithm)?


How secure is bit level permutation? Could anyone explain how secure is bit level permutation? What is the most serious threat against the security of this kind of cipher?

As a single transformation considered in isolation, a fixed bitwise permutation does not offer any security. If you examine the hamming weight (the quantity of '1' bits) of the data before and after a bitwise permutation, you will notice that it remains unchanged. A bitwise permutation simply shuffles the order of the bits of data. Repeated applications will not modify the hamming weight, and will just shuffle the bits more.

Since the permutation is fixed, we concede that anyone can calculate it at will, so anyone can calculate the inverse at will. This is pretty much the case for any fixed permutation. Since there is no additional variable that is kept secret (the key), anyone with the data and the permutation has all the information they need to invert it.

A single transformation is rarely "good enough" in cryptography, so that much can be said about almost anything. However, when considered in conjunction with other transformations, such as an s-box and a key addition layer, the result is equal to more then the sum of the components. Many strong modern ciphers are built from combinations of bitwise permutations combined with other operations.

Bitwise permutations are often the source of diffusion in modern ciphers, and diffusion is a critical part of the security of modern ciphers.

One potential downside of bitwise permutations is efficiency in software. Modern processors typically operate on words that are a minimum of 1 byte in size. To address the individual bits is possible via masking and shifting, but doing so requires more operations then we would like.

For example, a bitwise permutation that operates on 8 bytes (with 8 bits per byte) and spreads out each byte evenly among output bytes has good diffusion, but has a quadratic algorithmic complexity, which can easily make it the slowest single component of the cipher.


Is this approach able to protect against padding oracle attacks? I know that a protection against the padding oracle attack is to encrypt-then-mac. This is to avoid trying to decrypt a modified ciphertext, and leak information about padding errors.

Suppose that we have a content which is signed, and then encrypted. For decryption and signature control, this content is processed in the following manner:

decrypt the content without telling if the padding is correct on not.
check the signature on the decrypted content and return an error if it is incorrect, which should be the case if the ciphertext was modified.

Is this treatment correct when wanting to avoid PO attacks (or any other chosen ciphertext attacks)?

To be more precise, the scenario would be:

the content is signed with an asymetric key (say a RSA-PSS signature),
it's then encrypted with a symetric algo (say AES-256-CBC), with a random
key and a random IV,
the symetric key is encrypted with another asymetric key (say a RSA-OAEP encryption),
the ciphertext, the encrypted symetric key and the IV are then transmited to a receiver process.
the receiver process decrypts the symetric key without telling if there is a padding error (OAEP padding)
it then decrypts the ciphertext with the (possibly badly decrypted) symmetric key without telling if there is a padding error (AES-256-CBC padding)
it then checks the signature on the (possibly badly decrypted, but good sized) content and returns an error if it is incorrect, rejecting the received content.

You have to differentiate between it being theoretically OK and practically. Without fully checking, I can say that such an approach may be possible to fully prove. However, practically, it is almost impossible to implement it. Specifically, you have to be able to make it impossible to differentiate between an error due to the symmetric decryption or the signature. However, this is really hard to do (actually, pretty much impossible). The reason is that you need to make it time-independent. But, if you have a padding error, you don't even know how long the message is to verify. The Lucky13 attack on TLS worked exactly because code that was written to be time-independent turned out to not truly be so in certain cases. So, I would never do such a thing.

A huge number of SSL/TLS weaknesses are due to doing MAC-then-encrypt, so don't do this. GCM is so fast today on Intel processors that there's no reason not to use (just make sure you always have a different nonce).


Does exposing algorithm, key size and IV weaken the security? I am using an encryption program to encrypt my documents. Previously I have used PGP and AxCrypt, so I just wanted to see how this new tool encrypts the file.

This tool is keeping parameters like cipher name, key size,initialization vector etc. in plain text.

I want to know whether exposing these details can anyway help an attacker to focus his attacks.

Below are the top few lines of a sample encrypted file:

  »     ÌšÚ>Öùq¸ë®ûÑÅ#Ÿ £¦É² $Náøj_{
                "artifact":"header",
                "cipher":{
                         "algorithm":"AES",
                         "IvBytes":"c6+TSc609YSMQSeorKSwAg==",
                         "mac":{
                               "enabled":false
                               },
                         "mode":"CBC",
                         "padding":"PKCS7",
                         "keySize":256,
                         "blockSize":4096,
                         "iv":"c6+TSc609YSMQSeorKSwAg=="
                         },
                "metadata":{
                            "name":{
                                    "encrypted":false,
                                    "value":"~$$tmpFDC6.tmp.bc"
                                   }
                           },
                "version":1,
                "encryptedFileKeys":[{
                                      "type":"data",
                                      "id":"2705583903525488672",
                                      "value":"KIgNTpyr1+9QLSUijmpxh0jnfyi/6fIY2zoBzMsw2/B3WDmbV3+M2QsLbCLei++G8UDsjyjFiooXQpWJbUF75+Sg2AhhHS4YkvytSrgUW3/J56ky+a0XDti46e0I94oHAstL/BrS31NIqkCQW80qCja4nEzkRyHE5j3W8SR9nh8I2oDSONesy/BenzIUjz3IoNnYD750LKR7IA7xrJ75hT9uYZ9oZr9EKcKPR0Fwyy1dnVCaJWrstjnAYunnKw8irU70zmYxh6ytDsc3x70e7aj7rikQ7n3H4CquOyPqvIESpuGGWzlrTAvNoT8UHJuegAxWEMewOVkAYuwEcUnOIQt5YV8/B8ds+hfyAGRD4rf7GjsCExC+t69ekeDB63+s7LcmkCsZJKpiER3D3+OpYaANQxs2ceIEPPEPOrVbL98eTJa42elL29CeIkA5rmYtMhv6Nh+baH5LxOWxTrKM4n+dlnSwsd//CupGC0jWi8JNCu9MEx0o33S1TgqEGjYRSBLh/rfQu7CaYB4JxaluuqfOstb33JESaX77b1jBadwj1t977ZGKw4HK3HMcrQoJL1yjEd71uHOOX5bgKrvz1V9hrxNkT6MseeSV7N9Vf38oYAZrSz0dGemQBNpxZMwhKu9qd6Xi6V8v5Az7CcYcaEtQCc+tO7F3Vgmfv92U5WQ="
                                     }]
                }

No cryptography worth its salt should become less secure because its inner workings are known. It is usually assumed that the adversary has all that information when doing security proofs (Kerchoff's principle/Shannon's maxim).

In your particular case the tool is using pretty standard crypto (AES-CBC-256) so you don't need to worry about exposing its details.

As some of the other comments point out, the tool you're using seems to have disabled the MAC (message authentication code), which opens it up to attacks in which the attacker could modify the ciphertext of a given file in deterministic ways such that you would decrypt a message of his/her choosing. I would recommend you enable it.

Another thing to note about file encryption is that the ciphertext (or the AAD -Additional Authenticated Data- if you were using authenticated encryption such as GCM) should contain the filename as well. Otherwise an attacker can swap the ciphertext of a file for another one you also encrypted.

Now, you specifically ask if this helps an attacker focus his attacks. I guess the answer is yes, if there were attacks against a particular ciphersuite, knowing that it is the one being used will facilitate the attackers task. On the other hand, if the attacker can interact with the system he/she will most likely figure it out given enough time. Or they could just throw all known attacks at it. In summary, there is nothing to gain by hiding this type of information.


Encrypt without password, decrypt only with password I'm trying to implement a password manager and I want to achieve this behaviour.

User enters a master password once (eg. when the program is first run) and a key/hash of some sort is derived and stored (from which the original password cannot be recovered)
User can then choose to store data in the password bank eg.
store --id=myid --data=datatoencrypt. This data is encrypted using AES without having to prompt for a password using the stored key from step 1

At this point the encrypted data stored cannot be recovered without the original password, but new data can be added without the original password

store get --id=myid
Please enter your password: *******
The data is: datatoencrypt

I hope this makes sense. Any pointers on how I can achieve this? (I'm guessing a combination of asymmetric and symmetric encryption

Wouldn't this be just the usual asymmetric encryption, as if you were encrypting e.g. email with GnuPG?

Create a private key, store it password protected (this is your master password). Anything you need to save, encrypt using the corresponding public key (no need for a password). But only the private key can decrypt your data items, and you need to enter the password to use that.


Constructing division gate in R1CS One thing I don't quite understand is how to naively handle division operation in rank-1 constraint systems (R1CS).
supposedly A.s * B.s - C.s = 0 allows you to perform any addition/subtraction/multiplication/division operations, but how do you actually perform division from multiplication gate in any of the SNARKs system? the only thing I can think of is to use multiplicative inverse of the value you want to divide as your input for B in the A*Bpart, so that A*B becomes A*B^-1 which is same as performing A/B
My question is how does the verifier know the input prover send to the division gate is the multiplicative inverse of B? it seems that the verifier would need to either trust the prover sending the correct input (there is no way to check that the prover is sending B^-1 or some other B'^-1 ), did I miss something here?
-edited
My question is about how to build R1CS constraint on division. for example, how do I build a constraint matrix for (a*b)/(c*d) where a,b,c,d are inputs to an arithmetic circuit.

Well this question depends on what you mean by $\textit{division}$. R1CS is usually defined over a finite field $\mathbb{F}_p$, so constraints about modular inverses are quite easy to represent. On the other hand, if you're asking about integer division, which is not natively supported by finite field arithmetic, then this becomes more tricky.
Let me expand on this. I'll try to follow the notation used in Vitalik's popular post. In order to represent a modular inverse operation such as $x \cdot y^{-1} = z$, we could define two constraints in our flattened arithmetic circuit:
$\text{one = y}\cdot \text{y_inv}$
$\text{z = x}\cdot \text{y_inv}$
As you can see, we've introduced the extra variable $\text{y_inv}$ and added the constraint that $y \cdot y^{-1} = 1$ (i.e., the definition of modular inverse).
Now, you might instead be asking the question of how we perform integer division i.e., $\lfloor\frac{x}{y}\rfloor = z$, using finite field arithmetic? Recall that this is much different than taking modular inverses in $\mathbb{F}_p$.
As example, let's try $7 / 2$ in $\mathbb{F}_{11}$:
$7 / 2 = 7 \cdot 2^{-1} = 7 \cdot 6 = 42 = 9 \mod 11$, since $6$ is the modular inverse of $2$ in $\mathbb{F}_{11}$.
However, $\lfloor\frac{7}{2}\rfloor = 3$ (obviously) if we're talking about integer arithmetic. This more complex operation can be represented in $O(\log(p))$ R1CS gates using non-determinsitic advice e.g., by enforcing that $x = z \cdot y + r$ and $r < y$, where $r$ is provided by the prover.


When is an asymmetric scheme considered broken? Does the following quote imply that valid encrypted data can be created and decrypted by someone other than the owner of a private key:

  An asymmetric encryption scheme is considered to be broken if an
  attacker can decrypt a given ciphertext, even if he can convince you
  to decrypt arbitrary other ciphertexts

What conditions must exist for this to occur?  (Specifics would be appreciated)

I think you are referring to Colin Percival's Everything you need to know about Cryptography, in one hour in which he observes:

  An asymmetric authentication scheme is considered to be
  broken if an attacker with access to the verification key can
  generate any valid ciphertext, even if he can convince you to
  sign arbitrary other plaintexts.

This is called a chosen ciphertext attack, abbreviated CCA in literature.

I'm going to look at the RSA case. In the case of RSA, decryption given a ciphertext $c$ is $r = c^d \mod n$ and signing is $s = p^d \mod n$. As you have no doubt gathered, these both use $d$ the private key. So for the purposes of RSA, the two operations are related (this is a trapdoor permutation). However, assuming they weren't, being able to convince an attacker to sign arbitrary plaintexts may compromise the signing key and allow the attacker to pass themselves off as you.

Next up, actually exploiting a cryptosystem such as RSA. This paper discusses encrypting RSA properly (the use of padding) but also contains the observation that:

$$\epsilon_{n,e}(m_1)\epsilon_{n}{e}(m_2) = \epsilon_{n,e}(m_1m_2)\mod(n)$$

Re-writing this using slightly more familiar notation:

$$(m_1^e \mod n)(m_2^e \mod n) = m_1^e m_2^e \mod n = (m_1m_2)^e \mod n$$

Now, the paper notes that chosing $C\prime = C\cdot 2^e$ then $C\prime = m^e2^e$ which is equivalent to $(2m)^e$. Decrypted this is $(2m)^ed = 2m \mod n$ and so the attacker, having access to $2m \mod n$ knows $m$.

From a practical point of view, the attacker still needs to acquire the decrypted output. The attack doesn't make any assumptions as to how they achieve that, but it does demonstrate an exploit of RSA. To counter this, continue reading that paper; specifically, one should use an appropriate padding scheme.

Any crypto-system which has a similar homomorphic property will be vulnerable. For example, these slides explain similar behaviour in ElGamal.


Can the birthday attack be extended in this case? Let $H:\{0,1\}^*\to\{0,1\}^n$ be a cryptographic hash function as a black-box, and suppose we have unlimited space.

As I understand, finding $x$ such that $H(x)=0$ (if such exists) would require a preimage attack, and avg. time $O(2^n)$ (linear in the size of the output).
On the other hand, finding $x\neq y$ such that $H(x)\oplus H(y)=0$ could use the birthday attack, and therefore avg. time $O(2^{n/2})$.

My question is, if something better can be said for finding 3 (or more) distinct values $x,y,z$ such that $H(x)\oplus H(y)\oplus H(z)=0$. It seems clear that this could be done using less samples of $H$, but it's not clear to me if the time complexity could be improved.

So, as in @poncho's comment, the generalized birthday problem for $m=2^k$ inputs, fixed $k\geq 2$,
$$
H(x_1)\oplus \cdots \oplus H(x_m)=a,\qquad a \in \{0,1\}^n
$$
for any constant $a$ can be solved by using essentially (up to $o(n)$ terms in the exponent)
$$
T=O(m⋅2^{n/(k+1)}),
$$
and
$$
M=O(2^{n/(k+1)})
$$
by the algorithm in Wagner's paper.
If $m$ is not a power of two, one can use the algorithm for the next power of two.
As far as I know, no general algorithm with better complexity than $T=O(2^{n/2})$ is known for the case $m=3.$ Fix one input and do a birthday attack on the sum of the other two, which requires a list of size $O(2^n).$ If you are restricted to use the minimum memory possible, then a list of size $O(2^{n/3})$ suffices (this is also the lower bound from information theory to have a solution with non negligible probability) but it would seem that you need to generate all 2-wise sums from the list with time complexity $O(2^{2n/3})$ and check in the hash sorted list for collisions in constant time for each check.
Perhaps the experts here can enlighten us if the above  is not the case.
Calling the $m=3$ case, the 3XORSUM problem, the similar 3SUM problem for integers (instead of binary vectors) is of interest in algorithmics with many applications, see for example the question here from TCS stack exchange.


2-party private set intersection Are there dedicated protocols to achieve a private set intersection where one of the set is of small constant size $c$ and the other one of size $n$?

What are the resource complexities of this kind of protocol, in terms of communication and computation?

Here are some recent papers that explicitly study optimizing PSI for the case of unequal set sizes.

Private Set Intersection for Unequal Set Sizes with Mobile Applications; Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas
Fast Private Set Intersection from Homomorphic Encryption; Hao Chen, Kim Laine, Peter Rindal
Unbalanced Approximate Private Set Intersection; Amanda Cristina Davi Resende, Diego F. Aranha

Update:

PIR-PSI: Scaling Private Contact Discovery; Daniel Demmler, Peter Rindal, Mike Rosulek, Ni Trieu


Advantages of RSA / EC against QC attacks We know that both the RSA and ECC algorithms are vulnerable against attacks using (future) Quantum Computing (QC). Are there however any advantages of choosing one algorithm over the other?

As an example: would it be possible that the larger key size of RSA has advantages over the short key size used by ECC, possibly with regards to the amount of qbits or qbit configuration required? Would such an advantage matter in practice?

This is by no means a comprehensive answer on this subject, but perhaps it's a good start.
Shor's algorithm for (specific) ECC
This paper by Proos and Zalka compares implementations of Shor's algorithm for integer factorization and discrete logarithms for some elliptic curve groups (notably, ONLY those over prime finite fields).
If $n$ is the bit length of the group (from section 6.3):
RSA                      | ECC
-----+--------+----------+-----+--------+---------
n    | qubits | time     | n   | qubits | time
-----+--------+----------+-----+--------+---------
1024 |   2048 | 4.3*10^9 | 163 |   1000 | 1.6*10^9
2048 |   4098 |  34*10^9 | 224 |   1300 |   4*10^9
3072 |   6144 | 120*10^9 | 256 |   1500 |   6*10^9

RSA needs about $2n$ qubits, while ECC needs approximately $6n$ (for smaller $n$). Similarly, RSA needs ~$4n^3$ gates, while ECC only requires ~$360n^3$.
ECC is classically more difficult than RSA, allowing for smaller key sizes and more efficient computation. Quantumly, ECC is still more difficult than RSA, but less so, leading to what the authors call a "quantum advantage" for elliptic curve discrete logarithms over integer factorization.
Comparing RSA-3072 to ECC-256, they found that a quantum computer needs to be approximately $4\times$ as big and takes approximately $20\times$ as much time to crack RSA as compared to ECC.
Keep in mind that this work is from 2008 and is only relevant for curves over prime fields.
In practice
Obviously a factor of 4 in the number of qubits is not "much more quantum-resistant" as per the link given by fgrieu. It's very possible that ECC over GF($2^m$) is much more efficiently broken by quantum computing.
Due to the similarities of the two problems, I can't imagine that qubit configuration would have much of an impact in one direction or the other.
However, this is all conjecture on my part.

It is not likely that the gap between quantum
cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to
serve as a basis for a cryptographic strategy.

In any case, I interpret the above quote from as there being no practical difference between the two. Both should be considered utterly broken at that time.


What current authenticated key exchange standards exist? If neither of the 'big two' of TLS Handshake and IKE are appropriate in a given situation, what alternative Authenticated Key Exchange (AKE) standards exist and are recommended?

Many protocols have been proposed in the literature over the past 20+ years, though only a small subset have made it into standards of some form that are also still considered secure.

Since you do not describe why TLS Handshake and IKE are appropriate in your situation, and as long as you don't describe your situation, it's hard to really help you. Also, you haven't stated if it's only IKE that's not appropriate, or if that also includes IKEv2 (which improved the IKE protocol). Therefore, I'll simply assume you meant both.

As an alternative to IKE, the first thing that comes to mind is KINK (Kerberized Internet Negotiation of Keys). It's a protocol defined in RFC 4430. It is used to set up an IPsec security association (SA), similar to Internet Key Exchange (IKE), utilizing the Kerberos protocol to allow trusted third parties to handle authentication of peers and management of security policies in a centralized fashion.

As said — as long as you don't describe your situation, it's hard to pinpoint what might suit it best.

It could well be that your situation might be solved with RFC 6539, as IBAKE provides an Identity-Based Authenticated Key Exchange.

Or maybe "augmented PAKE" is a valid option for your situation. That's a variation applicable to client/server scenarios, in which the server does not store password-equivalent data. This means that an attacker that stole the server data still cannot masquerade as the client unless they first perform a brute force search for the password. Examples include: AMP, Augmented-EKE, B-SPEKE, PAK-Z, SRP, and AugPAKE (RFC 6628).

It's hard to tell when not knowing your situation. But I would check out KINK first… as that should be a close-to-perfect match, being an alternative to IKE.


Finding exponent $e$ in RSA given modulus and a plaintext/ciphertext pair Assuming
$$c = m ^ e \bmod n$$
and given the values of $c$, $m$ and $n$ (32 bit integers),

How would one find the exponent $e$ (also 32 bit integer) ?

In this question we are given $c$, $m$ and $n$ (32 bit integers with $0\le c<n$), and asked to find the exponent $e$ (also 32 bit integer, odd and at least $3$) matching the equation of textbook RSA encryption: $c=m^e\bmod n$.

That's impossible with certainty unless $n$ is prime (which would not be RSA) and exactly 32-bit, because then the solution is never unique; either there is no solution, or several values of $e$ are possible. For some parameters (like $m=c=0$, $m=c=1$, or $m=c=n-1$), all odd values of $e$ work. If there's a solution, there is one below $\lambda(n)$ with $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ when $n=p\;q$ with $p$ and $q$ distinct primes; that's the Carmichael function, and is less than $2^{31}$ in an RSA context when $n$ is an at-most-32-bit composite; and then $e+\lambda(n)$ will be at-most-32-bit and also be a solution.

What we can find is the lowest odd value of $e$ at least $3$ such that $c=m^e\bmod n$ holds. The simplest method is perfectly adequate in the context if we can use a computer:

$a\gets m\cdot m\bmod n$
$e\gets 1$
$b\gets m$; it holds that $b=m^e\bmod n$
repeat until $e=2^{32}-1$

$e\gets e+2$
$b\gets a\cdot b\bmod n$; again it holds that $b=m^e\bmod n$
if $c=b$

output "One solution is" $e$ and stop

output "There is no solution" and stop.

This requires $(e+1)/2$ modular multiplications if a solution is found, and  in any case no more than $2^{31}$.

There are at least two independent speedups which would allows to reduce the work, or/and tackle larger parameters:

There are better algorithms than exhaustive search to solve a Discrete Logarithm Problem, including baby-step/giant-step which reduces the work to $O(\sqrt n)$ modular multiplications; and Pollard's rho which is simpler and tends to be faster on average (but won't necessarily give the lowest $e$).
If we can factor $n$ (and it is square- free as customary in RSA), then we can solve the equation $c\equiv m^{e_p}\pmod p$ for each prime factor $p$ of $n$, then combine the results into $e$ using the Chinese Remainder Theorem, noting that if $e\equiv e_p\pmod{p-1}$ for each prime $p$ dividing $n$, this $e$ will be a solution (there might be cases where we miss the lowest $e$).


Why is RSA decryption the inverse of encryption? In RSA, to encrypt a message, the following formula is used:
$$c=m^e\bmod n$$
For decryption,
$$m = c^d\bmod n$$
is used.
However, when I try to substitute the value of $c$ from the first into the second formula, I am unable to satisfy the equation, or rather unable to simplify the expression below:
$$m = (m^e\bmod n)^d\bmod n$$
What am I missing here?

RSA is based on the Carmichael function $\lambda$ (or if you prefer Euler's totient function $\varphi$):

$$x^{\lambda(n)} \equiv 1 \pmod n$$

for every integer x that is coprime to n.

From this you trivially get:

$$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$

and multiplying both sides with x:

$$x^{k\lambda(n)+1} \equiv x \pmod n$$

the last equation holds for all integers even if they're not co-prime to n.

We chose $e$ and $d$ such that their product is 1 modulo $\lambda(n)$ or equivalently $e \cdot d = k\lambda(n)+1$ for some $k$.

Thus $(x^e)^d \equiv x^{ed} \equiv x \mod n$ which means that encryption followed by decryption returns an integer equivalent to the plaintext. By limiting $x$ to $0 \leq x < n$ you will get the original integer.

The wikipedia page for RSA lists proofs for the correctness of RSA as well.


Recovering key length from transposition block cipher ciphertext First of all I would like to say hello to all StackExchange users. So far I've been stalking the forum for some time, now it's time to leave the shadows.

In my master thesis I'm writing about heuristic methods in cryptanalysis, etc. ant colony algorithms or genetic algorithms. So far all methods seems to be quite intuitive, but I've got a problem in implementing part of them - most of these methods assume that key length is known. For substitution ciphers there are well known methods (Kasiski test, index of coincidence) of key length recovery.

Unfortunately I can't find any method of recovery key length in transposition block cipher (permutation cipher). Do you know such methods?

All best to you

It really depends on the key schedule.  IE, how is the key operated on to find the permutation to be used?

Absent that knowledge, really the only way to know is to launch searches in parallel at different key lengths, and the one that finds the answer first had the right key length.  Unfortunately anything more clever than that will utterly depend on how the key is used to generate a permutation.

Just a note:  As described, this cipher is terribly insecure; the attack is called parallel anagramming, and is not really more difficult than a crossword puzzle.  It breaks the instant the opponent has more than one block, assuming the same permutation is used for multiple blocks.

Permutation ciphers also fall to even a single block of known plaintext.


Why in BCNS protocol both parties don't follow the exact same key extraction approach Why in BCNC key-exchange protocol (page 8), Bob instead of:

$K_B \leftarrow \lfloor \bar v \rceil_{2q,2} \in \{ 0, 1\}^n$

do this instead:

$K_B \leftarrow rec(2bs', c) \in \{0, 1\}^n$.

or they are the same thing ... am I missing something? I don't understand the purpose of modular rounding function as defined by Peikert in Lattice Cryptography for the Internet (page 9) and BCNS (page 6)

Because the idea is one party (i.e. Bob) sends a signal or reconciliation information (i.e. $c$) to other party (i.e. Alice) and then both should follow the exact same approach to get one bit from every coefficient.

Answer of your question is in page $7$.

Lemma2:

For odd $q$, let $v=w+e\in Z_q$ for $w,e\in Z_q$ such that $2e\pm 1\in E \pmod q$. Let $\bar v=dbl(v)$ then $rec(2w,\langle \bar v\rangle _{2q,2})=\lfloor \bar v \rceil _{2q,2}$.


Difference between CBC-MAC and CMAC According to Wikipedia, CMAC is based on a variation of CBC-MAC and fixes some security deficiencies in it.  However, I could not find a simple and clear explanation of what the differences between the two algorithms actually are, so I thought I'd ask here:

How does CMAC differ from CBC-MAC, and why?

The problem with CBC-MAC for variable-length messages is that CBC-MAC applied to a one-block message essentially amounts to an oracle for evaluating the block cipher at values of the adversary's choice. And that oracle allows an adversary to break the scheme.

Consider first CMAC restricted to messages that consist of a whole number of blocks. Then the difference between CMAC and CBC-MAC is that CMAC xors the final block with a secret value - you could call it a tweak - (carefully) derived from the key before applying the block cipher. This ensures that the final block is treated differently from the other blocks, which in turn means that the adversary no longer has an oracle for evaluating the block cipher at values of his choice.

To make CMAC work for messages that do not consist of a whole number of blocks, CMAC (carefully) derives a second secret value. CMAC first pads the message so that it contains a whole number of blocks, then the second secret is xored with the final (padded) block before the block cipher is applied.

This extra complication could be avoided by always padding the message, but by not doing that, CMAC saves a block cipher evaluation for a significant fraction of all possible messages.

The secret values are derived by applying the block cipher to the all-zero block and then shifting the bit values (sometimes xoring bits into the low-order bits to get a finite field multiplication).


Oblivious Polynomial Evaluation and Encoding Payload I am trying to parse this paper. I think I do come to understand the general concepts go into this type of Private Set Intersection, based on Oblivious Polynomial Evaluation. I was able to produce a workable prototype based, with just the straight forward exponential El Gamal encryption.

The point-by-point of the protocol can be found in the section 4.2 PM Semi-Honest Protocol. What struck me that single remark in the step 2. where it says

  ... (One can also encrypt some additional payload data py by computing Enc(rP(y) + (y|py)). C obtains py iff y is in the intersection.)

I got quiet excited because that's what I was looking for, but the symbol '|' doesn't get explained and I couldn't find what is it supposed to be. Given that the idea is that in the case of a root P(y) evaluates to 0, and so ENC(rP(y) + y) = ENC(y). This means that anything I do with the added 'y' value will stop C (the client) to find the matching values with her own private set.

Is this some special property of the Paillier encryption I don't know about (I don't know this crypto-system very well yet), or is it something I can make work with using the exponential El Gamal encryption system?

The bar is just concatenation of strings. As long as you are comfortable treating things both as bit strings and as group elements, there is nothing special about the encryption scheme being used here.

Without these payloads, the idea of the protocol is the following. Bob sends a set $Z$ of ciphertexts. Alice computers her output as $\{ \mathsf{Dec}(z) \mid z \in Z \} \cap X$. Items shared by Alice & Bob will be output by Alice in this way. Items not shared by Alice and Bob will result in a random value for  $\mathsf{Dec}(z)$, so they are negligibly likely to be output by Alice.

Now, with the payloads, suppose the parties are doing PSI on items that are $\ell$ bits long. Now Alice would compute her output as
$\{ \mbox{first $\ell$ bits of } \mathsf{Dec}(z) \mid z \in Z \} \cap X$. It is still the case that any item not shared by the parties is negligibly likely to be output by Alice (negligibly likely that its first $\ell$ bits match one of Alice's items). But you can use the remaining bits to encode a payload for each item.

This assumes is that the ElGamal/Paillier group is large enough to encode strings of this extra length. But without loss of generality you can always:

shorten the items: agree on a common hash function and do PSI on hashes of your items.
shorten the payloads: make $p_y$ a short key for a symmetric-key encryption, and send along an encryption of your actual (possibly huge) payload using this key.

edit: Oh, just saw that you're using exponential El-Gamal. You will have to alter things syntactically but not conceptually. As an example, let $V$ be the group element whose bitwise representation is the item+payload string $y | p_y$. Now $V$ has some discrete log (that exists but would be hard to compute) $V = g^v$. I claim that Bob should encrypt $rP(y) + v$ in the exponent. Fortunately you don't have to know $v$ to do it, just obtain an ElGamal encryption of $g^{rP(y)}$ in the way you already know, and use its homomorphic property to multiply by $V$, making a standard ElGamal encryption of $g^{rP(y)} \cdot V$. When Alice decrypts, she either sees a random thing, or else she gets group element $V$. Instead of trying to reason about $V$'s discrete log, Alice can just look at the bit-representation of $V$ and identify it by whether $y$ is a prefix.

The reason for all this is that the payload can't be conveyed in the exponent (Alice will never be able to get it back). Instead it must appear in the result of her standard ElGamal decryption. In exponential ElGamal, you can test whether decryption equals a value you already know (in the exponent), you can't decrypt to learn a value in the exponent that is new to you.


How does DPA work on AES? I am really not much of a crypto guy so I don't really get how a differential power analysis on AES works.

Can somebody explain it to me how it basically works?

I'm not an expert yet, but this is how I remember it.

DPA or differential power analysis is a side-channel attack on hardware implementations of cryptographic algorithm.

All electronic circuits consume different amount of power depending on the activity of individual transistors. For example, more transistors may switch when adding the hexadecimal bytes A7 to B9 than when adding 01 to 00.

When attacker connects something like AES protected memory card to a machine that allows him to gather very precise information about it's power usage he can, after having enough measurements, statistically guess some things that he was not supposed to know and brake chosen-plaintext attack security. That way (given enough time) attacker will guess the key faster then using exhaustive search (brute force algorithm)


Are there any differences between PIR, oblivious transfer and differential privacy? I am trying to make a taxonomy of the different purposes of some cryptographic protocols. Generally speaking, the purpose of PIR, oblivious transfer and differential privacy--it sounds as if they were invented for the same purpose: "Give me the information I want without learning anything about this information".

Can we make the aforementioned generalization?

The other answers are good but I thought I would systemize the differences with a single example. Say Bob has a database with 10 entries of the form {name, salary} and Alice would like to query it.

With PIR, Alice can retrieve any entry or entries of her choosing (say the 8th entry) without Bob learning which one. The trivial PIR is Alice just retrieves the entire database. In this case, Bob doesn't know which entry she was interested in. PIR protocols aim to reduce the amount of information Alice has to retrieve from 10 entries in this trivial case to something like the size of 4 entries.

With OT, Alice can retrieve a single entry of her choosing (again say the 8th) without Bob learning which one. Bob is additionally guaranteed she can only see the single entry she chose and gets no information about the others.

With differential privacy, Alice is not retrieving entries themselves but is instead getting an aggregate statistic for all the entries. For example, say she wants to learn the average salary. With differential privacy, the true average salary is not returned. Instead enough noise is added to the average such that it masks the contribution of each individual entry. Put another way, the number returned would still be plausible if you dropped any single entry from the database.

OT and PIR are similar: cryptographic protection against information disclosure. Differential privacy is more of a statistical approach.


What is TPMFail attack and what are the countermeasures? Trusted Platform Module (TPM) is designed as a hardware-based root of trust to protect cryptographic keys even against system based adversaries.

Although Intel's firmware based fTPM has FIPS 140-2 and STMicroelectronics hardware-based TPM has Common Criteria EAL 4+ certifications, recently in an attack TPM-FAIL: TPM meets Timing and Lattice Attacks by Moghimi et al., They demonstrated that an attacker can recover server's private authentication key even by remotely.

How do the attacks work?
What are the countermeasures?

In short, TPMFail attack is black-box timing analysis of TPM 2.0 devices deployed on computers. The TPMfail team is able to extract the private authentication key of TPMS's 256-bit private keys for ECDSA and ECSchnorr signatures, even over networks. This attack successful since there was secret dependent execution in TPMs that causes the timing attacks. To mitigate this attack, a firmware update needed for Intel fTPM and hardware replacement for STMicroelectronics TPM is needed.

  How do the attacks work?

The attack is performed in three phases

Phase 1: The attacker generates signature pairs and timing information to profile of the given implementation fTPM or STM's. This is the pre-attack stage and the attackers know the secret keys and used nonces. This profile can be measured of-site. After the measurement, they have complete correlation information about the timing and secret nonce $k$ used in signatures. The bias is related to Leading Zero Bits (LZB).
Phase 2 With the timing on their hand the attackers target a system with the same TPM devices and collect signature pairs and timing information.
Phase 3 The attacker applies lattice-based cryptanalysis with filtered signatures to get biased nonces to recover the private key.

In more Details

The timing measurement Normally Intel fTPMs Linux kernel driver uses command response buffer in push mode. The driver checks the status after 20 milliseconds, if the calculation is not ready, the driver re-checks. It doubles the time for every check. This driver doesn't allow a perfect timing measurement, therefore, the TPMfail team developed their kernel driver to perfectly measure the timing. They collected 40000 ECDSA signature. They similarly build a driver for STM's hardware TPM.
Timing Analysis: They discovered that a bit-by-bit scalar point multiplication implementation that skips the computation for the most significant zero bits of the nonce. Therefore nonces with more leading zero bits are computed faster in TPMs.

On the below figure it is Intel fTPM's timing histogram. On the right a nonce depended software implementation. Comparing the figures leads to the information that Intel used a 4-bit fixed window during Fixed Window Scalar Multiplication.

In the left figure, there are 4 regions, the fastest one has nonces with 12 most significant windows are zero, next has 8, next has 4, and the slowest region has none.

The Lattice-based Cryptoanalysis

They used The Hidden Number problem lattice attacks. They used BKZ algorithm over the Sage. This attack recovers ECDSA nonces and private keys as long as the nonces are short. Since nonces are selected randomly half of them have zero in MSB, a quarter of them have two zeroes in MSB, etc. The side-channel will help to select the shorter nonces to apply the lattice-based attack.

The key recovery with attack models

System adversary a user with administrator privileges to extract the keys. The required signature for 12, 8, and 4 leading zeros for ECDSA

\begin{array}{|c|c|c|c|}\hline
\text{bias} & \text{need signatures} & \text{total sign operations} & \text{succes rate}  \\\hline
4-bit & 78 & 1248 & 92\text{%}\\ \hline
8-bit & 34 & 8748 & 100\text{%}\\ \hline
12-bit & 23 & & 100\text{%} \\ \hline
\end{array}

The time for collecting signatures on i7-7700 is 385 signature/minute. Collecting the 8784 signatures took less than 23 minutes. Once the data is collected the Lattice attack took 2 to 3 seconds! for dimension 30.

For Intel fTPM Schnorr signatures in 27 minutes 10,204 signature are collected with 8-bit leading zeroes. For 4-bit case 65 samples found from 1.040 signature in 1,5 minutes.

STMicroelectronics TPM ECDSA Key Recovery

They were able to recover the ECDSA key after 40,000 signature for 8-bit with 35 fastest signatures.
User level as before mentioned, in user-level the kernel driver checks the result, first in 20 micro seconds. This lead the below timing measure;

They collected 219,000 signatures that contain noisy 855 8-bit leading zeros. With filtering, they get 53 high-quality signatures with 100% recovery rate. They also look for the 4-bit case.
Remote adversary This is the weakest adversary in terms of capability. They set up a fast 1G network and requested 40,000 signatures to collect timing information. Although the timing histogram noisier, it still shows information about nonces with 4 and 8-bit leading zeroes. For the 4-bit case; 1,248 signatures are collected in less than 4 minutes and for the 8-bit case; the required signature is collected in 31 minutes.

They used this remote attack against StrongSwang, an open-source IPsec VPN implementation that is supported by modern OSes, including Linux and Microsoft Windows.

  What are the countermeasures.

countermeasures

The kernel driver can increase the delay time so that this doesn't leak information. However, this may require different levels with different TPM devices. Therefore this is no bulletproof.
Constant time implementation. This is the key to the attack point. With data depending calculation the TPMfail team is able to distinguish the calculations. Once calculations are done in constant time, the side channel will be harder. They have testest the patches and couldn't execute the attack anymore.
Using double size nonce and setting the high bit to 1 *

Patches

CVE-2019-11090. Intel issued a firmware update for Intel Management Engine (ME) including patches to address this issue on November 12, 2019.
CVE-2019-16863. STMicroelectronics updated version of their TPM product for verification and sent to authors. They tested and see that it is resistant. Since it is hardware it requires replacement.

Note: From authors:

  TPMs have previously suffered from vulnerabilities due to weak key generation. However, It is widely believed that the execution of cryptographic algorithms is secure even against system adversaries.

*Thanks to commentors. See :Why EdDSA held up better than ECDSA against Minerva. Minerva is also a smilar work on smart cards.


random number generator 10-side dice alternative A lot of sites (e.g. Dirk Rijmenants') refer to 10-side dice to generate random number for one-time-pad. I was thinking about new ways to generate random numbers, letters and passwords. here what I got…

To generate random numbers:

Take out keys numbers from 0-9 from old keyboard, calculator or mobile pad and put it in a cup shake it then take one out write it on paper threw it back, shake, and take another... so on till get my numbers.

To generate random letters for OTP:

Take out letters key from an old keyboard put them in a cup shake it and take one out write it on paper then threw it back, shake and take another one... repeat till get my otp letters.

To generate random passwords:

take out letters key from black keyboard (for small letters) and another one white for capital letters, symbols/numbers keys black keys for symbols, white for numbers, then put all keys (72 keys) in a hat, shake it and take one key out write it down throw it back shake, take another one... untill I get my true random password.

Can any one confirm that way as a true random numbers, letters and passwords generator?

One problem is that keyboard keys may or may not be uniform. Look at the F and J keys - they may have a little dot of plastic to identify them with your fingertips. That little dot may make them heavier or lighter than other keys, affecting how they shake up in a hat. Some keyboards, like Das Keyboard, were built with different spring actions for different keys, which might or might not affect the weight or shape of each key. And some keyboards have larger curvatures for various key tops, and those keys definitely have different mass.

The problem is that creating perfectly symmetric keys is not a design goal for keyboard designers, so without studying and measuring each keyboard, you won't have assurance that any particular keyboard is suitably random for your purpose.

They may also be just fine if you are not looking to generate thousands of passwords. If you're concerned, though, consider repurposing a device designed to generate random values. A bingo cage could be refilled with 26 hand lettered balls. Playing cards could have handwritten letters and shuffled extensively. A 100-sided dice could be repainted to match your character set, and extra values blacked out to indicate "roll again".

See also "diceware" for a way to turn 6 sided dice into passwords.


Is it theoretically possible to construct a string that contains its own hash value? After saw the xkcd comic Self-Description, I wonder if it is theoretically possible to construct a self-descriptive string that contains its own hash value?

Let's say the string's MD5 value is 663ef7d3f38cf900574cd4d9f83eb1b7, the string would be something like:

...
The md5sum value of this file is 663ef7d3f38cf900574cd4d9f83eb1b7
...

Yes, for any secure cryptographic hash function, it is overwhelmingly likely that there exists a string which contains, or even begins with, its own hash value (in any given encoding, even).  However, if the hash function is indeed secure, it is also exceeding unlikely that we could ever find such a string.

First, let's look on the positive side.  A good cryptographic hash is, a priori, supposed to be indistinguishable from a random function from the set of all bitstrings (or byte strings) to bitstring of a given fixed length $k$.  For such a random function, the probability that a randomly chosen $n$-bit string (where $n \ge k$) maps to its own $k$-bit prefix is $1/2^k$.  Since there are $2^n$ distinct $n$-bit strings, the probability that none of them maps to its own $k$-bit prefix is:

$$\begin{aligned}
(1 - 1/2^k)^{2^n}
&= \exp(2^n \log(1 - 1/2^k)) \\
&\lesssim \exp(-2^n/2^k) \\
&\to 0 \quad \text{as } n \to \infty
\end{aligned}$$

Thus, the probability that there is at least one $n$-bit string that maps to its own $k$-bit prefix tends to $1$ as $n$ increases.  Indeed, the convergence is extremely rapid, being given by the exponential of an exponential.  For example, for a 256-bit hash, the probability that there exists some 260-bit input string that hashes to its own 256-bit prefix is about $1 - \exp(-2^{260}/2^{256}) =$ $1 - \exp(-2^4) \approx$ $1 - 10^{-7}$.  For 261-bit inputs, it's $1 - \exp(-2^5) \approx$ $1 - 10^{-14}$, and so on.

Obviously, the probability that there is an input string that hashes to some substring of itself must be at least as high as the probability that there is one that hashes to its prefix.

In particular, a curious corollary of this result is that, for any secure hash function, the probability that there exists an input string that hashes exactly to itself is very close to $1 - \exp(-1) =$ $1 - 1/\mathrm e \approx$ $0.63$.  (This approximation is good as long as the output bit length $k$ is greater than about 4 or so.  For, say, a 256-bit hash function, it's as close to exact as makes no difference.)  This is a general mathematical result: for any sufficiently large set $S$, a randomly chosen function $f: S \to S$ has a fixed point with probability close to $1 - 1/\mathrm e$.

Now for the bad news: to find such a string by brute force, the expected number of trials we'd need is $2^k$.  For, say, $k=256$, such a search is way beyond not just currently available computing power, but any conceivable computing power achievable in the universe using known physics.

Now, of course, real hash functions are not actually random functions, and it's possible that there might be some way to find such strings more efficiently than by brute force.  However, if such a method were found, it would arguably be good evidence that the hash function in question was not secure, and that its use should be discontinued.

In particular, the ability to efficiently find an input string that hashes to a given value would be a clear break of first preimage resistance, and any hash function allowing it would be considered completely broken.  Technically, just having the ability to efficiently find strings that hash to a substring of themselves, without being able to control what the actual hash value is, would not violate any of the three standard security properties required of a hash function (first and second preimage resistance and collision resistance).  However, it would allow the hash function to be distinguished from a random function, and in practice, any plausible attack that would allow such input to be found would almost certainly compromise other security properties of the hash as well.


Why does the following SIS-based decision language not make sense? I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not.  I read in the question Relation between decisional SIS and leftover hash lemma in lattices that deciding between the distributions (A, u) when $A \in Z_{q}^{n \times m}$ and $u = Ax$ for some short x, versus the case that "u" is random is unfeasible because these distributions are statistically close.

However, what keeps us from looking on this language (which seems closely related to SIS to me), and ask how hard is it to decide it?

$$L_{m,n,\beta, q} = \{(A, u) \in Z_{q}^{n \times m}\times Z_{q}^{n}\,|\, \exists x \in Z_{q}^{m}: Ax = u \wedge ||x|| \leq \beta    \}$$

This language seems well defined to me and in the case of $\beta \leq q$ it feels non-trivial too (looking on the first norm to keep the combinatorics simple - at most $(\frac{\beta}{q})^{m}$ of u's are in the language for each A...)

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A = [B' | I]$. Then $C^{-1} u = A' x = B' x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.


Privacy of vote from tallying authority in El Gamal Voting Schemes I've been reading this paper about ElGamal encryptions and its application in electronic voting:

http://www.win.tue.nl/~berry/papers/euro97.pdf

Section 2.3 talks about using Shamir secret sharing so that t-out-of-n authorities need to combine to decrypt an ElGamal ciphertext. This makes sense so that after multiplying the voters' individual commitments, authorities can combine to reveal the sum of the votes.

My question is, if this is the case, can the authorities not take advantage of this to decrypt individual voters' commitments since the commitments still use the same $g$ and $h$ values after all? Where does the security of the vote from the authority come from.

Section 3 talks about creating commitments using random values $b \in \{-1, 1\}$ and then posting another value $e \in \{-1, 1\}$ such that vote $= b \cdot e$, which I think might be where the security comes from, but does not expand further on this.

Any help is appreciated!

The random $b,e$ values would seem to allow the uniform randomisation of the message between $G$ and $G^{-1}$.

Also, while reading a technical article at this level, one can note the citing of sources [SK94,CFSY96] where the technique seems to have been first used and follow up those.


How to correctly implement an archetypal encrypt-then-MAC AES-CTR + HMAC mode cipher? I've created an AES implementation in Python as a learning experience (mainly for encrypting/decrypting files), and wanted to make sure that I haven't made any huge mistakes in my logic (of course, implementation is another story).
The block cipher mode of operation is CTR. The implementation supports AES-128, AES-192, and AES-256 (default).
The AES key and HMAC key are generated from a user password using hashlib's pbkdf2_hmac with SHA-256, and a random 16-byte salt (I create a 64-byte key and split it in half for each key; for AES-128, I create a 32-byte key and split it in half).
The CTR IV is created by a random 8 byte nonce and an 8 byte counter that starts at 0. The salt is written as the first block of the ciphertext, followed by the CTR IV as the second block.
Lastly, a 32-byte HMAC value of the ciphertext is created using the HMAC key and SHA-256 and written as the last two blocks of the ciphertext (32 bytes).
When decrypting, the HMAC value is checked against the rest of the ciphertext before decrypting.
Is there any issues with this logic? From a cryptographical point, where are the weak points?
Thank you!

You are describing encrypt-then-MAC using AES-CTR for encryption and HMAC for the MAC. This indeed results in authenticated encryption.
There may be better choices for the key derivation function, but I'm not very familiar with the options, so I'll let others comment. I don't understand why you salt the KDF when deriving the key. This just means that you will need to re-key for each ciphertext. In some ways, re-keying is better for security (maybe not here with low-entropy passwords seeding the key), but usually people like to avoid re-keying for the sake of performance.
The IV is only $8 \text{ bytes} = 64 \text{ bits}$, so you will start to expect collisions after encrypting $2^{32} =$ a few billion ciphertexts. This doesn't seem very good to me. You are devoting a full $8 \text{ bytes} = 64 \text{ bits }$ to the counter. Do you really need to support ciphertexts that are $2^{64}$ blocks long? A better balance between IV+counter  length would be preferable. For example, with a 12-byte IV and 4-byte counter, you avoid IV collisions up to 2^48 and can support ciphertexts that are $2^{32}$ blocks long ( $2^{32} \times 128 \text { bits } = 0.5 \text{ terabits} = 64 \text{ gigabytes} ).$


New quantum attack on lattices (or Shor strikes again)? Lior Eldar and Peter W. Shor published a paper on arXiv.org in which they present a new quantum algorithm against a variant of BDD. They claim that their new algorithm can efficiently solve the following problem:

  Given a lattice $L$, a vector $v$, and numbers $b = {\lambda}_1(L)/n^{17}$, $a = {\lambda}_1(L)/n^{13}$ decide if $v$'s distance from $L$ is in the range $[a/2, a]$ or at most $b$, where ${\lambda}_1(L)$ is the length of $L$'s shortest non-zero vector

Moreover they state that

  improving these parameters to $a = b = {\lambda}_1(L)/\sqrt{n}$ would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.

Now, while I assume the authors refer here to Regev's original proposal, nowadays, there exists a zoo of LWE-type assumptions, used in lattice-based crypto. These assumptions mainly differ in the choice of parameters / used distributions.

My question is, does anyone have an idea how many of these or which class of LWE-type assumptions are broken by the proposed algorithm?

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) of http://www.scottaaronson.com/blog/?p=2996


Calculate the RSA private exponent from the CRT parameters I am trying to make the RSA structure of Openssl manually, knowing
the public key ($n$, $e$) and the CRT parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$.

That is, I want to get the $d$ value (private exponent) of the RSA structure by using Openssl API. If there are already any implemented functions, it would be great to me.

Bonus question: is it possible if I have $p$, $q$, $d_P$, $d_Q$ and $u$ but not the public key? I know that $n = p q$, but what about $e$?

Calculate $\phi(n) = (p-1) (q-1) = n - p - q + 1$. Then $d = e^{-1} \mod \phi(n)$.

With OpenSSL, the code should look something like this (error checking omitted):

BN_CTX *ctx = BN_ctx_new();
BIGNUM *d = BN_dup(n);
BN_sub(d, d, p);
BN_sub(d, d, q);
BN_add_word(d, 1);
BN_mod_inverse(d, e, d);
BN_ctx_free(ctx);
return d;

If the public exponent is not known, it's usually possible to guess it, since it's usually chosen from a very small pool. But failing that it's possible to find working values of both the public and private exponents from $d_p$, $d_q$, $p$ and $q$. See user94293's answer.

The inverse calculation is less straightforward. There's a good description in Twenty Years of
Attacks on the RSA Cryptosystem by Dan Boneh (Fact 1) or in How to calculate RSA CRT parameters from public key and private exponent


Analyzing/Breaking a strange One-Time-Pad In my assignment there is a bonus question:

It asks me to decrypt a file which has been encrypted using an One-Time-Pad.
But the ciphertext seems to contain english word fragments and other parts which in my opinion should not be in the file if an otp had been used.

The ciphertext seems to be some part of a boot log.

Now this all may have been done on purpose to confuse the students.

My question is:

Does this information help me in anyway to find the plaintext?
Would there be another way to find the plaintext, assuming that they did not use a completely random key?

I've uploaded the ciphertext here.

I didn't actually manage to download the ciphertext you linked to — I'm pretty sure I clicked the real download button, and not the fake one in the ad next to it, but all I got was a long delay followed by an error message, and the site itself looked shady enough that I didn't feel like investigating further.  However, since what you really seem to be asking is a general question about exploiting non-randomness in a one-time pad, and since anything else would be off-topic here anyway, let me just try to give a general answer.

A proper one-time pad, as the term is usually used in cryptography, requires each key letter (or byte, or whatever your cipher alphabet consists of) to be chosen independently and uniformly at random from the full cipher alphabet.  As a consequence, it follows that the ciphertext will also look like a perfectly random sequence of letters.

While such a random sequence can, just by chance, contain occasional substrings that look like English words, they shouldn't appear significantly more often than any other substrings of the same length.  (However, do note that the human brain tends to be good at picking apparent patterns out of randomness, so unless the non-randomness is really obvious, you really should check this with a proper statistical test rather than relying on just your intuition.)

If the ciphertext looks recognizably non-random, it's possible that either:

the key used to encrypt it isn't really random, but might instead e.g. be the contents of some non-random file; or
the encryption process itself might be somehow broken, e.g. some parts of the plaintext might not be encrypted at all for some reason.

In the first case, your situation is basically the same as if you were attacking a two-time pad (i.e. a proper one-time pad with a reused key).  Specifically, with a reused key, combining the messages lets you cancel out the key, after which you're left with the XOR (or modular sum or difference, depending on which kind of OTP is involved) of the two non-random plaintexts.

If you're lucky, you may be able to identify the source of one of the plaintexts (e.g. it might be available online), which will then let you directly decrypt the other.

If you're not so lucky, you may be faced with a painstaking letter-by-letter reconstruction process, using crib dragging, intuition and lucky guesses to construct two plausible messages that, when XORed, yield the known XOR of the ciphertexts (or, in your case, the ciphertext itself).  While this process can be automated to some extent, in my experience it tends to work poorly without close human guidance, at least unless you have a very good predictive statistical model available for at least one and preferably both of the messages.

Anyway, since this was given as an exercise, I assume it probably is solvable somehow using a reasonable amount of effort.  You'll just first have to figure out exactly what's gone wrong with the encryption, to produce such a non-random ciphertext.

Ps. See also:

How does one attack a two-time pad (i.e. one time pad with key reuse)? (already linked above)
Many time pad attack
Attacks on Biased OTP
What does it mean when two encrypted files, encrypted with the same method but with different keys, when xor'd together, produce a repeating pattern?

There are probably other relevant earlier questions on this site, too, but those happened to be ones that I'd answered myself before.


Verification in Threshold RSA or Threshold Paillier In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing decryption in the context of voting or lotteries") a square $v$ in $\mathbb{Z}_N^*$ ($\mathbb{Z}_{N^2}^*$ respectively) is used for the verification of the private key shares. For a private key share $s_i$ the public verification key $v_i$ is then $v_i = v^{s_i}$, where $v$ is an element of the cyclic subgroup of squares in $\mathbb{Z}_N^*$.

My question is, why does $v$ has to be a square?

This is to ensure $v$ is in the cyclic sub-group $G$ of $Z_N^*$ that has a large enough order $m=p'\cdot q'$. Moreover, with a large probability $v$ is a generator of $G$, so that $v_i=v^{s_i}$ is a one-to-one mapping from $s_i$ to $v_i$, which is important when proving correctness of the shares.


Degenerate discrete logarithm in binary field Given a field $\mathbb{F}_{2^n}$, are there any choices of primitive element $g$ that make the discrete logarithm easier for that generator? That is, are there any degenerate cases?

For example, if I choose a small generator like $g = x$ in $\mathbb{F}_{2^{256}}$, can I quickly find $n$ such that $g^n = a$ for a given $a$? Or is this equally difficult for any $g$ picked in any $\mathbb{F}_{2^n}$ over any irreducible polynomial?

It is equally difficult (within a factor of 2) for any irreducible polynomial.

Suppose $g$ was your 'cheap' irreducible polynomial, that is, one for which, given $g^n$, you can rederive $n$ quickly.  Then, given an arbitrary pair $h, h^x$, you can quickly find $a, b$, such that $h = g^a$ and $h^x = g^b$, and then immediately deduce that $x = a^{-1}b$


Get RSA PlainText without Knowing Private Key If I have an algorithm,RSA-Crack(), that, for a given RSA public key (n,e), is able to decrypt 1% of the messages encrypted with that key (without knowledge of the corresponding private key).Can there be an efficient algorithm that uses RSA-Crack() as a building block, and can decrypt any message - without knowing the private key.

Now, I know that I can use the factoring algorithm to devise the value of p & q from N (that is a part of the public key), after which I can use the Euler function to generate the new decryption exponent (e) and all.
But my main criteria is how do I use RSA-Crack() as a Building Block to decrypting the message.

A message is encrypted with RSA as follows:

$c_1 = m_1^e \bmod{n}$

If I throw this message at your function RSA-Crack(), there is a $0.01$ probability that the function will return the plaintext $m_1$.

To increase this probability, we can use the malleability of textbook RSA (this is also known as the homomorphic property of textbook RSA). Given $c_1$, compute $c_2 = c_1\cdot 2^e\bmod{n} = (m_1\cdot 2)^e \bmod{n}$. There is again a $0.01$ probability that $c_2$ can be broken by your function. Since a break there would give you $m_1$ (just divide the answer by $2$ if it is successful), the probability that you have recovered $m_1$ is now $0.02$.

Repeat this process replacing $2$ with $3,4,5,\cdots,100$ and you have a guaranteed break of the plaintext. I.e, compute $c_i = m_1\cdot i^e\bmod{n} = (m_1\cdot i)^e\bmod{n}$ and run $c_i$ through your RSA-Crack() function. If it is successful, divide the answer by $i$ to get $m_1$.


Katz/Lindell Problem 7.6 Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator?

The answer is yes if $f$ is a pseudorandom permutation according to theorem 7.6 in the book. I am fairly certain that the answer is no if $f$ is no longer bijective. Intuitively, the first part of the string $G(x)$ is no longer uniformly distributed if we choose a uniformly random $x$, so $G$ should generally not be pseudorandom. However, I think it may depend on how far $f$ strays from bijectivity, as demonstrated by the following two extreme cases:

If $f$ were constant (taking a value $y_0$), then an obvious distinguisher would be the done that outputs $1$ if the first part of the string $G(x)$ is $y_0$. This has advantage $1-2^{-n+1}$, which is not negligible. The issue, of course, is that $f$ is clearly not a one-way function.
If $f$ misses precisely one point of its codomain, then there is some $y_0$ which is hit exactly twice. Then the distinguisher from the above example has advantage $2\cdot 2^{-n+1}-2^{-n+1} = 2^{-n+1}$, which is negligible. I can't think of a better distinguisher either.

Let $g(x)$ be a length-preserving one-way function. Then $f(b||x)=1||g(x)$ (where $b$ is one bit of input) is a length-preserving one-way function and $\text{hc}(b||x)=b$ is a hard-core predicate for $f$. But $G(b||x)=f(b||x)\|\text{hc}(b||x)$ is not a pseudorandom generator.

So the answer to the problem is no.

edit: My original answer did not prove that the counterexample $f$ actually had a hard-core predicate.


PKCS#7 signed data structure in signed PDF document Is it mandatory to include PKCS#7 data (OID 1.2.840.113549.1.7.1) octet string into the sequence of PKCS#7 signed data?

I mean if you want to sign PDF, you are basically adding PKCS#7 container inside the document. And if the PCKS#7 signed data contains the whole data that was signed, that doubles the lenght of the signed PDF document.

If this is not mandatory, is there any way how to remove the octet string from OID 1.2.840.113549.1.7.1? Or is PKCS#7 signed data integrity protected so no one is able to just remove this octet string?

The actual data can be omitted from a SignedData encapContentInfo; see current CMS RFC which is not materially changed from earlier versions. The RFC calls this "external signature"; IME it is also called "detached signature" or "clear-sign[ing,ed]", and is widely used. For example S/MIME signed messages usually are a multipart containing the plaintext data and separately (the encoding of) a no-data/external/detached signature on that plaintext; this allows the text part to be handled by a non-SMIME-aware or even non-MIME-aware program (only without signature verification).


Predicting Java's PRNG using partial output I have a program (a game) that uses Java's nextInt function with parameter 0x10000 to get a random 16-bit number.
Java's nextInt() is an 48-bit seed LCG with the following formula:

seed[n+1] = (seed[n] * 0x5DEECE66DL + 0xB) mod (1 << 48)

nextInt() is implemented in such a way that the random number I receive is the current seed's most significant 16 bits when given argument 0x10000. [Java only does this for an argument that is a power of two]

So let me describe the situation: In the game, I get to have two sequential outputs of nextInt(0x10000), R[i] and R[i+1] (which are respectively seed[i] and seed[i+1]'s top 16 bits).

My question is: what information can I extrapolate about the next output of randInt() (R[i+2]) ?

EDIT: I'm in a situation in which a bruteforce of even more than 30,000 steps is not practical..and all I have are these two consecutive outputs. So, is it even feasible extracting some info given these restrictions? (And please be gentle, I don't have any knowledge in math beyond high school)

Assuming this generator is well-seeded, you probably can't learn much about the next output.  You observe two outputs, so 32 bits in total.  The state of the generator is 48 bits.  Thus, there will probably be about $2^{16}$ states of the generator that are compatible with your two observations.  This means that most of the 16-bit values for the next output are (heuristically) likely to be possible.

Thus, your best bet might be to look at how the generator is seeded.  I have a vague recollection that Java's PRNG is poorly seeded, using a seed that has less than 48 bits of entropy.  If this is the case, then it might be possible to predict the next output, by enumerating candidates for the initial seed and seeing which ones are consistent with the outputs you've observed.

If you need to enumerate which values for the next output are possible, here is a way to do it.

The naive way is to enumerate all $2^{32}$ possible values of seed[i] (you know its top 16 bits, thanks to your knowledge of R[i], so you just need to enumerate all possibilities for its low 32 bits), then test which ones are compatible with the observed value of R[i+1], and for each one that survives, compute the resulting value of R[i+2].  This takes about $2^{32}$ steps of computation, so you can probably make it run in a few seconds or tens of seconds of computation power.

With a little bit of cleverness, you can make this run a lot faster.  Since we know the value of R[i+1], we know the range of possible values for seed[i+1]: in particular, we know that 2^32 * R[i+1] <= seed[i+1] <= 2^32 * R[i+1] + 2^32 - 1.  Also, we know that seed[i+1] = 0x5DEECE66D * seed[i] + 11 - c * 2^48 for some c in the range 0x5DEEC * R[i] <= c <= 0x5DEED * (R[i]+1).  Moreover, we know the top 16 bits of seed[i], so we can write seed[i] = 2^32 * R[i] + x, for some integer x satisfying 0 <= x <= 2^32 - 1.

Combining all of this, it follows that

2^32 * R[i+1] <= 0x5DEECE66D * 2^32 * R[i] + 0x5DEECE66D * x + 11 - c * 2^48 <= 2^32 * R[i+1] + 2^32 - 1

or equivalently,

(2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] - 11 - c * 2^48)/0x5DEECE66D <= x <= (2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] + 2^{32} - 12 - c * 2^48)/0x5DEECE66D

This range is of width less than 1, so if you know the left-hand-side and the right-hand-side, you can immediately infer x.

Thus, if we know c, then the value of x is determined, which reveals seed[i] and thus the next output of the generator.  Finally, there are only about 0x5DEED$\approx 380,000$ possible values of c.

This gives an algorithm that enumerates all possible values for the next output, using about $380,000$ steps of computation.  We enumerate over all $380,000$ possible values of c; for each possible value of c, we round (2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] + 2^{32} - 12 - c * 2^48)/0x5DEECE66D down to the nearest integer, call it x, and then we infer the value of seed[i] (namely, seed[i] = 2^32 * R[i] + x) and run the generator for two steps to observe the implied next output.  We collect all possible next outputs of the generator.  This gives us the set of all possible values for the next output.  Each iteration uses just a few simple arithmetic operations, and we do $380,000$ iterations, so this procedure should run extremely fast: in milliseconds or less.


How can an adversary request decryption of an unused sector? The Wikipedia article on Disk Encryption Theory mentions this

  a powerful adversary can modify an unused sector on the disk and then request its decryption.

I understand that an adversary is capable of modifying an unused sector, but can anyone explain how they would be able to request its decryption?

I understand that an adversary is capable of modifying an unused sector, but can anyone explain how they would be able to request its decryption?

The first thing to understand here is that this is an adversary model. In cryptography we model our adversaries so we know exactly what capabilities they have and which they don't.
In this particular case it seems whoever came up with this model decided that it would be a good idea to give the adversary the ability to change the ciphertext of and decrypt unused sectors.

Now we could model our adversary so that they don't have this capability. But in general we want to come up with models that are as powerful as possible so that if we prove a scheme secure in that model, it provides the maximum protection possible.
The only limit to the powers of adversaries that we usually use is we don't give them powers that always break any scheme we could possible come up with. E.g. when we encrypt a challenge bit for the adversary we do not allow the adversary to ask for the decryption of that specific ciphertext.

So the default in cryptography is to always add powers right until we barely don't get trivial breaks of security. Now for this specific capability. It seems to be useful because it utterly breaks the ability of the disk encryption to use an unauthenticated deterministic stream cipher (e.g. initialized / keyed by the sector index). This is because an adversary can just look at the ciphertext, request a decryption and then compute any such static keystream as an XOR. The keystream could then later be used if the sector becomes used at some point to extract data and break security. Additionally if the scheme allows you to get some value out of knowing plaintext-ciphertext pairs (e.g. block-indexing parameters), getting them from an unused sector may prove useful, especially if the decryption capabilities of used sectors are somehow limited.