Practical implications of the switching lemma and the counter mode security bound I have some trouble with determining how many times a key can be safely used when using counter mode encryption.
If we, for example, split the IV into two parts, a message counter (nonce) and a block counter. Messages are always of the same length. We make sure that under the same key, the IV is never repeated, and we use AES128 for the block cipher.
The paper ‘A concrete security treatment of symmetric encryption’ tells me that the advantage of an attacker is at most half the security strength of the underlying PRF. Then with the switching lemma, the advantage of the underlying PRF can be bounded by the advantage of the underlying PRP (with AES-128 would be about $2^{-128}$) plus $q^22^{-l-1}$.

Does this $q^22^{-l-1}$ just show that there is no attack that is better than this bound, or does it also give us an attack? And if so, what does that imply?

Is $q$ the amount of queries that is allowed by the oracle and thus, assuming no other leaks, the total amount of cypher calls by my system? Or can the attacker create it’s own oracle like with a brute force attack on the key space?

Is there no time complexity in that part of the formula?

Let’s say I take an advantage bound $2^{-30}$ (very improbable) then I can have $2^{49}$ cipher calls ($1/2^{30} = q^22^{-128-1}$). Any adversary that wants to gain a better advantage has to do an attack on the underlying permutation, something like $2^{97}$ key checks on AES-128 for example.
Does that sound about right?

Does this $q^2 2^{−l−1}$ just show that there is no attack that is better than this bound, or does it also give us an attack? And if so, what does that imply?

The switching lemma is tight up to constant factors. If you make $q$ queries, then you can indeed distinguish between a PRF and PRP with probability at least $0.632 q^2 2^{-l-1}$. Here the 0.632 is $1 - 1/e$. More specifically, this is the probability that you will see a repeated output by a PRF (and obviously a repeated output from a PRP is impossible).
You can indeed attack the IND-CPA security of PRP+CTR with this advantage.

Suppose you ask for $q$ identical blocks to be encrypted. Assuming the IV+counter never repeats, it is not hard to see that there will be no repeated ciphertext blocks under a PRP.

Suppose you ask for $q$ uniformly distributed blocks to be encrypted. Then the ciphertext blocks will be uniformly distributed and therefore display duplicates with the above probability.

  Is $q$ the amount of queries that is allowed by the oracle and thus, assuming no other leaks, the total amount of cypher calls by my system?

In this context, $q$ is the number of calls to the PRP that the attacker induces the honest party to make.


Is there any patent free EC point compression available? If not, should I GPL/LGPL my code? I'm currently using the BouncyCastle implementation in uncompressed mode, and considering releasing an optimized version of EC code that uses point compression.

It appears the only thing limiting me is licensing for EC point compression, since the math seems straightforward.

I'm waiting for a response from the BouncyCastle mailing lists, but would like to solicit feedback from anyone who is more knowledgable and experienced in this area.

Classic affine point compression, storing only the x-coordinate and a single bit of the y-coordinate, is claimed in two different U.S. patents:

US 6,141,420: “The inventors have also recognized that the bandwidth and storage requirements of a cryptographic system utilizing elliptic curves can be significantly reduced where for any point P(x,y) on the curve, only the x coordinate and one bit of the y coordinate need be stored and transmitted, since the one bit will indicate which of the two possible solutions is the second coordinate.” The patent expired in 2014.
US 6,252,960: claiming “1. A method of compressing elliptic curve data which includes X and Y coordinate data, the X coordinate data consisting of N bits and the Y coordinate data consisting of at least 1 bit, using (a) a generator polynomial, and (b) a digital processing computer with at least first and second registers, said method comprising:” The patent expired in 2018 and may have been invalid all along because of the patent above already outlining the idea.

The patents have all expired by now; there is no need to live in fear of point compression any longer.

Daniel J. Bernstein convincingly argued that there was prior art for point compression all along so that we wouldn't have needed to live in fear of the patents in the first place. But considering the patents are all expired now, this is all but irrelevant history. Ed25519, when introduced in 2011, had point compression (recovering the x-coordinate from a y-coordinate), and evidently no lawsuit followed.

Other, more elaborate forms of point compression for Edwards and Montgomery curves have been proposed as well, namely Decaf and Ristretto. They are not only more efficient (a compressed point takes one bit less than the bit length of a full coordinate to represent because only non-negative points are considered valid when decoding), but also guarantee landing on the prime-order subgroup when decoding. They have each been out there for over a year now and no patents applicable to them seem to exist. For the Decaf case, it seemingly spawned from a series of threads on the public moderncrypto curves mailing list in 2014 and the final paper in 2015, so that if a patent were filed, it'd have to take that prior art and discovery process into account; Ristretto itself builds on the ideas in Decaf.


Random oracle : Replay What I understand about the random oracle game:

  The adversary can query the oracle polynomial many times with the same (secret but unknown) key. From the output returned by the oracle, the adversary has to tell whether the oracle has chosen RANDOM or CIPHER (with probability more than .5).

Now, how does that stop adversary from replay attack? Say, the adversary has told the oracle to keep the same key twice. Both the times the adversary queries the with same message. Now, if oracle has chosen RANDOM, both the outputs will be different with very high probability. Whereas, if oracle has chosen CIPHER, both the outputs from oracle will match.

How the safe-guard is given from the trivial attack?

One idea came to my mind: The oracle has an infinitly large memory. Everytime the oracle is queried, it checks if the same input has be supplied previously. If so, it returns an error/ returns a valid output only when the input is not found in its memory. Is this idea meaningful?

As far as I know, the "random oracle game" doesn't exist. What your are speaking (I think) is about pseudo-random functions. And when the challenger (not the oracle) is in the "RANDOM" mode, he could keep in memory the pair input/output, according to previous queries. Then it doesn't need to output "error", he could return the same output as in the previous query.

references:

en.wikipedia.org/wiki/Pseudorandom_function_family

https://crypto.stanford.edu/pbc/notes/crypto/prf.html


Can a digital money system exist, that's secure, anonymous and allows offline transactions? I just read Offline anonymous electronic money systems and their cryptographical base , which asks for anonymous offline systems. The OP claims eCash is such a system, and the answer claims that fairCash is such a system.

I've added security as a third requirement, since an insecure system seems useless to me. When evaluating a system, I assume that the mint/bank can be trusted, but that the persons who transfer the money don't trust each other, and have all hardware that's in their possession completely under control.

Looking at these three properties, it seems impossible to fulfill them all at the same time. In particular I don't see how you could prevent double spending.

The best offline system  I can think of, allows the bank to see the amount of cash flowing from/to a particular person, but only reveals the actual transaction if he double-spends, and then hopes that the double spent money can be recovered out of protocol(for example in court). But I feel like the reduced anonymity and security are worse than requiring online transactions. Edit: It seems like eCash falls in this category.

Depends on what you mean by secure. If you merely want the ability to detect and then presumably punish double spending, you can do that in a way that is secure and anonymous: double spending reveals enough information to provably identify the user. Since honest users don't double spend, they are still anonymous. This is used in Camenisch et al.'s Compact E-cash paper
These systems use techniques related to blind signatures and and similar to anonymous credentials ---e.g. signatures over committed values and zero knowledge proofs about those signatures --- which make it impossible to link the issue of a unit of currency to its spending or the spending of another unit of currency unless it is double spent. As a result, unlike bitcoin, they really are completely anonymous if the cryptographic assumptions hold.
If you mean prevent double spending. No, it's impossible without trusted hardware*. You run up against, among other things, the cap theorem. What stops me from making a clone of my data and executing the same protocol on other ends of the world ( or the galaxy)?
*
As others have pointed out, it might be possible in the quantum setting. Certainly you can make non-cloneable quantum "objects", but its unclear how you would transfer them.  (update) in fact you can potentially do it with quantum knots3


AES encryption using MPC SPDZ protocol I'm reading the article about SPDZ protocol for secure multiparty computation (and also improvements for offline phase like MASCOT).

However I'm thinking about practical application of SPDZ for AES encryption/decryption.

I have the following assumptions:
There are 3 parties $P_1, P_2, P_3$ from which $P_2, P_3$ each has a share to compute AES encryption/decryption, so no party should have knowledge of the whole clear-text AES key. Party $P_1$ has a clear-text, which should be encrypted, and do not want to share its value either.

I believe that I understand the setup correctly. Now, using the SPDZ, there is an offline preparation protocol which should distribute across parties shared secret key $[[\alpha]]$, triples $(\langle a \rangle, \langle b \rangle, \langle c \rangle)$, and pairs of random values $\langle r \rangle$, $[[r]]$. These are distributed to all parties using public key $pk$ and verified using $\Pi_{ZKPoPK}$.

Then in online protocol parties share their inputs $x_i$. And SPDZ can perform addition and multiplication on circuit using shared secrets.

How can the AES encryption/decryption computation be done in MPC? What is the secret AES key and how can the key be shared between 2 parties and have a different party join in the protocol with the plaintext? Should parties $P_2,P_3$ share the key using SPDZ and then party $P_3$ will use its share to see the real clear-text and cipher-text?

I would like to know it from practical point of view, there are many theoretical articles, I do not understand how to implement it in real world.

Ok, so the question is how is AES implemented within SPDZ. I'm going to explain the big picture and then whoever is interested in details should check out the original paper here or the code here.

Let's start with the setup: running the AES algorithm requires a 128-bit key $k$ and a 128-bit message $m$. In the generic SPDZ setting $k$ and $m$ are going to be additive shared across the $n$ parties: $k=\bigoplus_{i=1}^n k_i, m=\bigoplus_{i=1}^n m_i$. Namely no one knows the key or the message but they can reconstruct $k$ and $m$ if all parties broadcast their shares.

In your case $P_1$ sends random shares of $m_2, m_3$ to $P_2$ and $P_3$ and fixes $m_1 = m \oplus m_2 \oplus m_3$. Then $P_1$ can set its $k$ share as $k_1 = 0$ since the other parties $P_2, P_3$ can reconstruct the key using $k_2$ and $k_3$.

Next question that comes in mind is in which field must the shares live in. Since the cleartext computation of AES is performed on blocks of size $8$ the authors choose to have $k$ and $m$ split into $\frac{128}{8}$ blocks of $8$ bits. Now parse each share $k_i,m_i$ as $16$ blocks of $8$ bits each where each block lives in $\mathbb{F}_{2^{40}}$.

It's good to keep in mind that on secret data $[x]$:

Linear operations: $z = [x] \oplus [y]$ or $z = [x] \cdot y$ are for free - just local additions or multiplications by scalars.
Multiplications: $[z] = [x] \cdot [y]$ require special pre-processing data as Beaver triples and involves some data sent around between the parties.

Assume there is an embedding $f$ which converts $x \in \mathbb{F}_{2^8}$ to the same element $x$ but in a different field: $\mathbb{F}_{2^{40}}$. Similar for $f^{-1} : \mathbb{F}_{2^{40}} \mapsto \mathbb{F}_{2^8}$. If we have an embedded key and a message: $[f(k)], [f(m)]$ the AES algorithm in MPC looks like this:

ShiftRows, MixColumns, AddRoundKey come for free since they involve additions or multiplications by public scalars - check wiki.
SubBytes where we do $\mathsf{SBox}(x)$ involves first extracting the embedded bits from $\mathbb{F}_{2^{40}}$ by applying $[y] = f^{-1}([x])$, perform $[y^{2^k}]$ by bit-decomposing and shifting bits and then apply the embedding again on $f([y^{2^k}])$ to be able to multiply the squares in $\mathbb{F}_{2^{40}}$.

More details on: given a shared input $[x]$ how can we compute a share of $[\mathsf{Sbox}(x)]$? One can expand the Sbox in polynomial form and compute $[x] \mapsto [x^{254}]$ using Section 4.2 in the paper. To perform $[x] \mapsto [x^2]$ we can bit-decompose $[x]$ and then just move secret bits around to obtain the squaring $[x^2]$ - think how squaring happens in a characteristic two field.

All nice and neat: we can perform squarings (almost) for free by doing a bit-decomposition. Now the troublesome part comes when we need to multiply squarings according to section 4.2 such as $[x^2] \cdot [x^4]$. This is where the embedding $f$ comes into play to allow us to multiply $\mathbb{F}_{2^8}$ elements inside a bigger field $\mathbb{F}_{2^{40}}$.

You might ask: What's the magic that tells us how to construct an embedding $f$? Well, basically just a bit-decomposition and some bit shuffling.

I have skipped some details but I hope you get the gist: embed data to multiply stuff in a larger field, invert the embedding to obtain cheap squarings (or any bit-wise manipulation easier). The implementation uses the approach I told you here with some extra optimizations for switching back and forth between embeddings.


How to store encrypted solutions of a find location game? I'm coding a bot on Telegram to sustain a quiz game.
A group of people (authors) can upload photos of streets or particular landscapes that they have found on internet, without any description, and have autonomously work out the exact location they were taken.
So along with one photo the author has to enter the cordinates with a tolerance.
The bot stores this info and anyone (other authors included) can try to solve that photo.
Haversine formula is used to calculate distance between an attempt and the solution. A distance less than the tolerance yields a correct answer.

Anybody but me can access the .txt file with all the solutions. Of course I'll be honest, but how can I ultimately prevent myself from look into this file and use the solutions?

Hash encryption won't work because, obviously, answers are not expected to match the stored coordinates. Any pair of coordinates close enough has to be accepted.

There is the idea of a fuzzy vault, a coding theory based idea first proposed by Juels,
developed for biometric applications, it warrants a look.

Start at Wikipedia. These notes below are excellent:

https://wiki.cse.buffalo.edu/cse545/content/fuzzy-vault


Elliptic Curve Cryptography Point Arithmetic Libraries Are there any libraries out there that perform ECC point arithmetic:adding,subtraction whether it be in C for micro controllers for VHDL for fpgas? Or to go further any libraries that perform ElGamal encryption/decryption?

Here is a github repository link with which you can implement ECC arithmetic
and a research paper which gives you some idea on how to implement a software library for ECC

Hope this helps !


How to change hash checksum of a text file without changing the contents in the file I have created a text file called test.txt and the content of the file is Hello World
I would like to change the SHA checksum hash without modifying the contents and filename. Is there any way to do that without using any third party tool on the internet.

Hash functions are deterministic, same input same output. Without a modification, you cannot change the result.

The hash of a file is used at least for the integrity check. If you were able to change it without modification the integrity check will have problems.

Note: as mentioned by Ella Rose in the comments if a keyed-hash message authentication code HMAC is used then changing the key will result in a different hash-based message authentication code.


What is the advantage of XTS over CBC mode (with diffuser)? I have some problems in understanding the "advantage" of AES-XTS compared to CBC with diffuser.

I read something about FileVault, in this paper they mention the two modes of operations XTS and CBC (with diffuser) and the advantages of XTS.

Both modes encrypt data units almost the same way. For CBC, the sector number is somehow used to build the IV, for XTS, there is a "tweak value", which also includes (somehow) the block offset, so each data block can be encrypted independently (makes sense when encrypting harddrives/partitions). I cannot really see the advantage of XTS.

Now, they write the following about XTS:

  There are several advantages over alternatives such as AES in CBC: there is no requirement for an initialization vector (the tweak key can be derived from the block number); each block is encrypted differently (since the tweak value will be different); and unlike AES-CBC, AES-XTS prevents an attacker from changing one specific bit in a data unit by xor-ing each AES input with a different shifted version of the encrypted tweak.

Maybe they just compare XTS against CBC (without diffuser)... if so, does anybody know any advantage of XTS?

And can somebody explain the second advantage: "AES-XTS prevents an attacker from changing one specific bit in a data unit by xor-ing each AES input with a different shifted version of the encrypted tweak."?

XTS vs. Undiffused CBC. The issue here is malleability. Both XTS and CBC prevent an attacker from learning information about encrypted data. However, neither one completely succeeds in preventing an attacker from tampering with encrypted data.

However, it's arguably easier to tamper with an (undiffused) CBC ciphertext than it is to tamper with an XTS ciphertext. Let's say that an attacker happens to know some message says

  "blah blah Give Alice \$400 ... blah blah blah".

If this message is encrypted using CBC, the attacker can tamper with the ciphertext in such a way that it will now decrypt to

  "blah blah !^%@^^ Give Alice \$800 blah blah blah"

The \$400 has become \$800. This is what your quote about "AES-XTS prevents an attacker from changing one specific bit in a data unit" refers to. Here I write !^%@^^ to indicate that the previous 16-byte block will become gibberish once decrypted, and this gibberish will be beyond the attacker's control.

On the other hand, using XTS prevents this attack. The attacker can corrupt a message by turning any 16-byte block into random gibberish, but he will not be able to have the same degree of control as he did in the CBC example.

But Microsoft decided not to use XTS anyway. The reason is that the ability to corrupt a 16-byte block could still be damaging. Here's the quote from the paper dchest linked:

  For example, there could be
  a configuration file (or registry entry) with a value that, when set to 0, creates a security
  hole in the OS. On-disk the setting looks something like "enableSomeSecuritySetting =
  1". If the start of the value falls on a 16-byte boundary and the attacker randomizes the
  plaintext value, there is a $2^{16}$ chance that the first two bytes of the plaintext will be 0x30
  0x00 which is a string that encodes the ASCII value ’0’.

(This quote is referring to the LRW tweakable cipher, but the XEX tweakable cipher used in XTS has the same problem).

Adding a diffuser. Using a diffuser is Microsft's solution to this problem. The idea here is to "mix" the plaintext up before encrypting it so that an attacker can't change \$400 to \$800 --- meddling with part of the ciphertext will change almost the entire plaintext, not just small parts of it.

This sounds good, but there's a catch: No one actually knows if Microsoft's diffuser actually is secure. To my knowledge, it hasn't received any published formal analysis from cryptographers. This means you should be skeptical about relying on it. Microsoft acknowledges this:

  On the disadvantage side, the diffuser is a new unproven algorithm, and this inevitably
  leads to questions. Without extensive public scrutiny and analysis of an algorithm, there
  is a justified skepticism about its security. People are reluctant to trust new algorithms.
  So why did we choose this option anyway? In our final analysis, we decided this was the
  better choice for our product. The performance gain over the alternatives was important
  enough to outweigh the disadvantages of a new diffuser algorithm. Time will tell whether
  we made the right choice.

The bottom line.
XTS is less malleable than undiffused CBC. However, CBC+Diffuser is probably less malleable than XTS, at least for practical purposes.

An important aside.
Neither CBC nor XTS were designed to be non-malleable. Ensuring that ciphertexts are not tampered with is a separate problem, one that should be solved by using Message Authentication Codes (MACs), such as HMAC-SHA256. The reasons MACs aren't typically used for full-disk encryption algorithms are (1) performance issues and (2) using a MAC requires storing extra information with the ciphertext, which makes adding it transparently a bit tricky.

A middle ground between MACs and diffusers would be to use a wide-block encryption mode, such as CMC, EME, or HEH. You can think of these as having a "built-in" diffuser, that makes them non-malleable. Unlike Microsoft's diffuser, these algorithms have formal security definitions and peer-reviewed mathematical proofs. They are secure under the assumption that AES is secure. Microsoft opted not to use these because of (1) performance issues and (2) patents.


What should I think about these unique certificate serial numbers I  was looking at the serial numbers of the certificates for www.google.com and wordpress.com.  Wordpress was listed by openssl as:

04:0B:D4:F8:25:88:C5

This serial is listed as the serial for both my specific wordpress.com domain and for www.wordpress.com.  A google search using the serial number as a keyword shows only my wordpress.com domain (because I pasted the serial number into one of my pages) in the results.  I would expect to find  other hits on Google.

The site www.google.com was listed by openssl as:

5F:BB:FC:7C:4C:6E:FF:92

That serial number, in a google search, showed up with only two listings, mine (Because I again pasted the serial number into a page) and cryptostorm.org.

I would think these numbers would have been put on the google search engine, and yield (probably) many hits.

@cpast:  I'm not downvoting your answer, but I need a better one.  I can see that google indexes the serial numbers and that is obvious if you type or copy the serials I've provided (above) into the google search bar. Using fingerprints as a search term, I can normally see many items in a search result.

And - I know people often cut and paste whole certificate info pages from Firefox, and put them into forum posts, where they ask "What's this?" or "Why's this?"

Additionally, the statement that nobody cares seems silly. One of the first items in the certificate is the serial, and certificate revocation lists are indexed by certificate serial numbers. Those serial numbers are very important.  Your answer seems trollish.  Anyone else?

@SOJPM: Serial numbers are unique within a CA.  This serial number (e.g. Wordpress) - is supposedly used by hundreds of thousands of Wordpress associated domains.  It should have google indexed data associated with it. Unless I have a "special" one.

@cygnusv: No offense taken.

@all: Why can I edit cpast's comment? I'm new to stackexchange.  Seems odd.

@SOJPM: Thanks, and yes that's what I meant.

@truthserum:  Here's the expiry:

issued  on            : 2014-04-14 18:09:05
  expires on            : 2015-10-14 11:29:26

So, it's been around awhile (if what I see is valid) and should have been the cert for a lot (millions?) of users.  I'm not sure how many users WP has.

Maybe someone else can dump the cert or look at the Firefox Cert GUI - and see if the serials match what I have?

I would think these numbers would have been put on the google search engine, and yield (probably) many hits.

This assumption is wrong. Certificate serial numbers are not indexed by common search engines, nor are they typically posted to any HTML site. Frankly, I'm not sure why you would assume they'd be indexed.

The Wordpress certificate is used for all Wordpress domains; it is for *.wordpress.com (matching all subdomains of wordpress.com), and has wordpress.com as an alternate name (so it also works there). The Google certificate you list is only used for www.google.com; it is again something that commonly shows up (Chrome reports a different certificate for some reason).

The reason you don't find any posts about them on Google is that no one really cares.


Does this chat protocol exist? I want to implement a secure chat via mobile. I´ld like to know if the following protocol for key agreement – which can use any asymmetric encryption – exists.

Suppose Alice and Bob are two clients of the app. For this they have to register their public keys in a server:

Alice generates her public and private keys (pub_A, priv_A).
Alice sends pub_A to a public server.
Bob generates his public and private keys (pub_B, priv_B).
Bob sends pub_B to a public server.

Suppose A want to send a message m to B using AES:

The server generates a random symmetric key key_AES and encrypts it using pub_A and pub_B. Then it sends the encrypted key to Alice and Bob respectively.

Does this (chat) protocol for key exchange exist?

I don't know of any chat protocol that would use this approach.

I get it from your question that once the symmetric key is established, Alice and Bob communicate directly using it and that it is not an issue that the server, if malicious, can defeat any security achieved by this.

However, it appears to me that your protocol suffers from a major problem, namely the fact that the server itself is not authenticated in any way. That means that an adversary with control of the network could impersonate the server, which by design knows the secret symmetric key Alice and Bob would be using.

Alice and Bob also never authenticate each other and rely on the lower layer and the supposingly secure shared key to communicate, so they may be impersonated very easily in such a scenario.


Is there a LWE based public-key encryption scheme which is CCA1-secure? Is there a lattice based PKE which is IND-CCA1 secure? Actually I am only familiar with LWE and SIS. So I want to know that what the IND-CCA1-secure LWE based PKE scheme looks like?

Yes. You can see Micciancio's annotated bibliography for some relevant papers (including generic transformations from CPA security to CCA security in the random oracle model). If you want to see "actual" schemes which are CCA1 secure, Kyber is a CCA2-secure KEM with security based on a variant of LWE over "Module Lattices", which can be viewed as a slight generalization of R-LWE.


Key length and message length in AES and perfect secrecy if plaintext length <= key length As I understand it, a plaintext encrypted using a One Time Pad is uncrackable because all possible plaintexts of the same length are possible. As a concrete example, if you decrypt the first 3 bytes of a 4-byte plaintext that you know is in English and get "HEL" (and you knew that was correct somehow), that does not help you decrypt the final byte. It is equally likely that the plaintext is "HELO", "HELP', "HELL", etc. and there is no way for you to know which is correct.

What is the concrete step(s) of AES (or a similar popular symmetric key encryption algorithm) that makes encrypting an n-byte plaintext with an n-byte key not the same as a One Time Pad?

It feels intuitive that if the key is shorter than the plaintext, then all plaintexts cannot be possible regardless of the algorithm. The other way around (key longer than the plaintext) is not intuitive.

Block ciphers, AES is a block cipher, encryption $Enc$ can be formalized as

$$Enc:\mathcal{P} \times \mathcal{K} \to \mathcal{C}$$ where $\mathcal{P}$ is the plaintext space, $\mathcal{K}$ is the keyspace, and $\mathcal{C}$ is the ciphertext space. Similarly the decryption; $$Dec :\mathcal{C} \times \mathcal{K} \to \mathcal{P}.$$ For a block cipher the $\mathcal{P} = \mathcal{C}$. The number of elements of this space is determined by the bits, for $\mathcal{P}$ it is determined by the block size. AES has 128-bit block size and it has $2^{128}$ message space for a single block. For DES it is $2^{64}$. AES has variable key sizes like 128,192, and 256, therefore, the keyspace $\mathcal{K}$ is $2^{128},2^{192},\text{ and } 2^{256}$, respectively.

We require the operation of a block cipher invertible[*] so that we can decrypt. Therefore the block ciphers are permutations. Each key from the keyspace selects a permutation for all possible permutations. The number of permutations of the message space is $2^b!$ where $b$ is the block size and for AES this is $2^{128}!$. With the Stirling's approximation $$2^{128}! \approx \sqrt{2\pi 2^{128}}(\frac{2^{128}}{e})^{2^{128}}.$$ That cannot be covered by the tiny keyspace  $2^{128}$, tiny according to comparison, but huge for any classical computational power.

We expect that a block cipher behaves like a Pseudo-Random Permutation that is a function that cannot be distinguished from a random permutation and AES has believed to be one.

Back to your questions;

  What is the concrete step(s) of AES (or a similar popular symmetric key encryption algorithm) that makes encrypting an n-byte plaintext with an n-byte key not the same as a One Time Pad?

Block ciphers use the confusion diffusion paradigm, Shannon 1945. Here, what related to your approximation is, changing one bit of the key will affect all ciphertext bits. If the cipher achieves the avalanche effect property then it will randomly flip half of the bits. Therefore all of the bits of the block are affected  (affected doesn't mean changed) whereas in OPT changing one bit only affects one plaintext bit.

  It feels intuitive that if the key is shorter than the plaintext, then all plaintexts cannot be possible regardless of the algorithm. The other way around (key longer than the plaintext) is not intuitive.

It is not all of the plaintexts, it is all of the permutations. In AES. all of the 128 bits are valid plaintext and plaintext space contains all. But block ciphers randomly select permutations from all possible permutations space. With the keyspace, we cannot cover all of the permutations. They are limited to keyspace.

This the distinction between the OTP and AES or any block cipher. In block ciphers, the key size is fixed no matter the length of the plaintext. In block ciphers, We use computational security since we cannot achieve informational security without key bits equal to message bits.

  If the question is if the key is as large or larger than the plaintext, then why can AES be distinguished from a perfect cipher?

There is no guarantee that given a ciphertext $c$ decrypted under all possible keys $c=AES_k(x)$ gives all possible plaintexts or gives all but they are equally distributed. This is contradicting to perfect secrecy that OTP has.

To prove that AES has perfect secrecy in this sense, we need to fully analyze the AES. This is beyond our computation point. If possible, it may lead to a known-plaintext attack.

While it is reasonable property of a block cipher that reaches all possible plaintext, equally, most block ciphers try to approximate random permutation where each key is independent of the others. This means that we may not reach all plaintext with decryption of $c=AES_k(x)$ under all keys. Or similarly, possibly there are plaintexts where $E_{k_1}(c)=E_{k_2}(c)$.

[*] Block cipher need modes of operation, and not all modes require decryption, like CTR mode. In CTR mode, one can use Hash functions that are not permutations.


AES difference propagation when does active S box count reduce in AES difference propagation?
what is the relationship between active S-boxes and MixColumns?
can you please explain it with an example?

The answer to the second part of your question:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

So the number of active Sboxes is at least five.

See the answer to this question
and the following link for more details:


Why do we use (pseudo) random permutations and not (pseudo) random functions for en- and decryption? Why do we use pseudo random permutations and not pseudo random functions for encryption an decryption?

We do use PRFs for encryption and decryption!  We use them as stream ciphers to generate one-time pads.

For example, with the ChaCha20 stream cipher, the encryption of the $n^{\mathit{th}}$ message $m$ in a conversation is

\begin{equation*}
  \operatorname{ChaCha20-Encrypt}_{\;k}(n, m) = m \oplus p,
\end{equation*}
where $\oplus$ is xor, and the pad $p$ is generated by
\begin{equation*}
  p = \operatorname{ChaCha20}_{\,k}(n \mathbin\Vert 0)
                \mathbin\Vert
                \operatorname{ChaCha20}_{\,k}(n \mathbin\Vert 1)
                \mathbin\Vert
                \dots.
\end{equation*}

$\operatorname{ChaCha20}_{\,k}$ is the ChaCha20 core PRF under the key $k$.

Likewise for the AES-CTR stream cipher, but we use the PRP $\operatorname{AES256}_k$ approximating a PRF instead of the PRF $\operatorname{ChaCha20}_{\,k}$ to generate each block of the one-time pad.  In all cases with this pattern, decryption conveniently turns out to be exactly the same procedure—which is a bonus for AES, because $\operatorname{AES256}_k$ is usually faster to compute than ${\operatorname{AES256}_k}^{-1}$, the latter of which is unnecessary to use in AES-CTR.

N.B.: If you're thinking about doing this in practice, please use it responsibly in an authenticated encryption scheme like crypto_secretbox_xsalsa20poly1305 or AES-GCM, not alone, unless you're very carefully designing an exotic protocol.


Calculate private key from public key and r I watched this video where somebody finds bitcoin wallet private keys using only the "sigR" value and the public key using a python script named "formula".
How does this work and does converting the values to decimal help somehow?

The short answer is that it doesn't work.
Bitcoin uses ECDSA signatures. An ECDSA signature is comprised of two numbers $r$ and $s$.
It is impossible to recover the private key given only a signature made with this private key and the public key.
The security of ECDSA hinges on a secret value used during the signature process, usually written $k$: this value must be fully random and must be kept secret (it's thrown away after calculating the signature). It is possible to recover the private key given two signatures and the public key if the two signatures were made in a buggy way that uses the same value of $k$. More generally, even if exactly the same value of $k$ is not repeated, if there are biases in the generation of $k$, it may be possible to recover the private key given enough signatures.
Another way to break the security of ECDSA can be to observe the signature process and exploits flaws in the implementation of ECDSA, such as side channels. Breaks of cryptographic algorithms are extremely rare, but breaks of cryptographic implementations are common.
None of this is happening in the video. This video does not show any kind of cryptographic or security flaw.
The video shows someone copy a bunch of values which they say is a “private key”, then take an ECDSA signature, pass it to a program that they don't understand, and get out a value which they claim is a “private key”. There is no information about what that program does.
Whoever made this video is taking a long time just to convert between hexadecimal and decimal notation, which is a trivial detail that can be handled in a fraction of a line in Python. They clearly don't know the first thing about Python, otherwise they'd be able to modify the script to use a more convenient input/output format.
This video has zero technical interest or novelty. Given that it's cryptocurrency-related, it's probably part of a scam. The author is presumably trying to convince naive people that they know something the audience doesn't, but given how incompetent the author is, they're really aiming for the bottom of the barrel. Which is the best target when you're trying to scam people.


What consequences do the plaintext space size has on the performances in the BGV scheme? In the BGV paper [1], the authors say in §5.4 that you can have $\mathbb{Z}_p$ as plaintext size with a large $p$.

What is the impact of the size of $p$ on the ciphertext size and computational work of the cipher's algorithms?

I would need this to decide how big my plaintext space can be before it becomes impractical.

References

[1] Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) Fully Homomorphic Encryption Without Bootstrapping.” In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 309–25. ITCS ’12. New York, NY, USA: ACM, 2012. doi:10.1145/2090236.2090262.
http://eprint.iacr.org/2011/277

A helpful resource to assess which ring-based FHE scheme (like BGV) would work best for you, see here: https://eprint.iacr.org/2015/889

In this paper they compare four schemes: BGV, FV, NTRU, and YASHE.

The reason I point you there is that one major factor in the performance of these schemes is the value of p. If a large p is used, BGV outperforms the rest. If a small p is used, YASHE wins, but not by too much. The other main factor is the L parameter.

The metric they use to compare them is the ciphertext size, which is crude but gives a rough estimate as to the computational time needed.


What is the recommended format/notation for crypto design? Is there a recommended format or formal notation for documenting the combination of symmetric and asymmetric encryption, key derivation and other algorithms (and their inputs and outputs) that I think meet the needs of the software I'm contributing to the design of?

At the moment we're blithely using statements like "Encrypt with AES, reusing K1 with a fresh IV" - but of course that statement misses out details such as mode of operation, that I would certainly realise later, but wouldn't have initially written down in the design.

My goal is to document the design in a way that can be understood by other developers (with maybe a similar or better skill level), and to show all the system states, the movements between them and the encrypted/signed/etc messages that cause that - and perhaps eventually to use in a request for outside review.

As background, I have done a single undergrad cryptography course - I imagine this is the kind of thing covered later on, or in a more focussed degree?

TL;DR: Find the most important specification that is of the same type as the one you want to write and use its style for yourself, chances are, other people also have read it.

There is a myriad of ways to specify a crypto protocol / design.

However, there are four things that you really should take into consideration when writing a crypto-related specification.

The most important one first: Fancy pictures. A good picture (as in: a colorful graphic or even ASCII art) says more than a thousand words and can greatly help people quickly understand the essentials of what your protocol is all about. Examples of ASCII art can be found in the actual TLS specification and fancy picture can be found outside of that.
Data Encoding: ASN.1. If you want to submit data with your protocol, you need some structure within it and for notating structured data, nothing beats ASN.1 in terms of being deployed and well-understood. You should really consider using ASN.1 for specifying data structures, to which you only need to apply primitives afterwards (like "sign it!"). Don't forget to define encoding rules (like BER and DER) though. An example for an extensive use of ASN.1 would be CMS, the basis of S/MIME.
Protocol summary: The Handbook of Applied Cryptography (HAC) style. While fancy pictures are valueable, a written out summary is also very valueable and I in my experience the HAC does a really good job at writing them down. It consists of four parts: a) write down the TL;DR of the protocol, e.g. what does it do? b) write down the setup phase of the protocol c) write down the protocol messages as can be seen on the wire (encoding is implicit here, possibly using $\LaTeX$) and d) write down the protocol actions happening between each step. This summary should give everybody a good oversight, of what is done when and the notation also allows you to associate keys, IVs and other things with specific function calls. As a bonus for this method: Many serious cryptographers have read the HAC or have a copy of it very close at all times. Protocol 12.20 is an example for this style (PDF).
The details: The TLS specification style. When you want somebody to review / implement your full specification, this person likely has some experience in doing such things and usually usually has read the TLS specification at some time before, so using its notation is a no-brainer. Additionally, TLS also deals with a bunch of keys and the specification is clear enough to distinguish what to use when, by using things like digitally-signed struct.


Why is D_K only required to be infeasible to derive from E_K for almost every key K? In DH76 'New Directions in Cryptography', it states that

  3) for almost every $K \in \{K\}$, each easily computed algorithm equivalent to $D_K$ is computationally infeasible to derive from $E_K$

($E_K$ and $D_K$ means an encryption and decryption algorithm with key $K$, respectively.)

Then, why 'almost every', and not just 'every'?

As pointed out in the comments, this allows for a small and negligible number of weak keys which can be avoided.

Let us not forget that this pioneering paper was published before any examples of public key cryptosystems were known in the open literature. The authors took the astute position that if good cryptosystems were discovered, a few weak keys should not rule such algorithms out of contention for publication, analysis, and possible improvement.

Furthermore, from the theoretical point of view, one can sometimes prove strength of cryptosystems, for almost all keys, or for almost all choices of some design parameter, especially for randomized cryptosystems.


Hashing entropy with only 128 bits of internal state I am looking to implement the Fortuna algorithm (https://www.schneier.com/fortuna.pdf) on a system with very restrictive memory constraints, using AES-128 as the underlying cipher.

As the key size is only 128 bits, using a 256-bit entropy pool hashing algorithm to maintain each pool would seem to be excessive (and a waste of memory).  I would like to use a hashing algorithm for which I only need to maintain 128 bits of state information for each pool.  Given this, I have a couple of questions:

Would it be possible to use something like SHA-256, but only save (and restore) 128 bits of the internal state between invocations?  Would this somehow risk losing entropy in the process, or produce other undesirable effects?

Alternately, the crypto library I'm using also supports MD5, which does only require 128 bits of internal state.  Would it be better to use MD5 for this application, despite its potential weaknesses compared to SHA-2 hashes, or would SHA-256 be stronger, even when maintaining only half its internal state between calls?

Use SHA-256. Truncating the hash does reduce its collision resistance, but you can't "lose entropy" if you're only keeping 128 bits in each pool anyway.


Why are iterated substitution-permutation product ciphers only used on fixed-size plaintext blocks? Another way to ask this question: when block ciphers were invented, why did they add the restriction that the block cipher would be restricted to blocks of a fixed size?
From my laymen's point of view, I don't see why rounds of S-box and P-box operations couldn't be performed with inputs of variable size.

Let us begin with what is a block cipher;
A block cipher is a family of permutations $$F:\{0,1\}^\ell\times\{0,1\}^b \to\{0,1\}^b$$ where $\ell$ is the key lenght and $b$ is the block size ( DES has 64, AES has 128 bit block sizes). From the key space $\mathcal{K}$ with $2^\ell$-size, a block cipher with the given $k \in \mathcal{K}$ selects one permutation form all possible permutations from $\{0,1\}^b \to\{0,1\}^b$. That makes at most $2^b!$ permutations. With the Stirling Formula
$$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}$$ if you plug some numbers like AES-256 you will see how small the keyspace is compared to number of possible permutations;
$$2^{256}! \approx \sqrt{2\pi 2^{126}} \bigl(2^{256}/e\bigr)^{2^{256}} \!=  \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \gg 2^{256}$$
Still what we want from a block-cipher like AES that they are a Pseudo-Random Permutation (PRP), not distinguishable from a random permutation. No one is able to show a distinguisher for AES yet in more than 20 years and no-one is able to prove it. We strongly believe it is a PRP.

Why are iterated substitution-permutation product ciphers only used on fixed-size plaintext blocks?

The substitution (Sbox in AES) can be used to design a larger block size, however, when you changed the block size from 64 to 128 bits you need a new permutation. Besides, for a better design, you will need to change the substitution, too.
When block size increased more and more, the control of diffusion (MixColumns+ShiftRows in AES) will be harder, too.
The above are some theoretical aspects of such design. There are other problems with the software and hardware. You need to implement many different sizes for software and hardware. This will increase the cost and area. Besides, in the hardware, we want small designs to reduce the area size and reduce power consumption. Even using the CTR mode removes the decryption implementation of the block cipher.
Although one possibly easily implement these in software, the problems are multiplied. You need to provide countermeasures for each implementation against the side-channeled attacks. The same applies to the hardware, too. Yet we are not perfectly able to do one, we will face multiple problems. See AES side-channel attacks, including the cache-attacks on AES.
Instead, it is better to design one with a fixed block size so that we can analyze it with more concentration. There is a nice post about the block cipher analyzing methods;

What are recommended, general strategies to start block-cipher design and/or analysis?

We can use a block cipher with various modes of operation to achieve the goal of encryption of large messages up to a limit, of course. I'll not list all of them here, each has pros and cons. Some to be mentioned

the CBC mode is a chaining based mode that uses padding to achieve encrypting the long messages. You need to be careful about selecting the key uniform randomly, selecting an unpredictable IV, and applying an HMAC to authenticate against the bit flipping attacks and padding oracle attacks when possible.

The CTR mode is a counter bases mode that turns a block cipher into a stream cipher, Instead of listing all pros and cons please read here;Disadvantages of AES-CTR?. In your case, the CTR mode doesn't need padding at all, one can encrypt arbitrary long messages ( not that so long, CTR designed for PRF when using a PRP be careful).

With the above modes you can only achieve CPA security and in modern cryptography, we require more than that. One should use Authenticated Encryption modes (AE) ( and possibly with Associated Data (AEAD)), like AES-GCM and ChaCha20-Poly1305. You will achieve more than CCA (AEAD > CCA). Each has pros and cons,

What are the rules for using AES-GCM correctly?

Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes?
The one real problem with these two modes is the reuse of a (key, IV) pair. Both modes have an extension;

AES-GCM-SIV: The SIV Mode of Operation for
Deterministic Authenticated-Encryption (Key Wrap) and
Misuse-Resistant Nonce-Based Authenticated-Encryption

Daence: Salsa20 and ChaCha in Deterministic Authenticated Encryption with no noNCEnse

Arbitrary block sizes are also problematic if the block size is less than 128. There is a nice page about this, see

Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN

Another solution for your case the stream ciphers, they are designed to fast and can encrypt for large block sizes. They doesn't need paddings and they are encryption bit-by-bit or more in some designs.

Another way to ask this question: when block ciphers were invented, why did they add the restriction that the block cipher would be restricted to blocks of a fixed size?

The above reasons, especially the design and implementation. This will be more clear if you consider that during that age, people hadn't advanced as today. And the time showed that some decisions were right.

From my laymen point of view, I don't see why rounds of S-box and P-box operations couldn't be performed with inputs of variable size.

Hold on! they are not magical tools that like in LEGO that you may replace a 2x8 block with 4 2x2 blocks. Even there in some places, the structure will fail!
Each variation in the design needs to be designed, analyzed, and needs good implementation.


Zk-Snarks vs Homomorphic Encryption I have been reading a bit about encryption algorithms. I have come across these two algorithms.My use case is the ability to work with encrypted data and my data will be string data. I see that homomorphic encryption works with only numeric data.

I have read that homomorphic has scalability issues as it creates a 100x increase in encrypted data.

Does one have to use zk-snark along with homomorphic encryption or one of the two can be used?

Which one to use for which use-cases?

I am simplifying greatly, maybe someone else can provide a
more formal answer.

  I see that homomorphic encryption works with only numeric data.

There are many ways to encode strings into integers,
you can encode a string into bytes and then translate these bytes to an integer.

  I have read that homomorphic has scalability issues as it creates a 100x increase in encrypted data.

Homomorphic encryption indeed comes at a price both in size of the ciphertexts and efficiency of the computations.

  Which one to use for which use-cases?

ZK-SNARKS

ZK-Snark is a zero-knowledge proof-of-knowledge: One party, the Prover, knows a secret and wants to convince another party, the Verifier, that a statement involving the secret is true, without revealing the secret.

Example: A user knows a password $x$ and a server knows a hash of the password $h$, the user needs to prove the statement:

I know a value $x$ such that $H(x)=h$

Homomorphic encryption

Homomorphic encryption is type of an encryption scheme: A value $x$ is transformed into a ciphertext $c=Enc_k(x)$ using a secret key $k$, such that $c$ doesn't reveal anything about $x$ without the key.

We say that such a scheme is homomorphic for a specific operation (I will design it by $\cdot$) if given $Enc_k(x_1)$ and $Enc_k(x_2)$, one can compute
$Enc_k(x_1\cdot x_2)$ without decrypting the ciphertexts.

We say it is fully homomorphic, if given encrypted inputs
$Enc_k(x_1), \dots Enc_k(x_n)$, one can compute for any arbitrary function $f$, the value $Enc_k(f(x_1,\dots, x_n))$ without decrypting the ciphertexts.

Use case: We know some secret value $x$, and want the value $f(x)$. Since $f$ is too computationally intensive, we need to delegate it to a worker (e.g. a cloud server) with more resources.
To avoid revealing $x$ to the worker, we can send $Enc_k(x)$ to the worker, which computes $f$ via homomorphic computations, and sends back $Enc_k(f(x))$. We can then decrypt $f(x) := Dec_k(Enc_k(f(x)))$.

Comparison

Zk-snarks are usually used when the computation is realized by the party holding the secret, which is trusted to protect the secrets, but is not trusted to correctly execute the computation.

Homomorphic encryption is usually used when the computation is realized by a party that doesn't know the secrets, and is not trusted to protect these secrets, but is trusted to correctly execute the computation.

These two constructions could be combined if you want to make sure that the worker sends back $Enc_k(f(x))$ and not some other value $Enc_k(g(x'))$. Then we could require the worker
to send back a proof that the computation was done correctly.
But then we wouldn't need the zero-knowledge property, since the worker doesn't know any secret.


Diffie-Hellman over several non-secured HTTP requests - will it work? This problem is about setting up cryptographic keys on an IoT device. I don't want my devices to be set up with any cryptographic keys pre-baked, but actual communication have to be based on TLS. Now I need a way to inject an SSL certificate and its corresponding private key from the device the user is using. Can this be done by using several HTTP requests to perform a Diffie-Hellman key exchange?

The protocol:

The user presses a button on the device, key setup and the unencryted HTTP channel allowed.
Client to Server: GET /setup/dh.wib.
Server to Client: DH initial parameters, and a new random session cookie.
Client to Server: POST /setup/dh.wib with client's computed DH intermediates and session cookie.
Server to Client: Server's computed DH intermediates.

Up to this point, a cryptographic key that is suitable for AES encryption should be established. Then:

Client to Server: POST /setup/auth.wib with the the device's serial number (as printed on the back of the device) encrypted using the established key, a SHA512-HMAC of the serial number using the key in plain, and the session cookie.
Server to Client: HTTP status code 204 if serial number matched with the record stored inside the device, otherwise HTTP status code 401 and the session cookie removed and invalidated.
Client to Server: POST /setup/key.wib with the generated certificate, and its corresponding key bundled encrypted using the established key, a SHA512-HMAC of the aforementioned bundle using the key in plain and the valid, authenticated session cookie.
Server to Client: If the certificate and key pair worked then HTTP 204, otherwise HTTP 400. Session cookie is invalidated no matter what here. Key setup and unencrypted HTTP access disabled here.

First, I'd like to say: Don't roll your own crypto.

Your first protocol is basically "your own crypto". The easiest / standard solution to this problem is to use TLS. You can use TLS (with server-authentication only) as a replacement for your first part. I'd recommend though, using DNSSEC / DANE as well (if possible) so you don't have to have a (complex) root-certificate store.

What you do next is up to you. I'll first analyze your proposal and then provide another.

If an attacker (within your threat model) can get hands on the
serial number he can pretend being that device and thereby may break
security guarantees, because the server doesn't know who he's
talking to.
In your third step you say that "Client to Server" sends the key. I think you meant it the other way around? Note that if you send the private key over the wire, the key is only as secure as the connection (so if you use a "bad" DH private key the key could still be compromised even though it's high entropy).

Otherwise this looks fine and pretty standard.

You generate your own private key on the device along with a CSR.
You send the CSR to your server along with some "secret" that identifies the device in question and that can not easily be retrieved for attackers in your threat model.
The server will create the certificate from the CSR and send it back to the client.
The client can now use said certificate for client-authentication.

As for the "how" of the generation of the private key:

You stated that you have a somewhat reliable entropy source on the device.
If you can guess any private key generated on the device there's no chance that you can get a private key securely to the device as the transport key could be broken (because it's weak).
Assuming you can scratch enough entropy together (i.e. 128 bits of entropy distributed over an unspecified amount of bytes) you can run your "random" bytes through a key based key derivation function (e.g. HKDF), to get a key and an IV for the stream cipher of your choice (e.g. AES-CTR or ChaCha20 or Salsa20).
You can now use this stream cipher to generate a pseudo random stream of bytes that you can use as a replacement for your system RNG to get a good private RSA key. Note that 128-bit entropy is good enough for a 3072-bit RSA key as it anyways only provides a 128-bit security margin.


Strong key generation using PBKDF I know that PBKDF2 is very useful for generating strong keys. I'm trying to know is there any additional contribution of the given password to produce even stronger keys.

Which key is more secure:

A password: "123456"   (length 6) is entered into PBKDF2 ---> Produced key
A password: "XK6f+d"   (length 6) is entered into PBKDF2 ---> Produced key
A password: "123456789" (length 9) is entered into PBKDF2 ---> Produced key
A password: "dYn5p78+/" (length 9) is entered into PBKDF2 ---> Produced key
A password: "eh4P+S83ko/@bDBq" (length 16) is entered into PBKDF2 ----> Produced key

Does the strong key generation of PBKDF depends on the length of the password?
Does longer passwords produce more stronger keys then shorter passwords?
Does "XK6f+d" produces more stronger keys then "123456"?

There are two inputs to PBKDF2, and key derivation functions in general: the password and a salt. Assuming the attacker knows the salt, all the password hash can do is slow down a brute force or dictionary search (i.e. 1000x the complexity of HMAC with PBKDF2 default iterations), as well as force the attacker to search for each user's password individually. In that case "123456" is an insecure password with any realistic password hash.

If you for some reason could assume that the salt is a strong secret random number of sufficient size, then the keys produced from all of those passwords would be equivalently unknowable. However, in that case you could just use a fast key derivation function. It's not the problem PBKDF2 is meant to solve.

TL;DR: PBKDF2 does not make poor passwords secure, just mediocre ones somewhat less mediocre.


rotation offsets for KECCAK-$f$[800] So let's say you're trying to do SHA3-224.

If you're on a 64-bit machine you'd presumably use KECCAK-$f$[1600]. In-so-far as I understand it'd have the following parameters:

Rate: 448 (2*224)
Capacity: 1152 (1600 - rate)
Rounds: 24
Rotation constants: described in https://keccak.team/keccak_specs_summary.html  (last table)

With a 32-bit machine you'd presumably be using KECCAK-$f$[800] with the following parameters (last table):

Rate: 448 (2*224)
Capacity: 352 (800 - rate)
Rounds: 22 ($12 + 2*\log_2(800/25)$)

Assuming that that's all correct then what I'm wondering about is how the rotation constants would work.

https://keccak.team/files/Keccak-reference-3.0.pdf#page=21 gives a formula for determining the rotation constants: $(t+1)(t+2)/2$ and https://keccak.team/files/Keccak-reference-3.0.pdf#page=22 shows a table with the results of the formula. To get the rotation constants at https://keccak.team/keccak_specs_summary.html you take the lower lower six bits of each of those numbers (eg. $x \land 0x3F$ or $x \mod 64$).

For KECCAK-$f$[800] would you take the lower five bits (eg. $x \land 0x1F$ or $x \mod 32$) of each of those numbers?

A lot of the 32-bit SHA3 implementations I've seen seem to do KECCAK-$f$[1600] and just simulate 64-bit numbers with 2x 32-bit numbers.

The following two assumptions are mutually incompatible:

  you're trying to do SHA3-224

and

  with a 32-bit machine you'd presumably be using KECCAK-f[800]

because chapter 6.1 of the SHA-3 Standard FIPS PUB 202 (the link can be found here) defines

  $\text{SHA3-224}(M) = \text{Keccak}[448](M \mathbin\Vert 01, 224)$,

but chapter 2.4 of this Standard defines that

  $\text{Keccak}[c]$ is the Keccak instance with $\text{Keccak-}f[1600]$ as the underlying permutation and capacity $c$.

Regarding the question about the rotation offsets for $\text{Keccak-}f[800]$ — see chapter 3.2.2 of the SHA-3 Standard FIPS PUB 202 and note that $w=32$. For example, I have seen both the algorithm and the precomputed offsets here:

github.com/XKCP/XKCP/.../KeccakP-800-reference.c.


mutual authentication with pre-shared key A and B share two secrete keys: [keyA] and [keyB].
A sends this to B.
AUTH_A = prf(KeyA, ID_A)
B sends this to A.
AUTH_B = prf(KeyB, ID_B)
Does above scheme provide mutual authentication?
I think so because prf is just a key hashed function, as only A and B know the secret key, attacker cannot forge the message or learn the keyA or keyB from the messages.
When B received AUTH_A, it can calculate  prf(KeyA, ID_A) and compare it to AUTH_A to verify A's identity.
Do I miss any key concept or important consideration?

Typically, a preshared key itself is already mutually authenticated, i.e., you can simply use that key to encrypt and decrypt messages. The AUTH messages are not necessary and actually useless. However, here the mutual authentication does not imply that the public identities of both parties are explicitly authenticated, but depends on the authentication guarantees provided by the previous session that generated the pre-shared key. That is, direct use of a preshared key just guarantees the same two parties communicated before resume their session. More authentication procedures are required (e.g., each party signs a challenge message) to ensure explicit identity authentication, if it has not been guaranteed by the previous session.


Can we sign and encrypt with RSA keys of both sender and receiver? By using RSA encryption, it is possible to "encrypt" sign with sender's private key and then with receiver's public key, and decrypt with receiver's private key and then with sender's public key?
Like this:

Sender keys

private: $(n_s,d_s)$
public: $(n,s,e_s)$

Receiver keys

private: $(n_r,d_r)$
public: $(n_r,e_r)$

(Signature then) Encryption of message $m$

$c_1\gets m^{d_s}\bmod n_s$
$c_2\gets {c_1}^{e_r}\bmod n_r$

and then decryption with

$\widetilde{c_1}\gets {c_2}^{d_r}\bmod n_r$
$\widetilde{c_2}\gets {\widetilde{c_1}}^{e_s}\bmod n_s$

Mathematically speaking it should work, right?
EDIT: code with the methods to generate keys, encrypt and decrypt.
    import java.io.*;
    import java.math.BigInteger;
    import java.util.*;

public class ChatRSA {

        //inizializzazione di un oggetto BigInteger con valore intero randomico
    public static BigInteger Rand(){

            Random ra=new Random();

            int bits=1024;
            BigInteger bigran;
            do{
                //Numero che è probabilmente primo(la possibilità che non lo sia è di 1 ogni 100 miliardi di anni approssimativamente)
               bigran=BigInteger.probablePrime(bits, ra);
               //Eseguo un doppio controllo per aumentare la possibilità che sia primo
            }while(!bigran.isProbablePrime(100));// Più è grande il parametro, più aumenta la possibilità che sia primo

            return bigran;
        }
        //Calcolo primo numero delle 2 chiavi
        public static BigInteger N(BigInteger p, BigInteger q){

            BigInteger n=p.multiply(q);
            return n;
        }
        //Funzione Toziente(Conta in base a un numero n i numeri coprimi rispetto a n)
        public static BigInteger V(BigInteger p, BigInteger q){
            BigInteger v=p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
            return v;
        }
        //Secondo numero della chiave pubblica, che deve essere coprimo di V
        public static BigInteger Npub(BigInteger v){

            BigInteger npub;

            do{
               npub=ChatRSA.Rand();
               // gcd, il massimo comune divisore deve essere 1
            }while(!npub.gcd(v).equals(BigInteger.ONE)&&npub.compareTo(v)==-1);

            return npub;
        }
        //Secondo numero della chiave privata
        public static BigInteger Npri(BigInteger v, BigInteger npub){

            BigInteger npri;

            do{
                //(Npri * Npub)mod(v)Deve risultare = 1
                //quindi questo metodo opera npri^-1 mod(v)
                npri=npub.modInverse(v);

                //System.out.println((npri.multiply(npub)).mod(v).toString());
            }while(!(npri.multiply(npub)).mod(v).equals(BigInteger.ONE));

            return npri;
        }
        //Metodo per convertire la Stringa del messaggio in cifre
        public static BigInteger StringToCipher(String msg){

            //Array di byte, tipo di dato intero più piccolo. Viene usato e gestito in array
            //Recupera in array di bytes la stringa e la assegna
            byte [] bar=msg.getBytes();
            //Il valore dell'array di bytes convertito nel corrispondete grande intero
            BigInteger cmsg=new BigInteger(bar);
            return cmsg;
        }
        //Metodo per convertire il messaggio cifrato in stringa
        public static String CipherToString(BigInteger msg){

            byte [] bar=msg.toByteArray();
            String dcmsg=new String(bar);
            return dcmsg;
        }
        //Metodi per criptare e decriptare il messaggio
        public static BigInteger Encryption(BigInteger cmsg, BigInteger npub, BigInteger n){

            //Il metodo modPow utilizza la formula per criptare il messaggio nell RSA: cmsg^npub mod(n)
            BigInteger c=cmsg.modPow(npub, n);
            return c;
        }
        public static BigInteger Decryption(BigInteger c, BigInteger npri, BigInteger n){

            BigInteger m=c.modPow(npri, n);
            return m;

        }

}

As pointed in comment

"encrypt" with sender's private key is improper terminology; the proper term is sign. I took the liberty to fix that common error in the question. If we used anything else than trapdoor-permutation-based public-key cryptography (RSA, Rabin for the most), "encrypt" with sender's private key would be plain unintelligible.
It's assumed $n_r>n_s$ so that $c_1<n_r$, which is necessary to get $\widetilde{c_1}=c_1$. Thus the technique won't "work" with 100% reliability in both directions unless we take some precaution.

Also, the issue of padding is ignored. And more broadly the security goals are not stated.
Issue 2 can be solved in a number of ways:

The best is to use separate keys for signature and encryption, with a maximum $n$ for the first applied (signature in the question) lower than the minimum for the second. That abides to the time-proven security design principle: one usage, one key. It also avoids the embarrassment of ending up with $c_2=m$ when the sender is the receiver, something an adversary might induce.
Another option is to force all $n$ to share the same bit size and many high order bits (say 512, which become a fixed public arbitrary constant). That insures $c_1<n_r$ with overwhelming probability. It does not solve the send-to-self issue.
Yet another is to require all $n$ to have the same bit size, restrict to (say) even $m$, and use $c_2\gets\min\bigl(c_1,n_s-c_1)^{e_r}\bmod n_r$. On decryption, we'll end up with either $m=\widetilde{c_2}$ or $m=n_s-\widetilde{c_2}$, and the parity of $m$ allows to determine which (wince $n_s$ is odd). That does not solve the send-to-self issue.
A small variant of the above forces $m<n_s/2$ (typically by requiring $m$ to fit into two bits less than any $n$), which also allows recovery of $m$.

On the aforementioned padding issue: both RSA encryption and signing require redundancy for security; plus encryption requires random padding (or non-guessable plaintext) in what's processed with textbook RSA encryption. That can be solved by:

pad $m$ with randomness and redundancy
sign with textbook RSA using private key $(n_s,e_s)$ [in it's instance for signature, if distinct from encryption]
encrypt with textbook RSA using public key $(n_r,e_r)$ [in it's instance for encryption].

Proper checking of the redundancy on decryption insures integrity and protects against decryption padding oracle attacks.
Encrypt-then-Sign works as well, and is used in the RSA-based authentication protocol¹ between (pan-)European Digital Tachograph and it's Smart Cards. It uses the $\min$ and even padded message trick.

¹ Designed circa the end of the 20th century, I wish I knew exactly by who. A modern variant would use RSAES-OAEP padding and the $m<n/2$ trick, or best separate encryption and signature keys. It would also use public moduli much larger than 1024-bit, but I was instrumental in not increasing that value (see this) late in the project and causing yet another launch delay. I don't regret that bet: roads would have been rather less than more safe from drivers lacking sleep or over-speeding if Europe had waited 2048-bit RSA gizmos to be available to enforce something better than the old recording disc. As predicted, fraud on the new system ended up focusing elsewhere: pulling the power fuse during part of a long drive (pretending the battery was disconnected to avoid vehicle theft or fire risk to explain the record of that incident), using a magnet on the motion sensor (as an alternate way to stop recording while driving), unscrewing the real motion sensor and stimulating it artificially (to lower the recorded speed), somewhat getting the calibration factors off (to the same effect), drivers getting hold of two cards (doubling their driving allowance), plain not introducing their card, or purposely using old trucks (without the new Digital Tachograph mandated).


Encrypting Data with user + custodian private keys I want to be able to have a private user key (system generated) which, if destroyed, effectively renders all user data unrecoverable. This key would be used across the entire system to protect the user's data. Instead of having to implement and maintain integrations across all systems to delete  a user's sensitive data  we could just delete the key, rendering the data useless. However, the problem with this is that there is no granularity: the system has multiple custodians and each custodian should be able to determine who has access to decrypt the message.

We've been using KMS data keys for envelope encryption so the system must have permission to decrypt the envelope key before they can decrypt the message. I was hoping to be able to do something similar but incorporating the use of a user-specific key.

I gave this some more thought over the weekend and came up with a simpler solution. We'll store the data encrypted with the user key. For in-transit encryption we'll use a service key. The user data will be decrypted on read with the user key and then re-encrypted with the service key before transmitting the data. The data consumer will be required to have access to the service key to read it. This will also meet the requirement that the data will be rendered unrecoverable by deleting the user key.


Common modulus attack on RSA when the 2 public exponents differ by a single bit This is an exam question an i have no idea how to recover the message m.

John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and so John sends an email to Mary to ask for the key. mary's email reply is intercepted by Peter who replaces Mary's public key $\{e,n\}$ with $\{e_2, n\}$ where $e_2$ is obtained by changing one bit in $e$ from $0$ to $1$. Now john encrypts a message $m$ to Mary by using $\{e_2, n\}$. As Mary cannot decrypt the message, she resends her public key to John and asks John to send the encrypted message to her again. Peter does not interrupt this time. However, Peter eavesdrops the whole communication and obtains both encrypted message (one encrypted by $\{e_2,n\}$ and one by $\{e,n\}$. Explain how Peter can recover the message $m$.

How can encryption with both $\{e_2,n\}$ and $\{e,n\}$ be used to recover the message $m$?

I did think that it is related to common module attack, but i have no idea how to prove that $\gcd(e,e_2)=1$.

Does anyone have some idea on how to recover the message?

Proving $\gcd(e, e_2) = 1$ is easy; all you need to do is rely on the property

$\gcd(e, e_2) = \gcd(e, e-e_2)$

Now $e$ and $e_2$ differs in a single bit (because Peter flipped one bit in $e$ to form $e_2$), and hence $|e - e_2|$ is a power of two (the sign of which depends if Peter flipped a zero bit or a one bit), and hence has $2$ as its only prime factor.  On the other hand, we know $e$ is odd (because it is an RSA exponent), and so $e$ and $e-e_2$ do not have any prime factors in common (and hence, $e$ and $e_2$ do not either).

This result implies that the method you already have (which is effectively using the Euclidean method on the values $e$ and $e_2$ to compute $M^{gcd(e, e_2)}$) will give you $M$.


What does this part of the SHA-3 algorithm mean? I was reading through this paper and came across (pg. 11 of PDF, 5 of paper) the right_encode(x) and left_encode(x) pseudo-code sections. These contained this:

  Let $x_1,x_2,\ldots, x_n$ be the base-256 encoding of $x$ satisfying:
  $x = \Sigma \;2^{8(n-i)} x_i$, for $i = 1 $ to $n$.

What does this mean the algorithm does?

It's simply separating an integer into bytes with naive encoding. This is directly the represntation of the number, before padding length encoding etc. Think of binary representation of the number and group the bits into bytes. Those bytes are the Xi values. With X1 being the most significant and Xn being least significant.


Double spending on a given Blind Signature over ECC protocol Here's a blind signature protocol based on ECC. The question is if it has the double spending problem?

As I investigated, if we can change the c without changing the r and subsequently no change on m^, then there would be two different (F, s) for a single m.
And this can be achieved if considering F as (x, y), one can find another point on the curve with (x, -y) coordinates.

There's no such problem because, even if you find other $(F,s)$ pair, you still have signature for the same message $m$. So if your message contains anything like transaction id or serial number, it doesn't matter if you have more than one signature for it.

Second thing is that, even there are two pairs for single $m$, given one of them it's hard to find the other. Proof:

Given point $F$ with coordinates $(x,y)$, coordinates $(x,-y)$ correspond to point $-F$. So to have valid $s$ you have to calculate $c'$ that satisfies:

  $-F=b^{-1}R+ab^{-1}G+c'G$

After transformation:

  $c'G=-F-b^{-1}R-ab^{-1}G$

Let's set

  $C=-F-b^{-1}R-ab^{-1}G$.

Then we get:

  $c'G=C$

and this is exactly discrete logarithm problem.


Why are stream ciphers not PRPs? In a stream cipher like RC4, a message is xored with a random stream of bits, hence a n bits message will result in a n bits random-like ciphertext.

So it's a bijection, it's invertible, the output looks like a random element in {0,1}^n...

Why are stream ciphers not considered as PRPs?

I assume that for a fixed key $K$, you are asking why $f(m) \overset{\underset{\mathrm{def}}{}}{=} <STREAM> \oplus\ m $ is not a PRP, where $<STREAM>$ is the stream that is generated from the key $K$. $f$ verifies at least two properties that PRP in general do not verify:

$f(m_1) \oplus f(m_2) = m_1 \oplus m_2$
$f(f(m_1)) = m_1$


Is it easier to crack the Vernam Cipher with more than two ciphertexts I have just started looking into the cracking of the Vernam cipher with two ciphertexts encrypted with the same key by XORing them and then crib dragging and I was wondering if it is made easier if you have more ciphertexts like 3 or 4, and if so how that would be used to the crackers advantage?

Yes, in practice the more ciphertexts you have with the same key, the easier it is to break the encryption:

With more ciphertexts, you'll have more chances of hitting a crib, the more plaintext you'll reveal when you do, and the easier it is to be sure that a particular match is correct and not just plausible-looking by chance.
The more ciphertexts you have, the more opportunities you'll have for extending a decrypted segment, since you only need to guess how one of the messages continues outside the segment.

This homework exercise with 11 messages XORed with the same key is a good example: you can solve the puzzle almost entirely simply by starting with the assumption that the plaintexts (mostly) consist of ASCII letters and spaces, and observing that — due to the way the ASCII code is arranged — XORing a space with a letter has a specific and distinctive effect (it just flips the case of the letter) that is easily distinguishable from the result of XORing two letters (producing numbers, punctuation and/or non-printable control characters) or two spaces (which just produces a null byte).  With 11 plain English ASCII messages, most positions in the aligned ciphertexts end up containing a space in at least one of the messages, and the few remaining gaps are then easy to fill in.


Is there any way to hire someone to generate a sufficiently small hash of a value + nonce, without knowing value nor nonce? Suppose I have a 128-bit value X, and I want a keccak_256(X || nonce) sufficiently small to require a lot of work. Is there any simple/obvious way (possibly interactive) way to hire someone to find me such a nonce, in a way that he doesn't learn about X, and that he doesn't even know what nonce he produced?

I can't fit that particular problem on what zkSnarks seem to enable one to do.

Here's the obvious answer that avoids multiparty computation (which tends to be expensive):

Given your $X$, select a random value $N1$, which would be 256 bytes long for keccak_256 and 48 bytes long for SHA-256, and compute the intermediate hash state of $Hash(X || N1)$.

If your hash function is SHA-256, this is an intermediate hash of 64 bytes (1 SHA-256 block), which requires a single hash compression function evaluation (yielding a 256 bit intermediate state)
If your hash function is keccak_256, this is an intermediate hash of 272 bytes (2 Keccak-256 blocks), which requires two permutation evaluations (yielding a 1600 bit intermediate state).  We use two permutations for Keccak because the permutation function is invertible, and so if we used only a single block, the hireling could invert the permutation and recover $X$ and $N1$

We give the intermediate hash state to your hireling, who searches fir an N2 such that Hash(X || N1|| N2) is a small value; he can do this because both hash functions can be expressed as functions of the intermediate state and the rest of the message.
Once he has found such an N2, he sends it back to you. This gives you the value $nonce = N1 || N2$ you're looking for.

This solves the issue; the hireling cannot convert the hash state back into $X$, and since he does not know the value of $N1$, he doesn't know the full value of none.


How is the MJH double-block-length hash function constructed? I'm looking for information on the MJH double-block-length hash function, but the best free source I could find is the diagram on page 18 of Efficient hashing using the AES Instruction Set (submitted to the ECRYPT II Hash Workshop 2011).

Is source code available for this function? What are the standard symbols used (M, V, Z) when describing hash functions?

I had a look at the paper introducing the MJH construction (MJH: A Faster Alternative to MDC-2).

It actually presents a different diagram than the one in the paper Efficient hashing using the AES Instruction Set your referenced – there $V_2$ and $M$ are swapped. I'll describe the original one here, and the variation below.

The core of MJH is a compression function, using a similar construction like the JH hash function (one of the SHA-3 finalists), hence the name.

The JH construction

Given a (non-compressing) function $F : \{ 0,1\}^{2n} \to \{0,1\}^{2n}$, we define the compression function $JH[F] : \{0,1\}^{3n} \to \{0,1\}^{2n}$ as
$JH[F](V_1, V_2, M) := (Z_1, Z_2)$, with $(X_1, X_2) = (V_1, V_2 \oplus M)$, $(Y_1, Y_2) = F(X_1, X_2)$ and $(Z_1, Z_2) := (Y_1 \oplus M, Y_2)$.

In the JH hash function, F is a specially-made (fixed) permutation.

MJH's $F[\sigma, \theta]$

Given a $n$-bit-blockcipher $E$ with keysize $k = n$, $\sigma : \{0,1\}^{n} \to \{0,1\}^n$ an involution (i.e. $\sigma \circ \sigma = \mathrm{id}$) without fixed point (i.e. $\sigma(X) \neq X$) – an example would be an XOR with a non-zero constant –, and $\theta \in \mathbb{F}_{2^n} \setminus\{0,1\}$ a constant (so multiplication with $\theta$ is another non-trivial permutation).

We define $F[\sigma, \theta] : \{0,1\}^{2n} \to \{0,1\}^{2n}$ as $F(X, K) = (L, R)$, with $L = E_K(X) \oplus X$ and $R := \theta(E_K(\sigma(X)) \oplus \sigma(X) ) \oplus X$.

(The $E_K(X) \oplus X$ part is essentially the Davies-Meyer construction to make it one-way, even if $K$ is known. It is actually used twice here.)

The final Hash function

Combining these ideas, we get our compression function $\tilde F[\sigma, \theta] := JH[F[\sigma, \theta]] : \{0,1\}^{3n} \to \{0,1\}^{2n}$.

We then apply the known Merkle–Damgård caining construction on this compression function, receiving our final hash function $H[\sigma, \theta] = MD[\tilde F[\sigma, \theta]]$.

(This image is from Wikimedia Commons, the others are made by me.)

In practice we now also have to choose some specific $\sigma$ and $\theta$, a specific block cipher, as well as an initialization vector and padding for MD - the security proof still applies for all of them (if the block cipher is good).

Longer key variant

The paper also describes a variant of the compression function to be used when the key length $k$ is greater than the block size $n$. Then we use message blocks of size $k$, and split these blocks into two parts $z, z'$. $z$ (of size $n$)is used as before to be XOR'ed into the left half of the state before encryption and right half after, while $z'$ (of size $k-n$) is appended to the right half of the state to form the key for the block cipher.

By using a larger (hash) block size, this longer variant can be more efficient than the original one.

The variant depicted in Efficient Hashing

For $n = k$, this is the same compression function as the original one, but it is used in a different way in the MD-construction: Here the message blocks are passed in the key position, instead of being XOR'ed into the parts of the state before and after encryption. (This XOR'ing instead uses one half of the original state.)

This gives a more obvious generalization into the $k \geq n$ case, as we don't have to split the message block and compose the key, but simply can pass the longer key to the block cipher.

I didn't check if the proofs given in the MJH paper also apply to this variant, though, and I don't know which version the authors of Efficient Hashing actually measured.


Does the authenticity of messages by Alice still holds if the state of bob is compromised in Double Ratchet In the double ratchet algorithm, let's say if bob's device is compromised including his long term key.

Does the ephemeral keys generated by Alice during the half Diffie–Hellman key exchange produces a new sending chain for Alice which is not yet known to Bob.

Also does the messages from Alice still have the non-repudiation property even if bob's state is completely compromised.

if bob's device is compromised including his long term key.

  Does the ephemeral keys generated by Alice during the half Diffie–Hellman key exchange produces a new sending chain for Alice which is not yet known to bob

Double Rachet is secure against an attacker who records everything than compromise the sender or the receiver. As always said, if the receiver or sender stored previously generated keys then there is no forward secrecy, the attacker gets the keys and reads the recorded messages. Securely delete the keys.

A compromised secret key or device has more attack vectors that can be catastrophic.

The attacker can impersonate the attacked party and create new sessions.
The attackers can execute man-in-the-middle attacks constantly and maintain eavesdropping on the compromised session.

So the attacker will produce new chains that Alice and Bob are not aware of. The key and device must be replaced immediately if they are suspecting.

  if bob's device is compromised including his long term key.

  does the messages from Alice still has the non-repudiation property even if bob's state is completely compromised.

Alice will talk normally, so she cannot repudiate. The attacker has no power to forge a message that does not come from Alice. If they do, Bob can do, too and this is against the non-repudiation of the protocol.


Why do crypto libs use table lookups when they're vulnerable to timing attacks? AESEngine.java, from  BouncyCastle, uses table lookups as does aes_x86core.c, in OpenSSL. But per Cache-timing attacks on AES table lookups like what OpenSSL and BouncyCastle are doing are vulnerable to timing attacks. So why would they use them?

I believe that it is for two reasons:

Nontable based implementations of AES are possible, but (assuming you don't have AES-NI or something similar) are significantly slower than table based implementations (perhaps $10\times$ to $20\times$ slower)
For a lot of uses, timing attacks aren't particularly relevant (as either the attacker can't get the start/stop times, or can't get them to the precision needed to actually perform such an attack against AES)

Remember, when we deal with side channel attacks, there are a number of attack models possible:

At the simplest level, the attacker gets no information about the encryption process; he can (possibly) submit chosen plaintexts and ciphertexts, but the encryption operation looks like an abstract Oracle
The attacker might get some information (to some precision) about how long the encryption process takes
The attacker might also get some information about the memory accesses that the encryption process tables (cache-based side channel attacks)
The attacker might get some information about the state of the electronic gates of the device during the encryption process (DPA, EM-based side channel attacks)
The attacker might be able to cause a miscomputation during the encryption process (Fault Cryptanalysis)
The attacker might get unfettered access to the entire encryption process (White Box Cryptography)

The countermeasures needed as you go down the stack become increasingly expensive; it sounds reasonable that an implementation will say "we'll go down this far and no farther"


Why there isn't a consistent key transform function of HMAC? I am currently learning, the internal working of HMAC. There exists a key transformation process in the beginning, which works as follows:-

Make the length of $K$ (Key) equal to  $B$ (number of bits in each block):-

1) If Length of $K$ < $B$:- Pad 0 bits to the beginning of the message, to the point the the above condition is satisfied.

2) If Length of $K$ = $B$:- Do nothing (or proceed to the further step)

3) If Length of $K$ > $B$:- Pass $K$ with a Message Digest algorithm, which will return a key trimmed down i.e. it satisfy the condition len($K$) = len($B$)

QUESTIONS:-

Why can't we simply pass the $K$ via a Message Digest Algorithm,
whether the key size is less or more? Because the output will be of
the same size (the size that we expect), then why bother doing
padding in one process and passing via a Message Digest Algorithm in
other?
Or why not choose a consistent trimming/padding scheme instead of
using a Message Digest Algorithm. By that I mean, if the $K$ > $B$,
then do trimming of bits to a particular size which is predefined
(not the best option, but seems like a way to achieve the result
too).

Why does HMAC do that?

The process of expanding or compressing the key material to exactly one block length this way shouldn't be necessary from a security perspective. The reason for this transformation is to enable an optimization when the same key will be used to process multiple messages. (See RFC 2104)

If this optimization is used, it means that you can eliminate the need to process the inner key more than once. This part of the specification allows an implemenation take a snapshot of the hash function state after processing a whole block. If anything less than one block were used, then this wouldn't help. A hash function cannot process part of a message until after it knows the full block.

Because the first block never contains message bits, it is possible to pre-compute this hash function state as soon as you know the key. Had the first block been allowed to contain message bits, there wouldn't be much work HMAC's underlying hash function could do until it knew those message bits.

Consistently padding keys to a multiple of the block size would also allow pre-computation. But I'm guessing that method was ruled out to save a few bytes RAM/ROM and keep things related to this optimization simple.

The one security downside to the actual HMAC specification is that it is trivial to generate distinct but equivalent keys.

(That's only an issue if the source that provides the key is untrusted, key sizes are variable, and there is something application-specific that requires it be impossible to find equivalent keys. For basic message authentication a trusted source or fixed length key is enough to avoid that potential issue.)

Why is it inconsistent?

I don't know, but it was published in 1996. There are a bunch of examples of 90's cryptography that seem strange in hindsight.

HMAC could have been designed in some other way that enables similar optimizations. Something as simple as prepending the key length to the inner key then padding the new string with zeros to a multiple of one block size, for example.

In practice there isn't much need to implement case 3. Most modern hash algorithms (and even insecure algorithms from the same era as HMAC, like MD5, SHA-1, and RIPEMD) have block sizes much bigger than the length needed for symmetric keys.

(However, key exchange algorithms may generate larger shared secrets, but then you probably have access to something like HKDF. (You shouldn't use the same key for encryption and authentication, after all.))

It wouldn't be unreasonable to write an implementation that only supports case 1 and 2. (The decision should be documented and trying to use HMAC with overly long keys should be treated as an error.) In my opinion it's probably a good idea to force programmers to explicitly pre-hash long keys if they need full compatibility with HMAC.


Why has SSL v3 not yet been upgraded to a higher version with stronger principles, what are the dependencies and issues to do so? SSLv3 is almost 18 years old; why has it not been updated to a more advanced version with stronger rules and structure. What have been the issues and dependencies in doing so till now???

TLS 1.0 is in effect SSL 3.1. If you need more details about the history and why it is called TLS 1.0 instead of SSL 3.1 read Wikipedia.


Simple example to describe Bilinear mapping Notation : $\mathbb{G}$ is an additive group and $\mathbb{G}_T$ is multiplicative group of prime order $q$.

Bilinear mapping $e: \mathbb{G} \times \mathbb{G}  \rightarrow \mathbb{G}_T$ has to satisfy two properties.

1) $e(aP,bQ) = e(P,Q)^{ab}$        for all $P,Q \in \mathbb{G} , a,b \in \mathbb{Z}_q$

2) $e(P,P) \ne 1_{\mathbb{G}_T}$ for all $P \in G$

In addition to the above two, it has to be computable.

Is there any simple example for such bilinear pairing?

I searched over internet as I can but I didn't find.

I want example like this $e(x,y) = xy \mod n$ (It's not a valid example).

Note: The sets under consideration $\mathbb{G},\mathbb{G}_T$ must have at least four elements.

Duplicate question for https://math.stackexchange.com/questions/1380004/simple-example-for-bilinear-mapping

A toy example would be this simple map with $\mathbb{G} = \mathbb{Z}/5$ to $\mathbb{G}_T = \mathbb{Z}^*/11$, as follows:

$$e(x,y) = 3^{xy} \bmod 11$$

It's easy to verify that both equations hold (except that $e(0,0) = 1$; that's actually a necessary consequence of the first equation, and so I'll consider that an acceptable exception).

Of course, even if you scale this up to non-toy sizes, this particular style of bilinear mapping isn't cryptographically interesting; however it does answer your question.


Finding algorithm: desire RSA's uniqueness and ECDSA's space efficiency I am asking for help in finding a signature algorithm with the following property:

Given a message m and a private key prikey, the result of signing m with prikey is unique (which is stricter than deterministic). In another word, there is only one signature (or finding another one using prikey is securely hard) that can pass the verification by the public key of prikey.
High space efficiency of storing private key and signature.

ECDSA's space efficiency is satisfying, but the signature is not unique; RSA has uniqueness, but is there any alternative with better space efficiency?

Yes!  There are verifiably pseudorandom functions or VRFs made out of elliptic curves including EC-VRF, related to ECDSA, and VXEdDSA, related to EdDSA.  In addition to getting a unique output for each message, the output is a pseudorandom function of the message, and you get a proof of uniqueness.

More references on VRFs.


Does DROWN attack break 2048-bit key itself or just the plaintext encrypted with the RSA key Does the DROWN attack enable breaking strong RSA keys (e.g. the 2048-bit key itself) or enable breaking the plaintext (i.e. pre-master key) that is encrypted with a 2048-bit (or any strong) RSA, if the key is shared with SSLv2 server?

It breaks the secret key (master secret) that is encrypted using RSA; this secret key is the plaintext message; it is not the RSA private key.

Padding oracle attacks (DROWN uses a special form of the Bleichenbacher padding oracle attack) generally only attack the plaintext message, not the secret or private key used to create the ciphertext.


Probability of false positive key matching two plaintext/ciphertext pairs Given a keyspace of $ 2^{80} $ and plaintext space of $2^{64}$. And two plaintext and ciphertext pairs $(x_1, y_1)$ , $(x_2, y_2)$. Now we have $2^{80}/2^{64} = 2^{16}$ keys that encrypt $x_1$ to $y_1$ and another $2^{16}$ keys that encrypt $x_2$ to $y_2$, with only one key that is supposed to be the target key (correct key).
What is the probability that once brute-force identifies a first key ($k_1$) this same key happen by mistake to also encrypt $x_2$ to $y_2$, that is this this key happen to be a False-positive (that is, this key will likely not encrypt $x_3$ correctly). What is the equation used and how is it derived?

Under an ideal cipher model, every key implements a random permutation. A random wrong key that maps $x_1$ to $y_1$ thus maps $x_2\ne x_1$ to a random ciphertext $y_2'$ other than $y_1$. For a $b$-bit block cipher, there are $2^b-1$ such ciphertexts, thus the probability that $y_2'=y_2$ is $1/(2^b-1)$.
The probability that an incorrect key survives two tests is thus $p=1/(2^b\,(2^b-1))$.
A random $k$-bit key has probability $q=2^{-k}$ to be correct. It passes two tests with certainty if correct, with probability $p$ otherwise. Thus a random key has probability $q+(1-q)\,p$ to pass two tests [where the $q$ term is for the correct key, the $(1-q)\,p$ term is for incorrect keys, and obtained as the the probability that a key is incorrect, times the probability that it nevertheless passes the test with $(x_1,y_1)$ and $(x_2,y_2)$ ].
Thus a random key known to pass two tests has probability $q/(q+p\,(1-q))$ to be correct [where the numerator $q$ is the probability for a random key to be correct, and the denominator is the probability that a random key pass two tests]. That simplifies to $1/(1+p\,(1/q-1))$.
The desired probability of a false positive is the complement, that is
$$\begin{align}1-1/(1+p\,(1/q-1))\,&=\,1/(1+1/(p\,(1/q-1)))\\&=\,1/(1+2^b\,(2^b-1)/(2^k-1))\end{align}$$
For $b$ and $k$ at least 7, that's $1/(1+2^{2b-k})$ within 1%. When further $2b-k$ is at least 7, that's $2^{k-2b}$ within 1%, here $2^{-48}$, that is less than one in 280 million million.
More generally, it can be shown that the probability of false positive after testing $n$ distinct plaintext/ciphertext pairs is $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. For common block ciphers like DES and wider, that's very close to $1/(1+2^{n\,b-k})$, and when $n\,b-k$ is at least 7, that's $2^{k-n\,b}$ within 1%.