Constructing of 16x16 Involutory Binary Matrices of Branch Number 7 In the PDF  “Algebraic Construction of 16×16 Binary Matrices of Branch Number 7 with One Fixed Point”, it was given that:

Matrix 1h = 1 0 0 0
            0 1 0 0
            0 0 1 0
            0 0 0 1

Matrix 2h = 0 0 0 1
            1 0 0 1
            0 1 0 0
            0 0 1 0

Matrix 4h = 0 0 1 0
            0 0 1 1
            1 0 0 1
            0 1 0 0

Matrix Fh = 1 1 1 1
            1 0 0 0
            1 1 0 0
            1 1 1 0

What are the values of 3h, 5h, 7h, Ah, Eh?

I guess you can construct those matrices simply with M1h and M2h with a double and add algorithm.

Clearly, $M_{4h} = M_{2h} \cdot M_{2h}$ and $M_{Fh} = ((((M_{2h} \oplus M_{1h}) \cdot M_{2h}) \oplus M_{1h}) \cdot M_{2h}) \oplus M_{1h} $. From this you can deduce how to construct all the remaining matrices.


Why are there so many different elliptic curves? There are Chinese, French and NIST curves.  There's a Million Dollar one. The BADA55 Research Team studied 1 million variants.  Some are based on widely different formulae.  Indeed there are entire suites of curves, and we're still actively developing more.  It's all starting to look like a plate of spaghetti.

Why is there not just one or two curves that have been widely accepted as useful?

Why is there not just one or two curves that have been widely accepted as useful?

Several reasons; some of it is politics (for example, I suspect a good part of the reason behind national curves is, in fact, national pride), some of it is multiple teams working independently (for example, the Brainpool team, the NUMS time, the people behind the million dollar curves)

However, what can't be discounted is that people have different opinions on what makes a good curve.  Here are some of the highlights:

What sort of prime is the curve based on.  You can define an elliptic curve based on any finite field; recently, people have (mostly) settled on defining them based on large prime fields.  For these curves, a large part of the expense is performing modulo operations based on the large prime.  Now, if we select a prime with a simple binary representation, this modulo operation can be performed much faster than if we selected a random prime.  On the other hand, some people note that these special primes make some blinding operations (important for side channel protection) harder, and so they do prefer random primes.
Lack of suspicious design decisions.  If you look at the NIST curves, they are based on the equation $y^2 = x^3 - 3x + b$ where the value $b$ is a rather odd constant.  Some people worry that $b$ might have been selected to induce an obscure weakness; that's a good part of the motivation for a number of the curves.
Curve equation.  Traditionally, the curves have been based on the Weierstrass equation, $y^2 = x^3 + ax + b$ (for characteristic > 3), which can represent any curve (that is, if you have an EC curve formula, you can find a simple mapping from that to the equivalent Weierstrass curve).  However, some people say that there are advantages to other curve equations (even if they can't represent arbitrary curves); Curve25519 is the most prominent example here.

On the other hand, if we look at what curves people actually use, there isn't that huge of a variety.  We see P256 in wide spread use, we see some uses of P384 and uses of Curve25519 are becoming prominent.  Every other curve would appear to be to be, at least, niche; used for an application or two, but not really that wide spread (at least, in my experience)


Existence of MAC implies existence of OWF I'm having trouble understanding how the existence of a MAC implies the existence of an OWF.

If the MAC protocol is $(\operatorname{Gen}, \operatorname{MAC}, \operatorname{Ver})$ such that for any adversary $\mathcal{A}$,

\begin{gather*}
\underset{k \sim \operatorname{Gen}(1^n)}\Pr[\operatorname{Ver}(k, \operatorname{MAC}(k, m)) = m] = 1, \qquad\text{and} \\
\underset{k \sim \operatorname{Gen}(1^n)}\Pr[\mathcal{A}(1^n) = (m,t) \mathrel{\text{such that}} \operatorname{MAC}(k, m) = t] < \text{negligible}.
\end{gather*}

I am imagining the OWF I would construct to look something like $f(x) = \operatorname{MAC}(x, 0)$. If an adversary can invert $f$, then given the 'tag' $t$ of the zero string they are likely to be able to find some key $k$ such that $\operatorname{MAC}(k, 0) = t$. They could then break the security property of the MAC by using $k$ to forge new messages.

The problem I am running into is: just because inverting $f$ gives some key $k$ where $\operatorname{MAC}(k,0) = t$, it isn't necessarily the same with the challenger used, and may just happen to have the same tag at 0. How can I get around this?

It is not hard to construct a secure MAC where $f(k) = \textsf{MAC}(k,0)$ is not one-way. Take any secure $\textsf{MAC}$ and define a new one as

$$\textsf{MAC}^*\Bigl( (k_1,k_2), m \Bigr) = \textsf{MAC}(k_1,m) \oplus k_2.$$

It should be relatively clear that $\textsf{MAC}^*$ is also a secure MAC. Now given arbitrary $m$ and $t$, it is easy to find a key under which $\textsf{MAC}^*((k_1,k_2,m)=t$. Just choose arbitrary $k_1$ and then solve for $k_2 = t \oplus \textsf{MAC}(k_1,m)$. This leads to a natural way to invert the $f$ function you propose.

Another way to look at things: The function $f(k) = \textsf{MAC}(k,0)$ can only rely on the fact that the MAC is secure against an attacker who sees just one output. But there are information-theoretic MACs with this property, and you can't expect them to imply a OWF.

To get around this, you should use $f(k) =\textsf{MAC}(k,0) \| \textsf{MAC}(k,1) \| \cdots \| \textsf{MAC}(k,\ell)$ as your OWF candidate, where $\ell$ depends on the key size of this MAC. But even then the argument of one-wayness is not trivial.


Could multicollisions be used to mine large amounts of cryptocurrency? I'm reading about hash functions at the moment, and in the book I'm reading there's a section on multicollisions. Specifically, using a 2-collision to find $2^N$ collisions in $N2^N$ time.

If, theoretically, a collision was found which was valid for cryptocurrency mining (however many 0s on the end), couldn't one find a large number of blocks which also collide with that, allowing them to be much more efficient than other miners?

Is my understanding of multicollisions correct? If so, is the difficulty of finding a 2-collision the only thing preventing this from being done?

In the Bitcoin mining, hashcash version 2 (2002), one looks for the input $m$ such that $\operatorname{SHA256d}(m)$ is the desired output hash value that is below the current threshold of zeros. In other words  $$\operatorname{SHA256d}(x)/2^{(n-k)} = 0$$ where $k$ is the work factor, that is the number of leading zeros and $n$ is the output size that is 256 for SHA256. This was before factional is introduced;

$$\operatorname{SHA256d}(x)< 2^{(n-k)} $$

The required threshold is given therefore one look for the pre-images, that is given the hash value $x$ find a pre-image that the $\operatorname{SHA256d}(m) < \text{threshold}$. Since we are looking for a threshold the search easier than the preimage attack and still harder than the collision attack.

Note that BitCoin defines a term for this search pre-image with a partial output match.

The search doubles when the number of leading zeros is incremented by one. Therefore it is getting harder and harder. If someone is so lucky then they can find some of the required values easily but this probability is so lower than hitting your head with a meteorite!

The bitcoin miners reached $2^{92}$ double SHA2 searches in a year. If you consider that they find the block in one, they need two years, on average, or double the hardware and therefore the power consumption.

  Is my understanding of multi collision correct? If so, is the difficulty of finding a 2-collision the only thing preventing this from being done?

Yes, one firstly needs to find the collisions to apply multi-collisions. And, SHA256 is far from finding one.

Note: Finding pre-image is harder than collision attacks. The Cryptographic hash functions like MD5 and SHA-1 are collisionally broken since one can find collisions better than the generic collision attack, which is given by the birthday attack. However, none of the cryptographic hash functions, including the MD5 and SHA-1, are vulnerable to pre-image attacks. Currently, $\operatorname{SHA256}$ requires around $2^{256}$ hash computations to find a pre-image. Actually, during the search one can find nearly all the pre-images that have hash values with leading zeros.


Order of hashing concatenation A = hash("blue" + X);
B = hash("pink" + X);

If A and the literals are known and X is unknown, are there attacks on B aside from the attacks on directly on hash()?  In other words, is B safe?

Would it be better to reverse the concatenation?

A = Hash(X + "blue");
B = Hash(X + "pink");

If it matters, I am using hash=sha256.

It looks like you want a message authentication code (MAC).

A MAC is a computable function $M$ of two inputs $k$ and $x$ (usually with variable-sized $x$ and fixed-sized $k$ and output) such that:

Given a lot of pairs $(x_i, m_i)$ with $m_i = M(k, x_i)$ (and not given $k$), it is hard to find $(m, x)$ with $m = M(k, x)$ and $x$ is not one of the $x_i$s).

You actually only need a slightly weaker condition:

Given a lot of pairs $(x_i, m_i)$ with $m_i = M(k, x_i)$ and an $x$ which is not one of the $x_i$s (and not given $k$), and it is hard to find $m = M(k, x)$.

While a random oracle with simple concatenation of the inputs (in either order) would do fine as a MAC, real-life hash functions are not random oracles.
Thus we usually use specially-made MAC functions for this goal - there are ones based on hash functions (specifically HMAC which can be instantiated with every hash function), and others based on block ciphers.

It might be that SHA-256 is safe anyways (maybe depending on the length of your strings), but this is not what SHA-256 was made for.

Simply use HMAC-SHA-256 instead (with your $X$ in the key position).


How can a good pseudo-random number generator be made? I am trying to make a pseudo-random number generator so that I can use it in a synchronous stream cipher for encrypting plain text. I want it to generate numbers which are as random as possible.

What are good elements that my algorithm must have in order to do so?

This is for an interschool science competition.

There are two answers, really depending on your specifications and how your generator will be evaluated.

If all you need is to have a PRNG with statistically excellent random, but really don't care about predictability or cryptographic considerations, go for something simple like a Mersenne Twister.

If you actually need some effective stream-cipher, look up on existing ciphers. Yet again, I'd go for something simple, like using an AES in CTR.

Note: If you intend to use your solution for any real usage crypto, then by all means please read papers & think about using an existing solution, yours will most likely not be error-proof in the implementation


Is it possible to create "non overlapping" RNGs? For example, let's say I want two cryptographically strong RNGs (R1 and R2).
And I want them to have the following property:
R1 (resp. R2) will never generate the same random number twice.
R1 (resp. R2) will never generate a random number that R2 (resp. R1) can generate.

Is it possible for three RNGs, 4, N ?

Unlike other questions already on the site, I don't need the generated RNGs to be tracked back to their generator.

Take a block cipher with a random key and for one generator encrypt the even numbers then with the other generator encrypt the odd numbers.  Your output blocks will be pseudo-random and distinct.  For more than two generators just partition the inputs accordingly.


Is this method of string encrypting "uncrackable"? I was thinking of unique methods of encrypting strings, and I thought of this.

Given a string, for example "Hello, World!" we can convert it into a char array using a computer program, and then convert each char into the corresponding number from the ASCII charcode table. (For example, H is 72, e is 101 etc.) then multiply each number by a random "key", which is just an integer (which will be the same for each number), in this case lets say it is 3042 (So 72 is now 219024, 101 is now 307242).

Then, remove from each number a value, which will be our second key (In this case, lets say it's 287), So 219024 becomes 218737 etc.

Now you see, if 2nd key wasn't removed from the result of the number * key1, then we could simply find the common factors of all the numbers, and grab the key.

However since a second key is removed, is this method of encryption practically uncrackable without knowing at least the 2nd key?

What you describe is a sightly convoluted version of a substitution cypher.  Every letter in the plaintext is replaced with an integer in the cyphertext.  If I have two 'e's, both will encode to the same value.

Unfortunately, in this case, the algorithm is far from uncrackable. There's a famous phrase, "Anyone can create an encryption algorithm so complicated that even they cannot crack it." This is one of those cases.  All substitution cyphers fall victim to statistical analysis.  If you have any information as to the statistical likelyhood of letters or words, you can rather rapidly deduce the keys.  This kind of cypher was considered unbreakable in the era of Caesar, but since the formalization of probability in the 1600's, this kind of encryption is considered "fully broken."

The fastest approach to break this algorithm is to gather enough characters to be confident that you have two sequential characters (such as an 'a' and a 'b'   or a 'g' and an 'h').  This can be guaranteed in 14 unique characters if you limit yourself to uppercase letters, or 129 characters if you have the entire 8-bit ASCII space at your disposal (the pigeonhole principle guarantees that if you have that many characters, at least one pair of them must be sequential).  Once you have enough characters, simply sort them and find the smallest gap.  The letters with the smallest gap between them are sequential.  Once you have those two, you can do simple algebra to get the two keys.

If you attempt to avoid this hole by only using half of the alphabet (acegikmoprtvxz, for instance), the attacker will see gibberish if they make this attack.  When they realize this, they can simply look at multiples of the key they generated until the messages start making sense.


Is it dangerous to use plaintext as IV in CBC? Is it dangerous to use plaintext as IV in CBC?

For example: I want to encrypt $p1$, $p2$ with CBC. However I use $p2$ as the IV for CBC purposes.

What would be the risk of not using a IV based on random number(s)?

As already given as partial answer in the comments, you would have to leak the second block as an IV is normally transmitted without confidentiality. You could of course retrieve it from initially decrypting the ciphertext without IV, and retrieve the first block value later on. But using an encrypted IV has got it's own vulnerabilities.

The other issue is that the IV in CBC is XOR'ed with the first block of the plaintext. Now an attacker can look at previously transmitted (initial) ciphertext blocks and see if it matches the one it is currently investigated. If they match then it knows that the result of XOR'ing the IV and plaintext matches a previous combination. This means that IV ^ P1 == IV' ^ P1'. As IV and IV' are known, this leaves you with an equation with just two variables. If more identical ciphertext blocks are found, the amount of information about the first block of plaintext increases.

There are other issues as well. You require at least two plain text blocks for your algorithm to use for instance. If there is a repeat of the first two blocks, then you will end up with an encryption of just zero's, and block 3 will become vulnerable as well.

Now it may be that your protocol is secure against these attacks, but you are using CBC without it's preconditions being satisfied, so you should then prove security of your protocol yourself.

In general, this scheme is not a good idea. It's pretty close to using a static IV instead of one that is indistinguishable from random by an attacker.


The goal, the method, and the interface of the signcrypt primitive. Some time ago, I proposed making the site more educational by teaching correct cryptographic programming. The proposal had had somewhat good reception, but was met with cold ice as there had been little new questions on this topic.

Therefore today I'd like to ask a question centralize the idea behind the correct programmatic usage of the signcrypt (Sign and Encrypt) primitive.

The goal of signcrypt in its simple form can be stated as: to ensure the confidentiality of a non-repudiatable, authentic, integral message for its intended recipiant (correct me if I've mis-stated it). From this, I have the following questions at hand:

Per this recent question, should we a) query the signing oracle on the encrypted message, or b) query the encryption oracle on the signed message?
What is the interface of signcryption? What functions does the tuple consist of?
As it deserves a topic of its own, in short summary how does signcryption fit into the big picture of instant messaging protocol like the Double Ratchet Algorithm?

1. Order of signing and encrypting.

It is often done in authenticated encryption to Encrypt-Then-MAC. However, there's a bit of problem with Encrypt-Then-Sign here as mentioned by the linked answer in the linked question. So it's better to sign-then-encrypt unless we have a more dedicated signcrypt algorithm.

 2. The Interface.

The tuple generally consist of the following functions:

$\operatorname{GenSign}(\langle \text{entropy source}\rangle) \to (\text{key}_\text{sign}, \text{key}_\text{verify})$

$\operatorname{GenEnc}(\langle \text{entropy source}\rangle) \to (\text{key}_\text{enc}, \text{key}_\text{dec})$

$\operatorname{SignEnc}(\text{msg}, \text{key}_\text{sign}, \text{key}_\text{enc}) \to \text{ciphertext}$

$\operatorname{VerifyDec}(\text{ciphertext}, \text{key}_\text{verify}, \text{key}_\text{dec}) \to \text{msg}$ or $\text{FAIL}$

 3. Instant Messaging Protocol.

The double ratchet "instant messaging" protocol had already solved the confidentiality problem from two ends: forward secrecy and future secrecy. So it's only needed to sign the message in such framework.


Quality of randomness on a Linux system with haveged Has anyone checked if using haveged, a Linux daemon which uses the HAVEGE algorithm, changes the non-deterministic properties of the random data from /dev/random in any negative ways?

TL;DR: do not use HAVEGE, it was flawed. It's evolution HAVEGED (notice the additional D) has improvements, but this answer is about HAVEGE, because the original question was.

I do not buy some of HAVEGE, specifically the claim made here "tens of thousands of unpredictable bits can be gathered per operating system call in average", and the methodology used to support that claim, as found here.

Entropy gathering is described by this pseudocode:

where HARDTICK() is a function that reads a hardware clock counter. An experimental evaluation of the entropy gathered was made as follows:

  We determined the threshold for NMININT above which the content of
  Entrop array can be CONSISTENTLY considered as random, i.e. it cannot
  be distinguished by our battery of tests from truly random numbers
  (i.e DieHard + ent + FIPS 140 +NIST suite).

(Emphasis using bold is mine)

The data gathered in Entrop is built using a Pseudo-Random Number Generator, complete with repeated rotation by 5 bit of each 32-bit word of Entrop, combination by XOR with one bit of the least recently modified word of Entrop, and combination by XOR with the actual source of entropy, HARDTICK() (or rather, the delta between successive HARDTICK() which is to closest to the actual source of entropy). See HAVEGE's paper for more details.

The entropy at the output of that PRNG has been evaluated using an experimental test (not designed specifically against this PRNG). That's a cardinal mistake: any half-decent PRNG will pass this test, even if fed very little actual entropy in its input, which makes its output highly predictable.

While this does not constitute a practical break of HAVEGE, it shows that the justification of its entropy-gathering part is flawed. My recommendation is thus not to use HAVEGE.

The above is advice about HAVEGE, as in the original question, based on references from 2003. In it's successor HAVEGED (notice the additional D) of the 201x, there was some effort made towards a sound methodology, in particular checking the entropy at input of the PRNG, leading to the conclusion: "Most samples failed all tests!". It is acknowledged that theoretical analysis of the source of entropy to build a model suitable to support a demonstration of security "were not sufficient to constitute such a model". This at least is quite believable.


How can I store asymmetric keys server-side, so that they are only readable by devices? I am building a platform in which there is a central server & devices (computers).

These computers hold the same keys pairs that correspond to specific resources (shared between devices), so that only these devices can return signed data if required.

In that setup my question is:

How to store keys on the server-side, with only devices being able to read them AND no device interactions to replicate those keys?

Problem Statement:
I will answer this question as I think I understand your problem. I will write down what I've understood from your problem:

Your system is comprised of a central server and some nodes/devices/computers.
You need a digital signature of the devices as well as the server tying them to non-repudiation constraint (They can't deny having taken action.).
The public and private key pairs between devices shouldn't be exchanged between them but rather setup by the server.
The devices should be able to communicate with each other using those asymmetric key pair.

Assumptions:

You can't change packet format or constitution.
Every device obtains its asymmetric key pair from the server.

Solution:
Let every device have a global unique identifier (e.g Medium Access Control address), the configuration of the server takes place like this:

The server opens itself to requests (time-slotted) and creates a table of all the devices (IP, MAC, parameters based on design) then creates 2n keys (Public and Private) for n devices and communicates it to them.
Any device A which intends to communicate to any other device B requests B's public key from the server and locks the message using its (A's) private key.
The message is then passed on to the server which identifies the communicating parties A, B and passes it on to B.
B reads the message by unlocking it using its private key and finds it digitally signed using A's public key.

I would have liked to comment and verify a few details to make this answer  better catered to your problem but I need to gain some rep before commenting.
There are several security issues which will still remain but I will only solve them when you care enough about them.


Best way to encrypt lots of private keys with the same passphrase I'm working on software which deals with lots (several millions) of RSA private keys. Keysize is 2048.

I have to store them in a database, and I want them to be encrypted to mitigate risks of compromise from hostile access to the database. Naturally, applying a passphrase with PKCS #8 comes to mind.

I can't have a separate passphrase for each key because I can't store them securely. I can only store several passphrases in a secure vault.

But now I suspect that it's not safe to apply the same passphrase to millions of private keys with PKCS #8.

Could you please:

Confirm or refute my assumption that using the same passphrase to encrypt millions of keys with PKCS #8 significantly weakens encryption strength. If Eve gets enough encrypted keys, can she decrypt them knowing that an identical passphrase was applied? A kind of "many times pad" attack?
Suggest a better encryption method which uses the same passphrase (or a limited number of them).

Confirm or refute my assumption that using same passphrase to encrypt
  millions of keys with PKCS #8 significantly weakens encryption
  strength. If Eve gets enough encrypted keys, she can decrypt them
  knowing that same passphrase was applied? Kind of "many times pad"
  attack?

It depends.
If you are using PKCS#8 encryption using the methods from PKCS#5 v1.5 (and not >v2.0), then you are using ciphers with very short key-lengths, like DES. This is obviously bad, as we can reasonably brute-force the keys (of interest).

However, PKCS#5 (which is the encryption specified by PKCS#8) should generate a new random salt for each container and use password based key derivation with this salt and some reasonable iteration paramter to arrive at a key / IV pair for the encryption. That is, all private keys would be encrypted using different keys derived from different salts and the same password.

So overall the encryption is not weak because you encrypt a lot of data, but because you use a weak encryption method (if you use the old v1 PKCS#5 standard).

  Suggest a better encryption methods which use same passphrase (or
  limited number of them).

Assuming the password is strong and not leaked, PKCS#5 v2.X should do the trick indeed. One might consider adding additional indirection though, that is use the password to derive a master secret (eg 256-bit) which is then fed to the PKCS#5 calls, so that you can easily change the password when it is eg leaked or people go, but they didn't take the derivation parameters / keys.


What is the recommended number of iterations for Argon2? I've recompiled my operating system ("LionBSD" based on FreeBSD) to use Argon2i as the default password hashing algorithm in crypt/libcrypt.

I'm wondering what the recommended number of iterations would be?

As an example, OpenBSD uses 8 iterations of bcrypt by default.

I'm wondering what the recommended number of iterations would be?

Unlike bcrypt or traditional crypt, argon2 does not have a single iteration count, but three parameters affecting the computational cost:

Number of iterations $t$, affecting the time cost.
Size of memory used $m$, affecting the memory cost.
Number of threads $h$, affecting the degree of parallelism.

In addition there are two versions of argon2: argon2d uses data-dependent accesses for presumably stronger tradeoff resistance, while argon2i eschews them to avoid side channel attacks. The latter is recommended for password-hashing.

The argon2 paper gives the following procedure (paraphrased) for determining the parameters you should use:

Figure out how many threads you can use, choose $h$ accordingly.
Figure out how much memory you can use, choose $m$ accordingly.
Decide on the maximum time $x$ you can spend on it, choose the largest $t$ such that it takes less than $x$ with your system and other parameter choices.

I.e. they recommend you run it on your system and decide the largest parameters that match your limits on memory and processor time use.


What is the advantage of AES-GCM against CPA attack This questions is re GCM block-mode of AES. Assuming the TAG is cut to t bits, how can the strength of the cipher be calculated, that is, what is the Advantage of the cipher against CPA attack, and after how much authenticated data a new key has to be exchanged?

I'll use the 2012 paper: "Breaking and Repairing GCM Security Proofs" by Iwata, Ohashi and Minematsu as my primary source.

In said paper, the advantages for the privacy and authenticity game are stated. Only the latter one is being influenced by the tag length $\tau$.

  Theorem 1. Let $\operatorname{Perm}(n)$ and $\tau$ be the parameters of GCM. Then for any $\mathcal A$ that makes at most $q$
  encryption queries, where the total plaintext length is at most
   $\sigma$ blocks and the maximum nonce length is at most $l_N$ blocks,
   $$\textbf{Adv}^{\text{priv}}_{\operatorname{GCM}[\operatorname{Perm(n)},\tau]}(\mathcal
 A)\leq
 \frac{0.5(\sigma+q+1)^2}{2^n}+\frac{2^{22}q(\sigma+q)(l_N+1)}{2^n}$$

with $n=128$ because you pick AES here.

  Theorem 2. Let $\operatorname{Perm}(n)$ and $\tau$ be the parameters of GCM. Then for any $\mathcal A$ that makes at most $q$
  encryption queries and $q'$ decryption queries, where the total plaintext length is at most
   $\sigma$ blocks,the maximum nonce length is at most $l_N$ blocks and the maximum input length is at most $l_A$ blocks,
   $$\textbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm(n)},\tau]}(\mathcal
 A)\leq
 \frac{0.5(\sigma+q+q'+1)^2}{2^n}+\frac{2^{22}(q+q'+1)(\sigma+q)(l_N+1)}{2^n}+\frac{q'(l_A+1)}{2^\tau}$$

In theory you could just plug-in values into the theorem until you hit a security bounds that makes you feel uncomfortable and use it.

Or you could just follow NIST SP 800-38D Appendix C (PDF)'s guidance on short tags with AES-GCM. It contains nice tables and explanations thereof for 32-bit and 64-bit tags. If you do not intend to shorten the tag, then section 8 has guidance on message lengths.


Where does bootstrapping occur, client side or server side? In Fully Homomorphic Encryption, where does the bootstrapping procedure performed, in the client-side or the server-side?

Also, which side holds the secret key and the public key?

The aim of Fully Homomorphic Encryption (FHE) is out-sourcing the computation, especially onto the cloud or from small computing device into a more capable one securely. FHE was the holy grail of Cryptography that waited for around 30 years to be found, mentioned On data banks and privacy homomorphisms by Rivest.

In FHE schemes we are talking about circuit computation that is similar to electronics but this time mathematically. For semantical security, a noise is added and this is the main problem when performing FHE operations - i.e. dealing with the noise.

When circuit operations are performed with the used FHE scheme the noise increases. Especially the multiplication is problematic - doubling the noise. After a threshold is passed you can no longer decrypt the ciphertexts. For example in Fully Homomorphic Encryption over the Integers

$$c \leftarrow m + 2r + 2x$$ where $m \in \{0,1\}$, $r$ is the random (noise), and $x$ is the public key (note: here $x$ part it is simplified)

The bootstrapping is the novel idea given to us by Gentry. Before reaching the threshold, Gentry showed that we can run the circuit of the decryption algorithm of his scheme, and providing ciphertexts to this decryption circuit and encryption of the private key. In the end, we will get new ciphertext but the noise is gone.

Now, if we turn in to your question. For an FHE circuit, actually, you calculate the depth requirement and possible techniques available on your selected scheme, like bootstrapping, re-linearization, modulus switching. Once you designed and implemented your circuit, you send all the information to your outsource to compute (in FHE terms $\texttt{EVAL}$). If you need bootstrapping at some point to reduce the noise, you already provide the necessary information on your circuit and designed it with bootstrapping. Yes, actually, bootstrapping is a part of your circuit. There is no need for interaction. Fire and forget until the result is returned to you.

For the comment :

You prapere your circuit $\mathcal{C}$ and supply the required parameters for the evaluation;
 $$\texttt{EVAL} (k_{pub}, \mathcal{C}, c_1,\ldots,c_l, E_{k_{pub}}(prv))$$ where the $c_1,\ldots,c_l$ are the encryption of the plaintext, i.e. $c_i = E_{k_{prv}}(p_i)$, $k_{pub}$ is your public key, and encryption of your private key $E_{k_{pub}}(prv))$ if bootstrapping is required.

As always;

you keep the private key secret to yourself, and
the public key is public.


Order of MACing and Encrypting in TLS I've been working through how TLS1.0 works, and think I've basically understood most of it. One thing I can't seem to find a explanation of though is the order in which MACing and encrypting should happen. Let's say we've got the client finished message. You generate the 12 bytes of verify_data from the master secret, the finished label, and the md5/sha1 hashes of the handshake messages. At that point, do you:

a-> use your MAC key to create a hash of the 12 bytes, tag it onto the end and then encrypt the whole thing with your Write Key, or

b-> use your MAC key to create a hash of the 12 bytes, then use your Write Key to encrypt the 12 bytes, and tag the hash onto the end of the encrypted bytes?

It depends on which cipher suites and extensions the client and the server implement, enable and negotiate.

The default operation in TLS 1.2 and earlier, is MAC then Encrypt. This corresponds to alternative a in the question.
In TLS 1.2 it is possible to use AEAD cipher suites. Such cipher suites (e.g. AES-CCM but not AES-GCM) might correspond to alternative b in the question.
In all versions of TLS, the client and server might negotiate use of Encrypt then MAC with all non-AEAD cipher suites, provided that they both implement RFC 7366.


Updating values authenticated by Merkle Tree Assume we have 4 values: $v_1,v_2,v_3$ and $v_4$. We construct a Merkle tree on top of them such that the values are leaves of the tree.

I send the values and the tree to an untrusted server. But I keep the root of the tree locally.
Later on I want to modify (or replace) $v_4$ with new value $v_5$. Note that I Do NOT want to insert or delete any node. So I first verify the correctness of $v_4$
 and then replace $v_4$ with $v_5$ and generate the corresponding values (to update the tree). The update operation may take many times

Question: Would regular Merkle tree suffice to check the correctness of the values and the update operation?

In other words, can the server do any replay,... attack in the above scenario?

What do you mean that you keep the root of the merkle tree locally? Is the merkle tree signed?

If i understand what you are saying correctly, then the server can choose not to display to the public the changes you have made and keep presenting the merkle tree for the values before you updated them.

Even if you sign the merkle tree the server can still do that. However it cannot arbitrarily change the files. Only use old values.


"hash trail", iterative hash function that can be traced back along many steps What are some examples of an iterative hash function, where permutations along

A ---> B ---> C ---> D

can be compared, for example D/B, to see if D is a trail from B, and possibly the distance in steps from  C to D

SHA-256 or any at least as wide unbroken cryptographic hash will do, if the elements can be that wide (except the first A which is unconstrained). With a $w$-bit ideal hash, probability of entering a cycle in $n\ge1$ steps are $p<n^2/2^{w+1}$, by the Birthday problem. E.g. $w=256$, $n\le2^{100}$ gives residual odds of entering a cycle $p<2^{-57}$, and that's good enough in practice.

Things are not quite as easy when $w$ must be smaller; e.g. for $w=160$. In this case, we want a hash function less likely to iterate than random; that's not a common beast (to be continued after thinking about it).


Curve25519 base point speed up In the paper regarding Curve25519 DJB defines the base point to be $P_{base} = (9,y)$. The main reason for choosing it this way is, that $P_{base}$ has a big prime order which gives security advantages. But there are a lot of other points with the same properties. $x=9$ was choosen, because it is the smallest point with such a big order.
My question: Does a small x-value although give an advantage regarding the speed of the scalar point multiplication?

Yes it could be exploited to have a small performance advantage.
In pseudocode, the montgomery ladder is defined as:
 x2,z2,x3,z3 = 1,0,x1,1
 for i in reversed(range(255)):
     bit = 1 & (n >> i)
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
  return x2*z2^(p-2)

There is a line which uses $x1$ in the multiplication $x1*(x2*z3-z2*x3)^2$.
$x1$ is the x-coordinate of the input. It is possible to write an optimized implementation of that multiplication by hardcoding that value to 9 which will be faster than the generic multiplication by $x1$, where $x1$ could be any element of the field.
However I never seen an optimizations like that, mainly because the generic code is usable for all inputs and the speed-up could be around 5%.
You could try to put an conditional decision for that multiplication to have the best of both worlds (if the input is "9" then call the optimized multiplication otherwise the generic one) but putting branches in a constant-time code for a minimum speedup is not probably worth it. (even though I don't see security issue in doing that).
There are also better way to do optimized implementations if you know the input point in advance and don't have preconditions on the value of the x-coordinate. This achieves up to 44% speed up.


RSA cracking: The same message is sent to two different people problem Suppose we have two people: Smith and Jones.
Smith public key is e=9, n=179 and Jones public key is e=13, n=179.
Bob sends to them a message $M$.

The encrypted message $C_s$ to Smith is 32.

The encrypted message $C_j$ to Jones is 127

I tried to resolve this problem with no luck.

First I put both of them as an equation and tried to play with the module, multiplying and adding, but I can't retrieve the solution.
I know there is a way to resolve it but I haven't found it anywhere.

EDIT:
Is not a realistic situation. Is just for practice.
This is the primitive RSA. It has no padding.

I'm beginning to think that the problem is wrong maybe because the results I get are not correct.

This is the original problem text:

  Imagine that you are a CIA double agent. As good spy, you have discover that the agents Smith and Jones share the same modulo in their respective RSA public keys, namely ($e_s$ = 9, n = 179) and ($e_j$ = 13, n = 179).
  After some days sniffing the network, you see that the CIA director has sent the same message m to both
  agents. Concretely he has sent $c_s$ = 32 and $c_j$ = 127. Can you recover the original message m?.

    Solution m = 10

Resolution by me:

So I have the following equation:

$c_s$ = $m^9$ $mod$ 179

$c_j$ = $m^{13}$ $mod$ 179

And I began to use the extended Euclidean algorithm:

9*$a$ + 13*$b$ = $gcd$(9,13)
which gives me:

$a$ = 3 and $b$ = -2

As $b$ is negative, we calculate:

$i$ $=$ $c_j^{-1}mod179$

the inverse of $c_j$ (127) which is $-31$

And finally:

$M$ = $c_s^a$ * $i^{-b}$ $mod$ n

$M = 32^3*{-31}^2$ $mod$ $179$ $=$ $10$

Great! thanks!!!

$c_1 \equiv m^{e_1} \bmod n$

$c_2 \equiv m^{e_2} \bmod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \bmod n$

Note: In practice, either $a$ or $b$ will be negative. WLOG, let $b$ be negative. This leads to problems in the above equation. To get around this, use the following computation.

Let $i\equiv c_2^{-1} \bmod n$ (i.e., the modular inverse of $c_2$)

$m\equiv c_1^a\cdot i^{-b} \bmod n$

Update to show details of $m\equiv c_1^a\cdot c_2^b\bmod n$. All math below done modulo $n$.

$$
c_1^a\cdot c_2^b\\
(m^{e_1})^a\cdot (m^{e_2})^b\\
m^{e_1a}\cdot m^{e_2b}\\
m^{e_1a+e_2b}\\
m^1\\
m
$$


What is the key size currently used by RSA and Diffie-Hellman for secure communication over Internet? What is the key size that RSA and Diffie-Hellman are using now that can guarantee secure communication over Internet and will not be able to break by the best available algorithms (NFS & FFS or any others) in feasible time?

Currently (as of 2017-05-11) 2048-bit keys are most popular for use with RSA, and 2048 bit keys should also be used with classic Diffie-Hellman. These offer about the same security as a symmetric encryption algorithm with 112 bits of security.

Also in common use as of this date are 256 bit Elliptic Curve keys (mostly NIST P-256 and Curve25519) for ECDH/ECDSA/EdDSA which offer the same security as a 128-bit symmetric algorithm.

A good primer on the reasons for these key size differences can be found here.


Is One Time Pad something like this? Alphabet: [A-Z] = [0-25]

Plaintext = HELLO = 7 4 11 11 14

// QUESTION: do this key must be as long as plaintext?

KEY: [QWERT]
KEY = 16 23 4 17 19

Plaintext + Key = 23 27 15 28 33

Plaintext + Key (mod 26) = 23 1 15 2 7

Cyphertext: XBPCH

So is it correct that IF plaintext = "HELLO!" THEN the key must be six characters long, such as "QWERTY"?

For the one time pad, your key must be

The same length as the message. Whatever your unit of measurement (bits, bytes, etc), they must be the same length.
The key must be perfectly random.
The key is only ever used once.


Is this chat protocol safe? I am in the design phase of a secure chat application at the moment. I am trying to make this as secure as possible.

The Serverprovider should not have access to the messagedata.
So my idea was the following:

I have two base keys, one AES and one RSA Key.
The AES Key is derived from a password the user enters. The RSA Key is generated randomly and stored on the server. Public key normal, Private key encrypted using the AES Key. This is mainly to allow users to login from everywhere without having to transfer the privatekeyfile.
When a new Chat group is formed, a random AES Key is generated and encrypted using each users public key. Since this encryption happens on the device of the group creator, the provider of the server storing all keys never knows them. These encrypted keys are then uploaded to the server and therefore each Client can decrypt and use it.
When sending a message, a random IV is generated and stored together with the message.

So far so good, what makes me unsure is that the server knows multiple encrypted versions of the same data as well as the corresponding public keys.

Is there any way to recover the chat AES key using the combination of the encrypted keys and the public keys?

Some observations, though I would recommend against inventing your own protocol, at least for real world use:

  When a new Chat group is formed, a random AES Key is generated and encrypted using each users public key.

This means the protocol lacks forward secrecy. Anyone who compromises the private key of a chat participant can decrypt any previous chats they've been a part of. (Perhaps aside from ones where they've created the group.)

  Since this encryption happens on the device of the group creator, the provider of the server storing all keys never knows them.

Where does the group creator get the public keys? If the answer is "from the server", the server could swap one public key for another for which it has the private key. The server would then know the session key and could encrypt it for the real public key of the participant, with neither the group creator nor the spoofed participant noticing.

  Is there any way to recover the chat AES key using the combination of the encrypted keys and the public keys?

Other than the above, the server is also in a privileged position to decrypt the private keys. Since they are randomly generated, no one will be able to generate the same key and compare to the public key (assuming a secure RNG), but the server can try to brute force or dictionary attack the encryption password.

So you'll probably want to require strong passwords, include unique salts and use a password hash.


What pieces of information do you need to unhash a key to find out the original message? I am very new to the hashing world and despite hours of research (AKA Googling) I still don't understand this piece of information. What are the different pieces of information that are needed in order to unhash a SHA-256 key to reveal the original message, besides the original message itself? Or if I am way off base, what information do you need that gets you the closest to unhashing the SHA-256 key?

The closest thing I could find was this question and I would comment a question, but unfortunately, I bear the newbie banner.

If this has been answered, a redirect link or some good reading materials outside of Wikipedia would be great! I am just not sure of how/if I am asking the right questions.

You can't reverse a hash, because hash functions are one-way-functions by design. The best you can do is brute-forcing, meaning you try every input until you get the same hash-value and even then you can't be sure if you have found a hash-collision or the original message.


Forgery attack on OCB When using same nonce in OCB mode of authenticated encryption, how forgery attack can be done?

To obtain the tag, OCB xors the plaintext blocks and encrypts them. Thus a sufficient condition for a forgery is finding another plaintext with the same xor as an existing plaintext.

Consider a known plaintext attack where the attacker obtained (plaintext, ciphertext) pairs for two messages encrypted using the same key and nonce. The attacker picks between the two known blocks at each position, attempting to produce the same xor of the plaintexts.

This leads to a system of 128 linear equations, one equation for each bit in the tag. These equation constrain the attackers choice of blocks. If the messages are long enough so that the system of equations isn't overdetermined, they can solve that system of equations efficiently via standard linear algebra. If the plaintext were linearly independent, messages 128 blocks in length would suffice. In practice they're not, so you need more blocks, but I expect that increase to be modest.


Is it possible to track down copies of WW2-era codebooks? I've got an academic curiosity regarding some of the old Japanese naval codes used during World War II specifically.  I'm wondering if any of the codebooks from this era have been made available, or if they are still protected materials?

Yes, a good bunch of Japanese naval codebooks and related documents from WWII are available.

You might want to contact the National Archives and Records Administration (NARA) for that, as they hold the related NSA documents which have been declassified.

The “Declassified Documents Released to NARA” list at the NSA website points (among other things) to ample Japanese naval codebooks (random example: “NR 4037, ZEMA150, 45441A, 19440218, CODES AND CIPHERS: JAPAN JN-155 CODEBOOK”) as well as dozens of similar documents containing Japanese naval codebooks, naval call-signs, naval communications indicators, brevity codes, etc.

Looking at The Freedom of Information Act, it shouldn’t pose a big problem to get a copy of those documents to satisfy your academic curiosity.


Is every point on an elliptic curve of a prime order group a generator? If the order of elliptic group is prime then every point is a generator of that group.
I tested the above statement on some elliptic curves and found it true.
Does that really work on all curves?

Is there any lemma or theorem which states that?

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$.

Since orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, primes behave how you've been taught they do. Therefore the only possible subgroups of a group of order $p$ are the trivial group of order $1$ and the group of order $p$, i.e. the group itself.

This has a consequence, usually presented as a lemma of Lagrange's theorem - no element can generate a subgroup, so it must generate the full group.

For elliptic curve groups, there is a valid proper subgroup, the trivial subgroup consisting only of the identity, in this case $\mathcal{O}$.


What is the difference between subtracting the modulus from a scalar field element and reducing it? When implementing a Field element, we define the necessary operations on the data structure.

One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that it is in the scalar field.

What is the difference between this and subtracting the modulus from such number?

Example:

Let a be a scalar chosen at random
Let q be the modulus

I have seen code that does the following:

if a > q{
  a = q-a
}

Why did it not try to reduce a by doing the modulus?

We have many mathematical operations for the Cryptography as $$\neg, \ll, \gg , \oplus, + , \times, /, \operatorname{mod}, \operatorname{div}, \operatorname{exponential},\ldots$$ and the list goes on. As we all knew that the time is money and all of the operations have some cost. Our aim is the minimize the cost as much as possible.

For example, we prefer left shifts to multiplication by powers of two

$$ n \cdot 2^k = n \ll k$$

or right shifts to division by the powers of two

$$ n / 2^k = n \gg k$$

or combination of bitwise and operator ($\wedge$) and subtraction by 1 to remainder by the powers of two

$$ n \mod 2^k = n \wedge (2^k-1).$$

The cost of multiplication and division is reduced into the cost of the shift operation and the cost of the remainder into $\wedge$ (modulus $2^k$ is equivalent to taking the $k$ least significant bits).

In your question, you wrote

if a > q{
  a = q-a
}

This should be

if a >= q{
  a = a-q
}

for modular reduction by subtraction as noted by @fgrieu's in the comments.

In your case, we have a prime number $q$ and we are trying to take the modulus. One way during the calculations is to reduce modulo at the end. However, this may increase the size of the operands and this will result in larger operation costs.

What I can see from your piece of code that they reduce the number by subtraction with $q$. Assuming that the result $r = a-q$ is always in $$0 \leq r < q$$ then we can say that $$q\leq a<2q,$$ to see this subtract $q$ from the above equation;

$$q-q \leq a-q <2q-q$$ and get

$$0 \leq a-q=r <q.$$


Salt passwords with the username? Salts should be unique so that an attacker can't brute force multiple passwords at once. However, since usernames are unique, wouldn't it be possible to use some representation of the username as a salt?

Of course that means that if a username changes, the password needs to be rehashed. I'm asking from a cryptographic perspective, not a user-experience perspective.

However, since usernames are unique [...]

But the same user is supposed to get a fresh salt when they change their password.  Salts are not supposed to be bound to usernames as you suggest; they're bound to states of individual password database entries.  If the attacker gets their hands on multiple password entries for the same user in your scenario, those entries will have the same salt and thus there is a work savings they can achieve.

One practical illustration of this is to consider that many password storage APIs have been carefully designed to avoid salt misuse by factoring the process into these two operations:

Generate password token: Take a password as input and produce a password verification token as output.  This token incorporates:

A description of the algorithm that was used and any parameters required to rerun it;
A random salt (generated internally by the API operation);
The raw password hash output.

Verify password: Takes a password and a verification token as input, and outputs true if and only if the password checks out against the token.  Internally this:

Decodes the token to determine the algorithm, parameters, salt and raw hash;
Uses this information to select the password hashing algorithm and parameters;
Hashes the supplied password with those choices;
Compares the resulting raw hash to the one stored in the token.

When you use an API like this to manage your users' passwords, you call operation #1 not only when you enroll a new user, but also when an existing user changes their password.  Which means a new salt is implicitly generated afresh, and you can't make the mistake of reusing the same salt for the same user.

In addition, usernames are broadly predictable just like passwords are (or perhaps more so!).  Notably, an attacker can likely guess a bunch of your usernames even before they ever see your password database.  Which means that username salts are to some extent subject to precomputation attacks—if your scheme was broadly adopted, an attacker could conceivably precompute a rainbow table based on pairs of:

Common passwords (as is already well-known practice);
Usernames known to be common at large, or that have a high probability of being used among a small population of interest (e.g., a foreign adversary's influential politicians).

Which means that although password salts are nonsecret, they ideally should be unpredictable as well.  That sounds like an oxymoron at first, but what it means is that an attacker should not be able to guess what a password entry's salt might be before they actually see the entry.  Random salts trivially ace this test; usernames don't score well on that criterion, and neither do @cypherfox's "site identifiers" or counters, for that matter.


How do we prove that AES, DES etc. are secure? How do we prove that AES, DES etc. are secure? I've read about them and know the basics on how they work, but I still don't quite understand how we can be sure they are secure? What are the proofs?

We don't prove schemes like AES and DES secure. Instead, cryptanalysts try very hard to find attacks against the scheme. If, after much effort, no attack is found, we may with some justification consider the scheme secure.

The statement that a scheme is secure usually takes the form "any adversary that breaks the scheme with this much advantage must use at least this much time". For symmetric cryptography, this is often equivalent to saying that exhaustive key search is the best attack. Note that "breaking the scheme" is a technical notion, and the precise definition is often complicated.

Sometimes, schemes can be proved secure against certain classes of attacks. I think AES has been proved secure against certain forms of differential and linear cryptanalysis. This does not prove that no other attacks exist, of course.

Sometimes, schemes can be proved secure under the assumption that a smaller scheme is secure in some sense. E.g. the Merkle-Damgård construction shows that hash functions can be constructed from compression functions.

Sometimes, we can prove that a scheme is secure under number-theoretic or complexity-theoretic assumptions. Unfortunately, these schemes are often very slow compared to schemes like AES. It is also not a priori clear why a "natural mathematical problem" must be harder than the "man-made problems" posed by schemes like AES.

In idealized models, there are many provably secure schemes (typically indifferentiability proofs) that are both interesting and valuable, but these do not describe the real world, so the results must be interpreted and used with care.


Multithreading PBKDF2 or javascript alternative I'm using PBKDF2 in browser (can't use bcrypt, users are likely to have passwords > 72bytes, or whatever the number was). PBKDF2 is running in a webworker, something like so

const key = PBKDF2_HMAC_SHA512.bytes(passphrase, salt, Math.pow(2,17), 64)

This key is used to encrypt data to be stored in the user's localstorage. Now I wonder, seeing as I'm already using a webworker, why not use multiple? Would I not be able parrallelize it? Could I not do something like(simplified, in reality each key is generated in a separate web worker)

const key1 = PBKDF2_HMAC_SHA512.bytes(passphrase, salt1, Math.pow(2,17), 16)
const key2 = PBKDF2_HMAC_SHA512.bytes(passphrase, salt2, Math.pow(2,17), 16)
const key3 = PBKDF2_HMAC_SHA512.bytes(passphrase, salt3, Math.pow(2,17), 16)
const key4 = PBKDF2_HMAC_SHA512.bytes(passphrase, salt4, Math.pow(2,17), 16)
const key5 = new Uint8Array(64)
key5.set(key1)
key5.set(key2, 16)
key5.set(key3, 32)
key5.set(key4, 48)
const key = SHA_512.bytes(key5)

Would this not be 4x more secure? Or more importantly, could I not halve the rounds per instance of pbkdf2 and still end up with 2x the security? If I'm wrong, could someone point me in the right direction for a faster/more secure parallelizable kdf?

Yes, this would improve security. In fact, you do not even need to use individual salts. Simply concatenating the thread number as a counter with the input key would be enough:

Input: k, a short key to be strengthened with a KDF
Output: h, the final output hash

spawn_thread(h0 := slow_KDF(k || 0))
spawn_thread(h1 := slow_KDF(k || 1))
spawn_thread(h2 := slow_KDF(k || 2))
...
spawn_thread(hn := slow_KDF(k || n))

wait_for_all_threads()

h := fast_hash(h0 || h1 || h2 || ... || hn)

However, this is not particularly efficient. Every time you double the number of threads (assuming each thread is truly independent and not sharing any resources), you add the equivalent of one bit of security. A single extra byte added to the input provides the equivalent increase in difficulty as running this on a system with 256 independent hardware threads. Assuming you will not get more than 8 parallel KDF instances, you will never increase security by more than a mere 3 bits...

Instead, you should be using a KDF that is memory-hard, preventing an attacker from using a GPU or ASIC from parallelizing an attack against PBKDF2. An example would be Argon2, which natively supports parallelism in addition to a configurable amount of memory.


Procedure that does encryption I am looking for an algorithm/procedure that encrypts a text
where the alphanumeric data is encrypted into password-protected alphanumeric data.

I have seen other algorithms where a text like "Hello, How are you?" will be encrypted into something like this: JHo+8D337H/hLwg9n2n2n8+du783bsH9hdsSEWj93==

This is not what I am after.

I am looking for something that does this: "Hello, How are you?"
will be encrypted into "Kjehh, Jey uwh wmd?"

Any idea how to do that?

I would suggest using a classical cipher like Vigenère, for example:

Plaintext:  Hello, How are you?
Key:        topsecret
Ciphertext: Asads, Jfa tks ngy?

But bear in mind that classical encryption techniques are very insecure by modern standards.


Distributed key generation + signature scheme? I'm looking for a special signature scheme that has the following features:

There is a group. The group consists of $n$ key centers and 1 user.
All group members have their own private keys, and public keys that satisfies feature 3.
If the user signs (or, private key operation) a message using his private key, then the $n$ key centers (or specific $t < n$) can find out what the public key that used to sign the message is (or, who is the user).

Is there any scheme appropriate for these features? Or a scheme which is similar?

I looked at lots of signature schemes such as group/threshold/ring..., but I cannot find a suitable one.

If I understand you correctly, you want a system designed such that

A group of $n+1$ people -- Alice, Bob, Eve, Trent, and James -- each have their own private key, and each one knows who is in the group and all of the corresponding public keys of everyone in the group.
Alice can sign a message and package the message and the signature, and then transmit the packaged message publicly in such a way that:
Any one person in the group, such as Eve -- using only the information in the packaged message itself and her own list of people in the group and their corresponding public keys -- does not have enough information to figure out who the message came from, without the cooperation of anyone else in the group
If people in the group cooperate -- all $n$ people cooperate, or some specific threshold of people $1<t \leq n$ -- they can verify that the packaged message was signed with Alice's private key.

Off the top of my head (warning: untested protocol), perhaps something like this would fulfil those requirements:

Alice takes the original plaintext message, and signs it with her private key to generate a detached signature file.
Alice uses any secret splitting technique to divide a signing message -- something like "My name is Alice, and I sign Manifesto X thus:" concatenated to the detached signature file -- into $n+1$ share files.
Alice uses each one of the $n+1$ public keys in her list of group members to encrypt one of the share files.
Alice packages up all $n+1$ encrypted share files and (optionally) tags each encrypted file with the name of someone in the group and (optionally) the original plaintext message file, in one big packaged message.
Alice securely erases the detached signature file and the (unencrypted) share files, and then broadcasts the packaged message.
Eve attempts to decrypt all the share files in the packaged message, but her private key is only able to decrypt one of them (the one tagged "Eve"). Also, the decrypted contents of that file are a share file, which alone is not enough to recover any information about the signing message.
If enough people in the group cooperate, they can combine (decrypted) share files to reveal the signing message.
Once a person has the original plaintext message and the signing message and Alice's public key, that person can extract the detached signature and use it to verify that Alice's private key was used to sign that message. (If the signing message includes only the detached signature file, without any additional identification, then repeat this step with every public key of everyone in the group to find one that verifies).

I suspect there may be a group signature scheme or ring signature that may be a better solution than the above untested protocol.


ElGamal Decryption variant I am trying to do some ElGamal encryption but having a different encryption formula.
For that I doing the following steps:
The key generator:

Choosing value $p = 107$ and $a = 2$
Random number $d = 67$, and $b = a^d \bmod p$ where $b = 2^{67} \bmod 107 = 94$
$k_{priv} = 67$ and $k_{pub} = (p,a,b) = (107,2,94)$

Encryption

Random value $v = 45$ and $C_1 = a^v \bmod p = 2^{45} \bmod 107 = 28$
We have the message $m = 66$; $C_2 = m \cdot b^v \cdot a^v \bmod 107 = 66 \cdot 94^{45} \cdot 2^{45} \bmod 107 = 38$
Finally, $C = (C_1, C_2)$

My problem comes when I try to decrypt the message, maybe I am totally wrong. But I am doing:
$C_1 = a^v$
$C_2 = m \cdot a^v \cdot (a^d)^v$
$C_2 = m \cdot C_1 \cdot (a^d)^v$
I trying to do that is where I am a little bit lost. If someone can help me with a clue to decrypt the message I would be nice

Finally, the decryption is: $m = C_2 \cdot C_1^{-1} \cdot C_1^{-d}$


Does encrypting both the message and digital signature adds to the integrity of the digital signature? Reading Cryptography And Network Security Principles And Practices 6th Edition by William Stallings, I came across the following excerpt on digital signature that got me confused:

  A -> B: M || E(PRa, H(M))

  This method guarantees that A cannot later deny having sent the
  message. However, this technique is open to another kind of fraud. Bob
  composes a message to his boss Alice that contains an idea that will
  save the company money. He appends his digital signature and sends it
  into the e-mail system. Eventually, the message will get delivered to
  Alice’s mailbox. But suppose that Max has heard of Bob’s idea and
  gains access to the mail queue before delivery. He finds Bob’s
  message, strips off his signature, appends his, and requeues the
  message to be delivered to Alice. Max gets credit for Bob’s idea. To
  counter such a scheme, both the message and signature can be encrypted
  with the recipient’s public key:

A -> B: E(PUb, [M || E(PRa, H(M))])

Where

A -> B: A is the sender (Bob), B is the recipient (Alice)
M = Message
E = Encryption function
PRa = A's private key
H = Hash function
PUb = B's public key

My understanding of digital signature is that by decrypting with Bob's public key, Alice already knows that it was signed by Bob (provided Alice is guaranteed to have Bob's real public key, which is not discussed in this excerpt). So if Max replaces Bob's signature, Alice will be alerted already that the signature was forged. Encrypting the whole message as in the final solution does not add anything to the integrity of the signature, it only prevents from eavesdropping, right ?

First of all, the fact that A is Bob and Alice is B is a bit confusing.

In my explanation:

A - Alice (receiver), has keys PRa, PUa
B - Bob (sender), has keys PRb, PUb

The former approach has a couple of substantial drawbacks:

The message is send in a plain text. Any one who has an access to a communication channel can read its content.
The signature of a message hash is separated from the actual message. They are only concatenated together and as the signature has a fixed size it can be easily stripped from a content.

The first drawback allows Max to read a content and decide that he wants to commit a forgery as it makes sense for his agenda.

The second drawback actually allows him to forge the email. He can easily calculate H(M). Assuming Max knows Bob's public key he can strip of the H(M) "verifying" the signature with Bob's public key.

Then Max simply signs the H(M) with his private key (PRm) and substitutes block E(PRa, H(M)) with E(PRm, H(M)).

The result would be that the message looks like sent by Max as it's signed by his private key and nobody can detect that it was originally an idea of Bob.

The later approach with encrypting both content and a signature with Alice's public key guarantees that only Alice would be able to decrypt the whole packet (thus content + signature).

Max won't be able to substitute the signature with his own as he doesn't knows PUa. Neither M, nor H(M) is possible to recover for him.

When Alice would receive the message it would decrypt it with her own private key (PRa) and then verify the signature with Bob's public key (PUb) thus being sure that the message was indeed send by Bob.

This pattern would still lack integrity check but generally it's much better then the former one.


How badly does disclosing an M-bit prefix of an N-bit private key compromise security? I apologize profusely for knowing nothing about cryptography, please go easy on me!

I'm working on a project where I have a 2048-bit RSA private key and a public certificate generated from the private key. I encrypt secrets at one end-point using the certificate and decrypt them at another end-point using the private key.

On decryptor app startup, the code that parses the private key will throw an exception if the private key is unparseable. Right now the exception message discloses the first 21 bits of the key. My question is whether, and to what extent, this could compromise my secrets' security if the exception message got into a log file and was stolen by a malicious attacker.

Does disclosing the 21-bit prefix effectively reduce my 2048-bit private key to a 2027-bit private key? Or does it actually compromise things worse? Or does it not materially change the difficulty of guessing the full 2048-bit key?

EDIT: My private key is required to be DER-encoded in PKCS#8 format, so we are likely talking about the first 21 bits of a DER-encoded, PKCS#8-formatted, private key.

I further assume you mean a DER-encoded unencrypted PKCS#8 RSA key, since you wouldn't care about exposing an encrypted key, and it's a conventional two-prime key with equal-size factors (each 1024 bits) and the ubiquitous e=65537 using the standard PKCS#1 CRT-form representation.

I also note that 21 bits is a really odd amount to disclose: not 2 octets, not even 2 and half octets, but 2 and 5/8 octets? Anyway ...

It compromises ALMOST CERTAINLY NOTHING.

Unencrypted PKCS#8 is a SEQUENCE that contains a version INTEGER, an AlgorithmIdentifier and an OCTETSTRING containing the encoding of the key, which for PKCS#1 is a SEQUENCE containing another version INTEGER, then the modulus, then the public exponent, and only then the private exponent and other private values. For RSA the AlgorithmIdentifier is one of two fixed values depending on whether the inapplicable parameters are encoded as NULL or omitted.

Thus at least the first 20 octets of the PKCS#8 encoding are fixed values independent of your key, EXCEPT that the length field of the outer SEQUENCE reflects the length of the inner SEQUENCE, which in turn varies slightly (up to 4 octets) depending on whether the private exponent d happens to be >= 2^2047 and the three CRT values (dP, dQ, qInv) happen to be >= 2^1024, and thus need "extra" sign octets. If an adversary knows the PKCS#1 length (and thus the PKCS#8 length) is at its minimum or maximum, it gives less than 1 bit information about d. In between the min and max I don't think there are any usable relationships between dP dQ qInv and d but I can't rule it out, so worst case up to 1 bit there also. However the length ranges 0x04BC to 0x4C0 or 0x04BA to 0x04BE and is in the third and fourth octets, so IF your 21 bits are big-endian (that is, all of the first two octets and the top 5 bits of the third octet) then it includes no information about the part of the length that could be useful.


Is there an application of fully homomorphic encryption scheme such that encryption key and evaluation key are different? I want know if there is an application of FHE contains three kinds of users such that:

$A$ is the data owner and she has the secret key.
$B$ only has the permissions to encrypt (just like a general user).
$C$ has the permissions to both encrypt and evaluate (just like the cloud or other servers)

Dose this kind of application of FHE make sense? And it is under the condition that encryption key and evaluation key are different. However, I haven't seen the application like this.

On the literature, these are called 'keyed fully homomorphic encryptions', with three keys: $\mathit{pk}$ is the public encryption key, $\mathit{sk}$ is the secret decryption key, and $\mathit{ek}$ is the secret evaluation key.

Yes, the scenario actually makes sense at least for the cloud computing: there, only the 'cloud provider' needs to do homomorphic evaluation, and there's really no need to extend the capability further.

Rather, I think that it is the other way around: of course we can extend the evaluation capability to anybody, but why do we need to do that?  One reason might be that if the application is not about cloud computing, perhaps there could be reasons that an arbitrary person needs to evaluate ciphertexts homomorphically.  But, there could be many scenarios where the keyed FHE would be fine.

Moreover, for keyed FHE, you can actually define and achieve IND-CCA security: the reason why IND-CCA is impossible for FHE is the malleability, and when the adversary does not have the homomorphic evaluation ability, the attacker can no longer carry out the obvious CCA attack, so to an 'outsider' without $\mathit{ek}$, the scheme can be IND-CCA, but of course to an 'insider' with $\mathit{ek}$, the scheme can be at most IND-CPA.


Can high-entropy data be reconstructed from plaintext XORs in CTR nonce reuse? (My interest is academic; I certainly have no intention of rolling my own crypto, especially the known-broken type!)

I know that if the nonce gets reused in a CTR stream, the two cipher blocks can be XOR'ed together to produce a XOR of the plaintexts. From there, the plaintext is recovered using analysis, such as searching for words. This makes unathenticated memory encryption, used in practice, insecure against someone who can edit the counter and trigger reuse.

But my understanding is that such analysis is enabled by the very low entropy of sample plaintexts - the usual examples are English text or bitmap images, which only use a small fraction of the block's information capacity.

Since txt files and bitmaps are relics at this time (easily found in OS files, though), could the attacker still recover the key from XORs of higher-entropy plaintexts in modern data formats?

Specifically to consider .docx, which is compressed with zip (weak compression), and lossy-compressed images or video (high entropy, but they include structure and headers, and can be useful even if severely damaged).

What if the nonce was reused many times, giving the attacker a much larger amount of information? I have a feeling that there might be some mathematical limit, e.g. best-case plaintext recovery requiring at least 1-(1-(entropy/Shannon_limit))^number_of_pairs>entropy/Shannon_limit.

But no idea if that holds, or if there are techniques to reconstruct plaintexts from XORs of general-case data, rather than specific kinds such as natural language.

A block cipher in CTR mode is just a stream cipher.  You have a stream of bits that are indistinguishable from random (assuming good things about the block cipher) and you xor that stream with your plaintext.

What happens when you reuse the stream?  It allows an attack to take their knowledge of one plaintext and use that knowledge to expose information about the other plaintext.  If you encrypt all-zeros as the plaintext (or any message entirely known by the attacker) then the attacker knows the stream and can perfectly decrypt the second message, no matter what that message is.  If, for the re-used portion of the stream, you encrypt two different perfectly random and secret bitstrings then the attacker will learn the relation between the bitstrings, $M_1 \oplus M_2$ but nothing more.


NIST's Methods for Key Wrapping? NIST has specified a full Mode of Operation for Key wrapping. What are the pros and cons of key wrapping mode of operation as compared to CBC, CTR or authenticated encryption mode?

There are the differences (whether they're con's vs pro's depends somewhat on what you're using it for):

Performance; the NIST key wrap is much slower than anything else on your list (and can't be parallized; some algorithms on your list can be).  On one hand, if you're using it for key wrap, well, we typically don't wrap/unwrap keys so frequently that it really matters.  On the other hand, you probably don't want to try to use it to encrypt packets on your 10Gbps link...
Integrity; if the attacker modifies a key wrapped ciphertext, there is a probability circa $2^{-64}$ that, on unwrap, it would be a valid (and effectively random) key; this probability is considerably higher than an authenticated encryption mode (but better than CBC or CTR without any integrity protection whatsoever).
Determinism; the key wrap algorithm is deterministic (based on the wrapping key and the plaintext); hence, if you wrap the same key twice with the same wrapping key, an attacker can detect that; the other modes you have listed are randomized.  On the plus side, this means that the key wrap mechanism is not subject to 'algorithm substition attacks' (where the attacker doesn't use a truly random randomizer, but instead selects values that leak some information).  In addition, you can make the key wrap randomized by the simple expedient of including some random data along with the key (and which is discarded after the unwrap).
Ciphertext overhead; the key wrap adds 64 bits to the plaintext length (assuming that the key you're wrapping is a multiple of 64 bits in length); this is less overhead than the other algorithms.

You might be wondering about differences in cryptographic strength.  There is effectively no difference; as long as the wrapping key is secure, and everything is done properly, any of these methods listed is essentially immune to cryptanalysis.


The role of the dealer in visual cryptography In visual cryptography schemes (VCS), there is special person called dealer. The dealer sets up the system, and the only one who knows about secret image. After encryption, the dealer distributes the shares to participants.

My question is, the dealer is one of $n$ participants or it should be from outside?

The dealer is one of n participants or it should be from outside?

The dealer, knows the secret as he's the one who shared it. Thereby it makes no sense to give him a share as well, unless you have a such a scheme that requires all partys to collaborate to recover the image, but then the question becomes: "Why bother secret sharing at all if the dealer could just store it if consensus with him is required?"

TL;DR: He can be part of the participants, but there's no benefit of him being one.


Is the One Time Pad (OTP) considered a cryptographic hash function? As the title states, would the One Time Pad (OTP)  be considered a cryptographic hash function?

No, OTP would not be considered a cryptographical hash function.

OTP takes a key; cryptographical hash functions don't
It's generally expected that the output of a hash function be of fixed length, independent of input length.  The output of OTP is the same length as the input.
Hash functions are deterministic (that is, if you give the same input twice, you get the same output); if your hash-like OTP function uses a new portion of the keystream for every message, than the exact same input will yield different outputs if you call it repeatedly.


How does one deal with a negative "d" in RSA? I'm trying to write my own RSA implementation using the textbook approach — which I know is not optimal — of picking primes $p$ and $q$, then computing Euler's totient $phi$, then randomly picking an 'e' which is relatively prime to $phi$, and then computing a $d$ such that ($d*e$) mod $phi$ = 1.

For that last step, I'm using the algorithm provided at http://www.pagedon.com/extended-euclidean-algorithm-in-c/my_programming/

This algorithm often yields a negative $d$, which sure enough does satisfy $d*e$ mod $phi$ = 1. But obviously I can't use a negative $d$ as the exponent during decryption.

Is there some straightforward way I can amend this algorithm, Or is it rather my understanding that needs amending?

In modular arithmetic all of $a + k \cdot m$ with modulus $m$ and integral $k$ are equivalent. You need to solve this equation modulo $\phi$. So $-x$ is equivalent to $-x + k\cdot \phi$ with a sufficiently large $k$ to make it positive.

In code you can use something like:

d = d % phi;
if(d < 0)
    d += phi;


Can key hardening compensate lack of entropy? In the context of an offline brute-force attack on encrypted data at rest (say, a password-protected AES encrypted file), is a password with 64 bits of entropy and 65536 rounds of key hardening just as strong as a password with 80 bits of "true" entropy (and no key hardening)?  I guess what I really want to know is, can I get away with using a shorter password if I know that key hardening is applied?

Yes. That's the entire idea of key stretching, you can get away with a password that offers less strength against attacks. You add more operations to a brute force/dictionary attack to protect the keys. The disadvantage is that you need to do the same number of operations during key derivation.

Passwords commonly don't have 64 bits or 80 bits of entropy though. Say that the alphabet is 64 characters (6 bits) then you'd need a fully random password of 11 characters. For 80 bits you'd already need 14 characters. Those are easy to generate of course, but it may be tricky to remember them. And if you have to revert to a password manager, you might as well use a password that requires a few more keystrokes.

Note that shorter doesn't necessarily mean less strength. A password of 12 zero digits is not very strong. And although the idea behind "correct horse battery staple" is great, the strength of the passphrase is of course not the same as 28 fully random characters.

J.D. indicates that, indeed, different operations are performed for a single round. The amount of operations however will stay the same, so the increase should be in the same ball park. You could possibly assign a weight to each round of AES vs each round of the key strengthening routine to get a better estimate about the increase of strength.


Hash function for a small, enumerable set of elements Suppose you have a set of elements, that is relatively small (e.g. 100M) and its elements can be easily enumerated. For example phone numbers, that have a maximum fixed length and they are composed of only digits.

I would like to find a way for parties involved in an open communication to reference to elements without mentioning them in cleartext, so that only who "knows" a given element can understand that a message is referring to it.

For example, if elements would be arbitrary large files, parties may identify them by MD5 or SHA1 and communicate mentioning the hashes. Only the party that has the same file may understand that a hash actually refers to that file. This is based on the difficulty to invert the hashing function and to the fact that the set arbitrarly large files is almost infinite.

This mechanism however doesn't seem to work well when the set of the elements is small and enumerable.

QUESTION: do you envision another pattern the parties can implement to openly communicate and reference to the shared elements, without revealing their value?

To the best of my understanding, you're trying to make phone->ID an irreversible transformation. For long inputs, hashing would suffice, but there are so few possible inputs (phones) that enumeration is feasible and even a slow PBKDF won't make mapping prohibitively difficult.

Strong security is impossible in this scenario. The best you can do is slow down the data gathering process. To do that, you have to be the only one able to perform the transformation; that requires keeping a secret. It's not a salt then, but a key. The transformation can be hash(phone+key) or just encryption of the phone with the key - if the key is leaked, the security is broken either way.

Preferably, I'd suggest that you consider alternative approaches. If it's a way to find "friends", do you have to reveal the ID right away? For instance, when one enters a phone number, you only send a friend request to that number's corresponding ID if it exists, without confirming whether it does. Only upon request confirmation do you reveal the ID. Can be combined with a friends-of-friends system to limit random requests.

Don't count on this for much. But, combined with limits on accounts and friend requests, and some monitoring for suspicious activity, it could make mapping the users take more effort than it's worth. If and only if that mapping actually isn't worth much.


How is the message digest related to Signatures and Encryption? I was studying about 'Data Security' and I found out this one thing confusing.

What is a message digest? I got it is the hash of the message.

Is the message here referring to the plaintext or cipher text? I believe when using Digital Signatures, the message itself is also encrypted with a public key.

First of all, yes, the message digest is the hash of the message.

Secondly, do not mix things up. You are talking about public key encryption and signature. Let's redefine them to make sure we have everything right.

Alice and Bob got pairs of key ($A_{pub}$, $A_{priv}$), ($B_{pub}$, $B_{priv}$). Alice knows $B_{pub}$ and Bob knows $A_{pub}$.

Alice wants to send a message $m$ to Bob $\implies$ She encrypts it with $B_{pub}$.
Alice wants to prove to Bob that it was she who sent the message $\implies$ She signs it with her private key $A_{priv}$.

How does the message digest appear in all that ? Continue reading.

Problem: signing and encryption using RSA (standard procedure) is slow. How to speed up the process ?

Alice encrypts the message with a symmetric cipher (AES) using a random generated key $K_{sym}$. Then, encrypt $K_{sym}$ with the $B_{pub}$.
Alice does not sign the message, she signs the message digest. Smaller therefore faster.

All this together ? Here are the steps :

Alice hashes the message $m$ $\implies$ she gets the message digest.$H(m) \to MD$.
Alice signs $MD$ with her private key.
$E_{A_{priv}}(MD) \to Sig$.
Alice generates a random key for the symmetric encryption.
$rdm() \to K_{sym}$
Alice encrypts the message and the signature with a symmetric cypher.
$E_{K_{sym}}(m\|Sig) \to c$
Alice encrypts the symmetric key with Bob's public key.
$E_{B_{pub}}(K_{Sym}) \to K_{cipher}$
Alice sends $(c,K_{cipher})$ to Bob.

Remark: It is a good practice to have 2 pairs of keys : one for encryption, one for signatures.


Cryptographic hash function based on logistic map? Is there any secure cryptographic hash function based on the logistic map?

A brief description of such functions can be found in chapter 9.3 of the paper “Cryptographic Hash Functions: Recent Design Trends and Security Notions” (eprint.iacr.org/2011/565). The following excerpt is taken from page 29 of the paper:

  Hash functions based on chaos theory use chaotic maps, which are functions that exhibit particular chaotic behaviours; examples of these maps include: logistic map [source #75], tent map [source #120], and cat map [source #42]. Unfortunately, most chaos-based hash functions suffer from poor efficiency due to their inherent complex structure, which makes them unattractive as a practical approach for building hash functions.


My SSH server public key is 2048 bits, but my account's private key is 4096. What is my effective security? My SSH server has a 2048-bit public key. But my private key, for clients to login, is 4096-bit.

In this case, do I have the brute force protection of 2048 or 4096 bits?

My worry is that someone could brute force the private key and login to the server.

It appears that based on your description, the server has a 2048 bit key pair and the clients logging in have 4096 bit key pairs.

  In this case, do I have the brute force protection of 2048 or 4096 bits?

For someone to impersonate one of your users, they would have to break the 4096 bit key.

For someone to impersonate the server, they would have to break the 2048 bit key.

  My worry is that someone could brute force the private key and login to the server.

Unless you work for some huge financial institution or a government, if someone could break either of those key sizes they are likely not going to go after you. ATM, there is no publicly available way to brute force a 2048 bit key. Someone with the ability to do it could easily make millions of dollars. So I'd say you are safe.


Can I store the initialisation vector (IV) in the filename? I'm encrypting a file and I'm using an initialisation vector. Given that the IV doesn't need to be a secret, is it secure if I add it to the encrypted file's name?

Yes, you can store the IV any way you want.  Putting it in the file name is no different from putting it in the file contents.

(Actually, there's nothing specific to cryptography here.  You could take any file you want and decide to move, say, the first $n$ bytes of its content into the file name.  It's all just data.)

That said, as SEJPM notes in the comments, to protect your data from tampering you really should use some form of authenticated encryption (either with a bespoke AE mode, or using the generic Encrypt-then-MAC construction), and you do need to include the IV in the authenticated data, no matter where it's stored.

The risk here is that, depending on the cipher mode used, tampering with the IV could allow an attacker to modify the plaintext in more or less predictable ways.  Even if decrypting with the wrong IV just produces gibberish, an attacker may be able to combine this with other attacks to learn something about the plaintext, especially if your code leaks information about the "gibberish" on decryption failure.  Using authenticated encryption protects you from this.

Also, a practical risk with storing data in the file name is that people are much more likely to rename files than to randomly tamper with their contents (especially if the contents just looks like random binary data).  Thus, using the file name to store critical data like the IV could lead to an increased risk of accidental data loss or corruption.


PKI Encrypted hash vs Signing I have a confusion in a concept under cryptography context. What is the major difference between an encrypted hash and digital signed hash?

I have used PKI Encryption i.e. public / private key based encryption.

I calculated the hash and encrypted it with the private key of sender. Now, the receiver can unlock the hash with the public key of sender. Hence it proves the authenticity of the data. Now receiver can regenerate the hash and match with the decrypted one and if matches then it proves the data integrity.

Similarly, the signature is created by an hash and same is encrypted; and it is done by private key of sender. Now the receiver can verify the signature by public key of sender. It proves both authenticity and integrity.

I have used both in my case (that i am developing). I think I am using signature / hash as an extra element and only one of them will suffice.

Or is their any benefit of using both or any difference?

The difference between encrypted hash and a digital signed one is twofold:

the key to be used for signature generation is the private key, so technically it is not encryption;
the padding scheme is different for both situations.

The use of the wrong key is already enough to not talk about encryption as explained in my Q/A here.

In the case of PKCS#1 v1.5, both encryption and signature generation are often referred to by the same name. However, both use a rather different scheme for the padding of the content (the plaintext message for encryption and the hash for signature generation).  For RSA v1.5, RSA encryption is called RSAES-PKCS-v1_5 and uses the EME-PKCS1-v1_5 encoding scheme. Signature generation is called RSASSA-PKCS-v1_5 and it uses the EMSA-PKCS1-v1_5 encoding method. Note that these names have only been introduced in version 2.0 from the specification.

The main issue is that the padding for encryption was designed to add a random component to the padding. This is required because otherwise identical messages would result in identical ciphertext, leaking information to anybody seeing both ciphertext. As it is random padding, it cannot be validated. On the other hand, signature generation uses a known padding which can be validated. This is important because you would want the unpadding to fail when verifying the signature in case it has been tampered with.

So using the wrong padding scheme means that the security premises of the RSA mode and padding are not valid anymore. This is one more reason why signature generation should not be thought of as encryption of a hash value. Both use the RSA problem to be secure. Practically speaking only the modular exponentiation is identical for both.


Sodium crypto_aead_aes256gcm_encrypt ciphertext length > plaintext length Using the crypto_aead_aes256gcm functions from Sodium produces a ciphertext of "at most mlen (plaintext length) + crypto_aead_aes256gcm_ABYTES bytes (16 bytes) are put into c (ciphertext), and the actual number of bytes is stored into clen if clen is not a NULL pointer. The phrase "at most" is deceiving because, in testing, ciphertext length is always plaintext length + 16 bytes. Why is this the case if in the specifications for GCM the output is a ciphertext, denoted C, whose bit length is the same as that of the plaintext (5.2.1.2).

I was going to attempt to read/write files using this, so would I just read 32 bytes at a time?

The result you are getting is the cipher text (the encrypted data) plus 16 bytes of authentication data. The authentication data (mentioned directly below the ciphertext in the resource you cited) ensures that the ciphertext cannot be changed without the change being detected, and is the (most important) thing that distinguishes GCM from regular CTR-Mode.

The authentication data is the same length, no matter how much data you encrypt. So, if you encrypt 1024 bytes, you will still only get 16 bytes of authentication data. This means that you will only have to plan for those extra 16 bytes once and can read / write all remaining data as usual, although it would probably be a good idea to check some open source projects using the same library and cryptography and see how they are doing it, just to be sure you're not making any mistakes (at least that's what I usually do).

Edit: Also note that implementation questions are better suited for Stackoverflow, as the Crypto Stackexchange mostly deals with the concepts and not the implementations of cryptography.


Pseudorandom Generator In a cryptographic application, two types of (pseudo)random bit streams are needed:

a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and
a stream $B= b_{1}b_{2}b_{3}\ldots$ in which $\Pr[b_{i}=0]=2/3; \Pr[b_{i}=1]=1/3\ \forall i$.

Propose the following constructions:

Given a generator $G_{A}$ for $A$, propose an efficient construction that uses $G_{A}$ to generate $B$.
Given a generator $G_{B}$ for $B$, propose an efficient construction that uses $G_{B}$ to generate $A$.

I don't need the solution to this question. I want to know, how to think about this problem to get a solution. I know basic definition of Pseudorandom generator.

The hints given refer to unbiasing algorithms, which is the standard answer in cryptography. However, there is a very nice and different solution for the example of generating the $(2/3,1/3)$ distributed bits from an unbiased stream which I will mention here. For clarity call the output symbols $a$ and $b$ with $p_a=2/3=1-p_b$ instead of using binary symbols
Expand the probabilities in base 2 to get:
$$
\frac{2}{3}=0.101010101010\ldots
$$
and
$$
\frac{1}{3}=0.0101010101\ldots
$$
which means these probability atoms have dyadic expansions
$$
\frac{2}{3}=\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\cdots=\frac{1/2}{1-{1/4}}
$$
and
$$
\frac{1}{3}=\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\cdots=\frac{1/4}{1-{1/4}}
$$
This decomposition yields the following infinite tree which generates the symbols required:

if the unbiased bit is 0 go left, otherwise go right, when an $a$ or $b$ is emitted start again;

(the first left branch should have the symbol $a$).

In Chapter 5 of Cover & Thomas' Elements of Information Theory book  it is proved that this procedure is optimal, i.e., it gives a tree of expected minimum length generating this distribution.
Edit: As in the comments by @supercat, if $p$ is unknown but the input bits are independent, one can group say $3-$tuples into two sets of desired probability ratio, and also try to maximize the probability that a bit is actually output.  $k=3$ is convenient for this case since the binomial coefficients $\binom{3}{j}$ are divisible by 3, if we ignore the first and last coefficient, so the grouping to obtain a $(1/3,2/3)$ probability [when symbols are output] becomes possible. Concretely

If you see 100 or 011, output $b$. If you see 010, 001, 101, or 110, output $a.$ If you see 000 or 111, throw out the bits and try again.


Real life collision when only using truncated hash For MD5 two different inputs are known that produce the same 128 bit hash value. However, these inputs are artificially created for this specific purpose.

For normal, real life inputs I believe no such collision is known?

When you only consider the first n bits of the hash however certainly such collisions are known for small n.

My question: what is the largest n bits truncation for which an accidental collision is known?

(of course answers need not be limited to MD5 but can also be about others hashes)

Accidental collisions are interesting for certain applications, and one would expect accidental collisions to occur less frequently in a system than malicious collisions.

So, if you are not worried about malicious collisions, only accidental, it is easy to compute how many digests you would need to compute before seeing an accidental collision. If the output of the hash (either truncated or not) is $n$ bits long, you would expect to see an accidental collision once there are about $2^{n/2}$ digests in your database.

As for what is publicly known for accidental collisions, I haven't come across any data. Probably because accidental collisions are not very interesting. We know exactly how many digests to compute before expecting to see one, so why waste the electricity to experimentally validate what we already know mathematically?

Looking at some numbers for SHA-1 on a GPU, if you can perform $1,746,000,000\approx 2^{30}$ sha-1 operations per second, and we would expect a collision after $2^{80}$ operations, it would take $2^{50}$ seconds (or about $35702051$ years) to see an accidental collision (ignoring future increases in computation power).

On the other hand, the same website lists MD5 at about $5,570,000,000\approx 2^{32}$ MD5 computations per second. A collision would be expected after about $2^{64}$ computations. That equates to $2^{32}$ seconds (or about 136 years).

You can follow the math then to see how long for various truncated versions of both MD5 and SHA1.