A private key with multiple public keys? I'm trying to design a wallet, where any number of public keys can be handed out. Say Alice hands out the public keys to receive messages. She doesn't want others to be able to link all of the public keys to the same person. They should each look random, so that giving out N public keys causes a bystander to believe that there are N different people.

I know that this can be done by having a master private key $p_0$, and generate future private keys with something like $p_{i+1} = \text{Hash}(p_i, p_0)$. However, in order to decrypt the message, Alice would have to try every single private key. I'm doing this in a browser and JS Tests with ECC appear to show that it's a bit slow for a UI once you have a dozen or so keys, but doable if Alice can wait a second (Though not ideal). If you're trying to decrypt dozens of messages at a time, this quickly becomes impossible with too many private keys. And at least in my case, I will have to try to decrypt many messages.

What I really want, is to simply have one private key, and any number of desired public keys. Most cryptosystems have specific key-pairs. And while you can simply concatenate a group's Public Keys to get N Private Keys : 1 Public Key (Decryption requiring every individual), there doesn't appear to be well-known algorithm for 1 Private Key : N Public Keys.

The examples mentioned here did not help, because they are all too slow if decryption requires an ECC multiplication.

==

QA Format: I expected to find a solution on this SE, since it didn't seem like a complicated question, but couldn't. Anyway, I'm posing it here to help others / for those who are interested since I thought it was fairly neat.

Here's an idea:

Alice's private key is an AES key $k$, which Alice picks randomly.  Yes, we're using an AES key as a private key; bear with me a moment...
To generate a new public key, Alice picks a random value $r$, and generates the pair $(\text{AES}_k(r), rG)$, which she publishes, and which I will refer to as $(b, H)$.  Alice can optionally forget the value $r$ she picked.  Alice can generate and publish as many public keys as she needs...
To encrypt a message $m$ with this public key $(b, H)$, Bob selects a random value $s$, computes the point $sG$ and the AES key $KDF(sH)$, and outputs the triplet $(b, sG, \text{AES}_{KDF(sH)}(m))$
To decrypt $(b, sG, \text{AES}_{KDF(sH)}(m))$, Alice first decrypts $\text{AES}_k^{-1}(b) = r$, (and if that decryption fails, the message wasn't meant for her).  Then she computes $r(sG) = s(rG) = sH$, computes $KDF(sH)$, and then decrypts $\text{AES}_{KDF(sH)}(m))$, giving her the message $m$.

Two different public keys from Alice are unlinkable, as the only connection is that they contain the encryption of two different values with the same AES key, and that's indistinguishable from random.

And, all operations take time independent of the number of public keys Alice generates...

(Note: you'll use some authenticating encryption mode of AES, such as AES-GCM...)


Why blake2b is the fastest despite it being 512 bits hashing algorithm? I am struggling to understand why blake2b is faster than blake2s, despite that blake2b is 512 bits hashing. I hope someone can clarify that for me. I read the official paper for blake2b, but I am not a very technical guy. I didn't understand much of it.

I am struggling to understand why blake2b is faster than blake2s, despite that blake2b is 512 bits hashing.

Comparing is not easy. They designed

BLAKE2b for 64-bit platforms including NEON enabled ARMs. That can produce between 1 and 64-byte digest

BLAKE2s for 8- to 32-bit platforms. That can produce between 1 and 32-byte digest

They are fast on their target

Each one is portable to any CPU, but can be up twice as fast when used
on the CPU size for which it is optimized; for example, on a Tegra 2 (32-bit ARMv7-based SoC) BLAKE2s is expected to be about twice as fast as BLAKE2b, whereas on an AMD A10-5800K (64-bit, Piledriver microarchitecture), BLAKE2b is expected to be more than 1.5 times as fast as BLAKE2s.

Even BLAKE2b does 12 rounds, and BLAKE2s does 10 rounds it still faster on their platform. And the CPU word size has a huge effect, too.
They modified the original design of BLAKE with the confidence it's security well tested. From the Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition

Keccak received a significant amount of cryptanalysis, although not quite the depth of analysis applied to BLAKE, Grøstl, or Skein

Some of the modifications; BLAKE2b uses 24-bit rotations that use SSS3 and can perform two rotations on parallel. Originally BLAKE was using 25 (now 24) and 11 (now 63) bit rotations. In addition, the 63-bit rotation can be also fastened on some recent Intel CPUs.
AVX and AVX2 (Advanced Vector Extensions) can boost any code whenever applicable. BLAKE2b benefits form AVX/2 whenever available. More detail can be found at BLAKE and 256-bit advanced vector extensions paper.
As having past experience on Cray Vector Machines, I can pretty surely say that if your code is vectorizable, you gain huge speed up.


Use of orthogonal vectors in lattice-based cryptography In lattice-based cryptography, given the basis of the lattice we compute the orthogonal vectors using Gram-Schmidt Orthogonalization process. What is the use of orthogonal vectors in lattices?

Let $\left\{\vec{b}_1,\ldots,\vec{b}_n\right\}$ ba a lattice basis and $\left\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_n\right\}$ be its Gram-Schmidt orthogonolization. Here are some reasons:

It helps computing a reduced basis (an equivalent basis with shorter vectors) using LLL or BKZ algorithm,
The span of $\{\vec{b}_1,\ldots,\vec{b}_i\}$ is equal to the span of $\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_i\}$ for $1\leq i\leq n$,
It helps you finding the volume of the lattice by multiplying the norms of $\hat{\vec{b}}_i$'s rather than computing a determinant.
It provides you upper and lower bounds on successive minimas and smoothing parameter of the lattice.


What is the point of hash = (prime * hash + b) % 100 While looking though some code base I found the function which has no explanation and does something like this (pseudocode)

func something(str, num) { // str is a string, num is a number from 0 to 100
   hash = 0
   prime = 17
   for b in byte_array_of_base64decode(str){
       hash = (prime * hash + b) % 100
   }
   return hash < num
}

There is no explanation what the function suppose to do and the name of it also does not give any clue.

I assume that if this does any useful thing, it has something to do with hashing or sampling. Does anyone know the point of this function?

Distributing objects among buckets of a hash map

This looks like an (old) textbook algorithm for allocating elements in a hash map or hash table. Other than the last line, which doesn't really make sense, it would be used calculate which hash map 'bucket' to use for putting/getting this item, as you need to calculate a simple, cheap and fast (so, generally not a cryptographic hash, but a few multiplications) code that would be an integer in the range from 0 to length of the map backing array (probably 100 in this case) that preferably is different for nonidentical similar objects to reduce the number of collisions.

A textbook example from Algorithms 4th ed by Sedgewick&Wayne, the similarity should be obvious:

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

This has nothing to do with cryptography, though. Nowadays many standard libraries try to use a cryptographically unpredictable algorithm for hashmap hashes to prevent a risk of DoS attacks by data engineered to induce worst case performance, but this example is not one of these.


Is quantum cryptography unbreakable? People always say that "there is no such thing as unbreakable crypto!"

In most cases they are right. AES, RC4, RSA, C25519, DH, .... are all cryptographic algorithms which are crackable (with extreme effort).

The asymmetric stuff, you can factorize; the ciphers you would have to brute force.

But from what I understood, symmetric quantum crypto is kind of uncrackable. It uses quantum mechanics (who would have thought?) to directly send the symmetric key to the other machine. But the sequence changes every read cycle, so if the attacker would sniff the traffic he would have a key other than that which the recipient received, and the recipient would know that the key was tampered with.

So, is quantum cryptography even breakable without physical access to the machine? And if yes, how?

You have to distinguish between "theoretically" and "practically" breakable. Pretty much any cryptosystem can be broken in practice by violating the assumptions that the theoretical security proof uses.
For example, with Quantum Key Distribution and a OTP, you might have theoretical perfect secrecy. However, the proof for such a scheme does not address the possibility of "Wait for them to receive the message and then threaten them to obtain it" - and there is nothing that QKD + OTP or any cryptography can do about to prevent this type of attack. This is because such an attack specifically targets what the security proof of the cryptography does not cover.
So in that sense, when an adversary has such options, achieving "unbreakable" security in practice is not a realistic prospect: In the best case scenario, with theoretically perfect crypto (i.e. QKD + OTP), there still exists a trivial solution to breaching the confidentiality of the information: Simply extract the information physically from the recipient, after they receive it. The implementation might be complex and expensive, but it is certainly possible in a practical sense.
Edit
This rather scathing blog.cr.yp.to post reiterates the the importance of the used assumptions and raises some technical points aside from the ever present threat of rubber hose cryptanalysis:

A company named ID Quantique has been selling quantum-cryptography hardware, specifically hardware for BB84-type protocols, since 2004. ID Quantique claims that quantum cryptography provides "absolute security, guaranteed by the fundamental laws of physics." However, Vadim Makarov and his collaborators have shown that the ID Quantique devices are vulnerable to control by attackers, that various subsequent countermeasures are still vulnerable, and that analogous vulnerabilities in another quantum-key-distribution system are completely exploitable at low cost. The most reasonable extrapolation from the literature is that all of ID Quantique's devices are exploitable...
...how can a product be broken if it provides "absolute security, guaranteed by the fundamental laws of physics"? The correct answer is that the hypotheses of the theorems, the assumptions made in the theorems, are not the laws of physics. The hypotheses include

an embarrassingly oversimplified model of physics that can express some quantum concepts but that ignores critical long-distance interactions, notably electromagnetism; and
an embarrassingly oversimplified model of the attacker that allows the attacker to inspect photons being sent between quantum-cryptography devices but that does not allow the attacker to interact with the devices in any other way.


Using AES-CBC and providing the IV in file header -> security hole? currently I audit some code I've written in the past to use KeePass 1.x databases. I stumbled over the following question:

The database itself is decrypted with AES-CBC and inside the file header the IV is stored in plain text. Is this a security hole? Following this article it's not really one as the IV is only needed for the first block but following this it is as a watermark attack is possible. Could someone explain this please in more detail?

Thanks a lot.

As hunter said in his comment, IVs are not required to be secret. Recall that the purpose of an IV is to make an otherwise deterministic construction instead be non-deterministic; if this were not the case, then these constructions would no longer have indistinguishable encryptions under chosen-plaintext attacks, and that would be a real shame.

Thus, there is no real need to keep the IV secret. If revealing the IV in AES-CBC somehow weakened the scheme, then there would be something very wrong with AES, and as far as anyone in the past 15 years can tell, there isn't much wrong with it. Think about it: what role does the IV have? Well: it is XOR'd with the first block of the plaintext before encryption. There's not much that can go wrong.

Of course, it's not all fun and games. For CBC mode encryption, your IV does need to be unpredictable and never reused. Generally, just picking a good (pseudo)random number does the trick there, but the requirement's there all the same.

Note an exception: if you are using CBC-MAC, your IV needs to be some fixed constant, usually zero, to prevent a bit of trickery on the part of an adversary. This doesn't really apply to your question directly, but I wanted to mention it just in case someone stumbled across this answer and thought it applied to CBC-MAC.


Re-sending captured encrypted data Let’s assume Bob is some algorithmic stock trading machine. Bob takes commands from Alice, who sends messages to Bob.

For example: Alice could be sending a message to Bob to stop trading. But if Mallory is able to capture cipher and figure out the effect of sending that cipher to Bob, Mallory could send the captured cipher to Bob and make him stop trading at arbitrary times.

How do cryptographic systems handle such situations?

One way I could think of is to append the current epoch time to message before encrypting it. Then Bob can choose to discard the message if the time shown in the decrypted cypher is far off in the past. But this is not foolproof. What actually is done in real life?

How do cryptographic systems handle such situations? … What actually is done in real life?

In real life, cryptography handles situations like the one you describe by using “authentication”. Authentication links an action, a message or a situation to an identity. In the example you describe, this will practically boil down to a validation of something an entity knows… like a password, a key, or another kind of secret.

Simplified, you could think of authentication as something which enables you to validate if an entity is actually who they claim to be, or allowed to do something, by showing they know a secret that only they could know. (Note that “authentication” does not always mean an entity proves its individual identity; it can also be used to prove an entity is part of a group of entities knowing a certain secret.)

For better understanding of what “authentication” is, it may be helpful to know there are also other forms (better: factors) of “authentication”. Chances are, you’ve already have met such “authentication” in real life yourself, since “authentication” can be proven by something an entity has – like a passport, a smartcard, a token device, or something similar.

Besides that, “authentication” can be proven by an entity by something an entity is. For example: humans have specific, individual features. These can also be used for “authentication”… which makes up one of the areas biometrics covers. If you‘ve ever had your fingerprint or iris scanned, or if you ever saw that in a movie… well, that’s what we call “authentication” in the realms of cryptography.

As said, in your example Bob and Alice will use a shared secret to enable mutual authentication. Not knowing the secret, Mallory will not be able to successfully authenticate her messages as Bob will detect the missing or wrong authentication factor (the secret) and reject and/or ignore Mallory’s messages/attacks accordingly.

Of course, authentication alone won’t make a protocol secure. Besides authentication things like secure connections (using encryption, etc.) are needed to wrap a secure shield around things. But authentication is an important part of cryptography, as it allows (for example) to learn if the entity you are communicating with is indeed the entity you expect to be communicating with… and not some kind of adversary who tries to inject or even replace messages which you might think are secure. They may be secure due to encryption, but without authentication that’s not worth all too much. Yet, the combination of both make up a pretty solid way of exchanging information between two entities.


$(\epsilon, \delta)$-differential privacy: main motivation of $\delta$ I am wondering why (not how) we relax $\epsilon$-differential privacy to $(\epsilon, \delta)$-differential privacy. Is the main motivation to reduce the variance of the noise added to the query with a slight sacrifice from the strength of privacy?

I help implement and ship anonymization strategies based on differential privacy in a large tech company. In my experience, the $\delta$ is mainly used for two reasons.

Partition selection: when computing histograms on an unbounded space, you can threshold the results (or do smarter things) and, at the cost of a non-zero $\delta$, avoid having to specify the full list of partitions in advance>.
Gaussian noise: since Gaussian is based on the $L_2$ sensitivity, it is very convenient to use when adding noise to a lot of metrics at once; if a single user can influence $k$ metrics, the noise needs to be scaled by $\sqrt{k}$ instead of $k$ with Laplace noise$^1$. But Gaussian noise doesn't give you pure $\varepsilon$-DP, you have to have a non-zero $\delta$.

Gaussian noise is particularly used for machine learning use cases. In such contexts, you also often want to use results on amplification by sampling, which also require a non-zero $\delta$.


Can you correct my understanding of Argon2? I'm a bit new to the cryptography field (completely new), and could really use your guidance.

Please, correct my understanding, as defined by the following statements.

The Argon2 Hash Generator has won the Password Hashing Competition, and is therefore believed to be the best solution at the moment for safely hashing passwords. Is is recommended to be used instead of bcrypt or pbkdf2
The Argon2 requires additional configuration, through parallelism factors, memory cost, iterations and hash length in order to be used in the most effective. However, default parameters are usually just fine.
The Argon2 also requires a 'salt' for security reasons - this one is meant to be generated using Cryptographically Secure Pseudo Random Number Generators (CSPRNGs for short), but any reasonably random value can be used here.
Some implementations of the Argon2 (such as this one), allow to secret keys and additional data to the function, but these are optional and are not required for the resulting hash to be secure.
Since any reasonably random value can be used as a salt, the result of another hashing function, such as Blake3, could also be used as a salt.
If I want to store both email hash and password hash securely in a database, for the potential attacker to have as little information about the user as possible, I could:

Store the registration date (RD) of a user
Generate the Argon2 hash of the email address, using the Blake3 hash of the RD as the salt
Generate the Argon2 hash of the password, using the Blake3 hash of the Argon2 hash of the email as the salt

The point above would not compromise the security, offered by the Argon2 hash, and would make it quite difficult for anyone, even those with a direct access to the database and the source code, to figure out what the email and the password of the user actually are - but would make it trivial to verify whether the user's input was correct or not

Any criticism, comments, thoughts, opinions (grounded in facts) - are more than welcome.

Correction: as Marc pointed out, 6.2. doesn't make any sense - it would make it (nearly) impossible to look the email up for a registered user. If we substitute the step 6.2. with a random scrambling of the user's email - such as Fisher-Yates Shuffle, repeated for X iterations - to make it consume time, using a random generator from this function, with a seed number derived from the email once again, would the rest still make sense?

A) Don't hash Email. Store it as plain text or don't store at all.

If hashed, then looking up will be impossible. One would need to iterate through every single record in the database. On average 50% records need to be tested each time. In case there are 1 000 000 users, for every login case the application will need to check on average 500 000 records. Hashing needs to be expensive. Suppose it takes 1s. It means, checking of a single login will take 500 000 s, which is about 6 days. Even for a small database with 1 000 user this will take 500 s = more than 8 minutes to check login every time user logs in. No user will accept it.

B) Store login ID as a plain text, exactly as entered by user, without any transformation and obfuscation.

If you use any transformation, it must produce each time the same result, otherwise you will not be able to look up login in the database. If the result is always the same, then also an attacker will be able to easily generate the same code. Means, not more security, but more obscurity and thus more error prone.

C) Where random data are needed, use random generator, don't add anything else.

The RD is not random. Thus Blake3(RD) is also not random. Thus the salt is not random. Instead, use random generator. Furthermore, adding complexity or making an algorithm more obscure does not make it more secure, not even a little.

Also don't make Email address or any other fixed data a part of the secret. Such data are not really random. Each user has some more or less limited number of such attributes (nobody generates a new Email address every day). That's why such data don't give much entropy. But using them makes the algorithm more obscure and gives a false feeling of security.

D) Try to keep an algorithm as simple as possible.

Think of Kerckhoffs's principle. Adding obscurity does not give any more security. But more obscurity means more complexity in the implementation, which makes implementation more error prone and thus actually less secure.

E) Separate different goals clearly. Don't mix them.

Hashing of secret data (password) is one goal. It seems you want to protect personal data that easily identify a person (Email address). This is another goal. It is not good to mix them. This leads to dependency between them. Trying to reach one goal can lead to problems achieving another goal. In our case, Email should not be a part of secret used for login. Furthermore, if you want to keep Email secret, encrypt it with a password that only user knows (not necessarily the same as login password). But then also your application will not be able to use this Email address, e.g. to send info to restore forgotten password. And if your application can decrypt it, then also an attacker can easily decrypt it. Means, either store it as is, as a plain text, or don't store at all.

F) "The best" doesn't mean "approved".

It is true, that Argon2 has won the competition. But before deciding to use it please consider also following (this happens not so often, but still there are such cases):

Make sure your customer approved using of Argon2 for password hashing. It may be that this customer has some conservative process and Argon2 is not (yet) approved for usage in this organization. May be they still accept PBKDF2 only. Especially some organizations close to the government may have such regulations.
Make sure your customer approved usage of particular library that implements Argon2 for your software platform (depending on what you use - C++, C#, Java, etc.). If not approved, I would not recommend to implement Argon2 by yourself. Instead, use some other algorithm provided by some of the libraries approved by this customer, even if it is PBKDF2, bcrypt or scrypt.


How do I compare three cryptographic schemes with respect to security? I am working on a project which compares SEAL, HElib and libScarab in terms of their execution times and security. I have already checked for the execution times. How do I decide which one of them is more secure?

How do I analyse the security provided by these libraries when they are used for certain applications?

This examines prerequisites; it's not a comprehensive answer, but outgrew a comment.

It's necessary to define if one wants to evaluate the security of the homomorphic scheme(s) implemented by SEAL, HElib and libScarab; or/and the security of the implementations of such scheme(s) that these libraries provide.

It's necessary to define the legitimate user's goals; the assets to be protected. These can usually be discovered by writing down the use cases.

One must define the threat model: assumed goals and capabilities of adversaries; in particular, exactly what data (including, keys) they can read, write or otherwise alter. If implementation is in scope, what's the level of access they have to the computers running the code and holding the data: can they run code on the same CPU as the implementations? With what accuracy can they time the execution result? What resources can it be expected that the adversary use (computing power, available thru funding or otherwise; that might influence a choice of key size, and some libraries might not be flexible on that)?

Note: some fine-grained security analysis, especially of physical devices, consider the level of expertise/knowledge of adversaries. But that's against Kerckhoffs principle and should be avoided from a pure cryptographic standpoint. Plus, digital attacks can relatively easily be commoditized: script kiddies can mount complex (but generic) attacks.

Credit to Maarten Bodewes for large portions borrowed from his comment.


What should the nonce value be for client-side encryption? I am using the following chacha20poly1305 Rust library to encrypt some data in a desktop application. The user provides the key, which never leaves their device, to locally encrypt some data, and then the encrypted data is sent to a server for backup purposes.
This library requires a nonce in order to encrypt the data, and I am not sure what this value should be. Ideally, the user could recover this encrypted data with their key alone. However, in order to decrypt any data, the nonce is also required. Hard-coding some nonce in the application feels odd, but if I randomly generate a nonce, the user will be required to remember this nonce along with their provided key in order to recover the encrypted data.

The library uses XChaCha20Poly1305 and that requires a nonce of 192-bit (24-byte). It is an extension of ChaCha20Poly1305 to increase the nonce size, ChaCha20 had 96-bit nonces. There is no standard for it, only a draft in ietf.org
The nonce is an acronym for 'number used once'. The crucial point is that one must never use the (Key, nonce) pair again. We call it nonce-misuse. If it occurs, the confidentiality is lost as the attacker can use the crib-dragging technique to reveal the two plaintexts. There is even an automated approach to solve it:

A Natural Language Approach to Automated Cryptanalysis of Two-time Pads by Mason et al

Or for detailed examples see the answer of this question;

Taking advantage of one-time pad key reuse?

For 192-bit nonces, random nonce generation is safe, since as per birthday paradox you would need to encrypt $2^{96}$ messages under the same key to hit the same nonce again with 50% probability, so you should encrypt way less messages to ensure that this probability is negligible. Keep in mind that you need to use a good random number generator like /dev/urandom. You can still use counter-based nonces if you want.

I am not sure what this value should be. Ideally, the user could recover this encrypted data with their key alone.

The nonce does not need to be secret and can be saved together with the file without being encrypted. This is not insecurity, only the key is secret. The nonce helps to use a key securely for more than once. It is secure as long as a (key, nonce) pair never occurs twice.

However, in order to decrypt any data, the nonce is also required.

That is completely normal since the decryption is the reverse of the encryption with the same key and nonce. XChaCha20Poly1305 generates a stream and we use it to x-or the plaintext. In order to regenerate the stream we need to use the same inputs.

Hard-coding some nonce in the application feels odd, but if I randomly generate a nonce, the user will be required to remember this nonce along with their provided key in order to recover the encrypted data.

Hard-coding a nonce is not acceptable as then it would be used more than once. There is no problem with rememebering the nonce, it is secure. Save it in a file like $$nonce\mathbin\|encryptedFile\|tag.$$
Note 1: The XChaCha20Poly1305 is an Authenticated Encryption, that will provide you confidentiality, integrity, and authentication if correctly used. Incorrect tags must not be ignored during the decryption. If the tag doesn't match, throw an error.

Encryption
$$(c,tag)= XChaCha20Poly1305Enc(key,nonce,message)$$

Decryption
$$(m|\perp) = XChaCha20Poly1305Dec(key,nonce,c)$$
where $\perp$ (\perp) is the halt if the tag mismatch.

Note 2: There were a recent question about Is it dangerous to encrypt lots of small files with the same key?. One can use the similar idea to generate different keys for each file, too.
A final note: if you encrypt and update data multiple times with the same key and nonce this also can cause nonce-misuse and some part of the new and old version of the file may lose confidentiality. Therefore, for every update use a new nonce and encrypt the file again.


Why do people criticize and mistrust the e-voting based block chain? I am planning to implement an e-voting system based on hyperledger fabric blockchain, however, I came across many criticisms from well-known security experts like Josh Benaloh and others. The problem is I couldn't find any proof that the e-voting is definitely insecure. In my opinion, I think Blockchain can be considered the best solution compared to the current voting system as it covers many security aspects.

can anybody explain to me thoroughly with tangible examples and proofs?

There's a good reason many democracies reserve mail voting to rare cases where that's the only option: it allows one's vote to be influenced by duress or bribery, because one can prove how one voted. No remote voting technology that I know has solved that issue. Ergo, physically going to a polling station with isoloirs should remain the normal voting procedure for political elections in a democracy. And this comment is right to point that some¹ usages of blockchain in electronic voting can ease vote selling.

A large fraction of voters do not understand cryptography or math, some are not even able to follow a logical argument. Even if a complex system was impossible to fraud, they would not be convinced that it is. Therefore simple systems that people understand are the best ones from the standpoint of having the people trust the outcome, which is critical to why we vote: decide who leads without a civil war.

Many electronic voting systems in use (including, in physical polling stations) fail to give a convincing argument to a rational and knowledgeable person that a vote gets counted as cast. People who know something about e-security are the hardest ones to convince because they see how an insider can rig the machine/system. I can't criticize the "e-voting system based on hyperledger fabric blockchain" of the question from that standpoint since it is not described, but ask yourself: how could an insider rig the result? And would it be that easy to make a fraud that can't be detected in a traditional voting system, where voters put a paper bulletin in an envelope at a polling station, publicly insert the envelope in a transparent box, these get locally and publicly opened and bulletins counted at the end of the day, and results of each polling station nationwide are made public, so that anyone can check this public record for accuracy when it comes to the polling station where s/he was a witness, and redo the addition towards the national outcome?

¹ Blockchain-based solutions that aim at securing the collection of results of different voting places, or prevent double voting by an individual, do not necessarily facilitate vote selling.


Polynomial multiplication and division in $2^{128}$ I want to multiply and divide polynomials, and implement the extended Euclidean algorithm for polynomial greatest common divisors, over a Galois Field of size $2^{128}$. Moreover, I want to use the previous algorithms on an 8-bit microcontroller (ATMega128). Where can I find relevant libraries in C or Assembly? Ι would prefer C, if the implementation is not too inefficient. Thanks in advance.

The RELIC library has support for binary fields. Check the functions fb_inv_exgcd for inversion and fb_mul_lodah (which calls fb_muln_low and fb_rdcn_low) for multiplication. There is even a ATMega128 backend written in assembly, though it does not support 128-bit fields (but should give you a head start if you need to write it).

You will need to make a few adjustments in order to isolate the multiplication code, but it shouldn't be too hard. Or you can simply use the library as is.

(Disclosure: I'm one of its developers)


Needed: signature over a collection of hashes I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes. Call this a SignedSetOfHashes. I want to be able to distribute the SignedSetOfHashes (which should be smaller than simply a vector of all the hashes and a digital signature.) I then want anyone to be able to verify that hash H is in the SignedSetofHashes having only the SignedSetOfHashes and a public key that matches the private key used to create the signature.

One idea I had was multiplying all of the hashes together in a field and signing the residue. Then I could verify any of the hashes are in by showing that the residue is divisible by any of the hashes. Of course, I could verify the signature without having any of the hashes.

Is there an existing approach to do this?

I am not quite sure if I exactly get what you are looking for, but I'll give it a try.

This answer refers to the original question before the edit

  I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes such that I can verify that any of the hashes is in the set at a later point in time without having to distribute all of the hashes.

One possible approach to produce a signature for a sequence of messages $(m_1,\ldots,m_n)$ (or hash values) is to build a Merkle tree from this sequence.

The idea of a Merkle tree is
to assign the messages $m_i$ to the leaves of a binary tree from left to right,
and do the hashing recursively upwards, starting from the lowest level
in the tree.

More formally, a Merkle tree
is a complete binary tree, together with a cryptographic hash function
$H:\{0,1\}^*\rightarrow \{0,1\}^{\ell}$ and an assignment
$\phi:N\rightarrow \{0,1\}^{\ell}$, where $N$ is the set of nodes of the
tree. The assignment $\phi$ for the label of the nodes is recursively
defined, where $v_P$ is the parent node
and $v_L$ and $v_R$ the left and right child respectively. Furthermore,
$x$ is a string that is assigned to a leaf.
\begin{equation} \phi(v_P):= \begin{cases}
H(\phi(v_L)||\phi(v_R)) & \text{if $v_P$ has two children};\\
H(\phi(v_L)) & \text{if $v_P$ has one child};\\ H(x) & \text{if $v_P$ is
a leaf.} \end{cases} \end{equation}
Additionally, define the
authentication path $A_v=\{a_i|0<i\leq
h\}$ of a leaf $v$ as the set containing all values $a_i$. The value
$a_i$ at height $i$ is defined to be the label of the sibling of the
node of height $i$ at the unique path from $v$ to the root.

Note that if your values $(m_1,\ldots,m_n)$ are already hashes, then you can directly assign these values to the leaves (without hashing them again). Subsequently, the $m_i$ are denoted as messages (irrespective if they are messages or hash values).

Put differently, a Merkle tree can be used to release a message $m_i$ and the coresponding authentication path $A_{m_i}$ such that
everybody is able to verify that $m_i$ "is in the tree", but does not require access to the all the remaining messages.

Now take a secure signature scheme and sign the root-hash of the Merkle tree. Then given
the signature, $m_i$ and $A_{m_i}$ it can be checked that $m_i$ is in the signed sequence $(m_1,\ldots,m_n)$ without
requiring all the other messages $m_j$, $j\neq i$. Basically, from $m_i$ and $A_{m_i}$ one recomputes the root hash and checks the digital signature.

However, note that this does not ensure a real hiding of the remaining messages $m_j$. If the remaining messages have a short length and/or are known to come from a small set,
one can mount a brute-force attack by simply hashing all possible values and check whether the result
matches the root hash.

This can be prevented if one does not use simple hashes for the leaf nodes, but uses
commitments instead. This approach is for instance applied in redactable signatures (RS) or content extraction signatures (CES).

How does this related to what you seek

You do not have to distribute all hashes, but for every value $m_i$ a "proof" that the value is in the set (the Merkle tree) you have to distribute $(m_i,A_{m_i})$. The advantage is that if you use the commitment based approach as applied in RS or CES, nobody can test against your signature to check if a given value is in the set, unless you want to explicitly allow that by providing $(m_i,A_{m_i})$.

EDIT (to answer the edited question)

Any approach that will give you cryptographic security guarantees that you will not encounter false positives (such as cryptographic accumulators, Merkle trees, vector commitments, zero-knowledge sets, etc.) will require to provide a "witness" for every value to be able to check against the structure.

If you tolerate a larger false-positive probability you can use for instance Bloom filters to represent your set and allow set membership queries without any witnesses.


RSA - is it possible to find the modulus from both the private and public exponents? Let $e$ be the public exponent (which is equal to $65537$) and $d$ the private exponent. Knowing the values of those two, is it possible to deduce $N$, the modulus, and if yes, how?

Note: the value of $N$ is not known! I also don't need to get the values of $p$ and $q$, but seeing how $d$ is actually calculated makes me think it'd be easy to get them anyway.

It turns out that recovering $N$ from $e, d$ is a hard problem; in particular, if you can, you can factor values that are currently believed to be intractable (!).

To start with, a necessary and sufficient condition on $e, d$ being valid RSA exponents to a square-free modulus $N$ is that, for every prime factor $p$ of $N$, we have:

$$ed - 1 = k(p-1)$$

for some integer $k$.

Now, let us assume that we have an Oracle that, given $e, d$, will recover a value $N$ for which $e, d$ are valid RSA exponents (assuming there is such an $N$); we further assume that it gives a reasonably large value $N$, specifically, one in the range $\ell \sqrt{eq} < N < 5ed$ (for a modest constant $\ell$).

Now, suppose that we have a value $N = pq$, where $p, q$ are both unknown Sophie-Germain primes (that is, $2p+1$ and $2q+1$ are also prime), and are approximately the same size; that is $q < p < 2q$.  We will also assume that the value $2pq+1$ and $4pq+1$ both happen to be composite (which it will be for a majority of the possible $p, q$ pairs).

Assuming $N$ is sufficiently large, there is no known way to factor it.

We note that $p \equiv q \equiv 2 \pmod 3$, and hence $2N + 1$ is a multiple of 3.  So, we set $e = 3$ and $d = (2N + 1)/e$; and give $d, e$ to our Oracle.

What the Oracle will do is return a value $N' = p_1' p_2' … p_n' $ (where $p_1', p_2', …, p_n'$ is the prime factorization of $N'$.  Such an $N'$ will always exist, as $N' = (2p+1)(2q+1)$ is such a valid modulus (hence the Oracle must return some value, if not necessarily $(2p+1)(2q+1)$

Because of the condition on RSA exponents, we have $ed - 1 = 2pq = k_i(p_i' - 1)$ for every prime $p_i'$.

Because of the range limitation on $N'$ (that is, $\ell \sqrt{eq} < N'$), we must have $p$ as one of the factors of $p_i' - 1$ (for some $i$), and similarly have $q$ as a factor of $p_j'-1$ (for some different $j$; it must be different, otherwise this prime factor would be $2kpq+1$; we assumed that $k=1$ and $k=2$ didn't yield a prime, and $k>2$ have a value outside the $5ed$ range we assumed).

Hence, we have $N' = k''(k'''p + 1)(k''''q + 1)$, for modest $k'', k''', k''''$.  Given that, and $N = pq$, it's easy to factor $N$.

This is much more of a sketch than I originally intended; there are a number of missing details.  However it should not be hard to fill in the details...


Complexity of multiplication of two numbers If I am multiplying two numbers $m$ and $n$, where $n$ has $k$ digits and $m$ has at most $n/2$ digits, will it be considered polynomial time or exponential time in terms of $k$?
Addition (by proxy of mod): This multiplication's time will be exponential in $k$ (answering the above), yet polynomial in size of $m$. Will it be called an efficient result or not?

The maximum size of $m$ is $n/2$, and the maximum value of $n$ is $10^k-1$. It follows that the size of $m$ is exponential in $k$. Since (when $n>0$) the multiplication algorithm must read the whole of $m$, and that takes time at least proportional to the size of $m$, it follows that the complexity is at least exponential in $k$.
From a theoretical standpoint, the multiplication is thus not efficient for security parameter $k$, since efficient is defined as time bounded by a polynomial of the security parameter.
If the security parameter was $n$, the algorithm could be efficient (and we could prove that by exhibiting a multiplication algorithm with cost bounded by a polynomial in $n$, which is easy: the schoolbook algorithm turns out to be enough; this is left as an exercise to the reader).
In a crypto context, we want the security parameter to be such that it makes the normal user's cost at most polynomial (i.e. efficient), but the attacker's (conjectured) cost at least super-polynomial (hopefully exponential). Thus if our algorithm is to be considered interesting, then

if that multiplication is to be performed by the user, it must be efficient and thus our parameter can't be $k$.
if that multiplication is to be performed by an attacker in an attack, but not by the legitimate user, our parameter can be $k$, and probably should be. The multiplication then can be efficient (and is, unless the multiplication algorithm is abysmally inefficient).


Is there a KDF that can be computed in an untrusted environment? I'm looking for a Key Derivation Function, kind of like PBKDF2 or Scrypt, but which can be computed by a machine you don't trust.  Some way to give it a derivative of the source password, such that the key can be computed from the derivative but the derivative is opaque and otherwise useless to the untrusted machine.  Also, I should be able to verify that machine actually performed the KDF and didn't just throw back a random key.

For the first part, protecting the password, I imagined the system would have to be something like:

s = random()
P = F(s,password)
I = KDF(P)
K = G(s,I)

Where s is some random number, and F and G are some kind of functions such that K is always the same given the same password, regardless of s.

Basically, some way to "encrypt" the password into an opaque value that the KDF can generate an incomplete key from, and then we can use the secret from that encryption to get the real key.  We then throw away s. Later, to regenerate K from just the password, we can just pick another random s.

I don't know if any such combination of F, KDF, and G exist.  I also don't know how to approach the proof requirement; that we can prove the KDF was executed correctly.

And of course this needs to be practical. I'm sure you could accomplish all of this using general homomorphic encryption to implement scrypt, but that would be intolerably slow.

Also, I should be able to verify that machine actually performed the
  KDF and didn't just throw back a random key.

This is actually kinda hard, but can be worked-around by carrying out the very first computation of the hash function yourself. Then store this hash for the later verification with delegation or use it to derive your key to encrypt data. You will then verify that the returned result being correct by being able to successfully decrypt the data or by verifying that the "trusted" and the untrusted hash match.

  I'm looking for a [Password-based] Key Derivation Function [...], but which can be computed by a machine you don't trust. Some
  way to give it a derivative of the source password, such that the key
  can be computed from the derivative but the derivative is opaque and
  otherwise useless to the untrusted machine.

This functionality is precisely why our ursine overlord's Makwa has received a special recognition at the end of the Password-Hashing Competition (PHC). However it's has a somewhat "steep" baseline price. Namely you must perform about 300 (normal) modular exponentiations in an modular ring (ie modulo an RSA-like modulus) at setup time, additionally to finding a composite number similar to an RSA modulus. I will sketch the idea of it here, but I strongly urge you to read either the provided C / Java code or the specification (PDF). There are also other methods described / implemented there that will offer information-theoretic security instead of "mere" computational security if your psychology needs that.

To setup the things at your client, delegating the hashing do the following once at system-steup:

Pick a work-factor $w$, values of the form $\delta\in\mathbb N,\gamma\in\{2,3\}: w=\gamma\cdot2^\delta$ are recommended, with usual values being around $\delta=20$
Pick two primes $p,q$ such that it is infeasible to factor $n=pq$ (ie $p,q$ should be around 1024-bit long) and ensure that $p\equiv q\equiv 3\pmod 4$, store $n$ and keep $p,q$ for now
Pick an integer $m$ such that $2^{m/2}$ operations are infeasible, for example $m=300$
Pick $m$ random integers $r_i< n$, compute $\alpha_i=r_i^2\bmod n$ for each of them, compute $\alpha_i'=\alpha_i^{2^w}\bmod n$, use your knowledge of $p,q$ to reduce $2^w\bmod{\varphi(n)}$ first, where $\varphi(n)=(p-1)(q-1)$. Now compute $\beta_i=\alpha_i^{-1}\bmod n$ and store all $m$ pairs of $(\alpha_i,\beta_i)$, you don't need to keep these values secret
Discard $p,q$

To verify / derive the password hash (skip steps 5 and 7 and increase $w$ by one for your initial, trusted run):

Optionally pre-hash the password using HMAC-DRBG
Run the salt and the password through HMAC-DRBG to get $s_b$
Concatenate $s_b$, the password and the password-length to get $\chi$
Pick $m$ random bits $b_i$ using a CSPRNG
For all $j$ for which $b_j$ happens to be $1$: Compute $z=\chi^2\cdot \prod_j\alpha_j$, ie multiply the square of $\chi$ with all $\alpha_i$ where $b_i=1$
Send $n,w,z$ to the untrusted machine, let it compute $z'=z^{2^w}$, ie $w$-repeated-squarings and receive $z'$
Compute $y=z\cdot\prod_j \beta_j$ the same way as in step 5
Use $y$ as your output, which you may want to hash using any ordinary hash function if you intend to use it as a cryptographic key (because some bits won't have probability $\frac12$ of being $0$ or $1$) or if it is simply too large for you (with 256 bytes)


Advantages of using 64-bit word size over 32-bit word size I'm learning about cryptographic hash functions and I have some questions about SHA-2.

SHA-256 uses 8 32-bit words. SHA-512 uses 8 64-bit words.

Is there a specific reason why SHA-512 uses 64-bit words? Why not 16 32-bit words?

And if 64-bit words have their advantages over 32-bit words. Why doesn't SHA-256 use 4 64-bit words?

The main reason of using 64-bit word size over 32-bit word size is speed, on CPUs that manipulate words sequentially. Doubling the word size can hope to about double the number of elementary bitwise operations performed in a given amount of time, on a 64-bit CPU like one using the AMD64 instruction set.

As an aside, for constant number of words in the internal state of a an algorithm (like a hash), the number of bits in the state is twice as large, which can improve the cryptographic resistance (if other conditions apply; in particular, at least twice as many bit operations); and allows a larger result.

Accordingly, for large input, SHA-512 is typically faster than SHA-256 on the same 64-bit CPU, even though SHA-512 uses 25% more rounds, and has a state with twice more bits, making it arguably safer.

Update per comment: word size has no direct impact on security. As an illustration, it is possible to reformulate SHA-512 as using 32-bit words, with identical result thus security; compilers for 32-bit CPUs do this automatically.


Taking advantage of one-time pad key reuse? Suppose Alice wants to send encryptions (under a one-time pad) of $m_1$ and $m_2$ to Bob over a public channel.  Alice and Bob have a shared key $k$; however, both messages are the same length as the key $k$.  Since Alice is extraordinary lazy (and doesn't know about stream ciphers), she decides to just reuse the key.

Alice sends ciphertexts $c_1 = m_1 \oplus k$ and $c_2 = m_2 \oplus k$ to Bob through a public channel.  Unfortunately, Eve intercepts both of these ciphertexts and calculates $c_1 \oplus c_2 = m_1 \oplus m_2$.

  What can Eve do with $m_1 \oplus m_2$?

Intuitively, it makes sense that Alice and Bob would not want $m_1 \oplus m_2$ to fall into Eve's hands, but how exactly should Eve continue with her attack?

There is a great graphical representation (which I found on cryptosmith, but they keep changing their url structures, so I've added the graphics in here) of the possible problems that arise from reusing a one-time pad.

Let's say you have the image

and you encrypt it by using the binary one-time-pad (xor-ing on black and white)

.

You get the following extremely secure encryption

.

If you then encrypt a smiley face with the same one-time-pad,

you get another secure encryption

.

But if you have both and you xor them together

then you get the image

which, as you can qualitatively and intuitively see is very insecure.

Reusing the same key multiple times is called giving the encryption 'depth' - and it is intuitive that the more depth given, the more likely it is that information about the plaintext is contained within the encrypted text.

The process of 'peeling away' layered texts has been studied, as ir01 mentions, and those methods improve with more layers.


Distinguishing Attack on CBC-MACs I want to ask again about distinguishing attack on CBC MAC, based on the paper published by Ketting Jia, Xiaoyun Wang, Zheng Yuan, and Guangwu Xu: Distinguishing Attack and Second-Preimage Attack on the CBC-like MACs.

That paper says: "The adversary makes $2^{(n+1)/2}$ queries with $m$-block messages that have the same last $m−1$ blocks."

What I want to ask is why the authors choose $2^{(n+1)/2}$?

As we know, block cipher's input width is usually even, so if we operated it with $2^{(n+1)/2}$ the result will not be an integer, but fractional.

Why approximately $2^{(n+1)/2}$ queries?  Because it makes the attack work.

As far as your final comment, it sounds like you are confusing $(n+1)/2$ with $2^{(n+1)/2}$.  If we use AES, then $n=128$, so $(n+1)/2=64.5$.  However, $2^{64.5}$ is a very large number.  The exact number of queries is not important as long as it is approximately $2^{64.5}$, and it is easy to choose an integer near that number.


How to compare performances of lattice-based and pairing-based IBE schemes I try to compare the performances (cost of Enc, Dec, ... size of keys, ciphertexts, ...) of IBE schemes using lattices (LWE hardness assumption) or pairing (Diffie-Hellman hardness assumption).

I've observed that performances of lattice-based schemes are often expressed in terms of $n$ (the dimension of the lattice) whereas pairing problems use the bit size $|G|$ of the elements of the underlying group(s) $G$ (and the cost of basic operations such as exponentiation or pairing).

Are these 2 quantities "equivalent"? For instance, is it relevant to say:

keys of length $O(n)$ (in a lattice scheme) and $O(|G|)$ (in a pairing scheme) will have roughly the same size in practice
encryption of cost $O(n^2)$ (in a lattice scheme) is quicker than $O(|G|^3)$ (in a pairing scheme)
...

It is very hard to give a concrete, "apples-to-apples" comparison of lattice-based and pairing-based IBE schemes.  There are many reasons: the research surrounding concrete secure parameters for LWE is still evolving, efficient implementations of operations used in lattice-based IBE (e.g., discrete Gaussian sampling) are still works in progress, one can consider more efficient ring-based analogues, etc. etc.

However, it is possible to give meaningful asymptotic comparisons, at least up to poly-logarithmic factors, under reasonable hardness conjectures about lattices and pairings (so that we're normalizing to equivalent security levels).

To your specific questions: no, the dimension $n$ for LWE and the bit size $\log |G|$ are not equivalent.  However, they are asymptotically close, up to polylog factors, in the following sense: for conjectured $2^\lambda$ security, we can set $\log |G| = O(\lambda)$ and $n = \tilde{O}(\lambda)$.  For pairings, this implies that all key sizes are $O(\lambda)$.  For lattices it implies:

master public keys of size $\tilde{O}(n^2)$ [plain LWE], or $\tilde{O}(n)$ [ring LWE].
user secret keys of size $\tilde{O}(n \cdot \ell)$ for $\ell$-bit messages [plain LWE], or $\tilde{O}(n)$ [ring LWE] for $\ell = O(n)$.
encryption time of $\tilde{O}(n^2)$ [plain LWE], or $\tilde{O}(n)$ [ring LWE].
etc. etc.

In short, for ring-LWE all relevant sizes and runtimes can be made $\tilde{O}(n)$, though the hidden polylog factors can be significant in practice.


What is the translation for "hash" in french? I am doing a French presentation on basic cryptography, and the generation of random numbers. Most terms are easily translatable, but I can't seem to find a word for hash, as in cryptographic hashing, in french. The closest I can come up with is gâchis, which means "mess" or "failure.

In French, cryptographic hash function translates to fonction de hachage cryptographique.


Are there practical upper limits of RSA key lengths? Suppose one wanted to use RSA encryption for the sole purpose of sending key bits for use in symmetric crypto systems, a dedicated key exchange system so to speak.
And say you didn't think that the presently used RSA key lengths were going to be secure in ten or fifteen years.

What would be some of the technical difficulties (hardware and or software) of of using an RSA key length of say a million bits?

Assume that you are designing this from scratch and you have a clean slate as to your hardware-software design options. Also assume that you don't care if it takes 24 hours or so to encrypt or decrypt the information.

Computational cost of RSA with keys of length $n$ bits is roughly $O(n^2)$ for public key operations (encryption, signature verification), and $O(n^3)$ for private key operations (decryption, signature generation). So RSA with a million-bit key will be roughly one billion times slower than RSA with 1024-bit keys (for the private key operations); the latter takes about 1ms on a common PC, so you're in for a fortnight of computation with your million-bit key.
Memory space is not a hard constraint, because RSA computations require only to keep a few values of the size of the key; a one-million-bit integer is 128 kB; you can have thousands of those in RAM. You will, however, exceed level 1 cache (that's 32 or 64 kB on a common PC) so you can expect some slowdown (with Montgomery's multiplication, data access is sequential, so this effect should be limited).
Of course, security is not only about resisting attacks; it is also about having confidence in being able to resist attacks. My confidence in a system which uses RSA with one-million-bit keys would be near zero... because it makes no sense. RSA is secure because big integers are hard to factor. The best known algorithms with the best available hardware fail at about 1024 bits; 2048 bits are more than enough. Going beyond is making a wild and totally unsubstantiated guess about what not-yet-discovered algorithms may look like, which is speculation on rumours of legends about mythical glimpses of the future. When someone talks to me about having an oversized RSA key, like a 8192-bit key "just to be safe", I see it as if he was talking about buying a SUV to demonstrate his manhood (in your case, you are advocating buying an aircraft carrier).


Rabin cryptosystem - How many solutions? If in Rabin cryptosystem we have $n = p \cdot q$ where $p$ and $q$ is prime we have four solutions (roots) - exist four solution of $x^2 \equiv b \pmod{n}$.

However, when we have:

$n = p \cdot q \cdot r$

where $p$ and $q$ and $r$ is prime or:

$n = p \cdot q \cdot r \cdot z$

where $p$ and $q$ and $r$ and $z$ is prime

How much will we have solutions?

will they be $2^k$? where $k$ is the number of prime numbers?

How much will we have solutions?

Assuming:

$p, q, r, ..., z$ are distinct odd primes
$b$ is relatively prime to $n$
There exists at least one solution

Then, yes, there will be precisely $2^k$ solutions.

This is straight-forward to show; as we know there exists a solution $x_0$ such that $x_0^2 = b \pmod n$, then this implies that:

$$x_0^2 = b \pmod p$$

$$x_0^2 = b \pmod q$$

...

$$x_0^2 = b \pmod z$$

We know that the first equation has two solutions modulo $p$; $x_0$ and $-x_0$ (as $b$ is relatively prime to $p$, and hence $x_0 \ne 0 \pmod p$, and $p$ is odd, so $x_0 \ne -x_0 \pmod p$).  We also know there cannot be a third (as that would imply a nontrivial factorization of $p$, contradicting the assumption that $p$ was prime).

Similarly, the rest of the equations have 2 solutions; hence using the Chinese Remainder Theorem, there are $2^k$ was to recombine these solutions into an $x$ value that satisfies all these equations (and hence the original one).

We can also show that any value of $x$ not in the set of $2^k$ will not satisfy one of the prime equivalences, and hence cannot satisfy the original, hence we have precisely $2^k$ solutions.


Why derive keys from a master key instead of generating random keys? I noticed AWS KMS generates encryption keys based off of a master key, using a key derivation function (HKDF).

What's the practical advantage of deriving keys based on a master key? Isn't it simpler and typically more secure to just generate random keys with a CSPRNG?

Fewer keys to store?

Edit: to add context to AWS KMS, it uses a hardware security module, which would seem to add a storage constraint. However, given KMS basically just generates new data encryption keys (DEKs) and wraps (envelope encrypts) them with the master key for the user to store elsewhere, it doesn't seem to change storage requirements. So it begs the question, why derive the DEKs from the master key?

Here are various advantages.  Maybe they don't all apply in this case—I don't know, but there are cases in the real world in which they do apply.

Test vectors.  You can write known-answer tests for your entire cryptosystem, end-to-end.  You can verify these test vectors in a power-on self-test to cheaply detect catastrophic failure.  You can easily use these test vectors to debug an interoperable alternative implementation during development.
Reproducible subcomputations.  If you need to add a branch to a tree of subcomputations with an independent key, you can simply use a distinct label for the HKDF info parameter, and all the other computations will remain unchanged.  That way, e.g., you don't have to update your test vectors, whereas you would have to if you drew keys out of a sequential PRNG.
Reduced storage.  You only need to store as many keys as there are independent privilege domains in your system.  You can simply rederive any subkeys for different purposes within a privilege domain instead of having to store them separately.
Reduced reliance on entropy sources.  You can flash a key onto an embedded microcontroller, and use it to derive subkeys for various purposes, and even rotate keys and erase old ones, without having to rely on an entropy source on the microcontroller itself.


Why BouncyCastleAesCbcBytesEncryptor is using a salt and an initialization vector? I'm using the class BouncyCastleAesCbcBytesEncryptor from Spring Security. One of the constructor has the following signature:

BouncyCastleAesCbcBytesEncryptor(String password, CharSequence salt, BytesKeyGenerator ivGenerator)

I was first thinking that salting is not necessary with AES, my first idea was confirmed by this accepted Stackoverflow answer:

  Salting is generally something that is done when hashing a password, not when encrypting plaintext; for example, you would use a salt when generating a key from a password using PBEKeySpec. AES's "salt" is its initialization vector.

My question is: why does this constructor ask for a salt AND an initialization vector generator?

In short; salt is used for Key derivation function together with the password. IV is used for CBC which must be unpredictable.

In details;

The document is sparse for the details. One can guess that is is for key derivation from the supplied password and salt instead of a key. So the initial guess was it is used for key derivation from the password. When we look at the source code;

public BouncyCastleAesCbcBytesEncryptor(String password, CharSequence salt,
            BytesKeyGenerator ivGenerator) {
        super(password, salt, ivGenerator);
    }

The super class is BouncyCastleAesBytesEncryptor and there

PBEParametersGenerator keyGenerator = new PKCS5S2ParametersGenerator();
...
keyGenerator.init(pkcs12PasswordBytes, Hex.decode(salt), 1024);

And form the documents;

  Generator for PBE derived keys and ivs as defined by PKCS 5 V2.0 Scheme 2. This generator uses a SHA-1 HMac as the calculation function.


Difference between Zero Knowledge Proof and Challenge Response Protocol What exactly is the difference between Zero Knowledge Proof & Challenge Response Authentication?
I searched online and the best I could find are these:

techtarget.com

Zero-knowledge password proof systems depend on cryptographic methods
that enable both parties -- client and server -- to authenticate to
each other. These systems allow each party to confirm to each other
that they have a correct password, but without the need to share that
password with each other

cse.scu.edu : Implying that both of them are different and one improves on the other.

An instructor in my university had asked this question in one of the assignments and when I received the answer key for the same, I found this:

Distinguish between challenge response and Zero knowledge entity
authentication.
Challenge-response identification – Strong authentication.
Cryptographic challenge-response protocols is that one entity (the
claimant) “proves” its identity to another entity (the verifier) by
demonstrating knowledge of a secret known to be associated with that
entity, without revealing the secret itself to the verifier during the
protocol.  This is done by providing a response to a time-variant
challenge, where the response depends on both the entity’s secret and
the challenge.  The challenge is typically a number chosen by one
entity (randomly and secretly) at the outset of the protocol.  If the
communications line is monitored, the response from one execution of
the identification protocol should not provide an adversary with
useful information for a subsequent identification, as subsequent
challenges will differ.  Challenge-response protocols can be realized
by symmetric-key or asymmetric-key cryptography
Zero-Knowledge Proof
–  ZKP concept.  A disadvantage of simple password protocols is that
when a claimant A (called a prover in the context of zero-knowledge
protocols) gives the verifier B her password, B can thereafter
impersonate A.  Challenge-response protocols improve on this: A
responds to B’s challenge to demonstrate knowledge of A’s secret in a
time-variant manner, providing information not directly reusable by B.
Examples of ZKP.  Fiat-Shamir identification protocol.
Feige-Fiat-Shamir identification protocol.  Guilou-Quisquate
identification protocol.

which I feel is either wrongly worded or entirely wrong (leaning on the latter).
So, what exactly is the difference between them or are they not different at all? If possible, please explain with an example along with real-life algorithms where each of these is used.

They're just different things. A protocol may be challenge-response or not, and zero-knowledge or not; all four combinations are possible.

Plain password authentication is not challenge-response and not zero-knowledge.

The manual-lookup copy protection in old games is challenge-response and not zero-knowledge. Another example would be CAPTCHA.

Non-interactive zero-knowledge proofs are zero-knowledge and not challenge-response. Ex: Where's wally?

Colour Blind friend problem is an example for Zero-Knowledge Proof & Challenge-Response, both.

(Wikipedia says that plain password authentication is challenge-response because "tell me the password" is a challenge, and Modal Nest's answer says the same thing. By that definition I suppose any proof is necessarily challenge-response, because "prove it" is a challenge. But I think that definition is too broad and makes the term "challenge-response" largely useless. I'd limit it to protocols in which the prover has to do a nontrivial amount of work after getting the challenge, and can't just return a canned response.)


Retrieve message from rsa ciphertext based on some conditions Assume:

$x = m^{e-1}\bmod n$
$y = m^{d-1}\bmod n$

Here $m$ is a message, $e$ is the public exponent, $d$ is the private key and $n$ is the modulus of an RSA key pair.
Now if I know $e=65537$, $x$, $y$, and $n$, can I retrieve the message $m$?

let \begin{equation}
x*y=m^{e+d-2} \mod n \qquad (1)
\end{equation}
\begin{equation}
m(x+y)=(m^{e}+m^{d}) \mod n \qquad (2)
\end{equation}taking $log_m $ for each from (2) side with respect to $\mod n$, we will have
\begin{equation}
log_mm(x+y)=log_m(m^{e}+m^{d}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)=log_m(m^{e})+log_m(1+\frac{m^d} {m^e}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)\ge log_m(m^{e})+log_m(\frac{m^d} {m^e}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)\ge e+d-e \mod n \qquad
\end{equation}
\begin{equation}
d\simeq  1+log_m(x+y)\qquad (3)
\end{equation}
substitute $(3)$ in $(1)$
\begin{equation}
x*y=m^{e+(1+log_m(x+y))-2} \mod n \qquad
\end{equation}
\begin{equation}
x*y=m^{e-1}m^{log_m(x+y)} \mod n \qquad
\end{equation}
\begin{equation}
m^{e-1}=(x+y)^{-1}(x*y) \mod n \qquad
\end{equation}


Can I use my random IV (for AES) as a salt for PBKDF2? Also, where do I store my salt (can I just store it at the beginning of the encrypted file)?

I suppose that what you are trying to do is password-based encryption of some data; you use PBKDF2 to derive the password into an encryption key, and then use the key with AES to encrypt the data. The AES encryption needs an IV, and the PBKDF2 function needs a salt. Both IV and salt should be generated anew for each encryption (even if reusing the same password).

Generically, the salt and the IV can be just encoded in a header for the encrypted file. They are not secret values.

Your question is then: can you use the same value for both the salt and the IV (presumably to save space) ? I do not recommend it. I would be surprised if it really induced a security issue, but who can be sure ? It looks a bit funky, and that's bad enough to avoid it. What you can do, instead, is to store the salt in the file header, and use PBKDF2 to generate both the key and the IV. Thus, the IV needs not be stored anywhere. PBKDF2 is a key derivation function which can produce an output of arbitrary length.

Generating the key and the IV from the same source is what is done in OpenSSL (in its private symmetric encryption format), and also in SSL/TLS (up to TLS 1.0).

I hope that your AES-based encryption mechanism uses a mode with integrated integrity checks, like EAX. Integrity is not an option; it is often overlooked, but it is necessary for security.


Is there a notion of "computational security" in quantum cryptography? In classical cryptography, security proofs are often based on the (assumed) computational hardness of some mathematical problem. Using the principles of quantum mechanics might provide means to design cryptographic protocols that can classically not be implemented (information-theoretically) securely. But is there also a notion of computational security in quantum cryptography (assuming a polynomial-time quantum adversary)? Why does or doesn't make this notion of security sense?

But is there also a notion of computational security in quantum cryptography (assuming a polynomial-time quantum adversary)?

No, not really, or at least, none that has been explored.  The goal of Quantum Cryptography is to be secure, even if the adversary has a Quantum Computer and that they are computationally unbounded; that is, the goal is to rely (as much as possible) on security-by-the-laws-of-physics alone [1].
One could include the assumption that they are computationally bounded; however if you did that, you would have a number of competing options available, including large key symmetric cryptography and postquantum (public key) cryptography.  These existing solutions already solve the problem, and are considerably cheaper and more versatile.  Hence, there appears to be little need to lower the security bar on Quantum Cryptography.
Kelalaka brought up the paper "Computational Security of Quantum Encryption"; however a close review shows that the security targets it makes do not rely on the security assumptions of Quantum Mechanics.  Instead, it examines the extension of classical cryptography into the realm of Qubits (and how that differs in nontrivial ways from the cryptography on bits).  This may be semantics, however I do not believe that falls into the realm of "Quantum Cryptography".

[1]: Of course, that's not the only assumption; they always need to assume that there are no exploitable side channels, that the equipment is operating as designed (and not in a way that looks correct, but is exploitable) and also for many QKD systems, the shared keys are used to AES encrypt the actual traffic (and hence those systems need to assume AES is strong as well).


Can SHA or MD5 results be decrypted? I have learned that SHA-1 and MD5 are one way hash functions, which means that it is not possible to obtain the original value by performing the reverse calculation.

There however some online websites that 'decrypt' the hash function to the original value. I tried decrypting in the Linux command line but it seems that the input can only be hashed using sha1sum command.

I'm just curious if the reverse calculation is possible or not.

MD5, SHA-1, SHA-256, etc. are one-way functions: given the hash of an input, nobody knows how to find the input better than by guessing, and the best cryptographers in the world have tried.

But guessing is always a possibility. You just try a lot of inputs until you find one with the desired hash value. If the input is a member of a small set, for example if you know it's a dictionary word, this can be done very quickly. On the other hand, if the input includes enough unknown bits, it's unfeasible. For example, if the input includes 128 random bits, then it would take a billion PCs about the age of the universe¹ to get a decent chance of finding the right input.

The websites you found don't “decrypt” anything. What they do is, they calculated a lot of hash values and stored them in a database. When you ask them to reverse a hash, they look it up in the database. This only works if the hash is one that they have in the database.

¹  Say 2³⁰ calculations per second per computer, times 2³⁰ computers. The age of the universe is about 2⁶⁰ seconds, giving you a 2⁻⁸ chance of success.


Timing attacks on homomorphic encryption I've been wondering for a long time about programs that could potentially break fully homomorphic encryption schemes:

//Given input vector A
if(A[0] == A[1])
   while(true) ; // or do any time consuming calculation
else
   return <anything>;

System could execute such programs and using timing methods determine information about encrypted data. It could of course ask more clever questions about the data than equality and possibly decode full encrypted vector.

What is wrong with my thinking here?

It is not possible since the IF condition with semantically secure FHE's can be implemented as

$$Q = (A * S) + (B * S'),$$ this circuit is the combinational logic of the if/else statement and we can construct this with FHE.

FHE encrypted $S$ is the input by the if statement ( the boolean expression part).
FHE encrypted $A$ is the input by the  then statement
FHE encrypted $B$ is the input by the  else statement
FHE encrypted $Q$ is the output of the expression.

This is for calculation of the ternary operator
Q = S ? A : B;

The IF condition must be implemented in this way. This is due to the semantical security that prevents the output of the comparison circuit to be known to the evaluator. The above circuit will reveal nothing to any observer. Actually, a similar calculation is also performed during normal programming to mitigate the side-channels.

Note that the == can be achieved with 2's complement and substruction. For a little detail see this answer : Representing a function as FHE circuit

One might also wonder that does the comparison circuits in FHE are constant timing, the answer yes since we don't have IF then return/break statements.


How many keys in a Hybrid Cryptosystem? If symmetric cryptosystems have $C^2_n$ keys, and asymmetric systems have $2n$ keys, how many does a hybrid system have?  This was in an online quiz from school

  Company A is considering to adopt a cryptosystem for secure communications among its employees. Currently it has $5$ employees. Assume that every employee has used the adopted cryptosystem to communicate with all other employees once.

3) c. If the company adopts hybrid cryptosystem, how many keys would be used in this case? Show your working.

My answer was

  $C_n^2$ symmetric session key + $2n$ asymmetric keys

  $= C_5^2  + 2 \times 5$

  $= 20$ keys

This was marked wrong. Where did i go wrong here? As far as i understand, in a hybrid system they make use of asymmetric keys to encrypt the symmetric session key, which is used to encrypt/decrypt the document.

So first, for each employee there is a public-private-key pair, which is $2n$.

For each session one symmetric key is created. Your solution assumes the communication partners initially agree on a symmetric key they both use in the communication with each other.

Considering a session as a communication in just one direction, instead of $n*(n-1)/2$ symmetric keys, there would be $n*(n-1)$ symmetric keys, making a total of $2n + n*(n-1) = 30$ keys

Edit for clarification:

The initial question states "each employee communicated with all other employees once"

This could mean two things:

$A$ sends a message encrypted with $symkey_1$ to $B$
$B$ responds with a message also encrypted with $symkey_1$
So $A$ communicated once with $B$ and $B$ communicated once with $A$

Another interpretation:

$A$ sends a message encrypted with $symkey_1$ to $B$
Two days later, $B$ sends a message to $A$ encrypted with $symkey_2$
So $A$ communicated once with $B$ and $B$ communicated once with $A$

The second interpretation will create $n*(n-1)$ symmetric keys, while the first one created only $n*(n-1)/2$ symmetric keys


How terribly flawed is this design for key storage? Dave here, with a plan for storing secrets.

Threat model:

Database and keyfile may (will?) be stored on un-trusted servers.
Database contains many valuable secrets (passwords), encrypted by key stored in keyfile.
Source code is public.
Keyfile and database SHOULD never be stored on the same server, but will always need to be accessible from the client.

Out-of-scope threats:

keylogger, malware, rubber hose, chocolate

Failure mode:

Attacker obtains a copy of both keyfile and database and derives the encrypted key by attacking the keyfile.

Defenses:

keyfile is encrypted with a key derived from a password.
prototype uses bcrypt as the key derivation function.
The high-entropy master password is selected randomly (diceware).
the keyfile has no visible signature/structure -- someone who happens upon it will be unable to distinguish it from from random noise. This is not a big deal, but it adds plausible deniability.

Details

What I am most interested in is whether I am botching the keyfile encryption. The prototype (see https://github.com/scholarly/pynacl/blob/master/examples/bcrypt_wrap.py) is written in python using pynacl and py-bcrypt.

workfactor: 1 byte, default: 8
nonce: 24 random bytes
salt: 32 random bytes
key: 32 random bytes
magic = 24 bytes of sha1(salt+MAGIC+workfactor) [optional, looks random to casual observer]
kek = bcrypt.kdf(password,salt,key_bytes=32,rounds=1<<workfactor)
ciphertext = nacl.secret.SecretBox(kek).encrypt(key,nonce)
keyfile = magic + salt + ciphertext

Questions

Is this an appropriate way to use bcrypt.kdf? (which seems to be  PBKDF2withBcryptHash. I don't know if this is a standard implementation or only used in py-bcrypt)
Is there a problem with using SecretBox instead of a specialized key wrapping cipher?

To begin with, I see four potential problems with your key file.

The work factor (8) is probably too low. If we presume you pick your pass phrase by selecting $c$ words at random from a list of $2^{13}$ distinct words (e.g. correct horse battery staple) you get a pass phrase with $13c$ bits of entropy. (AFAIK the dictionary used by Diceware only barely contains $2^{13}$ words, but I presume it might be extended.) With a work factor $f$ you get an equivalent security strength $s = 13c+f$. A work factor $f=8$ is an odd choice, since it barely saves you of a single word in your pass phrase, to get an equivalent security strength that is greater or equal to your desired minimum security strength.
Presuming your $MAGIC$ parameter is a constant that is hard coded in your public source code, including the $magic$ tag is not consistent with your claim that the key file has no visible signal/structure. SHA-1 is fast enough, to make automatically searching for data that fits your format relatively easy.
There is at least one problem with your output lengths. The output length of SHA1 is only 20 bytes, but your pseudo code seems to pull 24 bytes from it. Also, if the bcrypt implementation you use conforms to the original paper (you seem to indicate otherwise), the maximum output length is limited to 192 bits or 24 bytes and not 32 bytes. Also, even if you use some form of PBKFD2 with bcrypt as PRF, the input length of bcrypt is limited to 56 bytes. A Diceware pass phrase with a minimum of $256-8$ bits of entropy is most likely to be longer than that.
According to the NaCl documentation, SecretBox performs authenticated encryption. This also adds structure to your key file, in the sense that an attacker will only need the key file, not both the key file and the encrypted database, in order to attack your pass phrase. While you don't specify exactly why you intend to put the encrypted key data in a separate file rather than a header of the encrypted database, or what you mean by "plausible deniability", this doesn't seem like a feature that is consistent with your general design.

The purpose of using bcrypt and other slow PBKDFs, is to to slow down attacks on the password, if the attacker should get hold of the cipher text, just enough to give all users an opportunity to change their passwords.

However, from your question it seems as if you intend to store the cipher text on an untrusted server. This means that it is not really a question of if the attacker will get hold of the cipher text. You must assume it has already happened, and that it is only a matter of time before the attacker manages to crack your password.

Presuming you use this scheme, what would be an appropriate usage policy?

Firstly, you have to change the password you use for encrypting the key file, with an interval that equals the time you expect it would take an attacker to crack your password, should the attacker have managed to get access to your files yesterday.
Secondly, as if that is not enough, you also have to change both the database encryption key and all passwords that are stored in the database, with the same frequency you change the password you use for the key file. Reason? Because the attacker only needs one generation of the key file and database pair, to be able to get to the contents of the database in that generation.

Consequently, in order to get this to fly, you really need a passphrase for the key file that contains enough entropy, to cause the password replacement interval to be 10 years or more. This means well above 80 bits of entropy in the pass phrase. Arguably, if you got a pass phrase that is that good, the bcrypt component is probably redundant. The extra bits of security strength you get by using bcrypt, are probably less than the confidence interval for your passphrase strength estimation. IOW, using bcrypt probably doesn't hurt, but you will have a hard time proving that it is necessary to get the desired security strength.


great discovery in the field of elliptic curves cryptography? Prof. Adi Shamir says in The Cryptographers' Panel 2016:

  i think that NSA has made a great discovery in the field of elliptic
  curves cryptography and NSA wants to avoid the increased use and
  growth of ECC, so the NSA's argument of the quantum computer would be a
  smokescreen.

i know that ECC is faster and better than RSA but my questions:

is ECC resistant against quantum computer? i know that RSA isn't!
what could be great discovery? is it on implementation?
professor shamir says that quantum computers aren't risk for cryptography nowadays(in the near future) but i read in internet that the rate of progression in quantum computer is faster than what was predicted for it. am i true?

note:my main question is 2 ;in another words which aspect of ECC can be a great discovery that this aspect is not clear and known for cryptographers? what does professor shamir talk about?

ECC is not resistant against quantum computers.

  Quantum complexity for breaking RSA and ECC are $O(\frac{s^9}{{(\log (s))}^5})$ and $O(s^3)$ respectively. Which $s$ is security level $(80-96)$.

So as SEJPM mentioned in comments, "ECC is less resistant against quantum computers than RSA".

One of newest post quantum cryptographic schemes is isogeny  based cryptography, and best known quantum complexity for breaking such schemes is exponential.

Also scientists believe that nowadays, providing such enormous quantum gates is very hard and may be infeasible . So 'quantum computers aren't risk for cryptography nowadays".


Speeding up the Denning-Sacco protocol? I have started to study cryptography and I have come across Denning-Sacco protocol. I understand multiplicity vulnerability.

My question is why Denning-Sacco protocol choose to generate key on trusted third party and send it to Alice who then sends it to Bob.

Would it not be faster and easier if A could generate key from some randomized variable such as last few key strokes by user or date, time and current temperature or any other such parameters.

The Denning-Sacco protocol is a key transport protocol designed for use over an insecure network. It adds timestamps to the Needham–Schroeder protocol to prevent replay attacks. Rishav Bhowmick, "Denning Sacco Protocol", summarizes the protocol as:

$A \rightarrow S: A,B$
$S \rightarrow A: E(K_{as}: B, K_{ab}, T, E(K_{bs}: A, K_{ab}, T))$
$A \rightarrow B: E(K_{bs}: A, K_{ab}, T)$

The entire point of the protocol is that $A$ and $B$ both need to know a shared secret key ( $K_{ab}$ ), but they don't already have a shared secret key at the beginning of the process – typically because key management is more convenient for Bob to remember and keep secret a single secret key shared between Bob and the central server ( $K_{bs}$ ) rather than a hundred secret keys shared between Bob and the hundred people Bob needs to communicate with.

It certainly would be faster and easier to A to generate a key and send it directly to Bob (skipping steps 1 and 2), but that would be insecure.
After Alice generates a key, there seems to be only 2 ways Alice can send that key directly to Bob:

Send the key Kab encrypted with some other key $Kold$ – perhaps something like $A \rightarrow B: E(Kold_{ab}: K_{ab}, T, etc.)$ – but why? If Alice and Bob already had a shared secret key $Kold_{ab}$, then there's little point to using DS to send another key, and if they don't, then Bob has no way of decrypting that message.
Send the key Kab in $plaintext: A \rightarrow B: K_{ab}$. This allows everyone listening to hear the key $K_{ab}$ and decrypt all the messages between $A$ and $B$ encrypted with that key, and it allows active attackers to inject messages of their choice encrypted with that key that might trick Alice or Bob into thinking the message came from the other.


Block cipher and parity of permutation Can anyone explain the following text passage to me?

  Most real-world block ciphers build even permutations,
  because it's hard to build odd ones using small operations (32 bit)
  on larger (128 bit) block size.

I don't understand the connection between parity of a permutation and small operations.

First of all, we need to review what they mean by "parity of a permutation"; they don't mean whether the input block had a even number of 1's.

Instead, they view the $n$ bit cipher (with a specific key) as a permutation on $2^n$ objects; that is, it can be review as a way of rearranging that set of $2^n$ objects onto itself.

Now, permutations on a finite set of objects has a "parity"; that is, any specific permutation can be generated by a series of exchanges between the objects; there are a large (actually, infinite) number of ways of expressing any specific permutation as a series of exchanges, however if an permutation can be expressed as an even number of exchanges, any other set of exchanges that express that same permutation will also be even; we then say that this is an "even" permutation.  Similarly, if a permutation can be expressed with an odd number of exchanges, we say that this is an odd permutation.

Now, if we perform an even permutation on a set of objects, and then do a second even permutation, the resulting permutation will also be even.  Because block ciphers are commonly expressed as concatenations of round functions (where you first do one round function, then the second, etc), that means that if each round function is even, then the overall block cipher will be even.

Now, what does this have to do with small operations?  Well, most of the obvious ways to use a 32 bit operation within a 128 bit block cipher will result in an even permutation.  For example:

If you use the 32 bit operation on 32 bits of the block in an invertible way, and don't touch the other 96 bits, this will always be even.  AES can be modeled in this way.
If you take a function of some of the block cipher bits (and possibly key bits), and exclusive-or that into the other block cipher bits (Feistal network), this will always be even, as long as you're excluseive-or'ing into at least two bits.  Hence, virtually most Feistal-based ciphers will be even.

Now, just because most operations will be even, it doesn't mean that all operations are.  Here is one that can be odd: if we split the 128 bit block into 4 32-bit tracks $A$, $B$, $C$, $D$, then this operation can be an odd permutation:

A += F(B, C, D, Key)

(where the addition is performed modulo $2^{32}$).  Obviously, that can be a part of an unbalanced Feistel design.

So, if it is possible that we can construct a block cipher with an odd permutation, why don't we?  Well, as far as I can tell, because no one cares.  If the attacker knows that a block cipher is an even permutation, all that means is that if he obtains $2^n-2$ entries in the code book, he can deduce the last two.  Given that he can't really deduce anything more than that, people are content to leave that on the table.


How can I convert numbers into prime numbers? I'm working with one-way accumulators, but I'm not knowledgable in cryptography. Is there an easy peasy way to hash numbers (or whatever) into prime numbers?
Obviously I'd like it to be collision resistant and all that, but this project is huge, I'm alone and I'm confident someone else in the field will pick up from there.
Also, primality tests are linear in n or what?
Thanks

Thank you for your answers but I think I found a better method.

Take the hash of your input $h(x)$, preferably with random oracle approximation
Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
Write to memory: $H(x)=p$

Done!

notes:

The random oracle makes collisions infeasible
Universal hashing gives high density of primes with high probability (there is a theorem out there but the principle is that, for a given prime, I have multiple hash outputs, so the probability that one of them is my input increases. See: Gennaro et al. - Secure hash-and-sign signatures without the Random Oracle, lemma 2)


What is a Trapdoor in Merkle Signature? Merkle signature (pag. 40) use than public key (verification key) the root of the Merkle Tree and than private key (to sign) the set of pre-images of the $g(Y_i)$ where $Y_i$ is the verification key of a choose One Time Signature. My question is What's is a trapdoor between these two keys?

As I already outlined in this answer, hash trees in combination with any one-time signature scheme gives the so called Merkle signature scheme. I assume there is some misunderstanding and therefore I sketch merkle signatures subsequently:

The idea is to produce $n$ key pairs $(X_i,Y_i)$ of a one-time signature scheme and then to take the hash values $g(Y_i)$ of the public keys $Y_i$ (where $g:\{0,1\}^*\rightarrow \{0,1\}^n$ is a cryptographic hash function as described in your reference) and to assign the hash values $g(Y_i)$ to the leaves of a complete binary tree with $n$ leaves.

Then, you recursively compute up the hash tree (by computing hash values of inner nodes as the hash value of the concatenation of the child nodes) and finally as root hash you obtain your "public key" which is then given to a receiver. Let's call this public key $PK$ and observe that this is a "virtual" public key as it is not directly used for signature verification of the one-time signature scheme (I will come back to that soon). The private key is $(X_1,\ldots,X_n)$, i.e., the sequence of signing keys of the one-time signature scheme.

Then, this public key $PK$ allows the verification of $n$ one-time signatures. Each of these one-time signatures is produced using the private signing key $X_i$ of the one-time signature scheme.

Now, the basic idea is that you use signing key $X_i$ for the $i$'th signature and the $i$'th signature for message $m_i$ is composed of:

the signature $\sigma_i$ obtained by signing $m_i$ with the signing algorithm of the chosen one-time signature scheme and signing key $X_i$.
the authentication path $A_i$ in the hash tree for the leave $i$ with label $g(Y_i)$. This path consists of all the siblings on the unique path from the leaf $g(Y_i)$ to the root. This allows you given the public key $Y_i$ required to verify the one-time signature on $m_i$, to recompute the root hash of the hash tree (which is the public key $PK$) and compare it to the public key $PK$ which you received.

A signature $s$ for a message $m_i$ is then $s=(i,\sigma_i,Y_i,A_i)$. Note that when given $(s,m_i)$ and being in possession of $PK$, for verifiying one checks whether:

$\sigma_i$ is a valid one-time signature for $m_i$ under public key $Y_i$
and the recomputation of the hash tree using the hashed public key $g(Y_i)$ (by hasing the public key $Y_i$ from the signature $s$) and the authentication path $A_i$ results in a root hash that is equal to $PK$.

I hope this answers your question and you see that there are no trapdoors involved with $g$ and $Y_i$. Essentially, the hash tree is used to aggregate $n$ public keys of a one-time signature scheme into a single "virtual" public key $PK$. Thus, this public key $PK$ allows to verify $n$ signatures. How the values $X_i$ and $Y_i$ are related depends on the used one-time signature scheme, but has nothing to do with the hash tree.


DES and AES cryptography I have a question that I can't answer:

  A plain text has been encrypted 3 times in a DES method with 3 different keys 56 bit each, after it the text was encrypted for the forth time using a AES method using a 128 bit key, an attacker is planning to decrypt the text using meet in the middle method, how many encryptions and decryption approximately he need to do.

  $2^{56}$
  $2^{112}$
  $2^{128}$
  $2^{168}$
  $2^{184}$
  $2^{240}$
  $2^{296}$

Assuming this is ECB mode encryption, the workload of a known-plaintext meet-in-the-middle attack will depend strongly on the plaintext here.

If the plaintext contains some non-identical 128 bit blocks that partly coincide on a DES-block, the adversary can reverse the final AES encryption with $2^{128}$ AES decryptions work factor. They can then execute a standard meet-in-the-middle attack on 3DES using parallel collision search (easy compared to the preceding step). See van Oorschot/Wiener for details on the techniques used.

If the plaintext consists only of non-identical 64-bit blocks, the adversary can use the same idea (look for collisions of 64-bit blocks in the ciphertext after AES decryption) to at least rule out some AES keys. They should be able to rule out the vast majority of AES keys when the size of all encrypted plaintexts significantly exceeds the birthday bound for a 64-bit block cipher.

If the plaintext is short and does not contain repetitions of DES blocks that are not also repetitions of AES blocks, there may be no better idea than to perform a meet in the middle attack between 3DES and AES using parallel collision search. This should be doable in time about $\approx 2^{212}/(\sqrt{w} m)$ on a machine with $2w$ AES blocks of memory and $m$ processors (see again the parallel collision search paper).


Mix Column of Rjindael In the mix column stage when multiplying the byte  value by 2 the following gives the correct answer. If the MSB of the byte value is 1, then left shift the byte value by 1 bit and then XOR the resultant with 27. What is the logic behind this number 27. How was it arrived at.

It is because the values being calculated are the byte representation of a polynomial in a finite field, and if the polynomial is too large to be in the field it must be reduced.

The reduction polynomial for Rijndael is $x^8 + x^4 + x^3 + x + 1$, which has a byte representation of 0x11b, and after you have shifted the byte by 1 bit, the 0x100 is no longer required so 0x1b or 27 is XOR'd against the value to complete the reduction.


Choosing between RLWE-KEX methods. Recently, I've been researching and implementing a bit of post-quantum cryptography, and I came across two RLWE-KEX algorithm for key exchange.

The first one, which I implement in my software, is the one by V.Singh http://eprint.iacr.org/2015/138 which provides 2 practical parameter sets. I find this one simple and easy to implement.

However, this paper seems to get little attention and few citation compared to NEWHOPE http://eprint.iacr.org/2015/1092 by L.Dacus et al. It provides only 1 set of practical parameters, but seems to get more attention. I remember seeing another stackexchanger recommending it to a fellow, and there are several proposals for improvements out there (although I feel these improvements also apply to the VS scheme back there).

So, should I switch? I do remember NIST saying they don't expect to "pick a winner", so I guess I could stick to my choice. Or is there an inherent advantage within NEWHOPE over the VS scheme?

As NEWHOPE builds its security proof based upon previous works, and that Google has been experimenting with it, I think I should read the paper more thoroughly and hop along.


Negative negligible functions If f(n) is a negligible function, is -f(n) also negligible by definition?
Since
$$f(n) < \frac{1}{p(n)}$$ for all positive polynomials $p(n)$ and for some integer N such that $n > N$

Thus
$$-f(n) < \frac{1}{p(n)}$$

Thanks very much in advance.

Per the standard definition, a negative quantity is always negligible. This does not matter, however, because when a definition demands that a quantity be negligible, that quantity is virtually always non-negative (e.g., a probability or an absolute value).


Send a symmetric key generated by one user to other users (more than two) using a server I am developing a software in which I am using AES for encrypting messages shared in a group.  The key is generated by one user, the admin of the group and needs to be shared with other members. How can I share this key with all other members of the group securely?

Are protocols like Needham-Schroeder, Diffie-Hellman applicable in my case? (I don't know much about cryptography)

PS: Can I encrypt the 'group key' generated by admin using AES, and save it on a server? The other users can request the server for the  encrypted key and then decrypt it. The key used for encrypting and decrypting the 'group key' will be pre-shared (embedded in the software).

The best way is to keep things simple. Once the key has been generated, keep it on the server and make sure only authenticated users can request the key from that location. Make all the clients request the key from the server.