Can Differential Privacy be used to show that two distributions are indistinguishable? Differential privacy can be used to show that the "privacy loss" of a certain computation is "bounded" in a meaningful way.
In cryptography, often "indistinguishability" is considered, i.e. we want $\Delta(D_0, D_1)$ to be small.
Can these two concepts be related?
I know vaguely that standard notions of differential privacy can be related to things like "concentrated differential privacy", which itself is a Renyi-type bound on two distributions (which is somewhat similar to the total variation distance bound that I want).
But I want to end my proof with "So, the two distributions are indistinguishable" --- can differential privacy help me with this goal?

These sorts of arguments come up in the theory of randomness extractors where we argue that a random function from a certain family when applied to inputs with a certain minimum entropy ($H_\infty$, the -ve log-maximum probability of an outcome in the Renyi notation) produce outputs that are indistinguishable from uniform up to some $\epsilon$ bound. The differential privacy of the uniform and extractor distributions can be bounded in terms of input size, output size and $H_\infty$ (see for example the Kamp and Zuckerman theorem of the article).
The min-entropy should be the choice of entropy function when using differential privacy as it bounds the worst case scenario of concentration of inputs.


Taking $p$ and $q$ to be the same value in paillier cryptosystem I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results.
As far as I can understand, when I take $p$ = $q$, the function $L(x)$ returns a fractional value instead of an integer one, meaning that in case when the primes are equal $L($$g^{\lambda}$ mod $n^{2}$) is not an integer. I also get that when the primes are equal, then $\lambda = (p-1)$, since lcm of $(a, a)$ is $a$.
Can someone explain that where do things go wrong when the primes are equal?
Reference for the scheme

Irrespective of the math, you CANNOT take $p=q$ since in this case the scheme is completely insecure. You must choose random, independent primes $p$ and $q$.


Attacking a blackbox PRNG Every single PRNG attack I could find during my research depends on knowing the PRNG algorithm(s) as well as having definite output.

Suppose you have the following scenario: nothing is known about the PRNG design and the output you get is filtered through an application such that you only get $A,B,C,D$ where each symbol has some 'probability'. To simplify this you can assume that the output of the PRNG is between 0 and 100 and that it is arbitrarily divided such that each symbol in $A,B,C,D$ has its own range. You do not actually get to see the PRNG output at any point.

What kind of attack is possible on this $A,B,C,D$ output stream? The only one I can think of is if the PRNG cycle is short and it starts repeating.

This depends on the type of attack planned, and the information available. Given only the output string (or parts of it), any decent cryptographic PRNG is infeasible to try to predict (which is usually what you want, since future keys or other parameters are desired).

Additionally, if your symbol distribution is uneven, it is not a very good PRNG. (For the simple reason that it is easier to try to simply brute-force prediction guesses). Their main protection typically is limited number of brute-force trials possible for the attacker.

However, NIST has a standardized test suite to test bit-valued PRNGs (NIST SP 800-22. Simple googling will give you the document, source code and binaries).

The test suite will try to find a common set of weaknesses from a bit-valued PRNG output. Using the results from the test suite, it would be possible to try to estimate the PRNG behavior, statistically, in case it was badly designed.

In case the PRNG symbols are not binary, and/or they have an uneven distribution, most of the NIST-tests would fail, or refuse to start. It is a straightforward (but not necessarily trivial) transformation of number bases to move from N (evenly distributed) symbols to a binary base.

For the unevenly distributed case, it might be useful to try to find an evenly distributed set of symbols to try to arrive to applicable binary base. For example:

Given a distribution of A: 1/2, B: 1/4, C: 3/16, D: 1/16
Assign a set of 4-bit codes for each: 8 codes for A, 4 codes for B, 3 codes for C and 1 code for D
Replace the symbol string with this assigned bit-string such that for example for an occurence of A, assign randomly one of its 8 codes to that occurrence.

Because this transformation does not look like the original bit string, you will need more samples (probably at least as many times as is the size of the largest bit-set) to compensate.

In general, some of the NIST tests require in the order of billion-bit samples to complete, so they may be applicable only for automated systems, not for example physical world gaming devices. (Slot machines have sometimes been attacked via weak PRNGs inside them, see e.g. https://www.ethicalhacker.net/features/book-reviews/mitnick-the-art-of-intrusion-ch-1-hacking-the-casinos-for-a-million-bucks)


Collision resistant hash functions with prime domain In order to use RSA accumulator the elements must be primes.
Is there examples of collision resistant hash
functions with prime domain?

Suppose you have a PPT algorithm $M(1^n;r)$ that given the length of your target prime and the randomness $r\in\{0,1\}^{\rho(n)}$ finds a prime of length $n$. Suppose further $M$ is secure in the sense that if you feed it a properly random input $r$ it will output an unpredictable, random prime suitable for use in say RSA. Most cryptographic libraries have an implementation of this.

Suppose further you have a PRG $G:\{0,1\}^l\to\{0,1\}^{p(l)}$ that given a properly random string as input outputs a (much) longer random-looking string as output. This is e.g. realized by using something like AES-CTR with the input being the key and using a fixed nonce.

Then take any hash function that can reasonably be modelled as a random oracle $O:\{0,1\}^*\to\{0,1\}^l$, e.g. SHA3. The defining feature of a random oracle is that you get fresh randomly drawn values as output for every fresh input value.

Now construct your hash as follows: $P_n(x)=M(1^n;G(O(x)))$. Assuming you can securely generate RSA keys this will also be secure (as long as $x$ is unnpredictable).


A block cipher whose key changes after each block I have been reading about various block cipher modes of operation, and all of them seem to treat the block cipher (including it's key and key schedule) as a sort of immutable black box.

I would like to know whether or not any one has designed a mode of operation where the effective key schedule of the cipher is changed between each block encrypted.

Suppose, purely for example, that we had a 256 bit block cipher, using a simple a 4 round Feistel structure.  The expanded key, generated from a secure hash of the user-supplied key and an IV, would be 512 bits.  In between each pair of blocks encrypted, we treat these 512 bits as the state of a 512-bit linear feedback shift register, advance the LFSR one step, then use the result as the scheduled key for the next block of data encrypted.

Like CTR mode, encryption and decryption are parallelizable, and it has the property of random read access.

Does anything remotely like that exist?

If not, is it because it would be obviously horribly secure in a way I'm not seeing, or for some other reason?

In general you want to treat primitives like block ciphers as black boxes. You first analyze and try to break the block cipher. Once it is proven to operate correctly you can use it as primitive for a block cipher mode of operation. The mode of operation can then be proven to be secure assuming that the block cipher primitive operates well.

If you don't treat the block cipher as a black box then you will basically have to show that the mode of operation doesn't invalidate the security analysis of the block cipher.

The subkey derivation may not be the most important part of a cipher, but that doesn't mean that there aren't many things to consider.

It seems that tweakable block ciphers do indeed provide an answer to what you want to achieve (see the answer of pg1989 and the comment of SEJPM).

Lets quote the paper that introduced them:

  Block ciphers (pseudorandom permutations) are inherently deterministic: every encryption of a given message with a given key will be the same. Many modes
  of operation and other applications using block ciphers have nonetheless a requirement for “essentially different” instances of the block cipher in order to
  prevent attacks that operate by, say, permuting blocks of the input. Attempts to
  resolve the conflict between keeping the same key for efficiency and yet achieving
  variability often results in a design that uses a fixed key, but which attempts
  to achieve variability by manipulating the input before encryption, the output
  after encryption, or both. Such designs seem inelegant—they are attempting to
  solve a problem with a primitive (a basic block cipher) that is not well suited
  for the problem at hand. Better to rethink what primitives are really wanted for
  such a problem.

That's from the introduction of the paper Moses Liskov, Ronald L. Rivest, and David Wagner: Tweakable Block Ciphers.


AES encryption with shared IV Sorry about the horrible title, didn't now what to say.

I'm trying to avoid having to send an IV with every message purely to keep packet sizes down, so I thought of a method to establish a "IV Pool".

This is how I thought it should be:

Client ---- Handshake ---> Server

Server ---- Handshake ---> Client

Client and Server now have a shared 1024-bit secret

First 256-bit's of the key are used as AES Key.

Now what I thought is, could I take the next 128-bits of the secret as the IV for the first encryption, and then send a massive list of random bytes to the server to use as IV's? For example:

Client ---- Sends 1024 bytes of random ---> Server

Then the client and server both take 128-bits of the random bytes each time they send a message as the IV. That way the IV is synced across both parties and the IV does not change and is theoretically "not-predictable".

My question is, is this safe? Or does it still defeat the purpose of having an IV?

Sending a big block of data to be then used as initialization vectors is secure (assuming it is transferred encrypted and authenticated), but kind of defeats the purpose of "keeping the message size down".

The requirements for an initialization vector depend on the mode of operation, not on the underlying cipher (AES in your case).

For CBC mode, the initialization vector for each message should be at least not predictable by an attacker before the message is known (otherwise there are some chosen-plaintext attacks which allow decrypting your message).
Old versions of SSL used the last block of the previous message, and were thus vulnerable to this attack – newer versions send an IV with each message.

One way to go here would be to use part of your 1024 bit shared secret as the seed for a CSPRNG (on both sides), and use the output of this as IVs. (Use separate generators for both directions.)

For CTR mode, the initialization vector can either be random (see above), or be simply counted up from the last counter value of the last package, and if this is decided in the protocol, you don't need to send it along with the message.

(Of course, in both cases this only holds if your messages are protected from reordering by some other mechanism – e.g. if this is done over TCP.)

Your MAC (you have a MAC, don't you?) should include the initialization vector, even if it is not sent.

There are other modes of operation, including most AEAD modes, which only require the nonce-property of the initialization vector, i.e. that it is not repeated. Then you can use a simple counter, or use an existing message number (maybe together with an identifier of the sending side).

Also note that the streams in both directions should use different keys, not the same one.


How to generate a bilinear group of prime order p for key generation I am trying to implement an IEEE Paper In Cryptography. I read many reference regarding an RSA key generation. But i am confused with above statement. Please someone explain me What it says with example.

EDIT *

I am trying to implement key generation from the paper Key-Aggregate Cryptosystem for Scalable Data Sharing in Cloud Storage. In the paper, the first step in key generation is a setup phase state as follows
SETUP(1^λ) : Randomly pick a bilinear group G of prime order p where
, a generator gϵG ...

In the definition I understand what is meant by bilinear, prime order and generator. But what is that parameter λ and what should its value be?

*Edit was added for clarification purposes (copy-and-paste from this dupe by same user).

Bilinear group in question is expected to be strong enough, and this depends on group order $p$. Namely, group order should be large enough. So, $\lambda$ is order size in bits. That is, size of the binary representation of order. Order of the group, or maybe just size of the order should be known before generating the group. Notation $1^{\lambda}$ is there to say SETUP() accepts a bitstring of size $\lambda$.


How can one calculate the estimated RSA key life based on Moore's law? How can someone estimate the number of years needed to factor an RSA key based on the advancement of technology if followed Moore's law?

It is hard. Main problem is that RSA key breaking relies on integer factorization, for which the most efficient (known) algorithms use CPU but also RAM, with constraints on parallel computation. Moore's law is already a crude approximation of how CPU power evolves over time for a given budget; it fails to take into account memory size and latency (two distinct things).

In fact, Moore's law, as expressed by Gordon Moore, is about transistor density, which does not equate with performance; and Moore himself changed it occasionally. The version that was fashionable about 12 years ago was: "every three years, one can put four times as many transistors in a given area, and clock that twice faster". This translates to an increase in computational power of 1 bit per year when breaking symmetric algorithms with FPGA or ASIC; but for general purpose computers, this is more like a double in power every 18 months, because register size does not increase as fast, and even when registers grow, the data elements we put in them do not. Also, over the last decade, clock rate of CPU has more or less stabilized, so Moore's law can be maintained only through parallelism -- multiple cores. But not all algorithms are amenable to easy parallelism, in particular the big matrix reduction which is the last step of General Number Field Sieve, the current best algorithm for breaking RSA. That matrix reduction appears to be the bottleneck for keys longer than the current record (768 bits).

Read section 6 of this report for a discussion and pointers on the subject. All see this site for estimates computed by various organizations, and even more pointers.


How likely is a AES KDF bypass? So I was wondering about some alternative attack scenario which I thought of when I started to understand KDF's .
So lets say you have a cipher like AES and a strong KDF . And the legit user uses a 30 character strong Password :

30-char Pass ---> KDF ( slow stuff : argon2,scrypt ) ----> AES256

And normally the attacker would have to start at the beginning with brute force and then passing through the KDF which slowes him down very much and then finally checking if the final bit string is accepted by AES to decrypt the ciphertext .

But I the attacker knows that the legit user uses a very strong Pasword and a decent KDF , would it not be more efficient to just bypass the KDF and brute force the AES bits directly ( takes longer , but much less slowdown ) like :

wordlist ---> Some random 256 hash ( sha256 ) -----> AES256

With that method the attacker could brutefoce every possible AES key and the length would not even matter . But It would be very difficult because of all the possibilities .

How likely is such a Scenario ? And is it even worth doing so ?

Let's assume a password consisting of 15 random longish words from several books.  It's likely then that the password's entropy will exceed 256 bits. (This is actually very difficult to compute accurately as there are linguistic /social /physiological issues to human password creation, but let's skip over those).  That's more than that of an AES-256 key.  So in this case it seems that it's worthwhile attacking the AES key directly as it's got less entropy.

This would be a brute force attack directly against an AES-256 key.  The futility of this is well covered on this site.  I'll just add this link and say that you'd need more than all of the batteries on Earth for the energy demand. And a lot of time measured in age of Universe units.  It's impossible and really not worth doing.

It also opens up the question of what would KDFs be for if you simply bypassed them and attacked the cipher key directly?


Is it hard to recover $p$ from $k \phi(p)$? Given $k\phi(p)$, is it hard to recover $p$? Here, $p$ is a large prime, $\phi(\cdot)$ is  Euler's totient function and $k$ is an unknown integer.

Or what's the complexity to recover $p$ from $k \phi(p)$.

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?"  It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of possibilities; we will consider it success if that attacker can create such a list with the correct value on it somewhere.

The answer would depend on how big $k$ (and $p-1$) is (and, how big the product is).  If either is small (say, no more than 100 or 200 bits), or alternately smooth (that is, consists of prime factors that are small), then ECM would be able to pull out $k$ (or $p-1$), giving the attacker a good guess.  In addition, if both have large factors, but the product is sufficiently small, then NFS would be able to factor the product.  However, if both have large primes as factors, then it is unlikely to be feasible to recover $p$.

However, the above assumes that the attacker has no further information about either $p$ or $k$; if he (for example) also knows the value $pq$ (for a large prime $q$), then it is easy for him to derive $p$; he selects a random value $a$, and computes $gcd( pq, a^{k\phi(p)}-1 \bmod pq )$; with high probability, that's $p$ (assuming $k$ is unrelated to $q$; if the value of $k$ is (say) a multiple of $q-1$, then there are other ways to recover $p$ and $q$.


Verifying EdDSA signatures using xedDSA verify function. I'm running into a problem where I generate signatures using a library like pynacl's (https://pynacl.readthedocs.io/en/stable/signing/) ed25519 implementation and then when I verify it using xedDSA's verify function (https://github.com/signalapp/curve25519-java/blob/master/android/jni/ed25519/additions/xeddsa.c#L45) it passes sometimes and fails other times.

This seems to be related to the priv/pub key pair that generates the signatures. Once a keypair generates a signature that the xedDSA function can verify, all subsequent signatures are also validated correctly from the same keypair. I'm converting the ed25519 public key that is given by pynacl into a curve25519 pub key (verify_key.to_curve25519_public_key()), which I then pass into the xedDSA function.

In the intro here: https://signal.org/docs/specifications/xeddsa/#curve25519

It is stated that an ed25519 signature will be correctly verified by a xedDSA verify function. But this is not the case here.

Can anyone tell me exactly why this is happening? I'm quite confident it has something to do with the key generation and the subsequent conversion of the ed pubkey to a curve pubkey. But I don't know enough about crypto to pinpoint the issue.

From your link:

  XEd25519 signatures are valid Ed25519 signatures and vice versa, provided the public keys are converted with the birational map.

Unfortunately, the vice-versa is wrong.

XEd25519 works by requiring the private key to be positive in the sense that it will produce a positive edwards public key.
This is obtained by negating the private key if it produces a public key with negative $x$. (negative and positive in the sense of LSB as in ed25519)

This is assumed to hold in verification but it doesn't if the signature was generated with ed25519.

More specifically, in ed25519 you can have both positive and negative public keys $A$. Then your signature is computed as: $R = rB, s = r + ha$
Note that in ed25519 you have that $A = aB$.
Verification is done by verifying that $R = sB - hA$.

In ed25519 this works because $R = rB = (r + ha)B - h(aB)$.

However, when using XEd25519 things changes as the public key are implicitly assumed to be positive (curve25519 lacks the sign information so some assumption should be made), so you would have end up with a sign bit flip in the verification equation: $rB \neq (r + ha)B - h*(-A)$.

So you could verify in this way only signatures made by an ed25519 key pair with a positive public key.

Fixes:
I think that you could probably be ok in testing $R = (r + ha)B \pm hA$ which will hold in one of two cases if the signature is valid, but I guess that would be a problem when your implementation uses a double base scalar multiplication which is pretty common for signature verification.
A better idea would be to replace XEd25519 with qDSA which is a more natural way to do signatures over Montgomery curves


Partial collisions for md5 Let $h$ be a bitstring and let $P(h, n)$ be the n-bit prefix of $h$. A partial collision of length $n$, for a hash function $H$ is a pair $(x,y)$, such that $P(H(x),n)=P(H(y),n)$.

What is known about this type of collisions? I'm particularly interested in md5. Can rainbow tables be adapted to quickly look for these? What values of $n$ are feasible to bruteforce (perhaps in an optimized way, like with rainbow tables).

I'd also like to know about the pre-image case: given $x$ and $P(H(x),n)$, how to find $y$ such that it's a $n$-partial collision for $x$.

If $H$ is secure in the random oracle model and of width at least $n$, then $x\mapsto P(H(x),n)$ is also secure, inasmuch as an $n$-bit hash can be (proof sketch: any attack that distinguishes $x\mapsto P(H(x),n)$ from a random oracle is trivially turned into a distinguisher for $H$). The converse is not true.

Finding a collision requires $O(2^{n/2})$ queries to the oracle (or evaluations of the inner function of $H$). More precisely it is expected to require $o(\sqrt{\pi/2}\cdot2^{n/2})$ distinct queries, and odds of success reach 50% after $o(\sqrt{\ln 4}\cdot2^{n/2})$ such queries (that's the generalized birthday problem). The standard paper on how to exhibit such collisions is Parallel Collision Search with Cryptanalytic Applications.

Finding a preimage is expected to require about $2^n$ queries to the oracle (I plan to dig out the right formulas someday). It is possible to speed-up an attack by pre-computation, e.g. with rainbow tables, in particular if the set of possible messages is known, or if $n$ is small enough.

Now we restrict to MD5, thus $n\le 128$.

The difficulty of finding collisions is about as for a good hash ($\approx 1.3\cdot2^{n/2}$ MD5 inner rounds) when the messages are tried without consideration of the inner structure of the MD5 round function (e.g. random messages or words from a dictionary). Without constraints on the message, finding collisions among messages of at least 1024-bit has been possible for any $n$ since that breakthrough, works even with some constraints, now has little cost, and was recently made possible with 512-bit messages. The lower $n$ is, the easier it gets. AFAIK there is no shortcut for heavily constrained messages, e.g. passwords of less than 10 ASCII characters.

The difficulty of finding a preimage is about as for a good hash (about $2^n$ MD5 inner rounds) when the messages are tried without consideration of the inner structure of the MD5 round function, nor knowledge on the origin of the target value. I am not aware of a practical method better than that, except when the message is in a known set smaller than $2^n$, which is when rainbow tables shine; in that case, I do not see that lowering $n$ changes the cost.


Authenticated encryption vs end-end encryption I am kind of new to crypto. can someone highlight the differences between authenticated encryption and End-to-End encryption

Authenticated encryption is an all-in-one encryption form (algorithm) that provides privacy, integrity, and authenticity together.

End-to-end encryption is a concept where only end-users read the encrypted message. end-to-end encryption aims to prevent man-in-the-middle eavesdrop such as telecom and internet providers. The transit data in the servers are encrypted and the service owners do not have keys and the possibility to decrypt it.

they are totally different.


What is the logic behind Compress function in iterated hash function I am working on cryptographic hash functions theorems. In the iterated hash functions part a specific word started appearing constantly: "Compress" for instance within the "compress function".

I am trying to find out what the logic is behind this "compress function". Many blogs, PDF's & forums didn't give any particular description about the logic behind "Compress". They just used the word "Compress" and solved the theorems.

Can anyone tell me what is the logic behind the word "Compress" in the compress function?

A compression function is necessary to fulfill the requirements of a hash function. This is because hash functions are expected to be able to accept as input bit strings of arbitrary length, and output a bit string of a constant length*.

The specifics of how the compression function compresses the input string is particular to the construction of the hash function in question. For example, the Merkle–Damgård construction tends to use a block cipher as the compression function. As to how it compresses, it typically uses one block of hash input at a time as the key to a block cipher, and uses this to successively encrypt the internal state.

There is also the sponge construction, which compresses the input data in a different way. The sponge construction holds an internal state consisting of rate + capacity bytes, and "absorbs" rate bytes of hash input into the rate section of the state, either via xor or direct replacement, then mixes the state using an invertible permutation.

*technically there is a reasonable maximum in practice as to the size of the inputs, and the sponge construct is notable for being able to produce arbitrary length outputs.


Multi-round Transposition/Playfair as a secure hand cipher in the computer age Given that computers can be easily compromised, there is a need for a hand cipher that can withstand computer attack.  Clearly the traditional hand ciphers fail.

One time pads work.  They also have the important property of being able to burn used keys and thus prevent decrypting old messages if keys are revealed.  But key management is obviously hard.

Schneier's Solitaire cipher is certainly secure.  But it is also completely impractical as a hand cipher.  One would need to be extremely diligent to correctly encipher even a very short message without making a mistake that would make the rest of the message undecipherable.

So strengthening the traditional hand ciphers seems to be a more fruitful approach.  Of the many traditional ciphers, Transposition/Playfair seem to go together beautifully because Playfair combines two letters together and transposition then scatters them.  Transposition defeats the traditional methods of breaking Playfair, and Playfair defeats anagraming transpositions.

The idea is to take the plain text, transpose it, Playfair the result, then transpose that, Playfair that result again.  After two rounds each ciphertext letter is distributed to four plain text ones.  After three rounds eight.

Both Playfair and Transpositions are relatively easy to do by hand.  In particular, Playfair processes two letters at a time, which is faster than ciphers like one time pads.

Transform/Playfair would certainly be secure if enough rounds are used.  It becomes very hard to analyze the intermediate values.  Each Transpose and Playfair would be performed with a different key, possibly based on some key schedule, so the key space would be huge.

But the question is, how many rounds are needed?  My guess is three, but that is just a guess.

A crude brute force attack will certainly not work, there are 25!^2 combinations in each round.  There would be very little to hill climb on.  But what would be a more effective cryptoanalysis?

Or are their better approaches?

("Secure" means in the context of hand ciphers.  So no chosen plain text attacks.  There will be a relatively small amount of text encoded, certainly not megabytes.  Etc.)

(There are other threads about hand ciphers, but I want to concentrate on the Transpose/Playfair here.)

Some years ago, someone (Terry Ritter maybe) suggested using Playfair as follows.

First: just normal Playfair with some key.
Second: add a single null at the front and at the end of the cypher text.
Third: go to First with new key.

This can be extended by repeating the process. The point of adding the nulls is to split letter pairs between rounds. You could improve it as suggested in your question by using a transposition cipher before the Playfair step. Computer attacks on Playfair often just exhaustive key guesses coupled with Playfair's lack of ability to diffuse the key through the plaintext. Transposition breaks up the keyword search and adding single null between steps increases diffusion.

Still, one needs a fairly long key for the Playfair part. Perhaps using parts of a shared book keyed off the date. (Bible, "Catcher in the Rye," "Texas Almanac," etc.)


Representing a function as FHE circuit I am actually trying to study homomorphic encryption (on lattices) but I'm facing a problem. Every paper that I have read so far talk about writing the function to evaluate on ciphertexts as a circuit, either boolean or arithmetic according to our scheme if I understood this part well. My problem is that I couldn't find explicit documentation on how to turn a function to a circuit.

Especially, in circuits, we can't have loops or conditions and I would have liked to apply my FHE scheme to the weights of a neural network, but I'm kinda stuck on how to represent the activation function (I think I would use the sigmoid, that can be represented with its Taylor expansion) and simple gradient descent.

Does anyone have a clue or a good paper to help me understand how to write such functions to circuits?

The circuit term in the evaluation of functions with FHE is a coming from  Electronics. In the notion of FHE circuit, we have almost the same problem; build a circuit of a function $f$ with available FHE operations so that we can evaluate the $f$ with FHE.
Somewhat Fully Homomorphic schemes allow us to operations on ciphertexts. In the bitwise case, for example; you will have two operations on the ciphertext bits;
$$ E(p_1) + E(p_2) = E(p_1 +p_2)$$ and
$$ E(p_1) * E(p_2) = E(p_1 *p_2),$$ where $p_1$ and $p_2$ are plaintext bits and E is a fully homomorphic scheme as;

Fully Homomorphic Encryption over the Integers
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

To evaluate a function $f$ with FHE, we consider it's circuit implementation with the two above operations. It is similar to what we do in Electronics, that is; we can build a circuit for $f$ by using the binary operations, AND, OR, NOR, etc. and see universal logic gates and Functional Completeness
In FHE we have two operations and this is enough, up to some point. The name Fully is meaning that it supports two operations.
Unfortunately (or fortunately), The FHE schemes are semantically secure, this means that;
$$a = b \not\Rightarrow E(a) = E(b),$$ and even the equality only hold with negligible probability. As a result of this; currently, it is not practical to build a circuit for every function to evaluate.

Some FHE circuits
In the below demonstrations, I'll stick to HELib based on Fully Homomorphic Encryption without Bootstrapping. Using different schemes may require different circuit implementation. In HeLib case; we have these binary FHE operations on the ciphertext;

$+$ is $\oplus$ and
$*$ is $\wedge$ opereation.

NAND Gate
Although the NAND gate is universal, we can construct it by using the AND and XOR
$A  \text{ nand } B = ( A * B ) + 1$
Full adder
Let $A=E(a),B=E(b),C=E(c)$ we will calulate the sum $S$ and carry $S'$ as;
$S= A \oplus B$ and $S'= A \wedge B$, as the usual circuit.
n-bit Full adder
can be implemented same as ripple carry adder
if/else
we can build it with a 2:1 multiplexer as;
$$Q = (A * S) + (B * S'),$$ this circuit is the combinational logic of the if/else statement and we can construct this with FHE.

FHE encrypted $S$ is the input by the if statement.

FHE encrypted $A$ is the input by the  then statement

FHE encrypted $B$ is the input by the  else statement

FHE encrypted $Q$ is the output of the expression.
Actually, This is the base of the FHE PIR implementation. Remember all values are encrypted semantically.

Equality
Given to 2 $n$-bit numbers $x$ and $y$;

$x= \{x_{n-1}, \ldots, x_{0}\}$
$y= \{y_{n-1}, \ldots, y_{0}\}$

with the FHE encrypted values;

$X= \{E(x_{n-1}), \ldots, E(x_{0})\}$
$Y= \{E(y_{n-1}), \ldots, E(y_{0})\},$

where $X$ and $Y$ holds the encrypted lists of $x$ and $y$.
we can compute two plaintext equality under FHE by using the following circuit;

component wise $\oplus$, $Z = \{E(x_{n-1}) \oplus E(y_{n-1}),\ldots,E(x_{0}) \oplus E(y_{0})\}$
component wise invert; $Z' = Z \oplus \{E(1),\ldots,E(1)\}$
$\wedge$ the bits; $R = z'_0 \wedge \ldots \wedge z'_n$

$$ R =
\begin{cases}
E(1),  & \text{if equal} \\
E(0),  & \text{else}
\end{cases}$$
To reduce the depth of the $\wedge$, a binary tree is preferred.
Comparison
Calculate comparsion by $\operatorname{C}(X,Y) = \operatorname{MSB}(X-Y)$ and 2's complements. This will keep $1$ if $X \geq Y$ and $0$ if $ X < Y$
Sorting SWAP with FHE
The swap of two FHE variable can be performed by the following equation;
$$ \operatorname{SWAP}(X,Y) = X*\overline{\operatorname{C}(X,Y)}+ Y*\operatorname{C}(X,Y), X*\operatorname{C}(X,Y)+ Y*\overline{\operatorname{C}(X,Y)}$$
where the overbar represents the complement.
Note that; the server doesn't know the output and doesn't need to know the real plaintext of the Comparison to perform a swap. This $\operatorname{SWAP}$ routine is used in sorting implementations that require a swap function (usual in comparison-based sortings), according to the FHE encrypted comparison $C$ result, the values are either swapped or not swapped and the server still doesn't know.

Some implementations articles;

Depth Optimized Efficient Homomorphic Sorting
Homomorphic AES Evaluation Using NTRU
Bandwidth Efficient PIR from NTRU
Searching and Sorting of Fully Homomorphic Encrypted Data on Cloud


What kind of operations are involved in NTRU? I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm?

When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where are the matrix-vector products?

Almost all lattice-based schemes that have somewhat practical performance use lattices from a subset of all lattices. Those lattices have additional structure and can be described using polynomials. The big advantage of doing this is that on the one hand the size of a description of the lattice is much smaller than for arbitrary lattices and on the other hand that one can use the fast Fourier transform (FFT) to do multiplication. If you want to learn more about this google for Ideal lattices or "the Ring setting" / Ring-LWE.

A different point one should note is that these advances in terms of performance are caused by additional structure that these lattices provide. Currently, we do not know any attacks that can exploit this additional structure to actually break the schemes (at least for the classes of lattices proposed). However, this is a topic of ongoing research and it is already known that for some spacial cases (if one selects these subsets in a bad way) schemes get insecure (see e.g. https://eprint.iacr.org/2015/176.pdf).


In R-LWE, is there any advantage to generate secret from normal distribution instead of uniform distribution In this quote from Lattice Cryptography for the Internet (page 8), author says that we can use error distribution (the same one that we used to generate error) to generate secret. My question is considering that sampling from normal distribution is costly, is there any advantage to also use normal distribution to generate secret instead of normal approach which is generating secret from uniform distribution. I am just wondering. Is just to prove that if secret is also generated from the same normal distribution, proof works ...

Because it is confusing and it does not make sense, newHope generates secret from distribution (binomial in case of newhope) (page 3) and this key exchange protocol also uses normal distribution to generate secret (page 8).

If I understood it correctly, in LWE only error has to be generated from normal distribution, not the secret. The same goes for R-LWE and R-LWE key exchange. Sampling from normal distribution is costly and we want the error to be close to zero so we can reconcile the key but why secret should be close to zero?

  We now recall the ring-LWE probability distribution and (decisional)
  computational problem. For simplicity and convenience for our
  applications, we present the problem in its discretized, "normal"
  form, where all quantities are from $R$ or $R_q = R/qR$, and the
  secret is drawn from the (discretized) error distribution.

Neither the secret nor the error in Ring-LWE (or LWE) encryption needs to be generated from the normal distribution.  Only to get the tightest security proofs does one care about the "shape" of the distribution.  For practical cryptanalysis, this does not matter -- only the size of the secret (and noise) does.

Having said this, there is an advantage to the normal distribution.  During decryption, terms that look like $\langle s,e\rangle$ (inner product of the secret vector $s$ and error vector $e$) appears in the decryption.  What we want for security is that $s$ and $e$ have large norms.  What we want to avoid decryption errors is that $\langle s,e\rangle$ is small.  And if one wants to have vectors $s$ and $e$ of a particular $l_2$ norm and have their inner-product be as small as possible, then these vectors should be chosen from a normal distribution.

The binomial distribution is a very good approximation to the normal and is much easier to generate.  This is why it's a good choice for practical applications.

Edit:
My original answer was incomplete.  Actually, the uniform distribution is just as good as the binomial one if one only cares about the above two properties.  The main advantage of the binomial distribution is that it has more entropy.  This is important to prevent brute force and man-in-the-middle attacks.


Differences between using HMAC-SHA1 vs HMAC-SHA256 for data storage? Reading the question “HMAC-SHA1 vs HMAC-SHA256”, I figured out that the known attacks on SHA1 don't apply to its HMAC version. So, HMAC-SHA1 is quite strong right now.

In a protocol like SSL, if it gets broken tomorrow, we can “simply” turn off all the cipher-suites that use HMAC-SHA1. But what if it is used as MAC protection for encrypted data storage? Let's say that I decide to use HMAC-SHA1 instead of HMAC-SHA256 and the former gets broken. It would be a problem because the old stored data will continue to have a broken MAC protection.

Would using HMAC-SHA256 help in that case?

To be more precise: Is HMAC-SHA256 likely to be much more difficult to break compared to HMAC-SHA1 and are both HMAC-SHA1 and HMAC-SHA256 likely to be broken in the near future?

In a protocol like SSL, if it gets broken tomorrow, we can “simply” turn off all the cipher-suites that use HMAC-SHA1. But what if it is used as MAC protection for encrypted data storage?

This isn't as big a problem as it may seem at first. Even with old data it can still be possible to upgrade the MAC later if you find out about a possible attack, as user4982 mentioned in a comment. Furthermore, the most likely attacks against a MAC would be the ones where the attacker would be able to use an "oracle" to MAC arbitrary messages, which may not exist in practice with data at rest (but is more likely with an interactive protocol).

  Would using HMAC-SHA256 help in that case?

  To be more precise: Is HMAC-SHA256 likely to be much more difficult to break compared to HMAC-SHA1 and are both HMAC-SHA1 and HMAC-SHA256 likely to be broken in the near future?

I would recommend, as in the linked question, using HMAC-SHA256 for new applications. I don't find it likely that either will be broken any time soon, but breaking HMAC with SHA-256 which is still collision resistant is even less likely than with SHA-1, so there is more of a security margin.

However, when designing a long term data storage system, the main thing to keep in mind is making sure that any algorithms are replaceable if they get too weak. I.e. make it possible to transition from whichever MAC is chosen to a stronger one and similarly for ciphers and such. (In an incremental fashion, if keys are held by third parties.)


The last 2 numbers are the ecdsa signature, it is two unsigned integers, when the highest byte happens to be larger than 127, the asn.1 BER encoding adds an extra zero.


Is the tag in a MAC scheme a fixed size? I've been reading up on MAC schemes. But I cannot seem to find out whether the tag's that are output by running MAC(m) is of a fixed size?
I can find a lot of stuff talking about the tag space being a specific size, which would indicate that the tag must have a specific length, but I could not find whether there are any rules for it.

A MAC is a type of function, that returns an authenticator given a message and a secret.
The output length is a property of a function, not a constant for all MACs.
With constructions such as HMAC, the output length is directly dependent on the underlying hash function. Other constructions such as KMAC can produce an arbitrary long output.
And no matter what the output size is, an application can always truncate it if needed.
Of course, the shorter the MAC is, the less secure it becomes. If a MAC is used in an online protocol, and an adversary has very limited time and allowed attempts, forgery may not be practical even with a short MAC. If offline attacks are practical, you’d better size the MAC for 128 bit security. The maximum length of a message also plays a role. The shorter the messages are, the more difficult forgery is.
So, there’s no fixed size for MACs. It depends on the actual functions and in what context they are used.


How to prove an encryption scheme is not CCA secure Given the following context below, how does one show or prove the encryption scheme is NOT IND-CCA secure

The IND-CPA secure private-key encryption scheme for n-bit messages can be constructed from a pseudorandom function as follows $F : \{0,1\}^n \times \{0,1\}^n → {0,1}^n$ as follows:

$Gen(1^n)$: Return $k ← \{0,1\}^n$
$Enc_k(m)$: Pick $r ← \{0,1\}^n$ and compute $s = m\oplus F_k(r)$. Return $c = (r,s)$.
$Dec_k(c)$: Parse $c$ as $(r,s) \in \{0,1\}^n \times \{0,1\}^n$ and return $m = s\oplus F_k(r)$.

How would one prove that this is NOT IND-CCA secure?

Let $\Pi$ denote the encryption scheme you just described, and $\mathcal{A}$ be the adversary trying to attack this scheme.

Define the experiment $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A}, \Pi}$ as follows:

$\mathcal{A}$ has access to the encryption oracle $E_k(\cdot)$ and the decryption oracle $D_k(\cdot)$.
$\mathcal{A}$ outputs two messages $m_0$ and $m_1$.
A uniform bit $b$ is chosen, unknown to $\mathcal{A}$. $\mathcal{A}$ is given $c=E_k(m_b)$.
$\mathcal{A}$ is not allowed to query the decryption oracle on $c$. $\mathcal{A}$ however continues to have oracle access to both encryption and decryption.
$\mathcal{A}$ outputs bit $b'$. The result of the experiment is $1$, if $b=b'$, otherwise $0$.

So now, the scheme is considered CCA secure if the probability that the output of the above experiment is 1, is negligible. However, an adversary $\mathcal{A}$ could output $m_0=0^n, m_1=1^n$ and receive the challenge ciphertext $c=(r,s)$. It is not allowed to query $D_k(\cdot)$ on $c$. However, querying $D_k(c') = D_k((r, s \oplus 0^{n-1}||1))$ would return $0^{n-1}||1$ if $c=E_k(m_0)$, and $1^{n-1}||0$ if $c=E_k(m_1)$.

Depending on the result of the query, the output of $\mathcal{A}$ is equal to $b$ with probability 1.


Is it insecure to encrypt the wrong plaintext? Most plaintext must be fed as a string or a binary object to be encrypted.
However, it's often possible to mis-decode the plaintext before encrypting it.

i.e. If it's received as a string in JSON, you often don't know if the string
is an encoded representation (e.g. plain, hex encoded, base64 encoded, etc)

Example:

If the message to encrypt is received as 48656c6c6f (which is Hello in hexadecimal encoding), it's possible to accidentally encrypt 48656c6c6f instead of Hello.

When you decrypt, you'll get back whatever you started with, so it's easy to
never know you are encrypting incorrectly.

This results in a plaintext input where the variation per-byte is very small.
If you accidentally encrypt 01001000 as an 8-byte string instead of a single
byte (0x48, H), then each resulting ciphertext byte is the result of only
one of two inputs: 0 or 1.

Question:

Is it insecure to make this mistake?
Is the ciphertext somehow easier to break because you used the wrong plaintext?
What if you make this same mistake with the key instead of the plaintext?

Example Ruby code:

require 'openssl'

=begin

Most plaintext must be fed as a string or a binary object to be encrypted.
However, it's often possible to mis-decode the plaintext before encrypting it.

i.e. If it's received as a string in JSON, you often don't know if the string
is an encoded representation (e.g. plain, hex encoded, base64 encoded, etc)

Example:
If the message to encrypt is received as "48656c6c6f" (which is "Hello" in hex),
it's possible to accidentally encrypt "48656c6c6f" instead of "Hello".

When you decrypt, you'll get back whatever you started with, so it's easy to
never know you are encrypting incorrectly.

This results in a plaintext input where the variation per-byte is very small.
If you accidentally encrypt "01001000" as an 8-byte string instead of a single
byte (0x48, 'H'), then each resulting ciphertext byte is the result of only
one of two inputs: '0' or '1'.

Question:

* Is it INSECURE to make this mistake?
* Is the ciphertext somehow easier to break because you used the wrong plaintext?
* What if you make this same mistake with the KEY instead of the plaintext?

=end

real_plaintext = "Hello" # 5 bytes
plaintext_1 = real_plaintext.unpack('H*').first
puts plaintext_1 # 48 65 6c 6c 6f
plaintext_2 = real_plaintext.unpack('B*').first
puts plaintext_2 # 01001000 01100101 01101100 01101100 01101111
plaintext_3 = [real_plaintext].pack('m')
puts plaintext_3 # SGVsbG8=

# Stream cipher used here to make it more obvious about
# the different resulting lengths
def encrypt(str, method='aes-256-ctr')
cipher = OpenSSL::Cipher::Cipher.new(method)
cipher.encrypt
key = cipher.key = cipher.random_key
iv = cipher.iv = cipher.random_iv
cipher.update(str) + cipher.final
end

puts "Result of real_plaintext:"
result = encrypt(real_plaintext)
puts "Len: #{result.length} - #{result.unpack('H*').first}"

puts "Result of plaintext_1:"
result = encrypt(plaintext_1)
puts "Len: #{result.length} - #{result.unpack('H*').first}"

puts "Result of plaintext_2:"
result = encrypt(plaintext_2)
puts "Len: #{result.length} - #{result.unpack('H*').first}"

puts "Result of plaintext_3:"
result = encrypt(plaintext_3)
puts "Len: #{result.length} - #{result.unpack('H*').first}"

As long as you're using any modern encryption algorithm (and you're using it correctly: random key, new random or unique IVs for each message, depending on the mode of operation, etc.) then you'll be fine. In fact, you'd be fine even if an attacker got to choose which plaintext you encrypted and got to see the result; this information would not help him decrypt other ciphertexts. (This is a chosen-plaintext attack, and any standard encryption algorithm can withstand one. Unless you consider ECB a standard encryption algorithm. Don't use ECB.)

There is, however, a possible exception to this rule that might relate to your third question. If you accidentally encrypt a plaintext that includes your encryption key, then in theory this could lead to problems. At least, one could no longer prove the system's security under standard assumptions about the blockcipher.

If your third point was asking "What if I use the wrong key?" then, yes, this is a problem. They key you accidentally use might be brute-forcible. For example, a 128-bit AES key consisting of 16 ASCII hex characters (0-9, A-F) permits only $16^{16} = (2^4)^{16} = 2^{64}$ possible keys.


Post-Quantum cryptography usability in IoT devices My question is very simple. Can I use Post-Quantum encryption/decryption algorithms in IoT devices such as RaspberryPi, Arduino etc, or should the hardware infrastructure obey in quantum logic?

Can I use Quantum encryption/decryption algorithms in IoT devices such as RaspberryPi, Arduino etc, or should the hardware infrastructure obey in quantum logic?

The question needs to be reformulated as:

  Can I use Post-Quantum encryption/decryption algorithms in IoT devices (..) ?

Yes. They can use such encryption/decryption/key exchange algorithms, designed for security against attacks by quantum computers. Such algorithms are an active research topic, with current candidates currently in a public selection process by NIST. They run on classical computers, and perform the same tacks as today's algorithms. The main functional difference is hopefully increased resistance to cryptanalysis.

Post-Quantum Cryptography tends to be more resource-intensive than the current generation of cryptography: slower computations, larger keys and messages, especially if we compare current parametrization of current algorithms to PKC with their proposed parametrization. But all RaspberryPi and I guess all except the most low-end Arduinos are adequate for many of the Post-Quantum algorithms under consideration.

The skeptical will say: why bother now?

Post-Quantum cryptography does not solve the actual security problems that pleague IoT: sometime abysmally poor security architecture, poor software quality, backdoors, implementation mistakes, side-channel and fault-injection attacks.
Post-Quantum cryptography algorithms are new (with few, not very practical exceptions). And the history of cryptography suggests that it sometime takes years of public exposure to uncover theoretical problems, and that implementation never get entirely safe to side-channel and fault-injection attacks if the attacker is invasive enough.
With parameters in the upper range of current crypto (AES-256 for block ciphers, SHA-512 for hashes, RSA-4096 or ECC cryptography on a large safe curve), current-generation crypto is safe from both classical and quantum computers in the foreseeable future: classical computers currently surpass quantum computers on nearly all tasks (with a few claimed exceptions in simulation of physical phenomena), and there are reasons to believe that cryptanalysis, because it requires exact results on large quantities, is among the problems that require the most difficult advances in quantum computers.

Addition: Quantum Key Distribution (which has next to nothing to do with PKC) is not feasible with the hardware available on current computers and network gear. It does not solve the problem of initial key distribution, nor of recovering from a complete state compromise, and has a poor security track record (see this). It is pointless in an IoT context in the foreseable future.

Advances in quantum technologies impact practical uses of crytography in other ways than Quantum cryptanalysis, QKD and PKC:

They enable increasingly fast, dense, and power-efficient devices, both using crypto and trying to break it. Except for password hashing, the net long term effect is more security against offline attacks.
But sensors based on quantum effects conceivably can be used for improved side-channel attacks extracting the secrets embedded in devices, including IoT and Smart Cards.


Derive both MAC and AES keys from same PBKDF2? When doing password-based encryption, is it OK to create one instance of PBKDF2 from the password, and then use it to create both the AES key and the MAC key? (Or should a new instance of PBKDF2 be created using a different salt or iteration count, for each?)

This answer   seems to say this isn't a good idea. While this one   seems to say it is. Am I misunderstanding one of them? (Or both.)

(And by the way, the first is marked as a duplicate of a question which deals with an initially strong key, while it itself deals with a simple passphrase.)

From a security point of view, deriving lots of key material using PBKDF2 is ok.

From a practical point of view, deriving lots of key material using PBKDF2 is inefficient (in the sense that to generate $n$ blocks and increase the adversary's work by $t$, you do work $nt$, instead of $n+t$).

A more practical solution uses PBKDF2 to generate a short string and a suitable generator (probably HMAC-based) to produce lots of key material. Typically:
$$k_0 \leftarrow PBKDF2(pw, \dots)$$
$$\text{key material} \leftarrow HMAC(k_0, 1) || HMAC(k_0, 2) || HMAC(k_0, 3) || ...$$


Is there a computational security of public-key encryption which is similar to the one of symmetric key encryption We say a symmetric key encryption scheme $\Pi_{1} = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is computational security if for every PPT algorithm $A$ and every $x_{0}, x_{1}$ ($|x_{0}| = |x_{1}|$),
$$ \left\vert \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{0})) = 1\right] - \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$

Is there a definition of computational security of public-key encryption as following？

We say a public-key encryption scheme $\Pi_{2} = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is computational security if for every PPT algorithm $A$ and every $x_{0}, x_{1}$ ($|x_{0}| = |x_{1}|$),
$$ \left\vert \Pr\left[\mathrm{Gen}(1^{n})= (pk, sk); A (pk, \mathrm{Enc}_{pk}(x_{0})) = 1\right] - \\
\Pr\left[\mathrm{Gen}(1^{n})= (pk, sk); A (pk, \mathrm{Enc}_{pk}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$

Is it equivalence to IND-CPA?

I am sorry, but I think you are misusing the term "computational security". This concept is a much broader than the definition you have written.

We say that a scheme is computational secure if it satisfies some security definition on which the attacker is supposed to have limited resources (typically, the attacker is supposed to run in polynomial time).

This concept must be seen as the opposite of unconditional security, which makes no assumptions about the resources available to an attacker.

That said, the definition you have provided to symmetric key encryption scheme is actually the definition of passive one-time semantic security, which you can find, for instance, on the book Introduction to Modern Cryptography (definitions 3.8 and 3.12 in the second edition. They are proved to be equivalent...)

There is no equivalent definition for public-key schemes because the attacker has the encryption key and knows the encryption algorithm (Kerckhoffs's principle), so one can't impede she/he from generating many pairs of cleartexts and ciphertexts (therefore, no one-time-like definition is possible). This is why we stick with IND-CPA security.

Moreover, this is also why the second security definition you have provided is not equivalent to IND-CPA: you are not supposing the adversary can chose several plaintexts and encrypt.

Considering the definition of IND-CPA on Wikipedia, you skipped the second step:

  The adversary may perform a polynomially bounded number of encryptions or other operations.


PBEWithHmacSHA512AndAES_128 and AES Modes like GCM I've asked this question on stackoverflow

And I think one gentleman has already answered the first part of question

  a) In my code i am keeping IV and salt with ciphertext. I wanted to use AES/GCM to check integrity of entire IV + salt.

I've got the following answer and I'm fine with it:

  PBEWithHmacSHA512AndAES_128 does not come with flexibility of
  specifying mode like GCM

Can you please help me with the next question:

  b) Why the byte [] of key is 9 bytes? (When I give input as Pree@2017 the key generated is 9 bytes - I have check the length of
  pbeKey.getEncoded() and its 9.

Can anyone from the community help please ...

Why the byte [] of key is 9 bytes? (When I give input as Pree@2017 the
  key generated is 9 bytes - I have check the length of
  pbeKey.getEncoded() and its 9.

The length of "Pree@2017" is 9 chars.
The reason why you are getting the original password is described here

  When you generate a SecretKey using the SecretKeyFactory
  PBEWithHmacSHA256AndAES_128 you will get an instance of
  com.sun.crypto.provider.PBEKey and this class has the "special
  feature" that it returns the original "key" (aka password) when
  calling getEncoded() and not the cryptographic key material. If I
  understand it correctly the key derivation will not be made by the
  KeyFactory but by the Cipher itself.

  Therefore you should not try to convert the SecretKey instance into a
  SecretKeySpec instance; instead just use the generated SecretKey
  instance in the correct cipher instance:

Cipher c = Cipher.getInstance("PBEWithHmacSHA256AndAES_128");
c.init(Cipher.ENCRYPT_MODE, secretKey);


Generate a new public/private key pair for each new message? When using PGP type public encrypted communication, would it be a good idea to generate a new
public for each message and attach that in the new public key in the reply to back to sender mail body? Idea is you start the communication with the known public key from a key server, but for each new message/chat message you generate a new public/private key for that particular end-user. That way if someone cracks your initial public/private key they may not read all the messages? Would that be a good or bad idea? Ie the person who want to read your mail conversation must crack all PGP keys in the conversation sequence to read all the messages.

In the case of emails your solution is not really practical. The problem is that the sender of an email uses the public key whereas the receiver should have the secret key. This means that whenever somebody wants to send you an email (and therefore generate a new key) you have to be online or you have to provide a set of pre-computed key pairs. If multiple people are sending you emails at the same time. Who is taking which key? Making the key management more complicated doesn't necessarily give you more security.

In the case of communications, like chats, the property you are asking for is called (perfect) forward secrecy. This property, roughly speaking, states that an adversary, who at some point obtains your secret key(s), should not be able to decrypt past conversations.
The following paper should be a good starting point for you:
https://otr.cypherpunks.ca/otr-wpes.pdf


Linear congruential generator with non constant increment Consider this random generator function.

A simplified version is provided below (this is C++, mind that "seed" is a reference):

uint32_t Rand(uint64_t& seed)
{
    seed = 1683268614LL * (seed & 0xffffffff) + (seed >> 32);
    return seed & 0xffffffff;
}

For those unfamiliar with C++: & denotes bit-wise AND, LL as a suffix denotes signed long long (signed 64-bit usually), >> denotes plain bit-shift, the uint64_t& in the header denotes that the input is a reference to an unsigned 64-bit integer, that is, updates also apply outside the function.

This is almost a linear congruential generator (LCG), the only difference is that the increment is not a constant, but a part of the seed itself.

My question is on the security of this algorithm, since LCGs are very easy to break.

Does using a non constant increment improve or decrease security? How could this be cracked other than by bruteforceing it?

The state can be trivially recovered from two consecutive output (and hence all further outputs can be predicted).

For the first output, the system updates the seed to $\text{seed}_1$, and then outputs the lower 32 bits of $\text{seed_1}$, which we'll call $\text{output}_1$

For the second output, the system first computes:

  $\text{seed}_2$ = 1683268614LL * $\text{output}_1$ + ($\text{seed}_1$ >> 32)

Then, the system outputs $\text{output}_2$, the lower 32 bits of $\text{seed}_2$.

Hence, if the attacker computes:

  $\text{output}_2$ - 1683268614LL * $\text{output}_1$ $\bmod{2^{32}}$

That gives him the upper 32 bits of $\text{seed}_1$.  With the entire value of $\text{seed}_1$, the rest of the sequence can be predicted.

With a standard LCG, you can also reconstruct internal states, but not this easily...


Is it safe to reuse the salt for generating symmetric keys for a chat application? I'm writing a program that allows two users to communicate over E2E encrypted chat with a secret they have agreed upon in the past.

The process works as follows:

A key is derived from the secret using Argon2id, where the salt is hardcoded in the application.
The key is used to encrypt the user's message using crypto_secretbox from NaCl.
The message is sent to the server and downloaded by the other user.
The user on the receiving end decrypts the message using the same key derived in the same way.

As I understand it, in a password hashing system, a unique salt per password prevents attacks where the bad guys have pre-computed the hashes for a ton of different passwords.

Would there be any advantage for my application to use a different salt for each user (possibly generated by the server)?

You should never re-use a salt, and you should especially not hardcode it for your entire application! A salt has several purposes, including the one you mentioned (defeating rainbow table attacks and others based on precomputation). However, a salt also prevents an attacker from trying to break multiple users' passwords at once. If you use a salt that is not unique, an attacker could trivially build a rainbow table for your application, or attack a batch of users. This is almost as bad as having no salt!

Generally, you want the salt to be exchanged along with the encrypted data or the hash. In this case, you'd want to send the salt and any other unencrypted metadata along with the ciphertext. The salt should be agreed upon by both parties, not generated by the server or any other third party.

With that said, you should not be using an agreed-upon preshared secret password to derive a key for encryption in an end-to-end chat application. The encryption key should be generated using public key encryption. I would recommend using an ECC algorithm like x25519, which is supported by NaCl. The agreed-upon secret should only be used for authentication. That ensures that a weak password does not result in confidentiality loss. You should learn from OTR, which uses SMP for mutual authentication.


How can there be AES-256-GCM, when GCM is defined for 128-sized blocks? In both node.js and OpenSSL, I am seeing cipher "aes-256-gcm".

However, in NIST Special Publication 800-38D, that defines GCM, I am reading:

  The underlying block cipher shall be approved, the block size shall be 128 bits, and the key size shall be at least 128 bits.

How is this possible?

edit:

I see a similar question has been asked already - GCM encryption for 256-bit and 512-bit block ciphers - but that one is more theoretical question, while in openssl, there is a practical implementation.

Those answers imply that it might be insecure. Is it true, and are the openssl implementations inherently insecure?

AES has a block-size of 128 bits in all its variants. The number in AES-128/192/256 is the key-size. Rijndael, the block-cipher that became AES, also supports 256 bit blocks, but that part was not standardized as AES.

Since the block-size is 128 bits, GCM works exactly the same way for AES-256 as it does for AES-128.


Using a hash with a constant key to create easily verifiable codes I'll keep my question short. If I keep handing out different codes generated by this function, will it be trivial to figure out the secret key?

secret_key = {random bytes}

function generate_code(parameters)
  return sha256(parameters + secret_key)

I know little about these things. What I like about this function is that it's trivial to verify if a code is valid given the same parameters. If this is a bad way of achieving this, what is a better way?

I will keep my answer short.

Yes it is trivial, in order to verify the code you need the parameters AND the key, thus there is no easy way to keep the key secure except through a hardware security module.

The correct way would be to use a digital signature:

Sign(SHA256(parameters),secret_key)

The signature can be verified by anyone with the public key, and the secret key is not required or exposed.


How to ensure that a cryptographic implementation is reasonably sound/robust? I know from the bottom of my heart how bad the idea of custom-crypto is. I absolutely concur with the recommendation that it should only be done by professionals who specialize in implementing crypto safely.
However, exactly because it's a Bad Idea ™ it's really hard to find good information on this topic. Say one of the aforementioned professionals is looking at a crypto implementation and they want to judge how safe it is. Some things that come to mind:

Constant-time implementation (to protect against timing/side-channel attacks)
Randomness

Source of randomness (true vs. pseudo RNGs)
Bits of entropy

Zeroing intermediate buffers
Appropriate test coverage with test vectors (e.g., NIST, Wycheproof)

What are other areas like this that need to be probed? Is there any documentation/checklist/book that can shed further light on the topic -- something like 1 but more comprehensive?

One widely accepted standard for information protection is the ISO Common Criteria framework. This set of slides gives some sense of what a Common Criteria evaluation will ask in its analysis.
The US FIPS-140-3 standard also carries a lot of weight, it specifies certain NIST special publications that give criteria beyond ISO.


estimating entropy of password How do I calculate the entropy of a password selected as described?

Choose 4 distinct words randomly from a list of 2000 words. Words can contain special-character substitutions. For example, the following substitutions may be used:

 Sub = {a; 0; i; e; /a; 8}
 Letter a -> @; Letter o -> 0; Letter i -> {1; !} Letter e -> 9;
 Letter a -> 6; Letter 8 -> &

Assume, uniform selection of alternatives:

ex: i is mapped to {i; 1; !} with the same probability.

Assume 90% of words have 1 of the letters in Sub, and 50% of them have 2 letters in Sub.

I know that since we're selecting 4 words from a list of 2000, then entropy in general must be 2000x2000x2000x2000, which expressed in bits would be around 44bits, since each word contributes about 11 bits (2^11 = 2000). Now I don't know how to attribute the fact that these words may contain special symbols. Please help. Thanks

If you have a rule such as "substitute 5 random letters with a fixed symbol" a direct calculation might be possible if you know average word length.

If you can't enumerate all the symbol substitutions into each word via a rule, it will be difficult to calculate directly.

A reasonable way estimate entropy when you can't calculate it is to use data compression. Write a script to output 1 million passwords generated using your method to a text file. Then compress with a high compression, slow algorithm such as LZMA on maximum settings. Perhaps use the 7-zip utility and try all of its available algorithms, picking the smallest result. The size of the resulting file in bits divided by the number of passwords in it should be pretty close to the entropy per password in bits.


How to find the type of symmetric cipher? How to find the type of symmetric cipher that was encrypted.
I have ciphertext, plaintext, key.

there is a command in openssl?

No, OpenSSL is a cryptographic API and TLS implementation with command line interface. It doesn't do crypt-analysis or algorithm detection.

You can try algorithms, probably starting with the most used ones. The size of the plaintext, ciphertext and key may also give hints - keysize and blocksize could point to specific ciphers for instance.

I'm not sure if there are open source or commercial analysis tools out there. You could ask the NSA, I would be hugely surprised if they would not have such a tool.

There is a list mentioned on ReverseEngineering but to me it doesn't give me much hope of finding an actual result.


How can a cryptosystem be unconditionally secure? The definition of an unconditionally secure cryptosystem states that the cryptosystem cannot be broken even with infinitely computational ressources and time.
However, since most books define the keyspace $\mathcal K$ to be finite, then with infinite time any computational device can perform an exhaustive keysearch.

Why are perfect secrecy cryptosystems unconditionally secure? I mean, how can the one-time pad with a small keyspace be considered to be unconditionally secure (take ${\mathcal K} = \{0,1\}^n$ for some small $n$)?

Are unconditionally secure cryptosystems the same as perfect secrecy cryptosystems?

In order to define computational security, one makes the relaxations of unconditional security, that it is possible to break the cryptosystem in superpolynomial time and with neglible probability. Why are these relaxations of unconditional security? Any cryptosystem can be broken with small probability by taking a key at random, even an unconditionally secure one?

The term unconditional security was (as far as I know) coined by Diffie and Hellman in their seminal paper New Directions in Cryptography. Here is the snippet

  [... ] a system which can resist any cryptanalytic attack, no matter how much computation
  is allowed, is called unconditionally secure. Unconditionally secure systems are discussed in [3] and [4] and belong to that portion of information theory, called the Shannon theory, which is concerned with optimal performance obtainable with unlimited computation.

The reason why a perfect implementation of one time pad (OTP) can be considered to be unconditional secure is because of Shannon's insight which may be succinctly described by
$$
Pr_{\mathbf{k}\leftarrow \mathcal{K}}\left[\mathbf{c} = \mathcal{E}\left(\mathbf{m}_0,\mathbf{k}\right)\right] = Pr_{\mathbf{k}\leftarrow \mathcal{K}}\left[\mathbf{c} = \mathcal{E}\left(\mathbf{m}_1,\mathbf{k}\right)\right],
$$

i.e. given a ciphertext $\textbf{c}$, the probability that it was the encryption of some plaintext $\textbf{m}_0$ is equal to the probability that it was the encryption of another plaintext $\textbf{m}_1$; and this holds true for all possible plaintexts and ciphertexts.

Note that it does not say anything about how big or small the keyspace is; for OTP, the only requirement is that the key be at least as large as the message.

Thinking purely from an adversarial perspective, the content of the message can be ANYTHING but there is nothing in the ciphertext that makes one message seem more probable than the other. I have tried to explain this with a cartoon image. Exhaustively searching for the original plaintext (by brute-force cryptanalysis) is an exercise in vain because every plaintext is equally likely! The world war II pigeon discovery is a case study of this kind.

Of course, in case the adversary has some side information that makes the context more specific, the actual message (or parts of it) may be correctly guessed. But it is important to know that any such information is not leaked by the OTP at least.


Difference between MAC and Authenticated Encryption? I am currently studying authenticated encryption and I was wondering if there was a difference between using a MAC and authenticated encryption.  It seemed like authenticated encryption schemes use MAC's in order to provide a level of integrity to the ciphertext.

However, I was unsure if there were specific modes of operation for different ciphers that inherently provided a level of authenticated encryption or if a MAC was always necessary to provide authenticated encryption?

Any examples would be of great help.

A mac is basically applied after encryption is totally complete, where "authenticated encryption" usually refers to something like a mode of operation that builds an authentication tag as the process of encryption moves along. The goal of the "authenticated encryption" is basically doing the same job as a mac in less passes/applications of crypto primitives.

Examples of "authenticated encryption" include GCM mode and the duplex mode offered by the sponge construction. Using either of these will produce an authentication tag with the ciphertext. If data was encrypted using either of these, then application of HMAC after encryption is not necessary.

Suppose a mode of operation like CBC was used instead. It does not produce an authentication tag, and in order to assure integrity and authentication we would require the application of HMAC. This must wait until after encryption was complete. Because this is essentially two totally separate operations, it is relatively slow compared to GCM mode.


Are sufficiently large key sizes enough to deter quantum attacks for symmetric key ciphers? Are sufficiently large key sizes enough to deter quantum attacks for symmetric key ciphers such as AES?

Current understanding of quantum cryptanalysis suggests: Generally, yes.

Symmetric crypto tends not to have any mathematical structure that can be exploited by, e.g., Shor's algorithm, so, absent specific quantum cryptanalysis of a specific primitive (which would be a remarkable publication about the specific primitive), the adversary is limited to the generic Grover's algorithm.

Grover's algorithm searches among $n$ possibilities for a preimage under some fixed function in $O(\sqrt{n})$ sequential qubit operations—for example, it should take about $2^{96}$ qubit operations to find $k$ among the $2^{192}$ possibilities given $f(k)$ where $f\colon k \mapsto \operatorname{AES-192}_k(8432715)$—so the conventional wisdom is that you just need to double your key sizes to attain the same security level against a quantum adversary as you had against a classical adversary.

Even better, a recent estimate with more careful attention to realism of cost models suggests that owing to Grover's poor parallelism in contrast to classical brute force, it doesn't take much to thwart generic quantum attacks in more practical terms—if AES-128 is construed to provide 128-bit security against a classical adversary (which is debatable in the multi-target setting!), even AES-192 should provide 128-bit security against a quantum adversary, for example.


For what does "Rcon" stand for in Rijndael/AES? How do we expand the abbreviation “Rcon” used in the Rijndael key schedule?

I know what it is, I know how it works; I just do not know for what it is a shortcut for. I mean: if "Sbox" is "Substitution box", then "Rcon" stands for… ?

Quoting from FIPS 197 (PDF), on page 11:

  Rcon[]   The round constant word array.

So, the answer is obviously "round constant".


How to devise cryptographic system with data-sharing ability and password reset I originally posted this in the security.stackexchange forums but then I was directed to this one which seems more befitting for my question.
I am writing a C# .NET application. For my application the following requirements should be met:

The data of the users should be stored encrypted in the database
Users can share data with other users
I, as the developer, should be unable to decrypt any user data
If the user resets their password, previously encrypted data should still be possible to decrypt
The private key should not be stored anywhere on disk. Ideally, I want the client application to be able to derive the private key, for example from the password, every time the user logs in.

I cannot seem to find a solution that meets all five requirements. So far, I have come up with the following cryptographic system using asymmetric encryption: When a user registers, a public-private key pair is derived based on the user password (Is that even possible/practical?). The public key is stored in the database. When the user shares data with another user, it is encrypted with that other user's public key and stored in the database. But now req. 4 is not met, since the key pair is based on the current password a reset will render all previously encrypted data undecryptable.
If instead I use symmetric encryption to encrypt the data, then I can encrypt the encryption key using some password based key, which solves req. 4. However, then I am unable to meet req. 2 i.e. share data with other users. This is, of course, because the user would need the other user's symmetric data encryption key which is encrypted with the private key.
So I am finding myself stuck and unable to come up with a solution that fixes all issues simultaneously.

The phrase "password reset" is not applicable for encryption.
Password reset means that starting from some moment only a new password can be used and none of the previous passwords can be used any more. For encryption this is not possible, because if some password (key) can be used for decryption, it can still be used without any limits. For instance, if reset was possible and user reset password to a new one, then a few days later found the previous password, this password would obviously still be able to decrypt the same data.
Thus, we cannot call it "reset". The requirement to be able to decrypt the data in case user forgotten the password actually means:

either you may help user to restore the current password (decryption key)
or, if encryption scheme allows multiple decryption keys, you give user an additional password (key)

In both cases you as a developer can obtain a password (decryption key) not only when user asked you about this, but also on your own. Thus, the requirement 3 would be violated.
Any schemes with secret sharing don't fit these requirements as well. If you implement secret sharing where user has one part of the additional decryption key, this can also be lost. If you implement secret sharing where user has none of parts of shared secret, then the secret (decryption key) can be restored without the user knowing about that, thus the requirement 3 would be violated.
Briefly: There is no way to fulfill all your requirements simultaneously. This has nothing to do with cryptography, this is just a common sense.  Means, at least one of requirements need to be changed.


Can Pohlig-Hellman encryption be done over elliptic curves? Following a bunch of questions on the topic of Pohlig-Hellman encryption. I was wondering if this could be trivially adapted to be done over elliptic curves just like we create EC-DH instead of DH.
surprisingly  my google searches came up with no references for this, or in fact any symmetric encryption based on elliptic curves.
It seems to me elliptic curves should provide the same properties of Pohlig-Hellman but allow same security with smaller keys.

I was wondering if this could be trivially adapted to be done over elliptic curves

If you don't mind the plaintexts being confined to points on the curve (as opposed to elements of $\mathbb{Z}^*_p$), then it's easy; pick a key $k$ that's relatively prime to the curve order $q$ (easy to do if you pick a curve with prime order), and then:

$$\begin{align}
Enc_k(P) &= kP\\
Dec_k(P) &= (k^{-1} \bmod q)P
\end{align}$$

Now, if you can't live with that restriction, one obvious possibility would be to use a curve with "twist security" (e.g. Curve25519), and so if the curve order is $q$, and the twist order is $q_T$ (note: $q$ and $q_T$ are the order of the curves, not the prime subgroups), then,

$$\begin{align}
Enc_k(P) &= kP\\
Dec_k(P) &= (k^{-1} \bmod q)P&&\text{if P is on the curve}\\
Dec_k(P) &= (k^{-1} \bmod q_T)P&&\text{if P is on the twist}
\end{align}$$

Curve25519 point multiplication can be done only using the $x$ coordinate, and so we can treat arbitrary values between 0 and $2^{255}-19$ as points.

Now, this construction preserves some of the properties of PH (for example, $$Enc_a(Enc_b(M)) = Enc_b(Enc_a(M))$$
but not others, for example, the question that was recently asked about combining two keys into a third that had $Dec_c(Enc_b(Enc_a(M))) = M$; that doesn't work as well; we can't define a $c$ that'll be able to decrypt both messages on the curve and messages on the twist (and giving someone both would allow them to potentially recover the values $a, b$)


Encryption scheme with high complexity encryption over decryption I need an encryption operation be 1000-1000000 times more complex than decryption operation. Is it possible to achieve with EC cryptography?

You could use a PoW style system combined with authenticated encryption similar to SIV mode as follows:

Determine the hash of the plaintext, $H$ = SHA512$(P)$

Using a 128-bit nonce $N$, an incrementing 64-bit counter $C$, calculate $S$ = SHA512$(E_k(H) | N | C)$  until you have the required amount of sequential high order bits with a value of 0, 32 for example.

Encrypting the plaintext hash makes sure you will not generate the same secret as someone else using the same plaintext and nonce but with a different key.

Truncate $S$ to the 96 lowest bits, and use that as the nonce for CTR mode to encrypt the data

The ciphertext will be supplied with the $N$ and $C$, after decryption you calculate $H$ then $S$ and verify that it matches BOTH the ctr nonce as well as having the correct 0-bit prefix, you should also authenticate $N$ and $C$ some how.

The scheme is configurable for the workload by choosing the amount of sequential 0-bits in the hash. Using a single iteration of SHA512 (or Blake2b) means one cannot use bitcoin ASIC to accelerate encryption, and that encryption requires high cpu but low memory. Hash calculation is generally much less complex than other algorithms such as ECC.

If you want there to be no way to have the same plaintext/key combo generate the same hash, the nonce can be based on prior data like in a blockchain, or based on the current time (if not fakeable), or a sequential counter. (or a combination of several values). You can also eliminate optimization attacks on the hash message schedule by making $S$ = SHA512$(E_k(C | C) | E_k(H) | N)$, but that is probably not a concern.


Can Eve break this public key cryptosystem if she can solve DLP or DHP? The PKC is in this way:

Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and sends the number $u = m^a\pmod p$ to Bob. Bob chooses a random exponent $b$ and sends $v = u ^ b = m^{ab}\pmod p$ back to Alice. Knowing the inverse of $a\pmod{p-1}$, Alice then computes $w = v ^ {a^{-1}} = m^{b}\pmod p$ and sends $w$ to Bob. Finally, Bob also computes $w ^ {b^{-1}} = m\pmod p$ and recovers the value of Alice's message.

I know a disadvantage of this PKC over ElGamal, that more times of data exchange is needed in order to send a single message. Are there any advantages of this cryptosystem over ElGamal? In particular, can Eve break it if she can solve the discrete logarithm problem? Can Eve break it if she can solve Diffie-Hellman problem?

Can Eve break it if she can solve Diffie-Hellman problem?

Yes, at least, the computational Diffie-Hellman problem.  This problem is "given the triplet $h, h^x, h^y$, recover $h^{xy}$"

Let us assume that Eve has an Oracle that solves this problem.  Then, she sets $h=m^{ab}$, $h^x = m^b = (m^{ab})^{a^{-1}}$ and $h^y = m^a = (m^{ab})^{b^{-1}}$, and passes $h, h^x, h^y$ to her Oracle.  The Oracle returns with $h^{xy} = (m^{ab})^{a^{-1}b^{-1}} = m$, problem solved.

And, if she can break the Discrete Log problem, she can solve the CDH problem, so this answers that question as well.

N.B. The protocol you listed is known as the "Shamir Three Pass Protocol", and is currently viewed more as a curiosity rather than something that solves some problem better than other solutions.


CDH between two groups implies weakness of El-Gamal Let $G$ a cyclic group of prime order $p$ with a generator $g$.

Let $H$ a cyclic group of prime order $p$ with a generator $h$.

Suppose that you have an algorithm $\mathcal{A}$ that given two elements $g^a$ and $g^b$ in $G$ outputs $h^{ab}$ in the group $H$.

Show that El-Gamal encryption is not secure in the sense of ciphertext-indistinguishabiliy.

Let $a$ the secret key and $(g,g^a)$ the public key.

I observed that if we can control $H$, we can take $H=G$ and $h=g^a$ and we can actually decode an encryption using $\mathcal{A}$.

So, given an encryption $(g^b,g^{ab}m)$ we can run $\mathcal{A}(g,g^b)=h^{1\cdot b}=(g^a)^b=g^{ab}$ and using this we can easily obtain $m$.

My question

If we cannot control $H$ is it still possible? Can we use group isomorphism to prove that we can adjust $\mathcal{A}$ to deal with our choice of $H$? or maybe we can use $\mathcal{A}$ to only break ciphertext-indistinguishabiliy rather than full decryption of messages?

You are actually quite close.

Because I'm not sure I understand the stated security notion, I will break IND-CPA security instead, you should be able to adapt the idea.

Let $m_0,m_1$ be our challenge messages with $m_0\neq m_1$. Let $(g,g^a)$ be the public key, $a$ be the private key and $(c_1=g^k,c_2=g^{ak}m_b)$ be the challenge ciphertext. Let $\mathcal O:G^2\to H:\mathcal O(g^a,g^b)\mapsto h^{ab}$. Assume $h$ to be known or to be defined as $\mathcal O(g,g)$.

We shall use $\mathcal O$ to build a Decisional Diffie-Hellman (DDH) oracle for the group G. As the IND-CPA security of ElGamal can only be reduced to DDH and not CDH, breaking DDH suffices to break IND-CPA security.

Let $h^a=\mathcal O(g,g^a)$ and $h^b=\mathcal O(g,g^k)$. Further let $h^{ak}=\mathcal O(g^a,g^k)$. Next compute $c'=c_2/m_0$. Return 0 iff $\mathcal O(g,c')=h^{ak}$ else return 1 as the guess for the challenge bit $b$.

So why does this work? Note how $c'=g^{ak}m_b/m_0$ which is $g^{ak}$ if $b=0$ and something else otherwise. Now $\mathcal O(g,c')$ sends this to $h^{ak}$ iff $b=0$, but as we have already computed $h^{ak}$ using the public keys, we can now make the comparison to verify our guess for $m_0$!


How secure is AES-256? The cipher AES-256 is used among other places in SSL/TLS across the Internet. It's considered among the top ciphers.

In theory it's not crackable since the combinations of keys are massive.

Although NSA has categorized this in Suite B, they have also recommended using higher than 128-bit keys for encryption.

So how secure is this cipher really? Should you assume the worlds top cracker-institutions are near or have cracked it already?

I wouldn't assume that the NSA has cracked AES ciphers. I would assume that most crypto systems that use AES have implementation flaws that the NSA exploits when they feel it is worth it.

In any case, when the only possible way a state can know something is by breaking a cipher, it's difficult for them to use that information; doing so would reveal that the cipher is broken. So in practice, a broken cipher is more likely to be used as a shortcut to find something that could be discovered (albeit with more difficulty) by other methods.

You might be interested in this recent story and commentary about NSA's crypt analytical capabilities.


Encrypting a key with the same key, for instance using AES I am new to crypto and trying to understand if it would be insecure to use a cipher such as AES to encrypt a key with the same key. If it is insecure, then why would it be insecure?

Basically, something like this:

encrypt(key, key)

What happens when both key and message are the same (128 bits)?

The obvious question would be why would I want to do that. If I have a secure channel to send the key, why encrypt it? My question is more for understanding.

I'm taking the question as: given some cryptosystem using AES-128 with some random secret key $K$, what are benefits and drawbacks of computing and making public $\hat K=\operatorname{AES}_K(K)$?

Benefit - $\hat K$ can be used as a KCV: A legitimate holder of $K$ could do the same calculation with the $K'$ he holds, and compare $\operatorname{AES}_{K'}(K')$ to the public $\hat K$. If there's no match, then one of $K'$, $K$, or the copy $\hat K$ used in the test is altered. If there's a match, it is almost as certain that $K'=K$ that it is certain that $\hat K$ is genuine. In this usage, $\hat K$ would be a Key Check Value (and far from the worst KCV ever used). And if the purpose of such a KCV and test is to guard against alteration of $K$, or of the AES encryption engine, and $\hat K$ is not made public but rather stored secretly along $K$, that seems a byzantine but effective idea (caveat emptor: side channel leakage considerations may apply).

Drawback 1 - $\hat K$ enables an attack on a reduced-round version of AES: A passive attacker knowing $\hat K$ has the same test as above to determine (with high confidence) if a guess of $K$ is right. That test is slightly more useful than just a random plaintext/ciphertext pair would be, because, in AES-128, the first computational step is to XOR the input and key; that gives zero in case of computation of $\hat K$; and thus the result of the first AES round is a constant (0x6363636363636363). Revealing $\hat K$ is like revealing a plaintext/ciphertext pair for a variant of AES-128 with 9 rounds instead of 10. This saves close to 10% of the work in an attack by brute force; and might conceivably open to a cryptanalytic attack that has a benefit at 9 rounds, but not the full 10; I do not see either as truly worrying in practice, though.

Drawback 2 - in some protocol, $K$ can leak: An active attacker might trick a legitimate party holding $K$ into revealing $K$, if that legitimate party uses $K$ to compute the function $\operatorname{AES}^{-1}_K()$. For example, assume a (dumbed down) authentication protocol where Alice draws a random $R$; computes $C=\operatorname{AES}_K(R)$; sends that to Bob, who computes $R'=\operatorname{AES}^{-1}_K(C)$ and sends that back to Alice (which compares $R$ to $R'$). An active adversary knowing $\hat K$ can obtain $K$ from Bob by submitting $\hat K$ instead of $C$, and will get $K$ as $R'$ (because $\operatorname{AES}^{-1}_K(\hat K)=K$). More generally, availability of $\hat K$ could entirely ruin the security of any protocol or encryption mode where $\operatorname{AES}^{-1}_K()$ is used anywhere, and invalidate the security argument of others.


RSA key pair generation and FIPS 140-2, 186-4 I need to securely generate RSA key pair and I need to have access to private exponent in order to process it further.

What's the difference in FIPS 140-2 and FIPS 186-4 in connection with RSA key pair generation?

If I understand it correctly generating RSA key pair in FIPS 140-2 compliant environment will never show the private part of the RSA key pair as it is protected by cryptographic module.

FIPS 186-4 is about validating that RSA key pair was correctly generated and fulfils requirements about primes and exponents.

So if I want to securely generate RSA key pair and I want to have access to its private part in a clear-text form, I need to use FIPS 186-4 compliant generation and validation.

Am I correct? Do I understand these correctly?

FIPS 140-2 specifies conditions applicable to the environment of RSA (and other) key generation, and refers to FIPS 186-4 for the generation itself.

Several recent Java Card Smart Cards can internally generate RSA-2048 key pairs per FIPS 186-4, with security policy and FIPS 140-2 level 3 certificate to attest that. Here is the one on top of the list at time of writing. A trivial Java Card applet runnign in that Smart Card's Java Card Virtual Machine can generate such RSA key, and export the private key, in clear if you want that. Such key would be for a FIPS-approved algorithm (certs# 1506-1507), and generated according to FIPS 186-4, as attested by a FIPS 140-2 level 3 certificate. That's not enough to pretend that the key was generated in a FIPS 140-2 compliant environment, because the security policy mentions

"The module is a limited operational environment under the FIPS 140-2 definitions";
accordingly the FIPS 140-2 level 3 certificate does not cover "operation environment";
"firmware loaded into this module (..) requires a separate FIPS 140-2 validation" where my reading is that this sentence applies to Java Card applets.

However a (less trivial) Java Card applet could "securely generate RSA key pair (with) access to private exponent in order to process it further" (as asked), for some definition of process like encryption of the private key under a master public key (a form of key escrow). I do not rule out that a FIPS 140-2 validation of that applet could be obtained, such that it would then be correct to tell that the RSA key pair was generated in a FIPS 140-2 validated environment.


Splitting Secret Key If I split a key $k$ into three pieces as $k1, k2$ and $k3$ how should I distribute the keys among three people such that any two of them are able to evaluate PRF, but be secure from any one of them trying to do so. The PRF is defined as
$F'((k_1,k_2,k_3),x)=F(k_1,x)⊕F(k_2,x)⊕F(k_3,x)$
It is known that the three people know what pieces they hold so in this case if I split the keys in pair as $k1, k2$ for first person, $(k1, k3)$ for second and $(k2, k3)$ for thrid person and compute
$F1((k1, k2), x) = F(k1, x) ⊕ F(k2, x)$
Now if I send this $F1$ to the second person and compute $F1 ⊕ F2$ where $F2$ is given as below then I should be able to recover the PRF $F'$. Is that correct?
$F2(k3, x) = F(k3, x)$

The mentioned approach of splitting the keys in pair as $(k1,k2)$ for first person, $(k1,k3)$ for second and $(k2,k3)$ for third person for the given situation is correct! And the PRF can be computed as follows:
First person computes: $F1((k1,k2),x)=F(k1,x)⊕F(k2,x)$
Send this F1 to the second person and compute F1⊕F2 where F2 is $F2(k3,x)=F(k3,x)$
$F1⊕F2 = F(k1,x)⊕F(k2,x)⊕F(k3,x) = F'((k1,k2,k3),x)$


Secrete message sharing using N private keys I'm looking for an encryption scheme that could possibly meet the following requirements.

Let,

$X = plaintext$
$M = (pub, priv)$, where $priv == (Ky + Kz)$

Given func [genKeys, partDec, fullDec, enc] perform,

$genKeys() \rightarrow (Ky, Kz)$
$enc(X, Mpub) \rightarrow C$

$partDec(C, Ky) \rightarrow C'$
$fullDec(C', Kx) \rightarrow X$

Now this is just my view of how the process should be done. I'm familiar with the aspects of symmetric vs asymmetric encryption. However, I have never encountered such requirements before.

To sum it all up:

I would like to share some encrypted message $C$ using $Mpub$. Generate dynamic keys $Ky$ and $Kz$.

$Ky_1+C$ can only be decrypted using $Kx_1$ and not any of the the other $Kx_n$ keys. This may be similar to one of the secret sharing algorithms or key regression scheme.

If this is not possible, then something similar should be sufficient.

I am not sure if I understand your requirement correctly, but from the first part of your
description I think you want the following (I skipped the second part since I do not understand the meaning of "$+$") :

Set up a public key $pk$ which can be
used to encrypt a message $m$ and you want to split the corresponding
private key $sk$ into two shares $sk_1$ and $sk_2$ such that given a
ciphertext $c$ encrypting a message $m$ under $pk$ can first be
decrypted using $sk_1$ to some intermediate ciphertext $c'$ and then
using $sk_2$ be decrypted to $m$. The goal is that decrypting with $sk_1$ reveals nothing about the message but if decrypted with $sk_1$ first and then with $sk_2$ will reveal the message to the entity holding $sk_2$.

Here is an example using ElGamal encryption.

Setup:

Let $p$ be a safe prime and $g$ be a generator of an order $q$ subgroup of $Z_p^*$. Let
the public key $y=g^x$ for some random $x\in Z_q^*$ and $x$ be the private key.

Now the partial private keys are $x_1$ and $x_2$ such that $x\equiv x_1+x_2 \pmod q$ and give
$x_1$ to $A$ and $x_2$ to $B$.

Standard Encryption:

To encrypt a message $m\in Z_p^*$ just do it as with standard ElGamal, i.e.,
compute the ciphertext $c$ as $c=(c_1,c_2)=(g^k,m\cdot y^k)$ for $k$ random in $Z_q^*$.

Standard Decryption

You can decrypt as you do it with ElGamal when you want to directly decrypt using $x$, i.e.,
compute $m$ as $c_2\cdot (c_1^x)^{-1}=m\cdot c_1^x\cdot (c_1^x)^{-1}=m$. Note that in the equation I write $y^k$ as $c_1^x$ as $c_1^x=(g^k)^x=(g^x)^k=y^k$.

Sequential Decryption

Now in order to sequentially decrypt a ciphertext $c=(g^k,m\cdot y^k)$ encrypted under public key $y$ by first
$A$ and then $B$ (one can also switch to first $B$ and then $A$) one proceeds as follows:

$A$ is given a ciphertext $c=(c_1,c_2)=(g^k,m\cdot y^k)$ and partially decrypts it to $c'$ by computing $c'=(c_1,c_2')$ where $c_2'= c_2\cdot (c_1^{x_1})^{-1}$.

Then $A$ gives the "partially decrypted" ciphertext $c'=(c_1,c_2')$ to $B$. $B$ then
decrypts $c'$ to $m$ by computing $m=c_2'\cdot (c_1^{x_2})^{-1}$.

To see that this is correct observe that

$$c_2'\cdot (c_1^{x_2})^{-1} = c_2\cdot (c_1^{x_1})^{-1}\cdot (c_1^{x_2})^{-1} = m\cdot c_1^{x_1}\cdot c_1^{x_2}\cdot (c_1^{x_1})^{-1}\cdot (c_1^{x_2})^{-1}=m.$$

Clearly you can generalise this to arbitrary $n>2$ additive shares of the private key $x$ such that only the $n$'th user in the chain of partial decryption learns the message $m$.