Suggestions for improving encrypt-then-mac flow I have a large piece of data I want to encrypt, and I have a key master_key.

Rather than encrypt the data directly with master_key, I generate a random key item_key, split it in two parts, and encrypt the data with the first half, and use the second half as an auth key in generating an authentication hash with HMAC.

I then encrypt item_key with master_key. This way, if the user were to change their master_key, I would only need to rewrite the item_key, and not the large piece of data.

So the end result of the overall encryption is:

the ciphertext
the authentication hash (or tag) of the ciphertext <- HMAC(ciphertext, auth key)
encrypted item_key

What I overlooked however is that I am generating two ciphertexts here, one of the encrypted data, and one of the encrypted key. But, I only have one auth hash. This is a flaw as I go on to decrypt the encrypted item key using the split master_key without checking its authenticity. I do however check the authenticity of the ciphertext, but that's not as useful.

My challenge now is to use the pieces that I already have to fix this problem. This means I don't want to introduce new keys.

To fix this flaw, I would need to generate an auth hash/tag for both the data ciphertext, and the item key ciphertext. The problem is, I don't have another secret authentication key to spare.

Possible solutions:

Do not generate an auth hash for the ciphertext, and instead generate an auth hash only for the encrypted item key, since that is what is being encrypted with the master key. The application promises to never decrypt the actual data ciphertext without first authenticating and decrypting the item key. Will I be roasted by the security community for doing this, even if it's theoretically safe? Is it "bad style"?
Derive from the master key an encryption key and an auth key using a PBKDF2 with a small iteration count (less than 3000). I would use this auth key to generate an auth hash for every encrypted item key. (The item key would then be used the same way explained in the beginning: split in half, one half used as encryption key, the other as auth key for the data).

I prefer to go with option 1. Does this sound reasonable? Or are there any other solutions I may be overlooking?

Note: AES-GCM would seem to solve this problem easily, as I do not need auth keys, but I cannot use this method since the platforms I intend to support do not provide native support for this algorithm.

The primary purpose of the MAC in an Encrypt-then-MAC scheme is not to detect attempts to decrypt with the wrong key (although it may accomplish that as a side effect, depending on how the encryption and MAC keys are derived), but rather to make the scheme non-malleable, and thus:

protect the user's data from tampering by an attacker who can modify the ciphertext, and
protect the encryption part of the scheme from attacks (such as padding oracle attacks against CBC mode encryption) which are based on feeding malformed ciphertext to the decryption algorithm.

Thus, if you want your scheme to resist such attacks, you really do need to apply a MAC to the actual ciphertext that encodes the user's data.  Only MACing the (encrypted) item keys will not protect the user's data from tampering.  Thus, your "option 1" is definitely insecure.

Your option 2, on the other hand, does appear reasonable, at least as far as you describe it.  (I cannot, of course, tell if there are security flaws in the parts that you haven't described, or in the way that you implement the parts you do describe.)

Note that the iterated key stretching aspect of PBKDF2 is only needed when the input is a user-entered password or some other potentially low entropy string.  In your case, since you already have a high-entropy master key as input, you may safely reduce the iteration count to 1, or even use a non-iterating KDF such as HKDF.

Alternatively, I don't see any reason why you couldn't just double the length of your master key, and split it into two parts like you currently do for the item keys, except that this will require slightly more storage space for the master key.  But since you only have one of those, I doubt that would be a major issue.

If you wish to minimize the overhead of storing and authenticating the item keys, I could suggest something like that following scheme:

Store a single base master key (of, say, 256 bits); use HKDF-Expand (or PBKDF2 with an iteration count of 1) to derive a master encryption key and a master MAC key from the base master key.
For each item, store a single base item key (again of, say, 256 bits) encrypted with the master encryption key and authenticated with the master authentication key.
Derive an item encryption key and an item MAC key from the base item key using HKDF-Expand (or PBKDF2 with an iteration count of 1), exactly the same way as for the master key in step 1.
Use the derived item encryption and MAC keys to encrypt and authenticate the user's data.

This should consume no more space than your current scheme (assuming that the MAC tokens aren't longer than 256 bits, which they really have no reason to be), while protecting both the item keys and the items themselves from tampering.

As an extra precaution, you may also wish to include some metadata (such as user and item IDs) as "associated data" in the MAC calculations in steps 2 and 4.  This will prevent an attacker from, say, replacing one encrypted item and its item key with the corresponding data and key of another item.  Whether such attacks are actually a relevant threat for you will depend on things like what these "items" are actually used for, but since they're easily enough prevented, you might as well do it anyway.


Consequences of AES-GCM always encrypting the same plaintext I am analysing an authentication protocol. In this protocol AES-GCM is used to encrypt part of the messages.
Regarding the authentication protocol, I made the following observations:

The plaintext that is being encrypted is always the same. It may be assumed that the plaintext is known by the adversary.
Deterministic construction is used for the IV. It can be assumed that the IVs are also known by the adversary.
only two blocks of data are encrypted.

So, the only thing that changes during different runs of the authentication protocol is the IV (but these IVs are known by the adversary).
My intuition tells me that it is not a good idea to always encrypt the same plaintext.
I have the feeling that this may leak information about the encryption key?
So, my question is:

Can the encryption key be compromised if you have enough transcripts of protocol runs?
How many protocol runs would you need (AES-128-GCM is used)?

The main obligation for the AES-GCM is never to reuse a (Key, IV) pair.

Can the encryption key be compromised if you have enough transcripts of protocol runs?

How many protocol runs would you need (AES-128-GCM is used)?

The standard IV size is 96-bits. If sequentially used (as NIST says counter/LFSR ) then one cannot finish this IV space in a lifetime. Once reuse occurs, however, with a system failure etc., then the confidentiality is revealed and the same string that always sent is compromised.
Also, using the same key with a new random IV can cause replay attacks. The attacker can just re-transmit and old data. It is valid since the same key is used. Mitigation is putting time-tamps on the encrypted message. A new key establishment per record is better as used in TLS 1.3.
AES-GCM for single (Key, IV) pair the total encryption is most $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits. No problem here.
Once the keystream revealed with the key reuse, the attacker needs to execute a known-plaintext attack against AES-CTR. AES-CTR is secure against KPA attacks it has Ind-CPA.

The plaintext that is being encrypted is always the same. It may be assumed that the plaintext is known by the adversary.

The IV used in the encryption provides probabilistic encryption so that the same message will have different ciphertexts. This is crucial in modern Cryptography. And, again AES-CTR is secure against this KPA attack even Ind-CPA.
Suggestions:

Change the key with a predefined protocol.
Don't send the same message again, use new challenges in each message.
If the message is known to the adversary, what is the point of the encryption? You just give the attacker lost of known-plaintext that is normally hard to collect.
Use timestamps to protect againstt replay attacks,


Appropriate public exponent choice for RSA encryption From what I understand, we can arbitrarily choose an exponent e as long as
 $\gcd(e,\phi(n)) =1$.

But what is the most appropriate choice for it?
Should it be small compared to $\phi(n)$ or approach it?

we can arbitrarily choose an exponent $e$ as long as $\gcd(e,\phi(n))=1$.

No. If we want any security, we further :

Must NOT choose $e=1$, because that makes $x\mapsto x^e\bmod n$ the identity function over $[0,n)$.
Must NOT choose $e$ in a way revealing information about of $\phi(n)$ or the factors of $n$ beyond that $\gcd(e,\phi(n))=1$. For example, we can not choose  $e$ as $e=p$, nor $e=\phi(n)-3$, nor as the first integer larger than $\phi(n)/42$ with $\gcd(e,\phi(n))=1$, nor in such a way that $d$ is small.
Should choose $e$ not too small if there is a regulatory minimum or we have little assurance about how the key will be used. This mitigates to some degree some poor message padding and some poor decryption implementations. Using $e\ge2\log_2(n)$ should be technically OK for all except the worst (or absent) paddings.

What is the most appropriate choice for $e$?

The simple, safe, standard option is: choose $e=F_4=2^{(2^4)}+1=65537$, then choose prime factors $p$ of $n$ with $p\bmod e\ne1$. This test (and factors being distinct of $e$, which holds for suitably large factors) is enough to ensure $\gcd(e,\phi(n))=1$, since we picked $e$ prime. And picking factors as a function of $e$, rather than the other way around, ensures minimal information is revealed about $\phi(n)$ and factors of $n$. $65537$ is large enough that $e\ge2\log_2(n)$ is met for practical sizes of $n$, and conforms to recommendations by all major security authorities.
If for some reason we must choose $e$ after factors of $n$, a common practice is to choose the lowest $e$ above some minimum with $\gcd(e,\phi(n))=1$. A very slightly safer practice would be to choose $e$ randomly in some interval $[m,2m)$ until $\gcd(e,\phi(n))=1$, but that's overkill (and there's seldom a good reason to choose $e$ after the factors of $n$ anyway).

Should $e$ be small compared to $\phi(n)$ or approach it?

The former: $e$ should be small, and $\phi(n)$ large. There is often a conventional upper limit to $e$, like $e<2^{256}$ in FIPS 186-4, or $e<2^{32}$ in some Windows APIs, when $\phi(n)$ must be in the thousands of bits. And for reasons already spelled, $e$ must not be chosen close to $\phi(n)$. Also, it is best to keep $e$ not too large for performance reason: public-key use requires time roughly proportional to the bit size of $e$. The standard $e=F_4=2^{(2^4)}+1$ is attractive because encryption with it is faster than with larger values of $e$ (and as well as most lower values). Still, that $e$ makes public-key use about 8 times slower than with $e=3$; the latter can be a good choice when the performance of public-key use is paramount, appropriate padding and implementations are used, and regulatory requirements allow.


What is an efficient random number generation algorithm I have been looking for the algorithm that generates random number and this algorithm has to be more secure.

I am going to use this algorithm to generate the salt that will be used in PBKDF2.

Through my reading, I found that ISAAC is fast algorithm and better than RC4 but it is not good in terms of the security. Also, I thought about Blum Blum Shub algorithm but some articles said it is not an efficient algorithm.

What I need is your opinions about which algorithm is better OR which algorithm you prefer to use?

Thanks

Since the goal is to generate the salt for PBKDF2, there is no need for an efficient (as in fast) random generator: PBKDF2 is (purposely) compute-intensive. Further, in many uses of PBKDF2 (e.g. storing a password), the salt is generated once, stored, and reused many times, further lowering the concern over efficiency of the salt generation. As the saying goes: premature optimization is the root of all evil.

In this usage, you also do not need a precisely uniform distribution (as would be the case for a random generator used e.g. in a casino machine). The (extremely slight) bias of RC4 is not a concern in the context of salt generation.

In that context, by far the most important criteria is that the generator should have low odds of generating twice the same value. As shown by recent anecdote in the context of RSA key generation (also here updated), that's difficult to implement correctly, especially on network appliances. The essential problem is that different runs of any deterministic RNG (such as RC4 or ISAAC) will generate the same result if fed the same input. Thus what matters is the seed material of the generator, and if/how its state is preserved across runs.

Two simple implementations of a generator that does not repeat are

Increment a persistent integer (stored e.g. in a data base), then output it. The integer should be wide enough to never overflow, or the  number of runs limited.
Obtain the UTC time to some granularity, wait at least as long as that granularity, plus twice the maximum absolute value of the uncertainty of the source of time, plus one second (to account for leap second), then output the result.

Notice that both methods assume a single instance runs, and can be broken if the attacker can influence the system (reset the persistent integer, alter the clock setting...). And of course, these generators are predictable, not random generators. But assuming the availability of a single secret randomly-seeded Key, this is easy to fix: given the output N of a generator that does not repeat, output HMAC(Key,N).

Practical designs of good software RNGs combine seed material gathered using several techniques, including the above, CPU clock since boot, process time, RAM content at boot, hard disk and network latency, mouse position, keyboard presses and their timing, hardware serial numbers such as in hard disk and network cards...

For more in-depth discussion on the desirable properties and design of software RNGs, see yarrow. For physical design and testing, see e.g. Design of Testable Random Bit Generators.


Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG? This exercise comes from Coursera's "Cryptography" course.

  Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG?

$F$ is a PRF with $n$ bit key, input, and output length. I know the answer is “NO it isn't!”, but I can't understand why.

Is that because on any input $x$, the keys for every $F$ in the concatenation sequence are fixed, which implies that the $F$ functions are not randomly chosen over $2^{-n}$? Could this be a possible answer?

Because the key-, input- and output-length of $F$ are equal, if the length of the seed $x$ is $n$, there are $2^n$ keys and so $G$ must compute $F$ $2^n$ times and output a string of length $n\cdot 2^n$. Hence, $G$ runs in time exponential in $n$, which means it can't be a pseudorandom generator because a pseudorandom generator is a deterministic polynomial-time algorithm.

(In addition, since a distinguisher runs in time polynomial in the length of $G(x)$, it runs in time exponential in the length of $x$, and brute force through all possible seeds is allowed.)


Can this AES encryption operation be described as being Homomorphic operation? Am doing some work on privacy preserving classification on encrypted dataset. Pls really need a clarification.
I encrypted a dataset (plaintext) with AES scheme and get a cypher text.
I was able to use a machine learning tool WEKA to do a data mining operation(train and classify) on the cypher text
I decrypt the cypher text and discovered that the decrypted result matches the one I obtained when the same operation was performed on plaintext.
Can this operation be termed Homomorphic?

No, it cannot. The idea is that homomorphic operations take place on the ciphertext, not on the plaintext. This is clearly described by the Wikipedia article on homomorphic encryption.

You can do limited homomorphic operations on AES ciphertext. For instance, if you perform CTR (counter) mode encryption then you can XOR one or more bits, and the result will be that, after decryption, the plaintext will also have those same bits flipped. So here the operation takes place on the ciphertext but it has the same effect on the plaintext without affecting the confidentiality of the message.

In general however homomorphic encryption will be performed on forms of encryption based on mathematical operations, such as modular exponentiation used for raw RSA. As the encryption/decryption operation itself are mathematical constructs it is easier to perform operations on the ciphertext that have the same effect on the plaintext, such as multiplication (the first example in the Wikipedia page).

Full homomorphic encryption, where you can do an unlimited amount of operations on the ciphertext, remains elusive.

Your question could also be read that you simply try to learn things from the ciphertext. Now unless you perform deterministic encryption you should not learn anything from the ciphertext except its length. If you would learn anything from properly encrypted and randomised ciphertext (i.e. with a proper IV) then the cipher would be broken.

So that would mean that your scheme is broken. You would still not perform homomorphic encryption as:

learning things from the ciphertext is exactly what (homomorphic) encryption tries to avoid and;
as you don't alter the ciphertext no morphing is actually performed.

So whichever way you look at it, no, this has nothing to do with homomorphic encryption.


DSS security in comparison to ECDSA or RSA OpenVPN allows the users to choose the TLS cipher suite, depending on the deployed SSL/TLS library. With OpenSSL 1.0.2g and OpenVPN 2.3.11 this is a rather long list (Full list).

Amongst the many options there are TLS cipher suites like the following available:

DH-DSS-AES256-GCM-SHA384

Which breaks down to:

Key Exchange: DH
Signature: DSS
Cipher: AES256
Mode: GCM
Digest/Used for PRN: SHA384

I'm trying to validate the security of the deployed cipher suites, but I can't find details of the DSS signature method.

Is there another name, I may identify DSS as, or is it just very uncommon?

How does DSS perform, only considering the security?

As noted in comments, DSS strictly means the Digital Signature Standard, a document (FIPS 186) published by NIST, a part of the US government. The original version of FIPS 186 in 1994 defined (and was the original definition of) a single algorithm, DSA the Digital Signature Algorithm. Later versions of FIPS 186 added other algorithms primarily by reference to definitions elsewhere: RSA from X9.31 and later PKCS1, ECDSA from X9.62 (and SEC1). So technically DSS is now ambiguous as an algorithm identification, but quite a few standards including SSL (now TLS) were set using 'DSS' when it actually meant DSA and those names still survive because it would be a huge hassle to change them and everyone who matters knows what is meant.

In principle both DSA and ECDSA rely on the difficulty of finding discrete logarithms (or equivalently the one-way-ness of exponentiation) in appropriately structured finite groups. For DSA this group is a generated subgroup of the multiplicative group of integers modulo a large prime, notated $Z_p^*$. For ECDSA it is a subgroup (often 'improper' = the whole group) using 'addition' of points on a suitable elliptic curve over a suitable finite field -- either a 'prime' curve over $F_p$ represented/implemented as integers modulo p ($Z_p$) or a 'characteristic two' or 'binary' curve over $F_{2^m}$ represented as binary polymonials modulo a given irreducible polynomial. Although the point operation is usually notated as addition and the curve operation as scalar multiplication, these operations are not ordinary arithmetic addition and multiplication.

Although in abstract the same, there are practical differences due to the size and resulting strength of the 'parameters' used.

The original versions of FIPS 186 specified that p, the prime defining $Z_p^*$, should be 512 to 1024 bits in steps of 64 bits only, and the subgroup size $q$ only 160 bits. These sizes were sufficient in the 1990s, but as the 2000s passed they no longer provided sufficient margin of safety. FIPS 186-3 in 2009 belatedly increased standard sizes of p to 2048 and 3072 bits and q to 224 and 256, but it took some time for implementations to follow; as one notable example, Java 7 was supported until 2015 (and appears to still be in use today from Qs in stackoverflow and similar places) and limits p in DSA (and also DH!) to 1024 bits.

RSA similarly needs larger sizes now than it did in the 1980s and 1990s, but the standards for RSA never set a fixed maximum and most implementations allowed some (often a lot) of leeway. Thus when most standards and authorities -- and especially SSL/TLS CAs -- began requiring RSA-2048 instead of RSA-1024 in or soon after 2014, a lot of people had to generate new keys and certs but did NOT need to change their software (at least not for this reason).

In contrast ECDSA was initially defined with curves covering a range of sizes up to 500+ bits with strengths up to 250+ bits, and NSA adopted two of them (P-256 and P-384) in its Suite B, so practically everybody began using those two (or at least the first) which are strong enough.

As a result in general you can assume that if ECDSA (or ECDH) is used at all it is probably used with sufficiently strong parameters, whereas you can't always make this assumption for DSA and RSA. However for OpenSSL this is usually not a problem; due perhaps to lucky timing OpenSSL 1.0.0 was released in 2010 and included the increased FIPS 186-3 sizes, so unless you're on a really old system stuck at 0.9.x you're okay.

Another feature/limitation of both DSA and ECDSA is that they require each signature to use a nonrepeating and at least nominally random value (a nonce), and if you do repeat a value an adversary can easily recover your private key and forge signatures, which is Bad. There are proposals to change this including by our very own bear but not much progress yet. RSA signatures do not strictly require randomization, and the most-common (mostly because oldest) scheme RSASSA-PKCS1v1_5 does not use it at all (after key generation, which does require good randomness but is done rarely).

FWIW a similar naming issue occured with DES, which formally was the Data Encryption Standard document FIPS 46 from what was then NBS, and defined a single algorithm DEA the Data Encryption Algorithm (modified from IBM's Lucifer). As time passed and 56-bit keys became too short -- or at least more visibly too short -- the document FIPS 46 (DES) was revised to include TDEA the Triple Data Encryption Algorithm which many people called (and still call) Triple-DES even though it was not a separate standard. Then after AES (document) FIPS 197 was published defining AEA (algorithm, a profile of Rindael) FIPS 46 was withdrawn and TDEA (but NOT DEA) was republished as a Special Publication which is formally not a standard and thus formally DES and Triple-DES no longer exist. But both people and software and documents written in the past still refer to them, and many (like some SSL/TLS ciphersuites and OpenSSL, and also Java crypto) refer to TDEA as DESEDE or DES-EDE, sometimes with 3 attached somewhere, which were basically the nicknames used during a discussion period before TDEA was standardized; this is because both encrypt-decrypt-encrypt (EDE) and encrypt-encrypt-encrypt (EEE) constructions were seriously considered before the former was chosen.


Encryption of small messages Some time ago, I asked how to encrypt small messages like e.g., four decimal digit numbers (banking PINs). I've got my answer, but also a warning like it makes no sense as it's easy to guess: Even having no information at all and bad luck implies 10000 trials only, which is nothing in crypto.
However, at an ATM you have three trials only, and a PIN encryption scheme not leaking any information makes a lot sense to me. What does the theory say?
Clarification:
I'm looking for something telling apart bad and good system for this encryption.

A bad system could be "add a constant to the PIN modulo $10^4$. The attacker with a single plaintext-ciphertext pair could decrypt any other ciphertext.
A perfect system would be "generate a permutation table with $10^4$ elements using a true RNG and a proper algorithm". Now the attacker with any number of plaintext-ciphertext pairs given an unseen-yet ciphertext knows nothing except that the corresponding plaintext is not in his collection.

You want to talk about format-preserving encryption. One of the main motivations for FPE is the ability to encrypt messages which lie in a short space, with an output which is in the same space.

The ideal encryption model on a space of size $S$ (e.g. $S = 10000$ for four-digit PIN codes) is that the encryption systems implements a permutation chosen randomly and uniformly among the set of $S!$ possible permutations. Or at least that the cipher is indistinguishable from such a randomly chosen permutation.

An extreme security model is then the following: assume that the attacker is given a black box which implements the encryption (and decryption) algorithms. He can ask for the encryption or decryption of the almost complete code book, i.e. $S-2$ requests. The attacker gets to choose the contents of each request, adaptatively. So at that point, the attacker can simulate the complete encryption function, except for two input values: he knows the two inputs (let's call them $p_0$ and $p_1$) and the two corresponding outputs ($s_0$ and $s_1$), but he does not know whether $p_0$ encrypts to $s_0$ or to $s_1$. His goal is to predict the encryption of $p_0$ with probability substantially better than pure luck (i.e. $1/2$).

A commonly quoted solution for FPE is the Thorp shuffle. It is an unbalanced Feistel cipher, with enough rounds to make it secure. The good part of it is that it is possible to prove security while keeping the number of rounds low enough to be practical (say 100 rounds or so). The bad part is that it does not realize the extreme model explained above. You have to relax a bit the model, because a Feistel scheme always implements an even permutation; so if you know all the code book except the encryptions of $p_0$ and $p_1$, then you can decide whether $p_0$ goes to $s_0$ or $s_1$ with 100% success rate, because only one of the two choices leads to an even permutation. However, the relaxation is not a big deal: if you give to the attacker only $S-3$ requests, then you can have the best possible under these conditions (attacker cannot predict the mapping of the three remaining inputs, except that they will have to comply to the "even permutation" rule).

To reach the "ideal" model with $S-2$ requests, you have to do heavier thing, like generating the complete permutation in a big array (this is certainly doable with only 10000 entries; for bigger spaces, memory-conscious solutions exist, but the CPU price is quite high). For a practical solution, use the Thorp shuffle.

For verifying PIN codes, encryption is probably not the right tool anyway. Indeed, as you notice, the space of PIN codes is so small that there must be a locking mechanism somewhere, which blocks the attempt after three wrong tries. You cannot have that from cryptography alone. In fact, you will get locking by using dedicated hardware: either a smart card (the smart card is tamper-resistant and locks itself after three wrong PIN codes) or a remote server (that enforces the locking policy).

FPE is used to realize other features, e.g. serial numbers with verifiable validity: you define an 8-digit number which embeds a 5-digit counter value, and you want to have a tool which can verify whether a given sequence of 8 digits is one of the 100000 sequences that you have issued; but you don't want anybody else to be able to generate random "valid" sequences with success probability higher than 1/1000. Solution is to encode the 5-digit counter as 8 digits by appending three zeros, then encrypting the whole lot with FPE. To verify, decrypt, and see if the three zeros are there.


Fully homomorphic encryption arbitrary functions formulation I am currently studying the interesting field of homomorphic encryption. I read that from a fully homomorphic encryption function that supports both addition and multiplication you can perform any mathematical and comparison operations. Ok, but how can you do this specifically? How do you for example perform comparisons ==, <. >= or exponential operations? How about floating number operations?

Suppose we want to compare two integers X and Y binary represented as X=x_0,x_1,...,x_n and Y=y_0,y_1,...,y_n. Comparing X and  Y translates to bit comparison, from the msb to lsb; therefore a toy example is to consider two bit comparison, x and y. The binary expressions(computation is done in Z_2) corresponding to three of their possible relations are the following:

x > y <=> x*y + 1 = 1
x = y <=> x + y + 1 = 1
x <= y <=> x*y + x + 1 = 1

This means that if we have the FH encryptions of x and y, namely C_x and C_y, we can evaluate C = C_x*C_y+C_x . Upon decryption of C, one can know if x>y (i.e. Dec(C)=1) or x<=y (i.e. Dec(C)=0).

Then you simply extend the above solution for n bits, namely you express conditions like ANDs as multiplications and conditions like ORs as additions.

For two bit integers, X=x_0,x_1 and Y=y_0,y_1, for comparison X > Y to be true, we have the following possibilities:
    x_0 > y_0 or
    x_0 = y_0 and x_1 > y_1.

Using comparison functions defined above for a single bit we have ( keep in mind that we treat OR as addition and AND as multiplication):

greaterThan(x,y) = ( x_0 > y_0) OR ( (x_0 = y_0) AND (x_1 > y_1) )
             = ( x_0*y_0 + x_0) + [ (x_0*y_0 + x_0 + 1) * (x_1*y_1 + 1)]

And that's all, you have a function ( greater than) expressed as a multivariate polynomial which you can write in terms of simple operations ( additions and multiplications). Now the best part is that for these simple operations we know they are homomorphic (namely DEC( ENC(x) + ENC(y) ) = x+y and likewise for multiplication) with respect to some underlying homomorphic encryption scheme (like BGV https://eprint.iacr.org/2011/277.pdf or ATV-FHE https://eprint.iacr.org/2013/094.pdf).

*-denotes bitwise multiplication

Please improve this answer by editing the mathematical notations.


Signing 2x128 bits key vs 1x256 Is signing something 2 times with two different 128 bit keys as safe
as signing once with 256 bit key ?
Does signing 2 times with 256 bit key will make it stronger than
signing once ?

Ok, first things first: Your question actually touches on two subjects:

Is it better / as good to sign something with two different half-length keys than with one full-length key?
Is it better / as good to use two half-entropy passwords as one full-entropy password?

The (theoretical) answer to both of these questions is a clear no. However, details matter, which can turn the "no" into a "yes".

To adress the first question: If "half-length" means that each key has a secure keylength to begin with, then yes, this is about as secure as using a full-length key, because each key is unbreakable to begin with, meaning we have "unbreakable" vs "even more unbreakable" at which point other considerations should pitch in. For example it might be easier to ensure correct usage if two keys are forced. It will be harder to extract two keys using side-channels or malware than it will be to extract one.

However, if half-length means that only the full-length key has a secure standard key-length, then this will be completely broken. As an example consider Elliptic Curve keys (such as used by ECDSA in Bitcoin): One 256-bit key is unbreakable right now because you need $2^{128}$ operations to break it, but two 128-bit keys are very much breakable because they require less than $2^{64}+2^{64}=2^{65}$ operations to be broken (because you can re-use parts of the computations).

Now for the specific instance noted in the comments:

  Are you familiar with bitcoin bip39 wallet creation ? My initial
  concern is, if multi-signature wallet created by two accounts with
  both seed of 12 words (128 bits of entropy) is safer or safe same as
  regular single signature account with seed of 24 words (256 bits of
  entropy ) ?

Now this is the question 2) I named above. While yes, this password will only offer 129 bits of security, this is already "unbreakable" at which point we would be discussing about "unbreakable" vs "unbreakable". Now nobody would successfully guess a 128-bit entropy secret, so it has to be stolen. It is harder to steal two secrets (which preferably are at different locations) than it is to steal one secret, so using two keys is actually preferable in this scenario.

  So it would be actually better to set up this account with 2x 24 word
  seed account which will produce 257 bits of [security].

Yes, it would be "better" in a theoretical sense. In a practical sense there's no security gain and all you achieve is making your own life harder by having to remember / type more words. Also see this Q&A on why really long passwords aren't better.

  Out of curiosity, does ed25519 support full security of 256 bits ?

No, Ed25519 has about 126 bits of security. The linked source talks about Curve25519 but can be equally applied to Ed25519 with minimal transformations.

  at some point i've heard that bitcoin developers were saying that it's
  way more secure than Secp256k1 ecdsa

Theoretically no, practically yes. secp256k1 provides the "full" 128-bit security that you would expect and thus is "more secure" than Ed25519. However, Ed25519 is a more modern mode and curve than ECDSA with secp256k1 meaning it is easier to get right and secure against implementation mistakes. This (and the speed bonus) is why it's usually preferred over ECDSA.

  Also - is there any asymmetrical cryptography algorithm with 256 bit
  security, if yes - then why Bitcoin or other crpyotcurrencies are not
  utilising it ?

Yes, if you replace secp256k1 with the P-521 curve, you get about 256-bits of security. However this will also be a lot slower because there are likely less optimizations and the operations are more complex due to larger values. Also see this answer for some discussion on curve sizes larger than 256-bit.

One final note: When I'm talking about "x-bit security" here, I mean that $2^x$ operations are needed to carry out a successful attack. The actual keying material may be bigger than the "security bitlength" which is only the lower bound.


Given a particular $1600$-bit output $Y$, is it feasible to find a $1600$-bit input $X$ such that $\text{Keccak-}f[1600](X) = Y$? I have read this answer on Crypto.SE and I want to clarify a few details.

Does this property of $\text{Keccak-}f[1600](x)$ imply that if we know a particular $1600$-bit output $Y$, it is feasible to find a $1600$-bit input $X$ such that $\text{Keccak-}f[1600](X) = Y$?

If yes, then consider the following situation.

An adversary $A$ has access to the full $1600$-bit state before the final truncation.
The original message $M$ has the length $L$ equal to, say, $552$ bits, and $A$ knows the exact value of $L$.

In this situation, will $A$ be able to find $M$?

Keccak-f is a permutation composed of trivially/efficiently invertible building blocks and is therefore itself trivially/efficiently invertible.

If you have the full state you can go backwards. In fact given a message of say, a MAC and the full state at the end you can go backwards and recover the secret key! So you may want to zero out part of the state after pushing your secret key through it in order to make going backwards intractable.

Using Keccak as a CSPRNG has a similar problem, need to periodically zero out a part of the state to defend against state compromise compromising past outputs, especially if there is no reseeding being done.

You can find the inverse operations here: https://github.com/CamMacFarlane/SHA3


When would I need DSA as opposed to RSA for digital signature? The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. This multiple encryptions is a pretty expensive process since public key encryption is so resource intensive.

On the other hand, the RSA-based digital signature algorithm encrypts the hash using only the senders private key, which is a much cheaper operation.

Under what circumstances would I need to use the expensive DSA as opposed to using the much faster RSA?

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key.

Huh?  I see two problems with the above statement;

"Encryption"; using the word encryption implies that there's a way somehow to decrypt it.  However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the hash.
"using ... the receiver's public key"; the signature operation most certainly does use the signer's private key, but it doesn't use any key (public or private) from the receiver.

  On the other hand the RSA-based digital signature algorithm encrypts the hash using only the senders private key, which is a much cheaper operation.

Not necessarily; if we're talking about the standard DSA operation, the expensive operation is a modular exponentiation of the generator over a (perhaps) 256 bit random exponent modulo the prime; for RSA, the expensive operation (I'm assuming CRT) is two modular exponentiations of arbitrary values modulo primes half in length of the key size.  I believe that you can implement the DSA operation (which, using precomputed tables, would take perhaps 50 multiplications modulo a 2048 bit prime) considerably faster than you can the RSA operation (which might take perhaps 2000+ multiplications modulo 1024 bit primes)

In addition, with DSA, you can potentially perform this computation before you learn the value you're signing; if you can do this in time where you would otherwise be idle, you can make the signing operation very cheap indeed.

And, if we're talking about DSA over Elliptic Curves, that is, ECDSA, the balance tilts even more radically towards ECDSA.

Where RSA shines is the signature verification operation; there's, it's considerably faster than (EC)DSA.

  Under what circumstances would I need to use the expensive DSA as opposed to using the much faster RSA?

Quite apart from your mischaracterization of DSA as expensive and RSA as cheap, actually, straight DSA is fairly rarely used in practice.  ECDSA (and relatives, such as EdDSA) are becoming more popular, in part because it is cheaper...


What information is revealed if we send our points in Projective Coordinates? Elliptic Curve Cryptosystem has various coordinate systems; like the Affine, Projective, and Jacobian coordinate systems.
We prefer not to use the Affine coordinate system during the calculations since the operations require inversion and that is much costlier than multiplication.
Katz and Lindell, in their book, wrote this sentence on page #332 of the 2nd ed. (bolds mine);

Specifically, a point expressed in projective coordinates may reveal some information about how that point was obtained, which may depend on some secret information.
To address this — as well as for reasons of efficiency — affine coordinates should be used for transmitting and storing points, with projective coordinates used only as an intermediate representation during the course of a computation (with points converted to/from
projective coordinates at the beginning/end of the computation).

So, what information is revealed? e.g. if we execute ECDH or ECDSA.
Is there a good example that shows how the information leaked?

The danger of revealing results in protective coordinates is pointed by David Naccache, Nigel P. Smart, and Jacques Stern's Projective Coordinates Leak, in proceedings of Eurocrypt 2004. As noted in comment, a concise re-exposition is in section 3 of Alejandro C. Aldaya, Cesar P. García and Billy B. Brumley's From A to Z: Projective coordinates leakage in the wild, in proceedings of CHES 2020 (which uses it in side-channel leakage attacks on implementations using projective coordinates internally, even when the result is output in affine coordinates).
In a nutshell: revealing $[k]\,G$ in projective coordinates can leak some information about $k$; that's problematic.

Slightly more detail: in affine coordinates, a point (other than the point at infinity) is expressed as $(x,y)$ satisfying the curve equation $y^2=x^3+a\,x+b$, where $x$ and $y$ are field elements. In standard projective coordinates, the same point is expressed as $(X,Y,Z)=(Z\,x,Z\,y,Z)$, where $Z$ is any non-zero field element. That becomes $(X,Y,Z)=(Z^2\,x,Z^3\,y,Z)$ in Jacobian projective coordinates.
Therefore giving a point in projective coordinate gives the point, and an extra information $Z$ that can be any non-zero field element. That $Z$ depends on how the point was obtained, and is a potential information leak.

More in detail: Assume that it is given $P=[k]\,G$ with unknown $k\in[1,n)$ as projective coordinates $(X_P,Y_P,Z_P)$, and that was computed starting from a known $G$ of projective coordinates $X_G,Y_G,Z_G=(x_g,y,g,1)$, and integer $k$, using standard formulas for point addition and point doubling, and the straightforward left-to-right exponent scanning algorithm:

$P\gets G$
for each bit $b$ of $k$ from second high-order to low-order

$P\gets P+P$ (point doubling)
if bit $b$ is set

$P\gets P+G$ (point addition)

It turns out that there is a relation between $k$ and the final $Z_P$, and that relation is exploitable to get some information on $k$.
[I started summarizing the first article, but did not finish, sorry. Feel free to expand!]


Key lengths of asymmetric encryption: ElGamal and ECC Recently I have been researching asymmetric encryption algorithms for a class, I cannot find any information anywhere on the key lengths used in any of the algorithms I'm looking into (ElGamal & Elliptic Curve Cryptography).

Is there a range of valid key sizes?

Key size and encryption system

Encryption systems are often grouped into families. Common families
 include symmetric systems (e.g. AES) and asymmetric systems (e.g.
 RSA); they may alternatively be grouped according to the central
 algorithm used (e.g. elliptic curve cryptography).

As each of these is of a different level of cryptographic complexity,
 it is usual to have different key sizes for the same level of
 security, depending upon the algorithm used. For example, the security
 available with a 1024-bit key using asymmetric RSA is considered
 approximately equal in security to an 80-bit key in a symmetric
 algorithm.

The actual degree of security achieved over time varies, as more
 computational power and more powerful mathematical analytic methods
 become available. For this reason cryptologists tend to look at
 indicators that an algorithm or key length shows signs of potential
 vulnerability, to move to longer key sizes or more difficult
 algorithms. For example, as of May 2007, a 1039 bit integer was
 factored with the special number field sieve using 400 computers over
 11 months. The factored number was of a special form; the special
 number field sieve cannot be used on RSA keys. The computation is
 roughly equivalent to breaking a 700 bit RSA key. However, this might
 be an advance warning that 1024 bit RSA used in secure online commerce
 should be deprecated, since they may become breakable in the near
 future. Cryptography professor Arjen Lenstra observed that "Last time,
 it took nine years for us to generalize from a special to a
 nonspecial, hard-to-factor number" and when asked whether 1024-bit RSA
 keys are dead, said: "The answer to that question is an unqualified
 yes."

The 2015 Logjam attack revealed additional dangers in using
 Diffie-Helman key exchange when only one or a few common 1024-bit or
 smaller prime moduli are in use. This common practice allows large
 amounts of communications to be compromised at the expense of
 attacking a small number of primes.

Acording to this Wiki Page

Also here are some more links to visit if you want to learn more about asymmetric cryptography:

asymmetric cryptography (public key cryptography)

Elliptic-curve cryptography

Elliptic-curve Cryptography Key Sizes

This 3rd link for Key Sizes is where it gets into some pretty complex methods, but if you really want to know Key length / sizes, then you will want to review that section.


What is a method for hiding RSA prime values from .exe De-Compiling? I've just been looking into RSA encryption with C++ and am wanting to make a program that can en/decrypt files of my own custom file extension. Obviously I need to choose two primes numbers (for my p and q values) to encrypt and decrypt this file, but I am curious as to how I could stop these values being pulled out of my program via de-compiling.

Obviously, with the primes in hand, someone could easily calculate the necessary values for the private key that ONLY this executable should have.

Are there methods for somehow generating a random private key that will always unlock the public key?

You can't. If the user can run the software, they can extract the key from it. There is research on how to make it difficult to extract the key (white box cryptography), but it's not very successful.

You need to think about what do you want to accomplish. Does the user encrypt the files to themselves, so that they can decrypt it later? Then you could derive a symmetric key from a user's password. Does the user want to encrypt the file to someone else? Then each user should generate a private key (the primes) for themselves, and send their public keys to one another.

(In each scenario there are a lot of details you should take care of, so you're just scratching the surface of the problem)


Accumulators with batch additions It was shown by Camacho that in batch deletions in accumulators, the information to update all witnesses is at least linear in the number of elements deleted.

I am wondering if there are accumulators with batch additions, where the information to update all witnesses is sublinear in the number of elements added. In the conclusion of his paper Camacho writes "such an accumulator can be trivially implemented by signing the elements of the set". However, I am interested only in publicly updatable accumulators where anyone (not just a privileged "manager" with a signing key) can update the accumulator.

Another non-publicly updatable accumulator is the RSA accumulator, where batching can happen by reducing the exponent modulo Euler's totient $\phi(n)$, which is to be kept secret by the manager.

Are there publicly updatable accumulators with batch additions?

Here's an overview of a strong [1], append-only accumulator with your desired properties. This accumulator was originally introduced by Reyzin and Yakoubov in [3]:

Supports provable batch additions.
Is publicly updatable.
The information to update all witnesses is sublinear in the number of elements added.

I'll describe this scheme by example, since formalization would be tedious and is not likely to enlighten.

First, take a look at the figure below.

It consists of a forest of Merkle trees. There's an old accumulator $F_7$ (orange nodes) and a new accumulator $F_{18}$ (orange & green nodes), which "includes" $F_7$. In fact, there's  an append-only proof of this consisting of the filled-in nodes (e.g., nodes 000, 0010, 00110, 00111, 01, 1000).

The prover stores all the leafs and the internal nodes (which include root nodes), while the verifier stores a digest of size $O(\log{n})$ consisting of all the root nodes, where $n$ is the number of accumulated elements.

For example, if you look at just $F_7$ (i.e., ignore all the green stuff), its digest $d_7$ consists of $\{h_{000}, h_{0010}, h_{00110}\}$ where $h_w$ denotes the hash of node $w$. Similarly, the digest $d_{18}$ of $F_{18}$ consists of $\{h_0, h_{1000}\}$.

Key ideas

The scheme is just a small tweak to Crosby and Wallach's history tree [2].

Adding elements

To add an element to the accumulator, the prover appends a leaf to the forest and merges nodes only when necessary so that all tree sizes are a power of two.

I think it's best to try out an example on paper to see when you would merge nodes to maintain this invariant. Formally, let $w = v|b$ denote a node with prefix $v$ concatenated with $b\in\{0,1\}$ and let $v|\bar{b}$ denote its sibling, where $\bar{b} = 1-b$. The idea is to only merge nodes that are siblings (i.e., we only merge $v|0$ with $v|1$ only if they are both in the forest).

For example, node 1000 has no (right) sibling so it cannot be merged with anything. In contrast, node 01 and node 00 are siblings so they were merged, resulting in a parent node 0. This process can continue recursively. For example, consider what happened when node 00111 was added: the first merge of 00111 with 00110 triggered two other merges, eventually creating node 00.

Membership proofs

The proof for an element $x$ being in a digest $d$ is just a Merkle path from $x$ to one of the roots in $d$. For example, the image below shows proofs for two different elements $x$ and $y$ w.r.t. digest $d = h_0$. The proof for $x$ consists of the filled-in nodes (i.e., $\pi_x = \{h_{00000}, h_{0001}, h_{001}, h_{01}\}$), while the proof for $y$ consists of the bold-circled nodes (i.e., $\pi_y = \{h_{00101},h_{0011}, h_{000}, h_{01}\}$). (It so happened that the proofs share a common node $h_{01}$ which I highlighted differently.)

Append-only proofs

If you look again at the overview picture, the append-only proof between $F_7$ and $F_{18}$ consists of "deduplicated" Merkle sibling paths (i.e., the filled-in nodes from the figure) from the old roots of $F_7$ to the new roots in $F_{18}$. Specifically, the nodes with $\times$ on them are "deduplicated": they are computed by hashing up the filled-in nodes.

The proof also consists of extra roots like $h_{1000}$ (also filled-in in the figure). This proof is very similar to the append-only proof in history trees [2] (except it's called a consistency proof in that paper).

Importantly, the size of an append-only proof between $d_m$ and $d_n, m<n$ is $O(\log{n})$.

Updating membership proofs (after an append-only proof)

After a batch addition in the old accumulator with digest $d$, the verifier receives an append-only proof from the prover and ensures nothing has been maliciously removed from $d$ or modified. As you indicated in your question, the verifier has some old membership proofs w.r.t. the old digest $d$ that he wants updated so they can verify w.r.t. the new digest $d'$.

First, note that the old membership proofs are sibling paths to the old root.s
Second, note that append-only proof between $d$ and $d'$ are sibling paths from the old roots to the new roots.
Third, recall that the append-only proof is $O(\log{n})$-sized, where $n$ is the size of the new accumulator.

By now, you might notice that one can easily "compose" the old membership proofs with the append-only proof to obtain new membership proofs w.r.t. the new digest $d'$. This necessarily involves linear computation in the number of old membership proofs, since the verifier needs to update them all. However, the bandwidth required to update the old membership proofs is sublinear since it's just the $O(\log{n})$-sized append-only proof.

For example, the old proof for $y$ w.r.t. to $d$ was $\pi_y = \{h_{00101}\}$ and the new proof is $\pi_y' = \{h_{00101},h_{0011},h_{000}, h_{01}\}$. Note that the verifier needs to compute $h_{0011}$ from its two children: an old root from $F_7$ and the 8th leaf in $F_18$. The verifier can easily do that because it has all the necessary information: the 8th leaf is part of the append-only proof.

In general, one can argue this will work for any element $x$ in any digest $d$ with updated digest $d'$. Again, the intuition is that the append-only proof consists of "deduplicated" Merkle sibling paths from old roots to new roots (e.g., no point in including $h_{0011}$ because it can be recomputed from its children which are included).

Conclusion

A strong, publicly-updatable accumulator with "batch addition" that can update old membership proofs with sublinear bandwidth exists. A slight tweak to Crosby and Wallach's elegant history tree [2] construction gives exactly that.

Hope this make sense and helps!

References

[1] "Strong Accumulators from Collision-Resistant Hashing", by Philippe Camacho, Alejandro Hevia, Marcos Kiwi, and Roberto Opazo

[2] "Efficient Data Structures for Tamper-Evident Logging", by Scott A. Crosby, and Dan S. Wallach

[3] "Efficient Asynchronous Accumulators for Distributed PKI", Leonid Reyzin, and Sophia Yakoubov


Which attacks are possible against raw/textbook elliptic curve? A quick question, we know that raw RSA is a no go. To solve this we have different PKCS standards forcing structure on the input messages.

For EC the story is something else. For signatures we have ECDSA, for general encryption we have ECIES (hybrid) and ElGamal encryption. Or ECDH for key agreement

None of those schemes define any formatting, does that mean that there a no know attacks against the raw schemes? Just compute the output and incorporate the raw binary into our network protocol?

None of those schemes define any formatting

You don't needs any input formatting for ECDSA, you just feed your plaintext into the hash function.
You only need a formatting if you want to exchange public keys and / or private keys (I'll count "with yourself" in the future as exchange here).
As far as ECIES goes, the situation is a bit more complicated. There are standards defining formats for ECIES (so you can decide how the payload was encrypted for example), but they haven't seen wide adoption (may be due to the pay walls) yet. Refer to this paper for a comparison of the standards.
EC-ElGamal isn't widely used and it's already hard to find good standards to achieve IND-CCA2 security with (EC-)ElGamal. I'd strongly recommend against using (EC-)ElGamal unless you need the homomorphic property.

  Does that mean that there a no know attacks against the raw schemes?

These schemes are different from RSA in that they are fairly "recent" and people already learned how to describe schemes when defining them, whereas the issue with RSA is that it's "just a modular exponentiation with the right exponents", these schemes are comparable in detail of specification to PKCS#1 (i.e. RSA-OAEP and RSA-PSS).

As for the security:

ECIES is a secure public key encryption scheme (IND-CCA2) assuming the hash can be modeled as a random oracle(RM) and the elliptic curve computational diffie-hellman(ECCDH) problem holds
ECDSA is a secure signature scheme (existentially unforgeable under chosen message attacks (EUF-CMA)) assuming the EC discrete logarithm problem (ECDLP) holds
ECDH is a secure key agreement scheme (provided that you authenticate the exchange and that you hash the derived point) assuming ECDDH (EC decisional DH) (or ECCDH + RM-Hash) holds.
EC-ElGamal is a somewhat secure public key encryption scheme (IND-CPA and maybe IND-CCA1, but not IND-CCA2) assuming that ECDDH holds

See our canonical "IND-" question for the basic notions.


How to identify the difference between two cryptographic schemes in terms of security? I am currently working on a project, that requires using encryption libraries namely (LibScarab and FHEW). I want to know how can I compare the two schemes in terms of security (I already compared between them in terms of execution time). All I know that LibScarab uses SV scheme, while FHEW uses LWE scheme. Can I get help in how to bring comparisons between two schemes to decide which one is more secure?

Security of the Smart-Vercauteren scheme is based on the Short Generator Principal Ideal Problem (SG-PIP), whilst FHEW is based on (ring)-LWE. There have recently been several attacks on SG-PIP that are much faster than the best known LWE attacks, so it would seem that FHEW currently has stronger security foundations.

In particular, Cramer, Ducas, Peikert and Regev described a subexponential attack that solves SG-PIP in $O(2^{n^{2/3 + \varepsilon}})$ time.

http://eprint.iacr.org/2015/313.pdf

I don't know whether LibScarab takes this attack into account, but I suspect at least the original SV parameters are much weaker than first suggested.

There are also polynomial time quantum attacks on SG-PIP that are referenced in that work, whereas there are currently no known efficient quantum algorithms for (ring)-LWE.


How does the probabilty for universal hashing work out? Hey for universal hashing we say the following:
Definition:
A randomized algorithm $H$ for constructing hash functions $h\colon U \to \{1,\ldots,M\}$
is universal if for all $x \neq y$ in $U$, we have
$\Pr_{h\gets H} [h(x) = h(y)] \leq 1/M$
I actually just can´t understand how the probability can be $1/M$ in any case. I alway try to think about any random function mod M as example and compare it with rolling a dice, but with a dice we have for every instance a probabilty of 1/6 as we have 1/M for mod M. But when I roll a dice two times after I have at least $\frac{1}{6}^2$ but saying we have binomial probabilty it looks even worse thinking that the dice would be thrown y times.
Can you help me understand how 1/m could be reached within this context?

Actualy chance of 2 dice throws to have the same value is 1\6, not 1\36. And definition also compares 2 values.
What you are asking is called https://en.wikipedia.org/wiki/Birthday_problem and it is still present even with universal hashing. Or dice throws. If more than 2 are compared.


What are the computational benefits of primes close to the power of 2? Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$.

What I missed or was unable to understand is what are the particular benefits of using a prime close to the power of 2. How does this for example help practically doing the reduction modulo $q$ of some number?

After a multiplication you have a number with $2 \cdot 255$ bits. Since $2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than $20 \cdot 2^{255}$. Repeat this to get a number that's smaller than $2 \cdot q$. Now check if the value is greater or equal to $q$ and subtract $q$.

Being close to a power-of-two matters in the first step. Since 19 is so small, the number after the first reduction step is only a few bits bigger than $q$.

If to the power-of-two the difference were bigger, the resulting number would be bigger and you'd need more steps to reduce it. If you have a random prime, the result is barely smaller than the input and you're better off with a different algorithm (such as montgomery reduction).


Interpolation Attack The example of two round iterated cipher(each round is cubic function) here shows polynomial after two rounds with 9 terms.

however if we find the polynomial for two rounds, it has 22 terms

one clue i have is, the difference in number of terms may be because of underlying mathematics difference, (use of finite field in case of 9 terms, so similar terms getting cancelled out instead of being add up)

and is there some formula to just find the number of terms in expansion, like explain here

As in the first equation one has $(x+k_1)^3 = (x^2+k_1^2)(x+k_1)$, i.e., $(x+k_1)^2 = x^2+k_1^2$ I'd conclude that the equation is over characteristic $2$.

This explains why all the terms with even coefficients are missing and why all odd coefficients are replaced by $1$.

The only remaining mystery is what happened to $3k_1^6k_2$ rsp. $k_1^6k_2$. Typo?


Is Mathematics or Computer Science more important for a career in cryptography I'm a Mathematics Major, and I currently enjoy the mathematical aspects of cryptography. I intend to pursue a career in cryptography research.

https://www.csit.gov.sg/join-us/job-opportunities/job-detail/cryptologist

However, although I'm comfortable with the mathematical aspects of it, I lack sufficient training in computer science and computer programming. Therefore, I'm trying to pick up programming and computer science skills at the moment. Are programming skills/computer science important for cryptography? (With respect to the job listed above)

And if so, which computer science topics are most relevant to cryptography? Are topics in data structures necessary for cryptography research? And lastly, how good do my programming skills need to be in order to pursue a career in cryptography? (Such as in the job listed above)

This question can be closed because the answers are opinion based. Nevertheless...

It depends. It does not look like they are going to design essentially new algorithms for encryption, signature, voting, etc. They have focus rather on applied aspects. In particular, they expect you to study and evaluate cryptographic algorithms and protocols of specific hardware and software. To be able to do that you definitely need skills in computer science.

Why are you asking about data structures particularly? It is a small topic compared to the others. Yes you should learn it, not because of this job, but because otherwise you will not be able to program.

To your questions: Yes, programming skills are important for this type of job.

Which topics are relevant? For this job following topics seem to be relevant:

Cryptography (of course)
Number theory
Programming
Software Architecture
Computer security
Networking


AES-GCM cipher tag and IV size, while attempting to render encrypted ciphertext useless by removing them I'm using AES in GCM mode of operation for encryption/decryption & authentication of segments of data in a file. The layout of each segment can be summerized by this diagram. Each segment is basically (enc-)decrypted separately from one another, using their individual (randomly generated) IV and Tag:

The encryption process of such segment is done as follows:

While decryption & auth would be carried out as such:

So let me explain my dilemma.

I'm trying to optimize the situation when one of those segments (pictured above) is deleted. The head-on approach would be to zero it out on disk. But, for the purpose of optimization, I was thinking to delete only its IV and Tag, thus hoping to make decryption of that segment's data computationally infeasible. But this brings up two points:

IV size of 12 bytes seems kinda low for that. I know that that is the default size of the IV for AES-GCM. But would I benefit in this scenario if I increase the IV size to 32 bytes? So that way if I remove a 256-bit IV, will it render the encrypted data "safe to discard"?
Tag itself. Is it used for decryption or just for authentication? In other words if I clear it out for my purpose of discarding the encrypted data, will it even matter. I was playing with the actual function that does AES-GCM decryption (implemented using Crypto++ function named CryptoPP::GCM<CryptoPP::AES>::Decryption::DecryptAndVerify()) and it seems to return different plaintext if I alter the tag, but I'm not 100% sure about it.

But, for the purpose of optimization, I was thinking to delete only its IV and Tag, thus hoping to make decryption of that segment's data computationally infeasible.

Neither work.  The IV might seem to work (as doing a brute force search over a space of size $2^{96}$ might appear to be daunting), however the attacker has another potential approach.

If an attacker has the ciphertext, has a correct guess to 16 bytes of the plaintext, and the key, he can recover the IV; from there, he can recover the rest of the plaintext.

Because of the likelihood of the attacker guessing 16 bytes of plaintext, this wouldn't appear to be feasible.

And, the tag is even worse (and so is the AAD, in case that occurs to you); an attacker with the key, iv and ciphertext can trivially decrypt the ciphertext without the tag.  He might not be certain that the ciphertext hasn't been modified; however he might be willing to assume that it wasn't.

Since I gave you two negative answers, lets give you a positive idea; why don't you make the key generation procedure:

key :=SHA2( master key || extra data )

Where the extra data is stored on in the segment header (and nowhere else); it is generated randomly when you first encrypt; when you decide to do a quick erasure, you overwrite it. The master key is the one derived from the password with PBKDF2.

If this extra data is at least 256 bits long, recovering the key is no easier than attacking AES-256 directly.


Showing the decrypted sum of encrypted values Is there a system that would allow to encrypt values with one or more keys, sum the encrypted values, and reveal a key which could only decrypt the sum.

Essentially would be able to show encrypted values where anyone could verify the sum by adding all of the encrypted values, then decrypting it.

There is a recent line of work that does exactly this; it is called functional encryption for inner-product. It allows to encrypt a vector of integers (from some exponent space $\mathbb{Z}_p$) so that one can generate secret keys that do only allow to decrypt a given inner product between the components of any such encrypted vector.

There is a simple construction under DDH, and under LWE. The construction from the Paillier cryptosysem is way more involved and was presented at the CRYPTO conference in august this year.

For the DDH-based variant, the intuition is simple: encrypt your vector with different keys, but the same random coin each time (id est: $E((m_1, \cdots, m_n);r) = (g^r, h^r_1g^{m_1}, \cdots, h^r_ng^{m_n})$, where $g$ is a generator of some group where DDH is hard, and each $h_i$ is $g^{s_i}$ for some secret key $s_i$). The secret key to decrypt an inner product with $a_1, \cdots, a_n$ is just $\sum_i s_i a_i$.

Here is the original article: http://eprint.iacr.org/2015/017. If you want to look into the more advanced constructions, I suggest looking the papers that cite this one.

EDIT: I forgot to mention, the DDH-based instantiation has the same drawback that the additive variant of ElGamal it relies on, which is that a discrete logarithm must be performed on $g^{\sum_i a_i m_i}$ at the end, so it works only when $\sum_i a_im_i$ remains small (say, less than $2^{30}$). If the messages can be large, then the LWE-based or the Paillier-based instantiations must be used.


Asymmetric encryption that is secure for (almost) any foreseeable future Recently, I've been reading a couple of papers about building cryptosystems that are secure for up to 30 years. But for some applications, this seems a bit low to me. So I am wondering if considering the current state of the art in cryptography and computing power evolution forecasts, one could instead build a public-key encryption system, running on today's consumer hardware, which is secure for any foreseeable future.

Of course, written like this, the problem is too broad, so my specific criteria are as follows:

Keys are permanent, ciphertext which has been encrypted today must remain secure
Security is broken if an attacker can reliably decipher text which has been encrypted with the public key, without possessing the private key
Scenarios in which the attacker gets a hold of the private key by stealing, torture, and other means of extracting it from the rightful owner, are not considered a breach of security
My (very generous) upper bound for performance forecast realism is 1000 years in the future
I personally do not consider general-purpose quantum computers, based on logic gates operating on a large number of entangled qubits, to be viable in any foreseeable future, so security against them is just a nice extra
More specialized quantum computing systems like D-wave's quantum annealing, however, which do not rely on many-particle entanglement, are within the realm of possibilities
Attacker may be considered to have access to exabytes of ciphertext and terabytes of plain text - ciphertext pairs
Attacker may have access to state-of-the-art computing power, like the supercomputers of his generation
It must be possible to transfer public keys over the Internet within a reasonable time (absolute maximum is 1 day on a low-end 30 kB/s Internet connection -> 2GB), but they do not need to be transmitted frequently so it is acceptable if the keys are unusually big
Encryption must be fast on today's hardware, let's say 30 MB/s on a high-end laptop as a lower performance bound

Is this totally crazy, or can it be done using today's knowledge in cryptographic algorithms + implementations which are either available today or can be made available in the near future?

I think that there is no chance of getting such an asymmetric cipher simply because you forgot about science.

The security on todays asymmetric cryptography is mostly based on the assumption that some mathematical algorithms cannot be reversed (e.g. the discrete logarithm or integer factorization).

If mathematics solves this problems then the algorithm is broken.

Such a breakthrough in mathematics can occur (e.g. for Fermat's Last Theorem in 1994).

So the major problem with assuring asymmetric cryptography as secure is to assure that no such breakthrough will occur.


Does perfect secrecy imply uniform ciphertext distribution? I suspect the answer is no, but I am not able to either prove it, or provide an example. In Katz and Lindell's book, it is only said that with a perfectly secret encryption scheme, the plain and ciphertext distributions are independent. But when I try to construct an example with a non-uniform ciphertext distribution, (using say, 4 plaintexts as a message space), I cannot devise a plaintext and key distribution such that the resulting ciphertext distribution is not uniform.

What I am getting wrong? (or can anyone provide such an example?)

For a nonuniform construction with perfect secrecy, consider this scheme, with 2 bits of plaintext $(b_1, b_0)$, and four bits of key $(k_3, k_2, k_1, k_0)$.

The ciphertext consists of the three bits:
$$(k_3 \land k_2) \oplus b_0 \oplus k_0$$
$$b_1 \oplus k_1$$
$$b_0 \oplus k_0$$

This has perfect secrecy, in that for each ciphertexts, there is the same number of keys that map to any particular plaintext.  For example, for the ciphertext $(0,0,0)$, there are three keys that it to any plaintext, say, the plaintext $(1,0)$

This is nonuniform; as for random keys, the ciphertext $(0,0,0)$ will occur with probability three times that the ciphertext $(0,0,1)$ occurs at.


Leakage in Secure Two party Computation Am trying to understand Garbled Circuit based approach for Secure Two party Computation. There isn't much leakage in the classic millionaire's problem where the comparison circuit is used.

But imagine they want to do some arithmetic operation (like addition or multiplication) without revealing their individual wealth.

Then although each of them need not reveal their individual wealth using Garbled Circuits approach (by running the protocol with an addition circuit),  the sum total of their wealth would easily reveal the other millionaire's wealth (By doing simple difference of the total wealth and self wealth)

So is secure two party computation recommended only for a class of circuits ?

Secure multiparty computation guarantees the nothing whatsoever is revealed by the process of computation. It does not say anything about the function. As you correctly point out, there are some functions that reveal a lot and shouldn't be computed, but this analysis is quite out of the scope of secure computation. The question of whether it's "recommended" depends on the application and the choices you may or may not have. You may, for example, want to use secure computation to compute a differentially private version of the function.


AES-CBC authentication and password validation Let's say, Alice uses AES256-CBC to encrypt some data. The key for encryption is derived using PBKDF2, where password is some passphrase Alice and Bob agreed on (using DH) and salt is random generated (using /dev/urandom for now)*. The IV for the CBC is generated the same way as the salt.

Now Bob receives the cipher and would like to authenticate it, so he can tell for sure, that the message really came from Alice (or anyone else who knows the passphrase). Should Alice encrypt the data first, use the derived key as password, the cipher as message and append/prepend the result to the cipher?
Or she ought to use the derived key as password, the plain text as message, prepend the HMAC to the plain text and encrypt?
(There is a lot of related questions and answers, I am just confused what to use when and what are the pros and cons)

Another problem I'm struggling with is, how will Bob get the IV and the salt which were randomly generated at encryption time?

Last problem I'm trying to solve is, when Bob will decrypt the cipher, how can he know the password he entered is correct, without decrypting all of the data?

*Is /dev/urandom secure enough to generate random salt and IV?

Just to clarify, I don't intend to use this implementation in real world situation, this is purely for educational purpose

Now Bob receives the cipher and would like to authenticate it, so he can tell for sure, that the message really came from Alice (or anyone else who knows the passphrase).

Bob should be using an AEAD mode of AES, full-stop. GCM is the go-to candidate for this, rolling your own CBC+HMAC mode is also possible, but should be used as a last resort and only if you emphatically know what you're doing.

  Another problem I'm struggling with is, how will Bob get the IV and the salt which were randomly generated at encryption time?

IVs and salts are not secret. Send them with the ciphertext.

Besides your direct question, it looks like you're trying to wire together your own transport encryption protocol. I strongly recommend you just use TLS instead. Barring that, I'd recommend using libsodium's out-of-the-box AEAD modes instead of rolling your own.


Is openssl library safe threaded? I'm encrypting in C++ with openssl library.

Basically I'm using these functions:

RAND_bytes(key, 32);
AES_set_encrypt_key(...)
AES_ctr128_encrypt(...)

My purpose is to encrypt parallelly with different threads. Obviously, every encryption/decryption will be on completely different objects.
Does these functions thread safe? If not, is there anything except mutex that can help? (mutex will awfully damage my systems' performance). Thanks!

OpenSSL is not threadsafe by default:

  OpenSSL currently is thread-NOT-safe by default. In order to make it
  thread-safe the caller has to provide various callbacks for locking,
  atomic integer addition, and thread ID determination (this last has
  reasonable defaults). This makes it difficult to use OpenSSL from
  multiple distinct objects in one multi-threaded process: one of them
  had better provide these callbacks, but only one of them should.

  Currently the only moderately safe way for libraries using OpenSSL to
  handle thread safety is to do the following as early as possible,
  possible in .init or DllMain:

  Check if the locking callback has been set, then set it if not;
  CRYPTO_w_lock(CRYPTO_LOCK_DYNLOCK), set the remaining callbacks (threadid, dynlock, and add_lock) if not already set, then CRYPTO_w_unlock(CRYPTO_LOCK_DYNLOCK);

  In the future we hope that OpenSSL will self-initialize thread-safely
  to use native threading where availab


Cryptanalysis of a feedback shift reigister with an S-box I’m just getting started on learning cryptography and here is a problem from exercises about which I'm totally confused:

This is a 32-bit feedback shift register to encrypt some message. The register shifts circularly by 4 bits. Before each shift the S-box takes the last 4 bits and feeds the 4-bit output back into the four bits just next to them (as shown above). This cryptosystem is keyed by the contents of the S-box. The questions are:

  If the S-box is not invertible, how many bits of information does it contain? And what if the S-box is invertible but entries selected randomly without replacement?

So what I'm confused about is: why is this cryptosystem "keyed by the contents of the S-box"? How to decrypt the ciphertext if we know the S-box (and times the register shifted if necessary)? And what does "information contained by the S-box" mean? How does the invertibility of the S-box affect the bits of information it contains?

I know that the initial value of an FSR is called the "seed" and from that the register can generate some pseudorandom keys to be used in some cryptosystems. But in this problem it seems that the seed itself is the plaintext to be encrypted and the ciphertext is one of its successors. Also, I know an S-box is used to perform substitution but I've never heard something about "the information it contains".

Hope that I've described this problem clearly.
Thank you guys in advance :)

why is this cryptosystem "keyed by the contents of the S-box" ?

It means that the content of the S-box is assumed secret, and part of the key (in addition to whatever part of the initial state is not a given).

  How to decrypt the ciphertext if we know the S-box ?

My reading is that what's shown is the keystream generator of a stream cipher, that gets combined by XOR with the plaintext outside of the drawing. We have to guess that, as in a Fibonnaci LFSR, the keystream is what's output on the right, so that the first 32 bits of the keystream are the initial state per some untold convention on bit order, likely the same as in reference material by the same author on Fibonnaci LFSR.

To decipher, the legitimate user would need to know the initial state, and repeatedly extract the right 4 bits and do three independent things with these:

XOR these with 4 bits of ciphertext to decipher 4 bits of plaintext
push these (not the ciphertext nor plaintext) on the left of the LFSR, removing them from the right
feed these in the S-box, and get 4 S-box output bits, that must be combined with XOR into the 4 bits that the above shift has moved on the right of the LFSR, and that the next step will extract.

  What does "information contained by the S-box" mean ?

That means the effective key length that the S-box represents, equivalently the entropy¹ necessary for coding an S-box (that is fully describing the input to output dunction that it implements). If there is a total of $s$ possible distinguishable S-boxes of equal probability, that's $\log_2(s)$.

  How does the invertibility of the S-box affect the bits of information it contains?

Invertibility of an S-box means that no two distinct combination of the $i$ input bits yield the same combination of the $b$ output bits. By the pigeonhole principle it implies $i\le b$ (this is the case here: we have $i=b=4$). This invertibility restricts the number of S-boxes, thus $s$ changes.

¹ If we knew how the keys are turned into an S-box (which is not the case here), we could compute the probability $p_j$ of each distinguishable S-box, and the Shannon entropy could be computed as
$$\displaystyle-\sum_{j\text{ with }p_j>0}p_j\,\log_2(p_j)$$


Symmetric key validity hypothesis? Can I use something like Shannon entropy to determine the suitability of a symmetric key? I found a symmetric key which wasn't generated using a CSPRNG and it had a very low Shannon entropy.
I ran an experiment on 1 million keys from a CSPRNG having a Shannon entropy of at least x where all the weak symmetric keys I found had a Shannon entropy of less than x. I don't think the value of x here particular important here but I was wondering if it would be reasonable to reject symmetric keys that don't meet this requirement. Basically as a countermeasure for bad configuration.

Per my understanding of these comments, the question's test takes $\ell=64$ bytes from a Windows RNGCryptoServiceProvider, makes it $n=2\ell=128$ groups of $b=4$ bits, counts the number $n_i$ of groups with each of the $2^b=16$ bit patterns $i$, computes $p_i=n_i/n$, and for a limit $x=0.9$ checks
$$x\le-\frac1b\sum_{p_i\ne0}p_\,\log_2\left(p_i\right)$$
The question's test should only fail very rarely. The probability that it does even once in one million tests (as reported) seems to be less than $0.2\%$ according to my simulation: I have seen $25$ events for $18\times10^9$ samples tested. Something is at odds, independently of what follows.

The test is inspired by the formula for Shannon entropy per bit of a source of $b$-bit independent values of known probability $p_i$, but here we do not compute a Shannon entropy, because we are operating on a sample, not on the source, and Shannon entropy is not defined for a sample. The $p_i$ are experimental frequency, not a probability for the source. I can't see how this formula can be justified.
Update: I have asked about that test there, and got a detailed answer. It turns out to be known as the G-test or Woolf's log likelihood ratio test, and a sound alternative to Pearson's $\chi^2$ test.

Can I use something like Shannon entropy to determine the suitability of a symmetric key?

If the source was known for certain to be from a construction aiming at being a CSPRNG, no. Tests on such output can only give a fallacious insurance of security, or detect gross errors. The correct method is to scrutinize the specification and if possible the implementation of the CSPRNG.
But that's not what the question is about.

I am worried that employing such a filter to protect against human error may in turn create a security risk.

It does not in practice. The two following nitpicks are theoretical only:

Restricting to keys that pass the test obviously reduces the keyspace to some (imperceptible) degree.
Performing the test may leak information about the key, if side channel attacks are an issue. However, if they are, that's the problem, not the test.

I do have serious reservations on trusting that test to catch a bad CSPRNG:

The most common issue with CSPRNGs is improper seeding, and the test won't catch it.
More generally it is demonstrably impossible to prove or even meaningfully confirm the quality of a CSPRNG from its output: we can make CSPRNGs that pass any pre-existing test, yet are extremely weak for who knows their internals.

Independently, as already stated, if only a million tests have reported a fail (and the key is 64 bytes as stated), that's most likely an anomaly. It could be in the test, or in how the generator is used, or in the assumptions on what the generator is designed to output, rather than in the generator itself.

A poorly chosen key was installed into the system by mistake

The test indeed has some chance to catch some forms of that, and if the small false-positive rate (much less than one in 100 million keys if I get it correctly) is tolerable, why not? However, attempts to detect errors from the value of the key itself are bound to be unreliable. For example, the test won't catch a favorite test key for DES, 0123456789ABCDEF, repeated.
A preferable practice is to have procedures that prevent such mistakes. Like, transmitting keys using dedicated devices, or data blobs with integrity protection, or as a last resort well-thought Key Check Values.


Costs of operations in elliptic curves explanation I'm trying to understand the cost of operation in elliptic curve (only Weierstrass curve for simplicity) from Wikipedia and there seems to be lack of online information/papers regarding this. I understand the concepts of EC, EDSA, point addition, multiplication, inverse and doubling.

My question is: what does the values of the table represent?

Why aren't the units in seconds?

Why does ADD have more operation, I thought they were the "cheapest"?

If someone could provide a sort of overview, it would be much appreciated.

Per poncho's comment: the values given in the linked table are the number of multiplication or squaring operations in the finite field on which the Elliptic Curve is defined (which could for example be $\mathbb Z_p$ for some prime $p$); the cost of other operations in this field is either ignored as marginal (addition, subtraction, multiplication by a small integer constant) or absent (field inversion, which if present would account for 100).

The units are not in second, because counting field operations allows independence from both the speed of the hardware used, and the size parameter of the field (like $p$), which would influence the result in second. Know the duration of multiplication in your field using your device, multiply by the integer in the table, and you have some approximation of the duration for a sequential implementation.

ADD usually has more operations than DBL, because point addition on an Elliptic Curve usually turns out to be more computationally intensive than point doubling (as pointed by CurveEnthusiast in comment, that's not absolute): the later can be viewed as a special case of the former where the two inputs are equal, which allows a shortcut (or rather, requires it). As a crude analogy, it is slightly harder to compute $124865+138747$ than it is to compute $2\cdot124865$; for a start, there's more input.


Filter party-1 strings against party-2 white/black list keeping the lists private Suppose I have a server and a client. The client has a list of arbitrary strings and the server is supposed to filter this list using white and black lists kept on the server side. It would be nice not to share the list of the strings to the server and the white/black lists to the client. For example, a list of open applications at the client side is sensitive data, and the white/black lists are not supposed to be exposed from the server to the outer world as well. I'm wondering whether it's possible to check the client strings against the white/black lists keeping them private at all parties. The only way I can see now is:

Client: split the list of strings to a list of split-by-whitespaces strings list and hash each element.
Server: do the same for the white and black lists.
Server: compare the client and the server hashes.

This solution has a lot of downsides. Is it possible to re-implement it in other way somehow? Or, is the idea feasible at all? Thank you.

I see two problems;

The number of keywords is very small and a dictionary attack is possible from the server.

for i in English_Dictionary
    if Hash(i) == target_hash
       return success

Also, one can use Rainbow tables, too. To overcome these, you will need to add salt to your plaintext to prevent any dictionary or rainbow attacks from the server side.

There are more advanced methods for protection, as;

The search on encrypted data which is started with the Song et. al's
idea.
There is another method, which may be too slow, use FHE
techniques. You can totally blind the server.
If the client asking whether this string is black or white, you can also use Private Information Retrieval (PIR) techniques. There is an FHE PIR implementation.

Also, the frequency of the hit may leak information 1,2. The frequency attack really depends on the application. The method listed above, not the salt, can overcome the frequency attack, too.


Is there short period in AES 128 key schedule? I am wondering if for some particular keys the AES 128 key schedule lead to a periodic pattern for the round keys.
The key schedule is only 10 rounds, but I am also wondering in the general case where we expand the key much more, as it happens if one use the last round key of an operation as the key for the next operation (definitely not a standard use of AES, but of some interest on small devices with on-the-fly key schedule).

During each round of the AES key schedule, they stir in an 'rcon' value.  This constant differs for each round, and so even if the state of the key schedule just happened to be exactly the same in, say, rounds 2 and 5, the differing rcon values would mean that the keys during round 3 and 6 would differ.  Hence, the AES 128 key schedule is nonperiodic.

So, if you take the last subkey, and reuse it as the key for the next block, the only way you can come up with a repeating pattern is to generate the same AES 128 key.  Since that's the normal way to use AES, that's not a problem.

On the other hand, doing what you propose would mean that the AES keys you use are related; that the subkey for the last round is exactly the same as the first subkey for the next block.  Now, AES-128 is not known to be vulnerable to related key attacks, and the related keys for the known AES-192 and AES-256 vulnerabilities are considerably different; however it does bear wondering whether this is something that you should trust.


Non-repudiation and digital signature of a dishonest participant Let's assume a dishonest Alice who sends, encrypts & digitally signs a message to Bob.

Bob stores the decrypted message and the digital signature in a database.

However, Alice is a bad girl and erases all data from her side, including her private/public keys. She then claims she never sent the message.

Is there a solution to this case?

In my case, Alice uses a communication tool that Bob has provided, where the private/public keys are generated within the context of the tool (with no 'public key' advertised anywhere else, hence making it even more difficult to prove anything).

Yes, the solution is that her public key needs to be stored in a place that is and will be accessible to Bob.

(such as in Bob's database)

I had not realized that importance of that before reading your question.


Anything known about this variation of Diffie-Hellman key exchange protocol? I'm considering a variation of the Diffie-Hellman key exchange protocol based on integer modular multiplication in place of exponentiation. If done naively, that would obviously be insecure, but I'm wondering if it is possible to recover security by erasing the least significant bits before transmitting a product. The idea is inspired by RLWE, where introducing random errors can transform a trivially insecure protocol into a possibly secure (maybe even quantum-proof) one; only here instead of addition of random errors I'm proposing deterministic erasure of the lower part of the data.

Here are the details: Let $n \in \mathbb N$ be fixed (say $n=1024$), and let $M=2^{3n} -1$. We will use the notation $x \bmod M$ to denote the unique integer $y$ in $0, 1, \dots, M-1$ with $x \equiv y \pmod M$.

Alice and Bob begin with a shared public value $g \in \mathbb N$ with $0 \leq g < M$. (Whoever initiates the protocol should choose $g$ uniformly at random and send it to the other party.)
Alice chooses a secret integer $0 \leq s_1 < 2^n$ uniformly at random,  computes $x_1 = gs_1 \bmod M$, rounds $x_1$ to a nearest multiple of $2^n$, and sends the result $\tilde x_1$ to Bob.
Bob chooses a secret integer $0 \leq s_2 < 2^n$ uniformly at random, computes $x_2 = gs_2 \bmod M$, rounds $x_2$ to a nearest multiple of $2^n$, and sends the result $\tilde x_2$ to Alice.
Alice computes $y_1 = \tilde x_2 s_1 \bmod M$, rounds $y_1$ to a nearest multiple of $2^{2n}$, and stores the result $\tilde y_1$.
Bob computes $y_2 = \tilde x_1 s_2 \bmod M$, rounds $y_2$ to a nearest multiple of $2^{2n}$, and stores the result $\tilde y_2$.

It can be shown that $\left\lfloor \frac{\tilde y_1}{2^{2n}}\right\rfloor$ and $\left\lfloor \frac{\tilde y_2}{2^{2n}}\right\rfloor$ differ by at most 1 (modulo $2^n$), and from this Alice and Bob can easily agree on a secret key of length $n-1$.

I'm wondering if anything is known about the security of this protocol? Has anything been published about this sort of technique, or is there some obvious attack that breaks it?

The most straightforward avenue for an adversary to break it would seem to be if they had some way where, given integers $g$ and $\tilde x$ in the interval $[0, M)$ they could find $s$ with $0 \leq s \leq 2^n$ such that the most significant $2n$ bits of $gs \bmod M$ agrees with $\tilde x$ (assuming that such $s$ exists, which it will if $\tilde x$ was produced as one of the $\tilde x_i$ in the protocol). Here the restriction $0 \leq s \leq 2^n$ is the part that is intended to make it hard; it would be easy for anyone to find an $s$ in $[0, M)$ such that $gs \equiv \tilde x \pmod M$, but that would not appear to be sufficient to succeed in an attack.

Edit: We run into trouble if $g$ or $s_i$ happen to share a large divisor with $M$. To fix this, we could replace $M$ with a prime number (say, the largest prime less than $2^{3n}$) or restrict $g$ and $s_i$ to be relatively prime to $M$.

... instead of addition of random errors I'm proposing deterministic erasure of the lower part of the data.

Truncation instead of addition of noise is an optimization that some LWE schemes use already.

  ... I'm wondering if anything is known about the security of this protocol? Has anything been published about this sort of technique, or is there some obvious attack that breaks it?

The more pertinent difference in your proposal is that it uses a one dimensional vector. There does exist a dimension/modulus size tradeoff for the LWE problem. But the problem is very sensitive to the concrete parameters that you instantiate it with.

An obvious algebraic attack might not be able to solve the problem, but you might be surprised at what the LLL algorithm can do. Understanding how to use LLL to actually do so is challenging. There are lots of papers about it.


Why don't we use MACs to store passwords? These days, the best practice for storing passwords is to use a scheme like scrypt or bcrypt. The goal of these schemes is to make dictionary attack inefficient for an attacker but it also slows down legitimate use of the function.

If you're doing thousands of password checks per second, there is a real world cost of this slow down.

I'm wondering why we can't simply use a MAC? You choose a random salt, $s$, for each password you want to store. You then compute: $MAC(s || password, k)$ and stores the result and the salt.

This construction operates quickly and seems to me to have superior security properties to scrypt and bcrypt. The only draw back is that we now have to securely store $k$. This limits its usefulness in some contexts but not in others.

For password based file encryption, this scheme wouldn't be suitable but for storing passwords for a website, we can use a HSM device to keep the attacker from getting $k$.

Yet I've never seen any advice that suggest we store passwords in this way. Why is this?

As K.G. and nightcracker note, the reason we don't recommend this method of password storage is that it becomes insecure if the secret $k$ is compromised.  Given that the whole point of password hashing is to protect the passwords in the event that your server is compromised, it's generally not safe to assume that the compromise won't include the secret key $k$.

That said, obviously the safest thing to do would be to use both a key-stretching KDF (like PBKDF2, bcrypt or scrypt) and a secret key, e.g. as:

$$\rm hash = KDF( MAC( password, key ), salt ) $$

or simply as:

$$\rm hash = KDF( password \,||\, key,salt ) $$

where $\rm key$ is a secret key, $\rm salt$ is a unique per-user salt, and $\rm KDF$ is a slow key-derivation function suitable for password hashing.


Derandomized version of RSA-OAEP We know a standard way (cf. RFC 6979) to derandomize ECDSA signatures, i.e., to generate ECDSA signature without an external source of randomness.

Is there any similar standard way, or academic-proof way, to derandomize RSA-OAEP encryption?

Derandomization for asymmetric encryption is a bad idea. Main reason for that is that if an asymmetric encryption mechanism is deterministic, then it allows a brute force attack on the plaintext: the attacker tries possible plaintext messages and encrypts them, and tries to see if it yields the same encrypted message as the one which was observed. Real-world plaintexts usually have much less entropy than cryptographic keys.

Some extra notes:

You could use asymmetric encryption only to convey a fully random symmetric key, in which case brute force on the key is not feasible. But then, this means that you have a random source at hand, so OAEP should not be an issue.
You could imagine a deterministic process that feeds on an extra secret value, thus not reproducible by attackers. But then, this would not really be "derandomization"; that process and the source secret value would better be described as a custom PRNG, i.e. you are just using normal RSA-OAEP.


Hash function based on pseudorandom functions and security Are there hash functions that make use of pseudorandom functions. Precisely, I'm looking for a specification of a hash function based on PRF (and based on the security of such a primitive).

Note that a PRP is a PRF for a large enough block size. Hash functions based on block ciphers will probably be of interest to you.

There are some general schemes for using block ciphers to build hash functions. You may want to investigate them and what requirements they have for the underlying block cipher. Unfortunately, the PRP model is a weak requirement for a block cipher, schemes that use block ciphers often use stronger assumptions (like the MDC-2 hash is built on block ciphers by using the Ideal Cipher model).

For a modern example, the popular SHA-3 hash contestant Skein is based on the block cipher Threefish. You could investigate if/what PRF or PRP models are used in the analysis of Skein and Threefish.