How to select parameters for elliptic curves not found in standards (Hessian, Jacobi Intersection, Jacobi Quartic, etc)? I am currently in the process of researching different forms of elliptic curves defined over prime fields. In many curve standards, such as NIST, Brainpool, etc, there exist a list of curve equations for Weierstrass, Montgomery, and (twisted) Edwards curves.
However, I wish to also investigate various other curve forms, such as Hessian, Doche-Icart-Kohel, Jacobi intersections, Jacobi quartics, etc, but unfortunately I have been unable to find any such standards covering the selection of these curves. I'd like to know if any such papers / websites exist that detail some curve equations for each form. A list of curve equations with different parameters for these forms would be ideal.

Weierstrass models can be converted to Hessian and Jacobi models (where such models exist) and in the days before Edwards curves were considered for ECC-based on implementation and side-channel properties.
The conversion to Jacobi model seems to be covered on mathoverflow.
To convert to Hessian, compute the $j$ invariant in $\mathbb F_p$ and then solve
$$j=\frac{c^3(c^3+216)}{(c^9-81c^6+2187c^3-19683)}$$
for $c\in\mathbb F_p$ (if the corresponding degree 9 polynomial has a root in $\mathbb F_p$). Your curve is then birationally equivalent to
$$X^3+Y^3+Z^3=cXYZ.$$
The Handbook of Elliptic and Hyperelliptic Curve Cryptography section 13.1.5.b shows how to explicitly calculate the binational maps if you want to find the image of specific points on the Hessian.
Thus you could take a standard Weierstrass model (e.g. NIST P256, Curve25519) and likely convert it to an alternative form if you so wished.


What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus? For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. What if the bitlength of $a$ is much greater than $2k$? Is the result of Barrett Reduction still correct?

This depends upon how close $\mu/2^{2k}$ is to $1/n$.
In Barrett reduction we approximate the integer $q=[a/n]$ with $q'=[a\mu/2^{2k}]$ in the operation
$$a\mapsto a-qn.$$
If we write $\delta=1/n - \mu/2^{2k}$ then the difference between $a/n$ and $a\mu/2^{2k}$ is $a\delta$ and if this is less than 1 then $q$ and $q'$ differ by at most 1 (which is why Barrett has a possible extra $-n$ step). In general, we know that $\delta<1/2^{2k}$ and so $a\delta<1$ for $a<2^{2k}$. For larger values of $a$, note $q-q'$ can be as large as $[a\delta]+1$ and so the number of surplus multiples of $n$ could be that large. In the worst cases, if $a$ is $m$ bits where $m>2k$, then we could be off by $2^{m-2k}$ multiples of $n$. We can of course apply Barrett iteratively or do more conditional subtracts, but this soon stops being efficient in comparison to direct computation of $q$.
Of course, there are also good very good cases where $\delta$ is small (a lower bound is $\delta\ge 1/2^{2k}n$) and we get good behaviour for a large range of $a$ (up to $a<n2^{2k}$ in the best case).
If you want a more accurate generalisation, you can for example use $\mu=[2^{m}/n]$ and shift $a\mu$ right by $m$ and conditional subtract. This is guaranteed fine for $a<2^{m}$, but be careful how $a\mu$ fits into various word sizes. The size $2k$ is chosen simply because it useful when multiplying two numbers less than $n$ together and reducing modulo $n$.


Multiple Keys for an Encrypted Secret I have the following problem:
I want to put a document on a ipfs store. So it is accessible via a distributed network.
Now, at first only two persons (Alice & Bob) should have access on the file. So I need to encrypt it and give them a private key. But I don't want that both have the same private key, because when one of both shares the key with someone else, probably the other doesn't want this. If the private key is unique I always know, who has shared the key.
But later it should also be possible to share the document with other persons if both agree. But then also these others should get their own unique private key(s) to decrypt the file.

The following text should describe the scenario:

  Alice and Bob have a secret. Both have a different key for decryption of the secret.

  Later Cesar gets a copy of the secret from Alice.
  Alice gives Cesar an additional private key to decrypt the secret.
  Now we have three private keys for decrypting the secret.

  Later Jack gets a copy of the secret from Bob with an additional private key. Again different from the others.

Would something like this be possible in any way?

Here is one possibility, which answers the scenario you asked about, but feels too fragile for real use.

We'll have a trusted dealer, which selects an RSA modulus N (with secret factorization), a large exponent $e$, and two decryption exponents $d_1 = e^{-1} \bmod \lambda(N) + k_1 \lambda(N)$ and $d_2 = e^{-1} \bmod \lambda(N) + k_2 \lambda(N)$, for distinct integers $k_1, k_2$ (and $\lambda(N) = \text{lcm}(p-1, q-1)$)

Then, he encrypts the secret using RSA and exponent $e$; he then hands $d_1$ and $N$ to Alice, and $d_2$ and $N$ to Bob; they can both use these to decrypt the secret using RSA.

Just given $d_1$ or $d_2$ (and $N$), neither of them can recover the other; hence you have the traitor-tracing properties you're looking for.

Of course, if anyone learns two of $e, d_1, d_2$, they can factor (and so can derive their own $d$ values), hence the fragility of the system I mentioned.


Fully or partially Decrypting Data with Multiple keys Is there any good paper or research carried out till now that a data is encrypted by a single key or onwer(user) and their are 2 or more decryption keys. One key can decrypt the entire data. Other keys decrypt partial data or a portion of data. A person having no key cannot decrypt the data but those having keys can fully or partially decrypt data based on the keys.

Functional encryption might fit your description; as far as I know it's still far from practical though.


Paid decryption scheme and possible attack surface This is how ransomware can work as far as I understand:

Most ransomware works with symmetric encryption on individual files. For each file the script generates a new key. A list is then generated containing all the file-paths with their respective keys.

This list is then asymmetrically encrypted. The victim has to pay for the private key to decrypt the master list.

The malware then reads the list to unlock all the files.

Is knowledge of part of this list (all the file-paths) helpful in finding the private key?

Knowing parts of the plaintext is commonly considered as one of the attackers capabilities when attacking a cryptographic scheme. So all the widely used schemes are resilient to that.

That means that for decent asymmetric encryption it will not help you.


What is the RFC order of peer certificate verification, trust chain or expiry first? If a certificate received from a peer:

Is expired,
has a valid signature, but from an untrusted root CA

What error should be thrown?  Untrusted certificate or expired certificate? I can't seem to locate what the relevant RFC would suggest.

Untrusted certificate or expired certificate?

If you go strictly by RFC 5280 ordering, "untrusted certificate" should be returned.

More specifically section 6.1.3 starts with

   The basic path processing actions to be performed for certificate i
   (for all i in [1..n]) are listed below.

      (a)  Verify the basic certificate information.  The certificate
           MUST satisfy each of the following:

         (1)  The signature on the certificate can be verified using
              working_public_key_algorithm, the working_public_key, and
              the working_public_key_parameters.

         (2)  The certificate validity period includes the current time.

As RFC 5280 goes the from signer to signee, the current working_public_key is the ones of all trusted CAs (section 6.1.2 (h)). As the CA in question is not trusted, no public key will yield a successful validation. As this is checked before the expiration, it should yield the error.

Note that this also makes sense from a cryptographic standpoint, as you always want to make sure that your data is authentic before parsing it to avoid malicious data (like maliciously crafted certificates) to break and exploit your parser.


Role of primitive roots in Pollard's P-1 factorization algorithm I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states...

  For example, note that 2^8 = 256 ≡ 1 mod 17 even though 2 is relatively prime to 17 and 8 ≠ 0.
  The point here is that this cannot happen if a is a primitive root modulo q. But a sizeable number of integers are primitive roots
  modulo q, and even if a is not a primitive root it’s not guaranteed that we necessarily have to run into this situation, so choosing a
  different a should work.

However I am a little confused and don't get exactly what it's saying. Can someone explain the role of primitive roots in Pollard's P-1 factorization.

I will follow the steps in the document, emphasizing where the primitive root comes in.

Let $n$ be a product of two primes, say $p$ and $q$, pick $1<a<n$, and choose some $L$. The document suggests some ways to choose $L$. Take the following steps:

Compute $d_0=\gcd(a,n)$.

1.1 If $d_0>1$, we are done.

1.2 Else, continue to 2.
Compute $d_1=\gcd(a^L-1,n)$.

2.1 If $d_1=1$, then $p\not\mid a^L-1$, i.e. $a^L\not\equiv1\pmod{p}$. Choose a new $L$ and repeat.

2.2 If $1<d_1<n$, we are done.

2.3 If $d_1=n$, choose a new $a$ and repeat.

The goal is to end up in situation 2.2, so we can wonder when we do not.

Instead, we could end up in 2.1. This happens when $a^L\not\equiv1\pmod{p}$, thus when $p-1\not\mid L$. As the document states, we actually want $p-1\mid L$. This is clearly a condition on $L$, independent of $a$, so we can simply choose a new $L$ and restart.

Finally, we could end up in situation 2.3. As explained, this happens when $$a^k\equiv 1\pmod{q}$$
where $k=L\pmod{q-1}$. For which $a$'s can this happen? Well, if $k=0$, then it happens for all of them. In this case we have been quite unlucky, and choosing a new $a$ has only a very small probability of being helpful.

If $k\neq 0$, then this can not happen for all $a$'s. Remember that a primitive root $x$ modulo $q$ is defined as a non-zero integer $x$ such that $x^n\neq1\pmod{q}$ for all $0<n<q-1$. In other words, $a^k\equiv1\pmod{q}$ can only happen if $a$ is not a primitive root modulo $q$. We can choose a new $a$, and hope that the new one is a primitive root.


The role of Shift Register Cascades in Cryptography? Clearly, there are stages when binary bits are needed and this can be done with the help of Linear Feedback Shift Registers.
Registers are required to be connected in such a manner that one register controls the clock.
can someone explain me more:

The role of Shift Register Cascades in Cryptography?

Linear Feedback Shift Registers can not safely be used as Cryptographically Secure Pseudo-Random Number Generator (e.g. for the keystream of a stream cipher), because the state  of any LFSR is easily recovered from this output. Even it's structure can, using e.g. the Berlekamp-Massey algorithm.

In cryptography, Shift Register Cascades combine multiple LFSRs (or variants) into hopefully more secure CSPRNGs. Examples include the Alternating Step Generator, and A5/1. Arguably, the modern Trivium is a sort of Shift Register Cascade (which does not use clock control like the previous two, but instead uses a more complex feedback scheme).

Shift Register Cascades tend to inherit the main quality of LFSRs: simple hardware implementation.


Breaking a PRNG Scheme Assume the following scheme for a PRNG generating decimals in [0,100)

Given a message and a key, compute tag := HMAC512(message, key).  Take the first 5 hexadecimal characters of the tag.  If the result is smaller than 1,000,000 in decimal, divide it by 10,000 and return it, otherwise take the subsequent 5 hexadecimal characters of the tag and repeat.  If all 25 cases of 5 hexadecimal character groups yield decimal integers >=1,000,000, the remaining 3 hex digits are divided by 100 (decimal) and returned (in decimal).

In order to compute a stream of numbers, there is a counter within the message that is incremented with each generation.

Obviously, this is not a good scheme (given the final clause listed).  But, can an attacker, knowing the message and not the key, predict subsequent numbers or predict if subsequent numbers will be within a threshold (either >=50 or <50)?

The generator in the question internally transforms the $512$-bit string designated tag into an output determined either:

as $1/10^4$ of a non-negative integer less than $10^6$, whenever the "If the result is smaller.." clause applies;
as $1/10^2$ of a non-negative integer less than $2^{12}$, otherwise.

Determination process 2 occurs for $d_2=(2^{20}-10^6)^{25}\cdot2^{12}$ among the $2^{512}$ bit strings that tag could take (ignoring for now how tag is generated), which forms a tiny proportion $d_2/2^{512}=2^{-110.8\dots}$ of theses bit strings.

At this stage the applied cryptographer:

concludes that determination process 2 is much more likely to occur as the result of a malfunction of something than for any other cause (including if the adversary knows and can manipulate key and message), and ignores that determination process 2 (at least with the level of other information available);
sees that the only credible determination process remaining produces output numbers $x$ with $0\le x<100$ and exactly expressible with 4 decimal digits after the point, with flat distribution if the tag bit string has flat distribution;
sees that any distinguisher between a perfect TRNG producing such $x$ (hereafter: apparent goal), and the output, would also be a distinguisher for HMAC512 assuming unknown key, which he rejects summarily;

and moves on, satisfied that the PRNG in the question is close enough to its apparent goal for any practical purpose, including being unpredictable if the key is unknown.

The theoretician continues unmoved, and carefully classifies the possible outputs into two categories:

one of the $2^{12}$ numbers $x$ with $0\le x<40.96$ and exactly expressible with 2 decimal digits after the point;
other numbers $x$ with $0\le x<100$ and exactly expressible with 4 decimal digits after the point.

Each of the $10^6-2^{12}$ outputs in category 2 is reached only by determination process 1, thus for $c_2=(2^{512}-d_2)/10^6$ tag bits strings. Thus assuming flat distribution of the tag bit string, category 2 is reached with odds $\widehat{p_2}=c_2\cdot(10^6-2^{12})/2^{512}$, which is less than odds $p_2=1-2^{12}/10^6$ of reaching that category in the apparent goal: $\widehat{p_2}=p_2\cdot(1-2^{-110.8\dots})$.

That generator is broken in the theoretician's eye, for he has a distinguisher much better than anything he can dream of for HMAC512.

That is, the theoretician can devise a strategy that will allows him to win with odds $p>1/2$ when playing a game where the objective is to guess, from one given RNG output, if that RNG was selected (by fair coin toss) as the RNG in the question (reaching category 2 with known odds $\widehat{p_2}>1/2$), or as a TRNG with the apparent goal (of reaching that category with known odds $p_2>\widehat{p_2}$). The theoretician is interested in the strategy giving him the highest possible advantage, defined as $\epsilon=|p-1/2|$ (the absolute value is used because it is trivial to turn a strategy worse than answering based on coin toss into one better than that).

Towards that goal the theoretician would hypothetically bet on the RNG in the question when the given RNG output is in category 1, and otherwise bet on a TRNG (not randomly according to the criteria that I gave previously, sorry about that mistake but I'm of the applied kind). To compute the odds $p$ of winning, we consider the two mutually exclusive winning cases for this strategy:

the RNG in the question is selected, and its output is in category 1, which has odds $(1-\widehat{p_2})/2$;
the TRNG is selected, and its output is in category 2, which has odds $p_2/2$;

giving $p=(p_2-\widehat{p_2}+1)/2$ thus advantage $\epsilon=(p_2-\widehat{p_2})/2=2^{-111.8\dots}$.

It is left as an exercise to the reader to show that if $n>1$ outputs of the same chosen RNG are given, the advantage obtained is less than $n\cdot\epsilon$; is still desperately marginal with $n\approx 1/\epsilon\approx2^{111.8}$ outputs; becomes sizable at $n\approx \epsilon^{-3/2}\approx2^{167.7}$ outputs.


Why do we have fixed output length in the algorithm SHA1 Why do we have fixed output length in the algorithm SHA1 . is there any explanation about that

SHA-1 is derived from MD4 and MD5, which are Merkle–Damgård type hash functions with a compression function based on a block cipher.

The initial values to an MD type hash function are essentially the plaintext to the block cipher, with the input to the hash function becoming the key. The maximum length of the hash is determined by the amount of bits of initial value, which is the same size as the block width of the cipher. A block width of five 32-bit words gives SHA-1 a state size and maximum output of 160 bits.

For SHA-1, there is no truncation of the block cipher state prior to output, so we have 160-bits in, and 160-bits out. This provided the required collision resistance of 80-bits as required by the lifespan estimate of how long the hash function was to be in service, which as of about 5 years ago was bumped to 112-bits.

If they so desired, a variable length output could have been implemented like they did with SHA-512/t, but since the maximum output length was the minimum security required, that was neither necessary nor wanted.


Why probabilistic syntax for encryption schemes? In Foundations of Cryptography II, Goldreich, the basic mechanism of encryption schemes is written as follows:

  Definition 5.1.1 (encryption scheme): An encryption scheme is a triple, $(G,E,D)$, of probabilistic polynomial-time algorithms satisfying the following two conditions:

  On input $1^n$, algorithm $G$ (called the key-generator) outputs a pair of bit strings.
  For every pair $(e,d)$ in the range of $G(1^n)$, and for every $\alpha\in\{0,1\}^*$, algorithms $E$ (encryption) and $D$ (decryption) satisfy

  Pr$[D(d,E(e,\alpha)) = \alpha] = 1$

  where the probability is taken over the internal coin tosses of algorithms $E$ and $D$.

I repeated this definition in my own work without too much thought for why the definition was given in probabilistic terms. It was posed to me that it is unnecessary, as written here, for probability to be included and that one could just as well write the consistency equation as $D(d,E(e,\alpha)) = \alpha$.

I read later in the book that this definition may have the probability bound relaxed to allow for some negligible chance that decryption is not possible, and that this may be necessary for certain public-key encryption schemes.

My question is whether this definition is better, tighter or more complete than one that does not consider the probability of the decryption succeeding? Why is the mechanism of encryption formulated in this way?

Why is the mechanism of encryption formulated in this way?

Writing $D(d,E(e,\alpha)) = \alpha$ would imply that $E(e, \alpha)$ is a unique value, and it generally is not in practice (as most encryption schemes are, in fact, nondeterministic; that is, there are a number of ciphertexts that correspond to any specific plaintext).

The text as written $\text{Pr}[D(d,E(e,\alpha)) = \alpha] = 1$ accounts of the fact that $E(e, \alpha)$ can take on a number of different values (with some probability distribution), and so matches reality (while respecting the formalism).

  I read later in the book that this definition may have the probability bound relaxed to allow for some negligible chance that decryption is not possible, and that this may be necessary for certain public-key encryption schemes.

Yes, it comes up in most lattice-based public key encryption schemes and in some code-based public key encryption schemes.  I have personally never heard of a symmetric system that had the possibility of a decryption failure; that is, where the decryption of the correctly encrypted (and unmodified) ciphertext would not result in the original plaintext.


Does IKEv1 support multiple combinations of a source IP range? I saw in several places online that the different between IKEv1 and IKEv2 is the use of multiple combinations of a source IP range as left and right subnets (locally and remote), a destination IP range, a source port range and a destination port range are allowed per Child SA.
I am using Strongswan 5.3.5 version on Ubuntu 16.4 LTE.

No, IKEv1 does not support negotiating multiple combinations of source IP ranges (or subnets) within a single SA.

The IKEv1 RFCs (specifically, 2407 and 2409) constrain the negotiated source IP to be either a single IP address, or an IP subnet (that is, an IP address and a mask; this is typically used to handle things such as 10.0.0.0/8; it can also handle "any" IP address) [1].  As for ports, you can ask for a specific port, or any port; nothing inbetween is allowed.  And, no, a single SA cannot have multiple; if you need to protect multiple subnets, you need to negotiate separate SAs.

It is possible that the Strongswan implementation of IKEv1 attempts to go beyond what the RFC permits (at least, when negotiating with other Strongswan implementations); however, I personally find that unlikely

[1]: Note: this is a subnet, not a range; it can't negotiate, say 10.0.0.1-10.0.0.6; the closest you can do is 10.0.0.0/29 (which also covers 10.0.0.0 and 10.0.0.7).  It could negotiate "discontiguous" subnets, such as 10.0.X.1 (for any X); I wouldn't be surprised if many IKEv1 implementations didn't support such an oddball thing...


Does encryption using PRP mean indistinguishable encryption against an eavesdropper? I am a student studying cryptography by reading "Introduction to Modern Cryptography".
I have some confusion about encryption using PRP (e.g., AES).

Briefly speaking, a keyed deterministic permutation $F_{k}$ is a strong PRP if no efficient adversary (who is given oracle access to $F_k$ and $F_k^{-1}$) can distinguish whether it is interacting with $F_k$ (for uniform $k$) or $f$, where $f$ is chosen uniformly from the set of all permutations having the same domain and range.

I think the definition above says nothing about the relation between two ciphertexts which are generated by a PRP.

Now, I consider the following experiment $PrivK_{\mathcal{A},\Pi}^{eav}(n)$ for any encryption scheme $\Pi= (Gen,Enc,Dec)$.

The adversary $\mathcal{A}$ is given input $1^n$, and outputs a pair of messages $m_0$,$m_1$, with $|m_0| = |m_1|$.
A key $k$ is generated by running $Gen(1^n)$, and a uniform bit $b \in \{0,1\}^n$ is chosen. Ciphertext $c \gets Enc_k(m_b)$ is computed and given to $\mathcal{A}$.
$\mathcal{A}$ outputs a bit $b^{'}$.
The output of the experiment is defined to be 1 if $b^{'}=b$, and 0 otherwise.

A private-key encryption scheme has indistinguishable encryptions in the presence of an eavesdropper if for all PPT adversaries $\mathcal{A}$ there is a negligible function $negl$ such that, for all $n$,
$Pr[PrivK_{A,\Pi}^{eav}(n)] <= \frac{1}{2} + negl(n)$.

Does the encryption scheme has indistinguishable encryptions in the presence of an eavesdropper if $Enc = F_k$ and $Dec = F_k^{-1}$, where $F_k$ is a strong PRP?

In other word, when I encrypt two messages by using PRP, adversaries can be able to tell whether the two messages are identical since PRP is deterministic. However, can I ensure that it is infeasible for adversaries to learn any partial infomation about the plaintext from the cipertext?

The PRP encryption scheme is secure in your security definition, but this security is very weak. It only achieves "one-time security" and is also weaker than perfect secrecy, i.e., the adversary's advantage is not exactly 1/2.

I think the security can be stronger (but still cannot be IND-CPA for instance). With PRP security, we can view $F_k$ (and hence $Enc_k,Dec_k$) as a real random permutation $f$ (except for a negligible PRP security advantage). Then, even if the adversary knows $p$ message-ciphertext pairs, it still cannot distinguish $m_0,m_1$ if they do not belong to the known $p$ messages.


RSA re-encryption scheme Is there such an algorithm that would allow to upgrade the encryption of an RSA-encrypted message without revealing the plaintext to the untrusted user?

Basically, such an algorithm would probably be split in two parts.

The algorithm would take the old private key and the new public key and generate a sort of intermediate key.
The key would then be distributed to untrusted parties who could upgrade their encrypted messages to the new keypair using the intermediate key and (maybe) the new public key.

Neither the old private key nor the new private key should not be easily recoverable (computationaly infeasible) from the intermediate key, so untrusted parties wouldn't be able to recover the plaintext.

Now I suppose that such a scheme does not exist, because I don't see a real use case for it, but it would be interesting to know if such a thing can be done.

As PulpSpy have mentioned, It is called proxy re-encryption. A company called NyCypher have implemented it but with secp251 keys https://blog.nucypher.com/proxy-re-encryption-playground-in-python-3bc66170b9bf.
Other option is charm-crypto,https://github.com/JHUISI/charm/tree/2.7-master


How fragile is 3DES nowadays? Mastercard, Visa, and several other organizations use 3DES to encrypt and decrypt credit card data. The sweet32 attack placed 3DES in the spotlight, but how fragile is 3DES for a very small amount of info, like 16 digit string (the card number) + 3 digit string (the CVV) + 4 digit string (month/year of expiration)?
How susceptible is it to brute force, dictionary or collision attacks?

There are three main issues with 3DES that an application needs to be aware of:

Small block size – 3DES has a small 64-bit block size. When encrypting non-negligible amounts of data with a single key, a small block size makes the Sweet32 attack possible.

Meet-in-the-middle attack – Due to its construction, the effective strength is reduced from 168 bits to 112 bits by virtue of a generic attack called meet-in-the-middle.

Inefficiency – DES itself is not very fast, and 3DES is three times slower.

When encrypting a very small amount of data, 3DES is sufficiently secure if one does not need a high performance cipher or a security level above 112 bits. Its use in smart cards is not an issue. Some smart cards use much weaker ciphers, or ciphers with even smaller block sizes (e.g. Simon32/64).

To answer your individual questions:

How susceptible is it to brute force

It provides a 2168 security against naïve brute force, and 2112 against brute force augmented with a meet-in-the-middle attack. This is generally sufficient.

dictionary

The key is not derived from a human-generated passphrase, so dictionary attacks do not apply.

or collision attacks?

Collision attacks are usually an issue with hash functions, not block ciphers, although the Sweet32 attack can be considered a type of collision attack. The small block size does make collision attacks possible, but only if a large amount of data is encrypted with a given key.


split up sha256 hash and compare indiv block results We have a h/w accelerator in our SoC and it can do sha256. The restrictions are it's input descriptors (which defines the input packet and len) must not straddle 64K boundary. When it does we can split the descriptors into two. However the total number of descriptors can be max of 64. This means 64K * 64 = 4MB seems to be max sha256 input block.

However i want to calculate sha256sum of a 12MB block

So is it possible to split sha256sum hash into multiple operations and somehow verify it back (i.e.)

hash(12MB) = x;
hash(4MB) = a; hash(4-8MB) = b; hash(8-12MB) = c;

Is there any way to compare

x = "some method of" (a,b,c)

No, if the crypto accelerator can do a straight SHA256 computation of up to 4MB messages, and nothing else, well, you're rather stuck; there's no way to combine independent sha256 hashes into a larger hash.

On the other hand, perhaps the designer of the accelerator provided some additional hooks.  One thing that they might have provided is an 'incremental' hash; where you give the messages in pieces (and they save the intermediate state between requests).

Alternatively, if they have a mode where:

You provide the IV (rather than using the fixed IV that SHA256 uses)
They don't do the final SHA256 padding; instead, they take an integral number of blocks, and output the intermediate state.

If so, then you can do the incremental processing yourself.  You would start with the SHA256 starting IV, and send the first 4MB (or smaller, as long as it is a multiple of 64 bytes), ask to do hashing with this mode, and give you the intermediate state.  Then, you use the intermediate state as the IV, and send it the next 4MB, and get that intermediate state.  For the final block, you would apply the SHA256 padding yourself (unless the hardware will do that for you; it's not the standard padding of the final block, because the message length will need to include the entire message) and the 'intermediate state' of that is the SHA256 of the combined message.


What is the best strategy to avoid getting even orders in Shor's algorithm? I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.  But is there a relationship between safe primes and the order of an element being even? In other words, is $N = pq$ --- where $p$, $q$ are safe primes --- the hardest integer for Shor's algorithm?

I'm not interested in order-finding.  I'm only interested in the classic-side of Shor's algorithm.  How can I slow Shor's algorithm down?

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.

Not really; to factor, all you need is a value $e$ such that $x^e \equiv 1 \pmod{N}$ a nontrivial fraction of the time (and practically it would be sufficient if it holds with probability $2^{-30}$ for random $x$); it doesn't matter if $e$ is even or odd.

And Shor's will hand you such an $e$ with quite high probability.

  I'm only interested in the classic-side of Shor's algorithm.  How can I slow Shor's algorithm down?

You can't; or at least, not to any significant extent.  If the attacker gets his hands on such an $e$, then the time taken by the classic-side of Shor's is utterly tiny compared to the Quantum side of things...

  is $N=pq$ --- where $p, q$ are safe primes --- the hardest integer for Shor's algorithm?

In some odd sense, that's the easy case.  If the attacker obtains any $x, e$ pair with $x^e \equiv 1$, $x \not\equiv 1, N-1$ and $e > 0$ and not ridiculously huge, it's straight-forward to factor $N$ with simple algebra.  In contrast, if we select $p, q$ with $\gcd(p-1, q-1)$ large, these simple algebraic methods often don't work; the attacker might have to resort to simple number theoretical attacks (but, as above, other than taking a small amount of additional time, they don't really have a drawback...)


What does $\Pi$ represent in cryptography? I am doing a project in cryptography and while reading a tag generation algorithm for files, I got stuck with the meaning of $\Pi$. The screenshot of the algorithm is inserted below.

Here the KeyGen algorithm generates 1 public key and 2 secret keys and the TagGen algorithm takes a file $M$ (which is divided into $n$ blocks which is again divided into $s$ sectors) and the secret keys generated by the KeyGen algorithm. TagGen has to compute tags for blocks of the file $M$. I am stuck with how the data tags are computed here.

This is standard mathematical notation and not specific to cryptography. The $\Pi$ symbol means Product in much the same sense $\Sigma$ means Sum. For instance,
$$\prod_{i=0}^2{u_i^{m_i}} = u_0^{m_0}u_1^{m_1}u_2^{m_2}$$


Decrypting an encrypted aes 256 cbc text with random IV, decrypts the string This may be a basic question but bear with me.

I started encrypting a text with aes 256 cbc mode generating a random iv of 16 bytes and a key.

text = 'hi I am learning encryption.';

Then I created another random iv and tried to decrypt the encrypted text. ( I know we are supposed to use the same iv we used for encryption to decrypt the ciphered text).

The result came as

(some rubbish text) encryption.

Then I padded the main text with 16 random characters, encrypted it and decrypted it I get my actual text padded with some junk text at the start.

I am unable to figure out why it messes with the first 16 bytes of text and then successfully extracts the remaining.

Can you explain?

Here is the picture for CBC decryption ($\oplus$ is the XOR operation of each bit/byte at the same position of the input blocks):

As you can see only the first block is altered by the IV.

During encryption every block is changed because the ciphertext will propagate the uniqueness of the IV over all subsequent blocks. However, during decryption only the first block is XOR'ed with the IV to get back the first block of plaintext.

If that block is random then the result will also be random. The rest of the blocks is unaffected.

If you change just a single bit of the original IV, then only that particular bit in the plaintext block will be affected.


Increases in the AES S-box AES uses one S-box to substitute all 16 bytes in one round. Will using 16 different S-boxes (with cryptographic properties similar to the AES S-box (i.e., non-linearity of 112, differential probability of $2^{-6}$ etc) increase some security against the following attacks?

Differential
Linear
Truncated Differential
Boomerang
Higher Order Differential

I can see at least one disadvantage of using 16 S-box to change the 16 bytes. The size of the code and the look up tables (should you use such implementation) would increase the size of the code. This increases the surface of exposure for cache timing attacks.

Due to the strong alignment of AES, i.e. differences are constrained within the byte, using one S-box or multiple ones (assuming that they share the same cryptographic properties: $P_{diff} < \frac{4}{256}$) would not really change the security of the whole algorithm. The probability of differential trails would be relatively similar.

So from a Linear and Differential cryptanalysis point of view, while making the research for differentials slightly harder, it would not increase the security against these attacks.

About Truncated Differentials, this attacks explores whether or not a difference is present on the bytes rather than on the bits. Therefore having multiple S-box or a single one, is likely to have no changes on it (only influence could be on the MixColumns).

About Boomerang and H.O.D I can't tell.

TL ; DR: using 16 S-box makes mainly the analysis of the block cipher harder (16 S-box to prove secure). It also makes the implementation of the block cipher harder (more places to screw up).


One time pad probability I'm trying to solve a question about one time pads but I'm not sure if my assumptions are correct.

I am to assume that I have a one time pad with perfect secrecy. This one time pad is used to encrypt a message of 7 bits in length (message space size is 2^7). This encryption yields a ciphertext of "0110011". What is the probability that the encrypted message was "1001001".

My understanding of one time pads is that if we assume the pad has perfect secrecy, then we can no nothing about the message given the ciphertext and thus we cannot determine the probability. Am I right in my assumption?

Actually, you are quite correct; you have not been given enough information to determine the probability.

The piece of information that you have not been given is the probability distribution that the plaintext was originally chosen from.  Perhaps all 128 possible plaintexts were chosen with equal probability (that is, with probability $1/128$).  Perhaps the plaintext 1001001 was chosen with probability 0.25, and the plaintext 0110110 was chosen with probability 0.75, and all other plaintexts had zero probability.  The point is that you do not know.

The entire point of a one time pad is that knowledge of the ciphertext gives the attacker no new information about the probability distribution of the plaintext; that is, the ciphertext does not make any specific plaintext any more or less probable.  The question asks you about the probability distribution given a specific ciphertext; we know that it is the same as it was without the ciphertext - however, we don't know what the original probability was.


Present an attack for the combination of OTP and textbook RSA Let $N=p \times q$ where $p$ and $q$ are two primes.
  Compute $\Phi (N) = (p-1)(q-1)$.
  Choose $e$ s.t. $1 < e < \Phi(N)$ and $gcd(e,\Phi(N))=1$.
  Compute $d = e^{-1}(mod  \ \Phi(N))$.
  Set $pk = (N, e)$ and $sk = (N, d)$.
  Let $m \in Z_N$ be a plaintext message. A random $r \in Z_N$ is selected, such that $|r|=|m|$, and the plaintext $m$ is encrypted: $E_{pk=(N,e)}(m; r) = ((m \oplus r), (r^e\ mod\ N))$.

Present an attack against this scheme assuming the weakest possible attacker capabilities.

I couldn't think of any easy attack here. The random key for the OTP is encrypted using textbook RSA, and aside for the "usual" textbook RSA attacks, I don't see anything special in this scheme that can be attacked. This is a question from a past exam, so I don't think the meaning is to simply state the known textbook RSA attacks. Any help would be appreciated.

This scheme follows the KEM/DEM approach of contructing secure asymmetric encryption schemes. However for a KEM/DEM PKCS (public key cryptosystem) to be secure it is required that both the key encapsulation mechanism (KEM) and the data encapsulation mechanism (DEM) are CPA or CCA secure for CPA or CCA of the whole scheme.

Indeed the DEM looks CPA secure as it is an OTP. The KEM scheme may be CPA secure, but I can't prove it now. Somebody else may be able to do this though. However the whole scheme isn't CPA secure as pointed out by Yehuda Lindell in the other answer.

But neither of the part is CCA secure. I'll present two attacks breaking this scheme by attacking the KEM and the DEM in isolation.

Attack 1: Breaking the DEM

The DEM is basically a simple OTP. Now let's assume you're given the ciphertext $c=(u,v)$ to be broken. First choose a random $s$ and construct $c'=(u\oplus s,v)$. Note that $c'\neq c$ so asking the decryption oracle for decryption of $c'$ is valid. Obtain the decryption $m'$ of $c'$ using you decryption oracle. Note that $m'=(m \oplus r \oplus s) \oplus r=m \oplus s$, now finally obtain the message $m=m'\oplus s$. You have successfully broken the DEM in a chosen ciphertext attack.

Attack 2: Breaking the KEM

The KEM is simple textbook RSA. However interaction is a bit more tricky here but still quite simple. Let's again assume you're given a ciphertext $c=(u,v)$ to decrypt. Now choose a random $s$ again and construct the ciphertext $c'=(t,v\cdot s^e\bmod N)$ with $t$ being a random message, note again that $c\neq c'$ so asking for the decryption of $c'$ is totally valid. Ask your decryption oracle for the decryption of $c'$ and learn the corresponding message $t'$. Note that $t\oplus t'=r'=r\cdot s$. Finally reconstruct the original $r=(t\oplus t')\cdot s^{-1} \bmod N$ and reconstruct the message as $m=u\oplus r$. You have now successfully broken the KEM.

So you see that this scheme is totally flawed in a chosen ciphertext setting and message recovery is quite easy.


NIST vectors for RSA 4K Key Please suggest the link where I can find out the NIST vectors for 4K Key to test my RSA API.

I don't think there are any. In principle key sizes can be of any bit length, although usually libraries require modulus a multiple of 8 bits and full powers of two are most common. So creating test vectors for all is not really an option.

The NIST test vectors for decryption just list 1024 and 2048 bits and the modular exponentiation primitive for PKCS#1 signature generation is just 2048 bits modulus. But that should be OK; there aren't any differences when it comes to 4096 bits. It's unlikely that your big number implementation behaves any differently. If you want to test against other bit sizes I would propose you generate them from another library instead.

If you use OAEP or PSS then I would strongly recommend that you test the MGF1 separately, using a different library as reference. There are some tricky size based calculations that need to be performed here and it is a good idea to test them well. Testing your I2OSP and OS2IP might be a good idea as well.

The vectors that are out there can be found here.


What does $(\mathbb{Z}_n^*)^2$ mean? In a paper they write once, $(\mathbb{Z}_n^*)^2$. Is this the group of quadratic residues or is it something else?

Here the theorem:

Under the strong RSA assumption, given a modulus $n$, along with random elements $g, h \in (\mathbb{Z}_n^∗)^2$, it is hard to compute $w \in \mathbb{Z}_n^*$ and integers $a, b, c$ such that $w^c = g^a h^b$ and ($c \nmid a$ or $c \nmid b$).

$\mathbb Z_n^*$ is a mathematical notation for the multiplicative group of integers modulo $n$.  In other words, it is the set of integers that are relatively prime to $n$, all taken modulo $n$ (excluding zero). The $*$ symbol is commonly used for denoting "the set of elements in the multiplicative group", which in this case means "the set of elements that are relatively prime to $n$".

Normally $\mathbb Z_n^*$ is treated as a multiplicative group, so it comes coupled with the multiplication operation modulo $n$.  (In contrast $\mathbb Z_n$ would denote the group of integers modulo $n$ under addition, or the field over the same set with both addition and multiplication.)

When such algebraic structures are raised to the power of two, it is an abbreviation for the Cartesian product of the underlying set with itself, in this case $\mathbb Z_n^* \times\mathbb Z_n^*$, i.e. the set of value pairs $(x,y)$ where both $x,y$ are integers in the range $1$ to $n-1$ and relatively prime to $n$.

Cartesian products of sets are also sets and might be coupled with one or more binary operations to form algebraic structures, such as fields and groups. In this case, the operations would be determined by context.

Edit: It should be noted that in mathematics, the $*$ symbol is more generally used for denoting a set excluding element zero. For instance, $\mathbb Z^*$ means the set of integers except $0$. However, it doesn't make sense to extrapolate this notation to finite sets such as $\mathbb Z_n^*$, except when $n$ is prime. If $n$ is composite, the set of integers $1$ to $n-1$ is not closed under multiplication, but the set of integers relatively prime to $n$ is. Hence, it is usually safe to presume $\mathbb Z_n^*$ denotes the (underlying set of the) multiplicative subgroup, unless explicitly stated otherwise.


WhatsApp end-to-end encryption WhatsApp offers end-to-end encryption. However, when I start using it on a second device such as a PC running Windows, I can decrypt incoming messages without providing any private key into my second device or application.

When a party sends a message to my account which has two clients receiving the incoming message, on PC and mobile device, they receive the same message perfectly.

If my private key is generated by my first device and stored on my first device, how is the private key being passed to my second device without any security flaw?

If by "using them on a second device such as a PC running Windows" you mean that you open Whatsapp web there, then no you cannot decrypt your messages there.

Whatsapp web is a client that connects to your phone (usually using whatsapp servers as proxy).

The client has shared keys with the phone (you scanned them as QR code) and the phone uses this to encrypt the already (on the phone) decrypted messages.

+----------------------------------+                     +----------------------------------------+
|                                  |                     |                                        |
|                                  +--------------------->                                        |
|    Whatsapp Web Client           |     encrypted       |         Whatsapp Servers               |
|                                  <---------------------+                                        |
|     shared key with phone        |                     |                                        |
+----------------------------------+                     +---+---------------------^--------------+
                                                             |                     |
                                                             |                     |
                                                             |                     |
                                                             |                     |
+-----------------------------------+                        |                     |
|         encryption secret keys    |                        |                     |
|                                   <------------------------+                     |
|                                   |                                              |
|      Your phone                   |         encrypted                            |
|                                   |                                              |
|      shared key with web client   +----------------------------------------------+
+-----------------------------------+

Basically the Web client is just a GUI for your phone client, connected (securely) over the web.

You can try the following: Turn off your phone while using whatsapp web. You will see, that you cannot send and receive messages anymore.


How to attack polyalphabetic affine cipher with only ciphertext? How to attack polyalphabetic affine cipher with only the ciphertext?

A polyalphabetic affine cipher can be seen as the composition of an affine cipher ($p \mapsto c \equiv a \times p + b \pmod{26})$ and a Vigenère cipher.

Consider we have a key such as $(a_{n\  mod\  3},b_{n\  mod\  3}) \in [(3,1); (7,2); (11,8)]$.
For instance itwas$_{plaintext}$ $\longrightarrow$ zgpbd$_{ciphertext}$.

This is a simple variant of the Vigenère cipher, and can be broken in basically the same way:

First, you need to determine the key length.  The standard methods for doing this for any Vigenère-like cipher, like Kasiski examination or calculating the index of coincidence, work just fine here.

Once you've determined that the key most likely consists of $k$ separate affine maps, you then split the plaintext into $k$ columns, each encrypted with a different affine map, and break each of them like you'd break a normal monoalphabetic affine cipher, using letter frequency analysis.

Note that crib dragging or $n$-gram frequency analysis generally won't work for solving the columns, since the letters in each column aren't consecutive in the plaintext.  On the other hand, since you have multiple columns taken from the same plaintext, you can mostly solve the cipher without knowing the actual letter frequency distribution of the plaintext (as long as it's sufficiently non-uniform).

To do that, simply take the letter frequencies from one of the ciphertext columns (say, the first one) and use them instead of the expected plaintext letter frequencies to solve all the other columns.  Assuming that you have enough ciphertext for the statistical analysis to yield robust results, and that the plaintext doesn't just happen to contain any repetitive elements with period equal to the key length, this should give you a "pseudo-key" that, when used to decrypt all the other columns, will convert them to the same cipher alphabet as the first one.  Thus you can effectively reduce the polyalphabetic cipher into a monoalphabetic one, which you can then solve e.g. by brute force.

(For increased robusteness, you can do the same thing with each of the ciphertext columns as the reference column, and check that the resulting affine maps between the columns are consistent with each other.  If you find any mismatches between the maps suggested as most likely by frequency analysis, that can be a sign that some columns don't have sufficiently similar plaintext letter frequency distributions.  In that case, you may want to examine the other reasonably likely maps found by frequency analysis to see if they'll solve the mismatch.)

This works because affine maps form a group.  In particular, the inverse of any affine map is an affine map, and so is the composition of any two affine maps.  Thus, decrypting a ciphertext column with one affine key and re-encrypting it with another is always equivalent to encrypting (or decrypting) it with some third key.  The same trick works for ordinary Vigenère ciphers too, and for any other repeating-key substitution cipher (like the XOR cipher) whose underlying monoalphabetic substitutions form a group.


What is the most secure key expansion routine? I am looking at G now, but is there a better, (in terms of security and speed), means by which a byte array can be expanded that doesn't involve another cipher, just a simple algorithm?

I need to expand 1024 bytes to 4096 for use in a stream cipher, and speed is less important than overall distribution of entropy. I am also trying to find something that is strictly algorithmic, that doesn't employ hashing or another cipher. Any thoughts/recommendations?

There are many possibilities here, depending on the particulars of where exactly you will use it.

Your use case may require a random looking derived key, where the 1024 bytes of entropy have been distributed evenly over all the bytes of the final key. In that case there's no avoiding a key derivation function. You will have to use either a block cipher, a hash function, or something equally complex.
Your use of it in a stream cipher may not care at all, if the entropy will be subsequently diffused over the state anyway (maybe with extra initial rounds). In that case you may as well just set the rest of the bytes to zero, or perhaps concatenate four copies of the original key to increase the speed of initial diffusion.
The second point above may be true, but your cipher may have internal symmetries that could make certain bits or bytes "cancel out". In that case you may have to make sure the initial configuration does not lead to weaknesses due to that symmetry.
You may have some sort of security proof or reduction for the structure of the cipher, like a Feistel network has, for example. That could put requirements on the key, e.g. that certain parts have to differ. HMAC is an example where simply padding the key with two different bit patterns was sufficient for proofs.

In the end, the main guidance I would give out is to look at what other stream ciphers are doing. The eSTREAM winners would be a decent starting place.


Why are finite groups used in cryptography? Most of the cryptographic schemes I know are all based on group theory, e.g. they use finite groups.
Can someone explain why is that the case? And why not base the schemes on elements and operations say from natural numbers or some other infinite sets? E.g. $\mathbb{Q, Z, R}$?

Can someone explain why is that the case?

Cryptosystems based on finite sets have two very nice properties:

There is an upper bound to the size of all involved mathematical objects. This also allows one to predict things like memory usage rather well. This also means that the precision / memory you need can't grow arbitrarily / infinitely.
You can actually draw numbers at random according to some distribution. You can't draw a number uniformly at random from the natural numbers because you'd have probability $0$ of drawing any single specific one. Also in theory if you wanted to sample a normal distribution, you could get $10^{10^{100}}$ drawn (even though that's unlikely) which also brings back the first point.


How to find out the block size of Xchacha20 in Libsodium? I heard that Xchacha20 works like a block cipher so that even if it wants to encrypt one byte, it will do the work of at least one block.  So technically it works similar to a block cipher in counter mode.
I want to find out the size of this block, which represents the minimum work that Xchacha20 can do.
How to find out?  Specifically in Libsodium.  I want to see it (not just believe it blindly).  Any idea where to look?

TL;DR; ChaCha's block size is 64-byte i.e. 512-bit.

Xchacha20 extends the nonce of ChaCha20 without changing the function of ChaCha20. The aim of Xchacha20 is to extend the 128-bit nonce size of ChaCha20 to 192-bit in order to generate random nonces to use safely in the long-lived keys without the fear of the nonce-collision.
The RFC 7539 in Section 2.3 mentions clearly.

2.3.  The ChaCha20 Block Function
The ChaCha block function transforms a ChaCha state by running multiple quarter rounds.
The inputs to ChaCha20 are:

A 256-bit key, treated as a concatenation of eight 32-bit little-endian integers.

A 96-bit nonce, treated as a concatenation of three 32-bit little-
endian integers.

A 32-bit block count parameter, treated as a 32-bit little-endian
integer.

The output is 64 random-looking bytes.

The ChaCha, a variant of Salsa20 paper;

This paper assumes that the reader is familiar with Salsa20, and focuses on the changes from Salsa20 to ChaCha

on the intro

The Salsa20/20 stream cipher expands a 256-bit key into $2^{64}$ randomly accessible streams, each containing $2^{64}$ randomly accessible $64$-byte blocks.

And the The Salsa20 family of stream ciphers paper wrote it more clearly;

Salsa20 generates the stream in 64-byte (512-bit) blocks

Some words on this

I heard that Xchacha20 works like a block cipher

Salsa and ChaCha are stream ciphers both build on Pseudo-Random Function (PRF).
A PRF defined over $(K,X,Y)$:
$$F: K \times X \mapsto Y$$ such that exists efficient algorithm to evaluate $F(k,x)$
They use CTR mode to turn a PRF into a stream cipher. CTR mode is designed for PRF by Whitfield Diffie and Martin Hellman in 1979;

Privacy and Authentication: An Introduction to Cryptography

In contrast, a block cipher is a family of permutations and is expected to be a Pseudo-Random Permutation (PRP). A PRP defined over $(K,X)$:
$$E: K \times X \mapsto X$$
such that:

There exists efficient algorithm to evaluate $E(k,x)$
The function $E( k, \cdot )$ is one-to-one ( and therefore permutation)
There exists efficient inversion algorithm $D(k,x)$

Note that a PRP is also PRF.
The CTR mode doesn't require the inverse of the function and therefore enables more range of functions to use. If we fix the output space into the same space for PRF's then there are $2^{n^{2^n}}$ PRFs and $2^n!$ PRPs from $n$-bit input space to $n$-bit output space.
If you need to use a PRP in the CTR mode then you need to be careful on the  PRF-PRF switching lemma. , Bellare et. al, 97 provide the security bounds.

A concrete Security of Treatment of Symmetric Encryption

In contrast to conventional stream cipher that output bits per clock, Salsa and ChaCha both produce long outputs per encryption by design and are still stream ciphers.


Generating secure hash using iPhone Secure Enclave I need to turn a password plus salt into a 256 bit hash. The hash is used as a key to encrypt / decrypt a database on an iPhone, so it need never be generated outside the phone. It also need not be moved to a different iPhone. Currently we use a standard hash function with lots of rounds, to make a brute force attack hard.

I would like to involve the iPhone's secure enclave into the process, in the hope to make it more secure. However, functionality is very limited: I can generate an elliptic curve private / public key pair, I can encrypt / decrypt, and I can generate or verify an ECC signature.

My idea to generate a hash is: Generate an ECC private / public key pair; ignore the public key. Take password and salt, then use the ECC key to calculate a signature of the data repeatedly for 100 ms (the number of iterations would be quite low, because the Secure Enclave is slow). Then use some standard cryptographically secure hash function to turn the result into the hash that I need.

PS. Comment said that a signature wouldn't necessarily be unique. I suppose it could be filled with random data, for example. Since all I want is a random looking, but deterministic bit pattern, it might be better to fill the password + salt with deterministic padding and then encrypt. Still not sure if that would be deterministic.

Do you think this is safe?

The biggest question is whether repeatedly calculating a signature loses entropy. It shouldn't, but then what I'm doing is not a typical use case, and the designer of the signature algorithm might be fine with losing 2 bits of entropy every round. The normal use case would still have 254 bit entropy. Do you think this method will generate 2^256 possible keys or fewer?

Another objection is that an attacker might get hold of the public keys and use them somehow to undo signature calculation. Of course just because public keys are called "public", they are not publically known unless someone makes them public.

(If there are no objections, then this method should be quite secure. A reference to the private key is stored in the keychain; to get it an attacker would have to unlock the phone and install an app with a forged or stolen signature from my company. Then they would have to brute force the key on the iPhone, since the private key cannot be removed from the secure enclave, losing the ability to use powerful hardware).

PS. It had never occurred to me, but generating 10 signatures for the string "abcdef", using the same key in the iPhone Secure Enclave, did in fact produce 10 different signatures :-( So whether my idea was good or not, it doesn't work.

You can simply create a database / enclave specific (symmetric) key and encrypt that using Enclave key pair. You can retrieve that wrapped key back by decrypting.

The password-derived key can simply be calculated like you do now.

So all that is left is to combine the keys back to one single key that depends on both. You could simply XOR the keys together for that. Or you could concatenate them and then use a KBKDF (which, in the simplest form, could just be a hash algorithm) to derive a new data key.

You could also concatenate the salt and the unwrapped key together and use that as salt input. Such a combination is called salt-and-pepper, where pepper is the secret part of the input. That way the derived key depends both on the secret and the password.

The derived data key can then be used to protect the database.

Don't forget to add authentication if you don't want the database to get corrupted by an attacker.


Where do I securely store the key for a system where the source is visible? I have a customer with an Access database (ugh!) in which credit cards are stored in plaintext (yikes!), so amongst other changes I'm doing in the app, I'm applying some encryption in there.

I've used Rijndael as the algorithm of choice, but I'm struggling to find the correct approach to storing the encryption/decryption key, since an access database is inherently source-visible.  How can I provide decent security on this one to prevent someone grabbing the database (by local access - this machine is NOT Internet connected) ?  I feel I'm omst of the way there, but missing this vital piece of the jigsaw

You can use a password based key, which is a similar approach to the PGP method, create a key somehow (random clicks, random numbers etc.), encrypt it with a password and store it somewhere. When the user wants to access the DB, he enters the password, which is the key for the DB decryption key file and then you get the clear password for the DB.

The main idea is to remove the key from the machine itself, and pass it to the user, and meanwhile generate a unique key for each user (computer), so if I have the SW on my computer, I still don't have the key to another's DB.


Linear Feedback Shift Register Taps Linear feedback shift register tap charts are availale for registers of length 3 to 168. Does anyone have a chart for register lengths from 168 to 256 or beyond?

When I need something on that tune I might use Jörg's useful and ugly page of mathematical data.

In particular, all-trinomial-primpoly gives primitive GF(2) trinomials (LFSR with 2 taps, the minimum number) to degree 400. 100,63,0 tells you that $x^{100}+x^{63}+1$ is primitive, meaning the same as 100|100,63 at LFSR Feedback Taps to 168 bits.

Also of interest is eq-primpoly-w5, giving one primitive pentanomial (LFSR with 4 taps) per degree up to 660. The entry 660 498 329 164 0 tells that $x^{660}+x^{498}+x^{329}+x^{164}+1$ is primitive (equivalent to 660|660,498,329,164 in a Feedback Taps table). Reference is given to: Janusz Rajski et Jerzy Tyszer, Primitive Polynomials Over GF(2) of Degree up to 660 with Uniformly Distributed Coefficients.

Further, highbit-normalprimpoly gives one primitive polynomial per degree up to 400, selected has having the lowest non-constant term as high as possible. That one is handy for software implementations, for the representation of the polynomials can be compressed into a small bitmask.


Efficient parameters for group Diffie-Hellman I want to implement a basic version of Diffie-Hellman key agreement for groups.

So, my key is $K=g^{abc} \mod p$. Following this, the parameters I would need to transfer would be $K_a = g^{bc}$ etc. The group may become large (up to 100 member), so I don't want to calculate every parameter anew and reuse $K$. Is there an efficient way to do this? I tried multiplying $K$ with $(g^a)^{-1}$ but that did not create a valid parameter since the resulting key was not correct.

Another idea I didn't have implemented yet is to calculate the key as $K=g^t$ with $t=abc \mod p$. I think, that in this case I could compute the inverse $a^{-1}$of $a$ in $Z_p^*$ and get my parameters as e.g. $K_a=K^{a^{-1}}\mod p$. Do you think this would work? Are there possible security issues in this approach?

You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$.

So your optimization isn't possible in practice. Take a look at the alternatives at Can one generalize the Diffie-Hellman key exchange to three or more parties?. Thomas Pornin describes a two-round shared key algorithm based on DH and links to an single-round scheme that uses advanced crypto.


How secure is Shamir's Secret Sharing for password sharing when attacker has t-1 shares? I am designing protocol to share a random generated n long password between k parties using Shamir's Secret Sharing. I know that share alone does not reveal much information about the original password to the attacker except for the size of password. My solution now is to extend each password to 512 bits using constant pattern.

How secure is this against brute-force attack when attacker has t-1 shares and knows the stretching pattern? Is there any better way to obfuscate the original password size? Would it be better to encrypt the password with symmetric cipher let's say AES256-CTR and random key K and then split that key with SSS algorithm?

Shamir secret sharing is information theoretically secure. This holds as long as the attacker knows fewer than $t$ shares. So, even with $t-1$ shares, the attacker still knows nothing about the secret. So a brute force attack given $t-1$ shares is impossible, even an attacker with infinite computing resources could not brute force the secret.

Using a deterministic (yet known to the attacker) transform on the secret to get it to be 512 bits, then secret sharing that value is just fine for protecting the length of the secret.

Yes, you could encrypt the secret with a symmetric cipher like AES-256, though you still have to pad the secret to hide the length. Then you could share the encryption key with SSS. This does lose information theoretic security, however, as AES is not information theoretically secure. In practice I don't believe this to be a major issue, however.


Major Block Ciphers between DES and AES competitions DES was announced as a standard in 1976. AES competition started in 1997 and Rijndael was selected as standard in 2000. What are major block ciphers and block cipher designs made/proposed from 1976 to 1997?

IDEA and CAST-128 (aka CAST5) first come to my mind as widely deployed/used ciphers. Blowfish and TEA are next. The first two (and to some degree the third) got support in PGP early on.

Update per comment: RC2, RC5, and GOST 28147-89 (in the Eastern block) also have been widely used.

All 7 are 64-bit block ciphers; that's typical of the era, and made these block ciphers a painless substitute for DES and 3DES (the dominant ciphers). They stood the test of time quite well, with no practical attack better than brute force by more than very few bits (except for GHOST, but when used with its full 256-bit key it remains safe enough). While TEA is involved in a notorious incident where a game console misused it for hashing, that's hardly a problem attributable to TEA itself.

Note: I'd have included RC4 if is was a block cipher; that used to be widespread in quite a few commercial applications.


Can the hash of one message be used to make it easier to find the hash of a very similar message? Background:

I am trying to get an understanding of using a hash of a passphrase as a secret.

Example:

sha256("EasyToRememberPassphrase") -> secret.

I am assuming a properly designed hash function used this way above will yield a secret with the same or fairly similar entropy as the input passphrase (or the size of the hash, whatever is smaller), thus as far as being used as a secret goes, the passphrase and secret are equally hard to guess.

On to the question:

Say I generate two secrets, secretA and secretB in the following way:

passphrase = "EasyToRememberPassphrase"
sha256(passphrase + "a") -> secretA
sha256(passphrase + "b") -> secretB

Assuming an attacker gets access to two pieces of information:

secretA
the fact that secretB was hashed from data very similar to secretA

Does this give the attacker an easier time figuring out secretB? And if so, to what degree? Or are good hash functions immune/sufficiently resistant to an attack using this particular set of information?

Knowing secretA; that it what obtained as sha256(passphrase + "a") -> secretA; and that passphrase is easy to remember; is enough for a password cracker to find passphrase. From that, secretB succumbs.

Thus yes, what's known gives the attacker an easy time figuring out secretB. If there are $n$ bits of entropy in the passphrase, the attacker's work is on average $2^{n-1}$ SHA-256 hashes. For many definitions of an easy to remember passphrase, that's feasible with readily available hardware and software, and technical progress is making that easier every year (by perhaps 0.2 to 2 bit of entropy, depending on what one thinks the state of Moore's law is). Morality: hashing something a human can remember does not turn it into a key. For this, use scrypt (or another Key Derivation Function intended for passwords, such as the lesser bcrypt or PBKDF2); and add salt at the KDF input, if at all possible.

No weakness in SHA-256 was involved in the above, only its excessive speed for the application. As far as we know (we have no proof), SHA-256 has properties close enough to a random function that in the application, a practical adversary (unable to perform work comparable to $2^{256}$ hashes) can not exploit that SHA-256 was used for producing both secretA and secretB with only 2 bits different in the input (assuming ASCII), other than by guessing that input.

That property of SHA-256 (that nearly equal input induce no exploitable similarity in outputs) was not one of SHA-256's primary design goals, and does not follow from these goals, stated as: "The hash algorithms specified in this Standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest").

If we wanted something with that property, and a strong argument (which would be useful if passphrase was replaced by a true key), we could use a MAC of an arbitrary constant for each desired secret. That could be HMAC with SHA-256 rather than just SHA-256, used as HMAC(key,"a") -> secretA and  HMAC(key,"b") -> secretB.

Update: on second thought, in the setup in the question, and given the internals of SHA-256, we can argument in favor of that property (which is better than having no known evidence of the contrary): the two inputs to SHA-256 differ in the same block, thus any relation between the two outputs would amount to a related-key attack on the cipher from which the round function of SHA-256 is built. This argument is still much weaker than the modern argument for HMAC using SHA-256.


Yao's Garbled Circuit- Why does Alice need to rearrange the circuit? My understanding of Yao's Garbled Circuit (based mostly on this summary) is as follows:

Alice creates a garbled circuit based on the function f to be computed. She then hard-codes her input into the circuit and rearranges the gates in such a way that Bob will not be able to figure out what the circuit does. She then assigns a pair of random keys, $K^0_i, K^1_i$  to each wire $w_i$. She sends Bob four (unlabeled, shuffled) values $X_s^a,X_s^b,X_s^c,X_s^d$ for each gate $g_s$. These $X_s$ values are chosen such that if Bob knows the keys  $K_i^{v_i}$ and $K_j^{v_j}$ for the two input wires of $g_s$ with values $v_i$ and $v_j$ then he can calculate the key $K_k^{v_k}$. Specifically, he does this by taking the XOR of $K_i^{v_i}$ and $K_j^{v_j}$ and each $X_s$ value. One of these four results will be $K_k^{v_k}$, the others will be meaningless random bits. Alice gives Bob the values $AUTH(K_k^0),AUTH(K_k^1)$ for some one-way trapdoor hash function AUTH. Thus, Bob can figure out which of the four values is not random bits.

I don't understand why Alice needed to hard-code her input and rearrange the gates. Could she not have just given Bob the circuit as is and the keys to her inputs? Except for his own input wires and wires determined from them, Bob does not know whether the key on a wire represents the wire being in the state 0 or the state 1. So even if he knows the function he is computing (what the circuit does) he should not be able to figure out what the values are of this function.

I also realize from this question that the keys as well as the X values would have to be generated again for a second computation. But I don't see why the structure of the circuit itself needs to change.

Alice does not need to hard-code her input and does not need to shuffle the gates (it is only necessary to shuffle the ciphertexts inside each gate). Bob needs to hold a key on every input wire. For the input wires associated with Alice's input, she can just send the appropriate key (this reveals nothing since both the 0 and 1 values are just random).


Can multiplication of two primes be seen as a strong cipher? If we were define such a cipher:

A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a random prime $p_1$
A key derivation function $\operatorname{kdf}$ with a similar blueprint, with key $k$ and initialization vector $\text{IV}_2$ where $\operatorname{kdf}(\text{IV}_2, k) = p_2$
The encryption can then be defined simply as $p_1 . p_2 = C$
Decryption would then be $C / \operatorname{kdf}(\text{IV}_2, k) = C / p_2 = p_1$ and $M = \operatorname{map}^{'}(\text{IV}_1, p_1)$

I see this would be very similar to OTP; and can it be seen secure considering the idea is almost the same (and assuming factorization is hard)

Intuitively I can speculate, it might pave some way for some commutative and homomorphic properties as well...

This answer is supplementary to the one provided by Mikero.

Assuming that the $\operatorname{map}$ and $\operatorname{kdf}$ functions are properly randomized and provide appropriate output (e.g. large enough to be non-repeating), then no two ciphertexts will share common factors. So being able to use $\operatorname{gcd}$ to break ciphertexts is not applicable in the basic form of the proposal.

  I see this would be very similar to OTP; and can it be seen secure considering the idea is almost the same (and assuming factorization is hard)

Emphasizing the point raised by Mikero: This is not a one-time pad, as it lacks information-theoretic security.

An efficient algorithm for factoring can recover $p_1$ from $p_1 p_2$ and compute $M$ by inverting the $\operatorname{map}$ function.

An adversary that knows or can guess $M$ can recover $p_2$ from the ciphertext by computing $p_1 = \operatorname{kdf}(\text{IV}_1, M)$ and then $p_2 = \frac{p_1 p_2}{p_1}$. Since each $p_2$ is randomized, this should not help them to decrypt other ciphertexts that they do not already know the plaintext of. However, it would allow them to mount an attack on $\operatorname{kdf}$.

  Intuitively I can speculate, it might pave some way for some commutative and homomorphic properties as well...

It is conceivable that the ability to meaningfully multiply ciphertexts could be worked into the scheme. However, it would require a very clever $\operatorname{map}$ function - one which would also need to preserve the multiplication operator on it's own outputs.

The ability to add ciphertexts together appears to be barred by the requirement for each "key factor" ($p_2$) to be different. Something like $p_1 p_2 + p_3 p_4$ will not let you decrypt to $p_1 + p_3$ by dividing by $p_2$ and/or $p_4$

As for commutativity, decryption could be commutative, but encryption can't successfully be performed as such.

For decryption: $$\frac{p_1 p_2 p_3}{p_2} = p_1 p_3\\\frac{p_1 p_3}{p_3} = p_1\\\frac{p_1 p_2 p_3}{p_3} = p_1 p_2\\\frac{p_1 p_2}{p_2} = p_1$$

Clearly, the sequence of factors that you divide by has no influence on the output.

However, for encryption, let's try the Three-pass Protocol (one of the things you might want a commutative cipher for): $$c_0 = p_1 p_2\\c_1 = c_0 p_3 = p_1 p_2 p_3\\c_2 = \frac{c_1}{p_2} = \frac{p_1 p_2 p_3}{p_2} = p_1 p_3\\p^{'}_1 = \frac{c_2}{p_3} = \frac{p_1 p_3}{p_3}$$

An attacker who has seen $c_0$ and $c_1$ can compute $\operatorname{gcd}(c_0, c_1)$ to recover $p_3$. When they obtain $c_2$, they can then recover $p_1$ by dividing by $p_3$.

This demonstrates that the proposal does not provide a secure commutative cipher.


On a lower bound for the birthday problem I'm now familiar with a lower bound for the birthday problem as exposed in the theorem A.16 of Katz and Lindell book (alternatively see this webpage).

If one denotes by $C(q,N)$ the probability of collision when taking elements independent and uniformly distributed from a set of size $N$ The bound is obtained by assuming $q \le \sqrt{2N}$:

$C(q,N) \ge \frac{q(q-1)}{4N}$

However, the bound that I has been hold in my class is (without the inequality assumption in $q$):

$\forall N \in \mathbb{N}.C(q,N) \ge \frac{(q-1)^2}{2N}$

How can I prove this bound correct?

The question's $\displaystyle C(q,N) \ge \frac{(q-1)^2}{2N}$ bound is wrong. That's incompatible with the well-known fact that for $N=q^2$ and large, $C(q,N)\approx1-e^{-1/2}\approx39.3\%$.

A correct bound is $\displaystyle C(q,N) \le \frac{(q-1)\,q}{2N}$, valid for all $q$ and $N\ge1$, and tight when $q\ll\sqrt N$.

Another correct bound is $\displaystyle C(q,N) \ge \frac{(q-1)^2}{4N}$ when $1\le q\le\sqrt{2N}$, which follows from the question's lemma.

See this answer for some derivations, but beware that the notation there is $(n,k)$ and $p_n$ where the question has $(q,N)$ and $C(q,N)$.


How secure is the E0 stream cipher used in Bluetooth? The question is about E0, the stream cipher used to secure Bluetooth communication. The impression I get is that it's more secure than A5/1. Also, why wasn't AES used instead?

Bluetooth has gone through a few transitions in protocol.  Bluetooth BR/EDR uses E0/SAFER for a cipher and Bluetooth LE uses AES-CCM.   Fundamentally, when you write a specification as an engineer, you are looking for a minimally viable CMOS implementation.  You make choices that are not always the best from a cryptographic standpoint because you have space or power constraints.  For instance, AES is rather large compared to some stream ciphers and I believe the motivation of using E0 was die space because LFSRs are smaller than an AES implementation.  I personally use SIMON over AES in hardware because it's smaller, faster and lower power in a CMOS implementation, and this is particularly true when you are encoding a "bit stream", such you'll have in RFID or Bluetooth.

I know from being in a meeting that FIPS-140 validation for Bluetooth was an important conversation with the Bluetooth LE spec, which is why AES was added.  I can only assume that AES was not used in the original ICs due to cost on the hardware side.  Looking at 130nm dies (so, back in the day), AES would cost me about 0.03 USD in area.  Just by guessing the area of E0, I would say it's 0.01 USD, so it must have mostly been an economic consideration during the time of early adoption.

E0 itself is not particularly secure and is vulnerable to known plaintext attacks.


Is it OK to embed mac key in cipher I am in a case where I can not share a mac key, only the encryption key. I need to provide authentication and integrity with the cipher so I would like to send a mac with the cipher. I cannot use AES-GCM for example, I am limited to AES-CBC.

Is it ok to embed mac key in the cipher in this case in term of security?

For example, like this:

encrypt(text, key)
  mac_key = generateRandom256bitsKey()
  cipher = aes_encrypt(mac_key + text, key)
  return hmac(cipher, mac_key) + cipher

decrypt(cipher, hmac_sig, key)
  decrypted = aes_decrypt(cipher, key)
  mac_key = decrypted[0, 255]
  if (hmac(cipher, mac_key) != hmac_sig)
    return null;
  return decrypted[256, decrypted.length - 1]

Thanks,

To answer the question, no, you can't hope to get 256-bit IND-CCA2, by encrypting a 256 bit mac key.

Suppose you are playing the IND-CCA2 game and have got to the point where you have submitted two plain text messages $M_1, M_2$ and have got a challenge cipher text $C$. Your job is to decide which plain text $C$ corresponds to, with less than $2^{256}$ calls to the decryption oracle. Since you may choose both the mac and randomize the mac key (by modifying the first blocks of cipher text), the birthday paradox applies, and you are limited only by the collision resistance of the underlying hash function.

Depending on potential vulnerabilities in the underlying hash function, being able to modify the second half of the mac key, while leaving the first 128 bits of the mac key unmodified, might entail vulnerability to chose key attacks.

A more conventional IND-CCA2 secure construct would be:

encrypt(text, enc_key, mac_key)
  iv = generaterandom()
  cipher = iv + aes_cbc_encrypt(enc_key, iv, text)
  return cipher + hmac(mac_key, cipher)

decrypt(cipher, mac, enc_key, mac_key)
  if (hmac(mac_key, cipher) != mac)
    return null;
  iv = cipher[0..127]
  return aes_cbc_decrypt(enc_key,iv,cipher[128..cipher.length-1])

Please note that the usual caveats regarding all block chaining modes for 128 bit block sizes, and CBC mode in particular, apply regarding maximum amount of cipher text and maximum number of messages, before you start loosing security.

If you may choose the enc key and the mac key independently at random, that would be ideal. If not, but you are limited by a fixed size key material (the key in your question), you may extend it and split it, using a standard KDF, such as HKDF.

Please also note that if timing attacks apply, you might want to go ahead and decrypt the cipher text, even if the hmac verification fails (but still discard it in case of mac verification failure). However, if timing attacks against the application layer apply, you would anyway have to put in counter measures at that level.


Security of Fernet Construction (wrt non self delimiting tokens and HMAC short key size) Fernet is a described as a "high level symmetric encryption recipe" (source) that seems to be the default high level encryption scheme in the cryptography python library. The construction is described in full here, it basically takes a message $m$ and produces a token as follows:

Encrypt $m$ via AES-CBC i.e. $IV \gets \{0,1\}^{128}$, $c = \text{AES-CBC}_{k1}(m, IV)$
Take a timestamp $t$, version number $v$ and compute $tag = \text{HMAC}_{k2}(v || t || IV || c)$
Send $token = v || t || IV || c || tag$ to the recipient

The recipient then takes the $token$ and decrypts as follows:

Verify that $\text{HMAC}_{k2}(v || t || IV || c)$ == $tag$
Decrypt $c$ via AES-CBC i.e. $m = \text{AES-CBC}_{k1}(c, IV)$ (only if tag is correct of course)

Key exchange is not included and it is assumed two 128 bit keys $k1, k2$ can be securely established. My questions are the following:

The spec states that

  Fernet tokens are not self-delimiting. It is assumed that the transport will provide a means of finding the length of each complete fernet token.

Does this allow us to tamper with the tokens in a way we shouldn't be able to by adding data to the front or the end of a token? My intuition says no as HMAC is computed over all the data and the composition is Encrypt-then-MAC.
Is there any danger in computing HMAC (with SHA256 as the underlying hash function) using only a 128 bit key? My understanding is that the standard key size would be 256 bits in this case.

The spec states that

  Fernet tokens are not self-delimiting. It is assumed that the transport will provide a means of finding the length of each complete fernet token.

Does this allow us to tamper with the tokens in a way we shouldn't be able to by adding data to the front or the end of a token? My intuition says no as HMAC is computed over all the data and the composition is Encrypt-then-MAC.

HMAC is not vulnerable to length extension attacks, and prefixing or removing data from the start of end should indeed result in a different HMAC (assuming that the HMAC is indeed over that part of the data).

Is there any danger in computing HMAC (with SHA256 as the underlying hash function) using only a 128 bit key? My understanding is that the standard key size would be 256 bits in this case.

No, HMAC is surprisingly resilient and has been defined for smaller key sizes. 256 bits key would give you (at least) a 256 bits of security, but 128 bits is plenty.

Note that this answer tries to answer the given questions directly, rather than to perform a full review of Fernet. Note that Fernet has gone through several revisions by now; please check if the questions / answers are still valid.


Why isn't the maximum security of triple DES 48 * 2 vs 56 * 2? The security of quadruple or even more encryption isn't much more than that of double encryption. But each round also counts as one encryption. So why isn't triple DES only 96-bits secure?

A meet-in-the-middle attack basically halves the number of bits of the total key size, rounding up. So 3 and 4 both have 2x security and 5 and 6 block cipher encrypts provide 3x security of the original cipher. I think that this is the main misunderstanding of meet-in-the-middle attacks.

The DES cipher itself is protected against meet-in-the-middle attacks, mainly due to how the key is expanded. Note that the key material is related and that there are many rounds within a single DES block encrypt, which makes it different from how block ciphers can be stacked on top of each other. You can see a question about meet in the middle attacks within block ciphers  here (note who is asking the question).
So it isn't that this isn't an active field of crypt-analysis. Actually, many amateur block ciphers will probably fail against the meet-in-the-middle attacks and are thus rendered insecure (assuming that they specify e.g. 128 bit security for a 128 bit key).


What is Post-Compromise security exactly? After reading these papers on Post-Compromise Security:

Post Compromise Security
  Asynchronous Ratcheting Trees
My understanding is the following: it is possible for a key-agreement protocol to offer post-compromise security if the protocol offers a key update process and if the adversary is passive.
Therefore, can a key-agreement such as ECDH-RSA can be updated to provide Post-Compromise security? And is my understanding of Post-Compromise security correct?

Post-compromise security secures future messages if the key for present messages is compromised. It repairs itself by using key update process. Key update process derives new key for future messages by using assymetric key exchange like DHE and chain of key derivation function.
If your present key is compromised by external sources, anytime when next DHE will happen, it will derive new key from that point. So the compromised key cannot be used to decrypt future messages. Whereas in key derivation chain, if it outputs separate key for each message, compromising one key will not compromise future keys but with a condition that the key that goes into the chain as input shouldn't be compromised because it acts as seed.
Based on how frequently DHE happens during the session, the attacker can compromise only subset of messages. But as DHE can itself be compromised by MITM, it only works in a condition if the attacker is passively listening the communication and relies on external sources to compromise keys.
Signal protocol does that by exchanging new key using DHE with every incoming message and derives new key for each message from symmetric ratchet.


Hardware random number generator for lottery? To be able to generate random numbers for lottery games, we have the following requirement:

  The random number generator, which uses the deterministic algorithm to determine the game result, has to work with a length of at least $$2^{64}$$ period to ensure that the random process is generated so that in the case of a particular gambling there is no detectable repetition of the results, and must produce a sequence of game results based on initial values that are random or unpredictable

What does it mean in terms of certifications and hardware random number generators?

Am I able to fullfill the requirement with hardware device which is compliant with P2 Class of BSI AIS-31 (for example CryptoMate64 USB cryptographic dongle or other HW certified cryptographic device according FIPS 140-2 Level 3)?

The wording of this requirement contains the meaningless

  has to work with a length of at least $2^{64}$ period

that I hereafter reorder into

    has to work with a period of length at least $2^{64}$

We need to solve the ambiguity left in

  must produce a sequence of game results based on initial values that are random or unpredictable

about if random or unpredictable applies to initial values or to game results. Because of the earlier text "deterministic algorithm to determine the game result", the game results can't be random, since that opposes squarely to deterministic. Thus random or unpredictable can only apply to initial values. We are left with a sequence of game results that is never prescribed to be unpredictable, and the requirement is perfectly met by a generator that

uses 8 throws of 8-sided dices to build a 64-bit seed initializing a 64-bit counter;
at each uses, increments the counter modulo $2^{64}$ and outputs it.

Yet this generator is clearly unsuitable for a lottery, because the next result is trivially inferred from the previous one.

Also missing is the range of game outcomes ($2^{64}$ outcomes as in the above example is unheard-of in lotteries); a requirement that these game outcomes are equiprobable, and to what degree; if two outcomes in the sequence generated from the same seed can repeat (they should not in something that mimics a traditional loto).

Ah, and if we take it to the letter, it seems we must have a period of at least $2^{64}$ for all seeds, and that condition is not part of P2 Class of BSI AIS-31 or FIPS 140-2 Level 3. Therefore, game outcomes determined by some deterministic memory-less function from output of generators certified by these standards arguably can not meet the requirement. Further, AIS-31 allows (or requires for some class) that the generator is reseeded while used, when the requirement asks for something deterministic except for seed.

In the end, even after it has been reordered, the requirement remains utterly technically defective, and arguably prevents using established RNGs. The best is to ignore this requirement entirely and start afresh, if that can be done without getting fired poorly graded.

To engineer sound requirements, we must know the intent. It could be that the seed is archived, so that it can be proved afterwards that the PRNG worked correctly. It could be that this archival is distributed, so that collusion of some number of dishonest parties in the archival process would be necessary to predict the outcome. Again there's the range and rules for outcomes. There are assumptions to be made on what is trusted, and what's not.


Ideas for non duplicate cryptographically secure numbers My Boss asked me this today. I am not a math major. He needs to generate 50 billion non-sequential non-duplicate (no collisions) cryptographically secure random numbers. I work in GO. Any ideas?

I had to do the exact same thing for unique product identifier codes. In my case they needed to be random looking, not cryptographically secure, so I had more room to work with. I still went with a cryptographic method since that is what I was familiar with.

In your case, you are looking for just under $2^{36}$ values, for which all values are unique, and where guessing the next number in a sequence is infeasible (at least 50 billion possible choices), even when given all previous values.

For this the easiest option is a block cipher with a block size of at least 37-bits performing the encryption operation on an incrementing counter. DES, Blowfish, AES, and others all meet the criteria, the difference being key size, ciphertext size, and hardware support. Since 64-bit Go supports AES hardware acceleration, it is probably your best option.

Simply generate a cryptographically random key, start with an all 0 block, encrypt the block and save the output, increment the input block by treating it as 2 64-bit integers and incrementing the 2nd one (+1), repeat steps as needed until all values are generated. You can generate quadrillions of unique and cryptographically pseudorandom 128-bit values.


AES MixColumns Predefined Lookup 2D Tables and Rcon Predefined Lookup 2D Table I need to have the  a copy of predefined 2D table lookup for AES MixColumns when state is multiplied by 2 and 3, 9,11,13,14 and also the Rcon predefine table. I search it everywhere but I couldn't find it. I don't want how to generate it. I just want the tables. Can someone provide me with a link or even a title of a paper containing it. Thank you so much. I really need to have it.

I just want the actual 2d table: the mul2, mul3, mul9, mul11, mul13, mul14 and the rcon table. I want the 16 by 16  table version of mul2, mul3, mul9, mul11, mul13, mul14 and rcon table, not the array format of it. Thanks.


In Paillier homomorphism, how do you deal with bit length? I'm trying to figure out homomorphic encryption and would like to multiply two paillier encrypted numbers.
Like so:
[a].[b]=[a+b]

To try this I got this Paillier.java and tried the following:

BigInteger Paillier p = new Paillier (2048);
BigIntegera=p.encrypt(BigInteger.valueOf(12345));
BigInteger b=p.encrypt(BigInteger.valueOf(54321));
BigInteger c=a.multiply(b);
BigInteger res=p.decrypt(c)

Except this gives me the error

Exception in thread "main" java.lang.Exception: Paillier.decrypt(BigInteger c): ciphertext c is not in Z*_{n^2}
    at pet4.Paillier.decrypt(Paillier.java:180)
    at pet4.Main.main(Main.java:13)

Now looking at the bitcount of c I can see that it's above 4000 (it varies a bit). So how do we deal with the fact that multiplying paillier encryped numbers results in larger bitcounts?

What you're missing is the fact that your $c$ value can get waaay beyond what the library is expecting there and thus issues an error which can be read as "your value is too large".

The solution is simple: Reduce the multiplication result $\bmod N^2$, where $N=pq$ is the actual value of your modulus.

The code-line which you would need to add there would then be

 c=c.remained(p.getNsquare())

after the multiplication.


Encrypting user-specific hash? When a user registers, a random personal salt is generated. Then hashing is done like so:

hash(hash(USERNAME . PEPPER . PASSWORD) . PERSONALSALT)

Then the personal salt is encrypted using password as key and placed in the database along with hash. When user attempts to log in, personal salt is decrypted, and used to hash and compare. Is this a good idea? The hashing function is SHA-256 iterated roughly half a million times depending on sever specs.

Yes I am aware that "rolling your own encryption" is a mortal sin. I am just wondering hypothetically if it would function. I would never use something made sketchily in a production environment.

No it is not a good idea as a password cannot be directly used as a key. You would need a PBKDF (password based key derivation function) with a salt and work factor to create a reasonably secure key out of a password. But that leaves us with a problem: you are trying to create exactly such a function - password hashes and PBKDF's are largely synonymous.

If you do not derive a key correctly then the decryption may leak information by which you can retrieve your password even without going through the iterations. If padding oracles apply during decryption in your scheme then the resulting implementation would be very weak, to name just one issue.

The salt does not require confidentiality in PBKDF schemes, so encrypting it should not disallow any attack.


Password length versus hash length? If a system hashes passwords with a 256-bit long hash, are passwords (which are not necessarily alphanumeric, can be any value per byte (0-255)) longer than 32 bytes useless under the context in which an attacker with a VERY fast machine brute forces passwords?

The entropy of passwords is not universally distributed. So hashing can be used to concentrate the input of a hash.

The concentration of entropy from another source is called extraction by HKDF, which is a key based key derivation function (which should not be used for passwords). This is from the introduction of RFC 5869, which defined HKDF:

  Thus, the goal of the "extract"
     stage is to "concentrate" the possibly dispersed entropy of the input
     keying material into a short, but cryptographically strong,
     pseudorandom key.

Now the problem with passwords it that they usually does not contain enough entropy or randomness. The size of a password is an important part of estimating the strength of a password. If a password has enough entropy then you could even use a KBKDF such as HKDF or a hash directly. But the table on the same Wikipedia page shows that you would need 20 fully random printable ASCII characters to accomplish a 128 bit security level.

Instead what is used is a Password Based Key Derivation Function or PBKDF. The usage of such a function is often called password hashing to distinguish it from directly applying a hash over the password. Common implementations are PBKDF2, bcrypt and scrypt. The PBKDF uses password stretching to accomplish password strengthening. It adds at least two input variables besides the password: a salt and a work factor.

So to get back to your question:

don't use a normal hash for password hashing, use a password hash/PBKDF;
the more randomness in the password, the better - this usually means longer hashes not shorter ones;
the size of the password is not in any way limited by the (password) hash function.

A human will never - in real life scenarios - remember a password or care to type in a password that contains enough randomness to reach the security level provided by even the least of the hash functions (MD5).

In the end it doesn't really make sense to limit the size of passwords unless for backwards compatibility reasons. The minimum size should be controlled however, and as many possible additional measures should be taken to protect the password as passwords are inherently weak.


CRC32 catches errors, but then what's the point of SHA? If crc or CRC32 is specially designed to catch errors, then what's the point of SHA or md4-5 or any other hashing function? What I did was, I had a 190 mb png file (rendered in 16k resolution with blender lol) and I took its sha256 and CRC32 hash, then I did the same, only changing 1 bit of the image. Just 1 bit. And I got a different crc, but also a different sha256

190 mb ~ 1 520 000 000 bits,

So what's the point then, if they both detect such small errors?

CRCs are OK to detect naturally-occurring errors. But in cryptography, we face intelligent adversaries, which can use the mathematical properties of CRCs in order to make an arbitrary alteration in a file without altering its CRC. This is easy, even for large CRCs.

Hashes are designed to prevent that (called a second-preimage attack), and other attacks such as making two different files with the same hash (called a collision attack).

If CRCs or cryptographic hashes are different, then their input is different. In a cryptographic context, if CRCs are equal, we can't tell if their input are equal or not; whereas if cryptographic hashes are equal, then their input must be equal (or the hash used is not a secure cryptographic hash).