How to measure the complexity of the discrete logarithm problem? I looked here. The answer basically says that to calculate the complexity of the logarithm problem we have to take the length of the number representing the size of the group into accounts. It seems arbitrary, why don't we chose the size of the group as the argument? Is there a criterion to know what argument to chose? In fact, I know I overlooked something important since the complexity changes hugely if we do it by the size of the group. So please give me an answer.

To clarify: I think you ask why we only consider the bitlength of the size of the group and not the actual size of the group for complexity estimates, at least that's what I try to answer.

  Why don't we chose the size of the group as the argument?

We do.
It entirely depends on the conventions you want to use. If $q$ is the size of the group and $n\approx\log_2(q)$ (don't forget that $2^n\approx q$) the bitlength, then you can either write the effort needed for brute-force as $\mathcal O(2^n)$ or $\mathcal O(q)$, with the first being slightly less precise (but not to a point where it matters) and the second being the more accurate one. However the first one nicely shows how the effort needed grows exponentially while the second one may leave you with the impression it's linear at which point people may find it harder to understand "how that's hard, after all it grows only linearly".

  Is there a criterion to know what argument to chose?

Basically whatever you want. If you want to be clear and know your audience understands what you're meaning anyways, use $q$ otherwise use $2^n$ to make it easier to understand.


Does XTS provide random write access? I'm trying to find a sufficient encryption mode that supports random read and write access. It seems like XTS is a perfect fit, since in my use case authentication and integrity insurance are handled elsewhere, and from my current understanding, these are the only two drawbacks of XTS.

The only thing I don't get (yet) is: I'm not supposed to encrypt any data with the same key and IV twice, right? Now, what if I edit one of the XTS encrypted blocks? The tweak will stay the same since it depends on the block location, so if I use the same key again, this premise is violated. If I use a new key, I'd have to encrypt the whole file again, which means I don't really have random access anymore.

I feel like I got something wrong here. Can someone enlighten me please – and/or maybe even suggest a sufficient mode if XTS is not it?

Thanks in advance.

XTS has been designed for disk encryption, where an attacker typically has access to the disk only a single time (when they steal/confiscate the device).

When an attacker sees several ciphertexts encrypted using the same key, they can tell which blocks differ between the versions, but not the content of the blocks. Compare this with CTR mode, which leaks which bits differ, which is far worse.

XTS should be used when an attacker typically sees only one version, but it doesn't fail completely when they see several.

As an alternative, you could either increase the effective block size. Since blocks being identical becomes rarer with longer blocks, this reduces the leak, but it doesn't eliminate it. BEAR, LION, LIONESS, "wide blockcipher" EME and AEZ might be worth reading about (I'm not familiar with the details of these).

Or you could store an IV alongside each sector of ciphertext, replacing it by a new IV when overwriting. If you use a 16 byte IV and 4096 byte sectors, this is an overhead of 0.4%. The bigger downside is that you won't have a direct mapping between equal sized plaintext and ciphertext blocks, which may impact performance and prevents write-through.

You can't avoid information leaks completely, if you can't afford per-sector IVs and need random write access.


Signature scheme doesn't seem to hold I can't seem to verify the signature scheme described below.

Key Generation

Public Key:
$$y_1=g^{a_1}y^{a_2} \pmod p$$
$$y_2=g^{b_1}y^{b_2} \pmod p$$
$g$ denotes a generator of $Z_p^*$ and $y$ is a random element from $Z_p^*$. The private key is $(a_1,a_2,b_1,b_2)$.

Signing
$$\sigma_1=a_1m+b_1  \pmod q$$
$$\sigma_2=a_2m+b_2  \pmod q$$
where $q\mid p-1$. The signature on $m$ is $(\sigma_1,\sigma_2)$.

Verification. To verify $(m,\sigma_1,\sigma_2)$ one does the following.
$$y_1^my_2   \overset{?}{=}   g^{\sigma_1}y^{\sigma_2}\pmod p$$

Taking this as an example:
$p = 23$, $g = 7$, Private Key : $(12$, $20$, $3$, $18)$, $y = 16$ and $q = 2$

This will give me:

$$y_1 = 7^{12} \cdot 16^{20} = 13 \pmod{23}$$
$$y_2 = 7^{3}\cdot 16^{18} = 10 \pmod{23}$$

Now signing a message $m = 13$:

$$\text{output}_1 = 12(13) + 3 = 1 \pmod 2$$
$$\text{output}_2 = 20(13) + 18 = 0 \pmod 2$$

Verifying gives me:

Equation 1 = $13^{13} \cdot 10 = 11 \pmod {23}$

Equation 2 = $7^1\cdot 16^0   = 7 \pmod {23}$

As you can see from the above equation, 11 is not equal to 7 and I cannot verify it.

I suspect the problem lies with using the wrong $q$. Should the value of q exclude 1 and 2?

Any idea at which step I go wrong?

The text you quoted appears to be incorrect; as specified, it doesn't always work (as you found out).

$y_1^m y_2 = g^{\sigma_1} y^{\sigma_2}$ will hold in general if both of the following are true:

$$a_1 m + b_1 \equiv \sigma_1 \pmod{p-1}$$

$$a_2 m + b_2 \equiv \sigma_2 \pmod{Order(y)}$$

Note: it is possible for the equation to hold in other conditions, but because $y$ has no known relationship with $g$, it would be infeasible to find other solutions for non-toy instances of this problem, even for the valid signer.

However, the text specifies that $\sigma_1$ and $\sigma_2$ are computed modulo $q$; if $q < p-1$, then neither of these equations are guaranteed to hold.

I can see two obvious ways to fix up this method:

Specify $q = p-1$; then both $\sigma_1$ and $\sigma_2$ will satistfy the above conditions (N.B.: all possible values of $y$ have an order that is a divisor of $p-1$)
Allow any $q | p-1$; however, specify that both $g$ and $y$ must be of order q.

Also, as specified, this scheme would appear to be insecure as a signature scheme; with two valid signatures, an attacker should be able to recover $a_1, a_2, b_1, b_2$, which is the private key.


How to distinguish a transposition cipher from a simple substitution cipher only given a ciphertext? I am working on one interesting question. There is a ciphertext that has 10,000 letters. We need to distingish whether this ciphertext was encrypted by a transposition cipher or a simple subsitution cipher.

I understand a transposition cipher will keep the identity of each letter and a substitution cipher will change the letter to something new. So, I think we could probably check the common English patterns in the ciphertext (like 'ing', 'th', etc). If those patterns exist, we could conclude that this is a subsitution cipher. Otherwise, it would be a transposition cipher. However, this answer is not convincing for me. I hope to get an answer from an expert.

Think about what properties of the plaintext are preserved by the candidate ciphers. You want to look for those patterns.

Transposition moves letters around but keeps their identity. Substituting keeps positioning but changes identity.

So, you can do a test for whether letter identity is preserved.

The easiest is to do a frequency analysis: if your common letters (e, t, etc) are still common, you probably have a transposition. Of course if not, you are half way to breaking the substitution!

A bonus test goes the other way: see whether position is preserved. A perfect transposition will shuffle the letters, so no pairs should come up more often than expected by chance. If there are any weirdly frequent letter pairs, those are evidence that you have a substitution cipher.


Is this distributed OTP scheme secure? This is for a distributed system: we don't want to have
to maintain synchronization of random streams neither
enforce uniqueness of pads because this would require some synchronization.

Alice and Bob met once.
They agreed on a secret (S) and a symmetric cipher (C).
Let's assume S is 128 bits in length.

Then, they want to communicate in the following way.

Alice want to send a message (M) to bob.
Alice generate a random number (R).
Let's assume R is also 128 bits in length.
She symmetrically encrypt R using S and C.
This become the message header (H), also 128 bits long.
Then, she use R to generate the pad for M, using
a cryptographically strong random number generator.
The generator she uses must be non repeating: it will
never produce the same output twice.
She obtain (M'), the encrypted message.

Then, Alice send to Bob the concatenation of H and M'.

On his side, Bob will first decipher H to generate the pad to decipher M'.

I think the risk of reusing a pad is only 1/(2^256),
which looks terribly small.

Let's say that if Alice and BOB want a MAC, then they
agree on a second secret and a MAC scheme and will
encrypt concatenate(MAC(M),M) instead of just M.

The question describes a stream cipher with key $S$, using $C_S(R)$ to transmit a random session key $R$, and a keystream (or pad) generated from $R$ using a CSPRNG to encipher the message.

This is not an OTP; and contrary to an OTP, it is not secure against a computationally unbounded adversary, who hypothetically, knowing a plaintext/ciphertext pair significantly more than 128 bits, could find by enumeration the (much probably unique) $S$ that could have generated that pair, breaking the system entirely.

Another error is made in computing the risk of reusing a keystream (or pad). It raises with the number of messages. Odds of reusing the same $R$ on or before $n$ messages are
$$1-\prod_{j=0}^{n-1}\Big(1-{j\over2^{128}}\Big)$$
which for small $n$ is about $n(n-1)2^{-129}$; it that happens, the keystreams are the same, and that's detectable by the identical header, and exploitable for cryptanalysis assuming a known plaintext, or plaintext with enough redundancy.

Even for two messages, odd of key reuse are $2^{-128}$ (not $2^{-256}$), and become near $2^{-41}$ for $n=2^{44}$. Which is still perfectly fine in practice.


Applications of Group Ciphers I've been reading a paper [1], and I've ran across something called a "Group Cipher", which is similar to homomorphic encryption, with an important difference.

In homomorphic encryption we have an encryption operation $E_k: P \rightarrow C$, where $P$ is the set of plain texts and $C$ is the set of cipher texts. We also have an efficient group operation on $C$ that induces a homomorphism to the group operation on $P$.

The difference with Group Ciphers is that the group operation on $C$ is composition of encryption $E$, and it induces a homomorphism on the group operation of the set of keys $K$. That means, if we denote an encryption of a plain text $X$ as ${X}_i$, then we would have that ${ { X }_i }_j = { X }_{i \circ j}$.

In the paper they use it to do something like asymmetric encryption, but using symmetric encryption. They do need a semi-trusted third party.

For example, Alice's key is $i$, Bob's key is $j$. Ted has the key $i^{-1} \circ j$.

Alice will encryption something : ${X}_i$. Send it to Ted, who will then encrypt it again : ${ {X}_i }_{i^{-1} \circ j}$ , which will yield ${X}_j$, then Ted send it to Alice again. After that Alice sends it to Bob. Bob can then decrypt it.

What happened here is that Alice can send to Bob, without knowing bob's (symmetric) key. And Bob can decrypt without knowing Alice's (symmetric) key. Just like asymmetric encryption. But using symmetric encryption instead (and a semi-trusted third party).

They also prove that the Pohlig-Hellman cipher has this property.

The question is:

  1- Does Group Ciphers have any other applications in the literature (with references) ?

  2- What are the drawbacks of this scheme compared to asymmetric encryption (other than the required semi-trusted third party) ?

(I was not sure of which tag to use for this question.)

1 S. M. Bellovin and W. R. Cheskwick (2004). "Privacy-Enhanced Searches Using Encrypted Bloom Filters". Draft.

What they are calling a "group cipher" is much more commonly referred to as proxy re-encryption. Proxy re-encryption is typically asymmetric but I don't think there is anything prohibiting it being symmetric. It has many applications (see this list) but most of these applications are using the asymmetric variants. I myself cannot point to another application of symmetric proxy re-encryption.

One drawback is that it is almost as expensive as an asymmetric scheme, so there is little reason to prefer it with today's computational abilities.

Another is that it requires a small multi-party computation between the three parties so that the third party learns the ratio key without Alice or Bob learning it, or the third party learning anything other than it. This MPC requires secure channels, which for all scenarios where at least one pair of parties haven't exchanged keys in-person, this means using asymmetric cryptography to setup the channels.


Is it easy to factorize a number of the form $n = t^{2} \cdotp p$? Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?

Integers of the form $n = p\cdot q^2$, $p$ and $q$ prime, are the basis of a few public-key cryptosystems, including ESIGN, Okamoto-Uchiyama, cryptosystems based around the hardness of finding the class number of quadratic fields. As such, being able to efficiently factor numbers of this form would immediately break a number of cryptosystems. This would be a big deal. Additionally, this is also related to a classic problem in number theory, which would be of independent interest.

As far as concrete factorization algorithms targeting this type of integers, there are various strands:

Peralta and Okamoto slightly optimized ECM against this form, but the result is not significantly superior to regular ECM.
Boneh, Durfee, and Howgrave-Graham used Coppersmith-style root-finding techniques to factor $n$ in approximately $n^{1/9}$ operations when $p$ and $q$ are similarly-sized. While this may sound impressive, it is not better than the number field sieve for numbers of cryptographically-relevant size.
Castagnos, Joux, Laguillaumie, and Nguyen observed that, given some extra information about $n$ it becomes possible to factor $n$ in polynomial time. But this is not the general case and only applies to special cases, like NICE.


The chi-square test for cryptography I have a question about the chi-square test How can we use it in cryptography? And what results should we expect from it when a file is encrypted? I mean, when a file is encrypted, should its value increase?

$\chi^2$ measures the uniformity of a sample distribution. It's commonly used to test samples for randomness (I don't want any hassle on this), to do with true and pseudo random number generators. Uniformity is absolutely necessary for cryptography which you can  read about elsewhere herein.
E.g.
$dd if=/dev/urandom of=/tmp/urandom bs=1000 count=1000

$ent /tmp/urandom
Entropy = 7.999799 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 278.05, and randomly
would exceed this value 15.37 percent of the times.

Arithmetic mean value of data bytes is 127.3541 (127.5 = random).
Monte Carlo value for Pi is 3.141468566 (error 0.00 percent).
Serial correlation coefficient is 0.000781 (totally uncorrelated = 0.0).

A mean value is about 255 for an eight bit window (byte) if a thing is randomesque, or properly encrypted. So yes, generally the thing's information entropy increases to ~8 bits/byte or ~1 bit/bit when encrypted.


Is ChaCha12 considered 256-bit secure? ChaCha20 is considered 256-bit secure (no attack faster than brute force).  However, the best known cryptanalysis that I know of is on ChaCha7.

That gives ChaCha20 a rather large security margin (much larger than, say, AES-256).  Is ChaCha12 still considered to be 256-bit secure (as in "considered usable when top performance and 256-bit security are needed, no HW AES support, and ChaCha20 is too slow")?

Yes, the best attack still seems to be on 7 rounds. Namely, "Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha" shows a $2^{246.5}$ time attack on the 7-round variant.

So even the 12-round variant has a decent security margin – better than AES-256 had when standardized, much less currently.


How to encrypt a file for random access I am a programmer familiar with C/C++ and Python. Lately, we got an assignment from a team asking us to work on one of their projects: we need to make a small program to encrypt a large file using symmetric key encryption. We could easily achieve this using AES128 or AES256 in CRT mode.

The catch however is that if a small part of the file is given along with the location of that bytes from the beginning of the file we should be able to decrypt just that piece.

We thought cutting the file into multiple pieces and applying separate generated key for each but the issue is that regarding what we can do if the said part is not exactly a slice of the size we cut it into. Also would like to know if two over lapping such blocks can be handle.

The idea we are currently working on is this:

We are slicing into 128 bytes each.
Calculate number of bytes from the last slice. So if we get bytes from 10 to 128. It will be 9.
Generate a random padding of 9 bytes at the beginning and then decrypt it. Then remove the first 9 Bytes.
In case multiple slices overlap they are split and the method is repeated.

So, what I would like to know is if this is sensible or if there's a better cipher or algorithm that allows this.

PS:

The files will be image files or document files.
Only know some basics of cryptography.

You basically want a full disk encryption mode for a block cipher; XTS mode seems to be the current standard. In your case each "disk block" is actually a file offset.

Note that using a stream cipher or counter mode is NOT secure if the data is ever modified in the file, as it would violate the cardinal sin of using the same key and initialization vector to encrypt different messages. This is why fancier modes like XTS were created.

CTR mode could be secure if the file were encrypted exactly once per (key,IV) and was then read-only or append-only. However, going that route would involve a massive rewrite and data migration if your requirements ever changed. So find a respected library that implements XTS mode, do not write it yourself as you are not a cryptographer.

Failing that, I would strongly consider punting and using whatever OS-level file or volume encryption system do its job, such as EFS/BitLocker on Windows or eCryptfs/dm-crypt on Linux. All modern OS have such facilities. Even if you might need some platform specific code or configuration, it would be a massive time-saver and isolate the crypto layer from your application.


Help to understand the KDM in SP800-56A, and the usage of "FixedInfo" Can somebody help me to understand the LOGIC behind Key-Derivation Methods (SP800 56A CH5.8)?
This is my common understanding and please correct me if any wrong..

Alice and Bob can general individual key-pair, by any public
cryptography method (RSA, ECC, DL, etc..);
Based on the Key Exchange protocol (for exp ECDH), Alice and Bob can obtain the shared secret Z between them, and using Z as AES key for the afterwards communication.
If they like they can generate the new shared secret Z as they want--that is named as Ephemeral ECDH.

OK my question would be: here I don't really understand the Key-Derivation Methods (SP800 56A CH5.8) application scenarios--it looks like based on the common key agreement scheme (like ECDH), this KDM introduce a "FixedInfo" (which can be a readable text or just some hex string) concept.

I didn't find detail infor about how this "FixedInfo"  works:

Does it use some Hash to process the "FixedInfo" and then derive new Secrete Key?

And does that mean each time a new FixedInfo shall be applied for both Alice and Bob?

Anyway, adding this "FixedInfo" looks NOT enhance security if compare to an Ephemeral ECDH--from my point-of-view..

---self update:
OK after some study I have one explain but am not sure if that is correct--add such "FixedInfo" is actually a kinds of Ephemeral ECDH--it does not require a new ECC key-pair to be generated, so would reduce the key leakage risk? or from computing point-of-view this would save computing power?

There is a couple of reasons one would want to do SP800-56A key derivation in real life scenarios.

Computational and communication cost - while it's true that for each usage the two parties could negotiate a fresh Diffie-Hellman shared secret $Z$ and use it to derive a session key, usually this process is computationally expensive and requires communication between the parties. More frugal approach is to do the key exchange once to agree on a shared secret and then do key derivation to derive shared keys for various purposes.
Shared secret is not a cryptographic key - most likely the shared secret the parties agreed upon is not suitable for use as a cryptographic key. Usually, secrets agreed with DH are too long and (when seen as bit strings) not uniformly distributed. For example, the result of a Diffie-Hellman process over $\mathbb{F}_p^\ast$ would be a number with length 4096 bits. One cannot use it directly as e.g. AES key because it's too long and using only a part of it as a key is an extremely bad idea. So we need to do entropy extraction and this boils down to key derivation.
Many derived keys are required - usually, we need more than one key in a system. E.g. we may need symmetric encryption session keys, maybe HMAC key for integrity protection, etc... The good practice is to use a different cryptographic key for each usage.
And in order to get the required number of different cryptographic keys from one "master secret" $Z$ we need key derivation. And here comes the FixedInfo parameter - it allows to parametrize the key derivation process and bind keys to their usages. For example, FixedInfo would contain the information about parties (so that we separate key derivations for different parties), purpose (so that we separate encryption keys from MAC keys), session (so that keys used for different sessions are different).

A drawback of the key derivation approach that is worth noting is that if the "master secret" $Z$ is compromised, all derived keys need to be treated as compromised as well.
On the other hand, compromise of any of the derived keys does not constitute a compromise of other derived keys or the master secret.


Cryptography - Perfect secrecy => adversarial indistinguishability - proof I'm just starting out with cryptography now and have gone over the various defnitions for a perfectly secret cipher. One of the equvilant definitons is adversarial indistinguishability. When trying to prove the equivilance I had a bit of trouble with one of the directions and ended up finding this proof online:

(Source: http://goutampaul.com/wp-content/uploads/2015/09/lecture4.pdf)

What I don't understand is where they use their inital assumption that the system is perfectly secret. Could someone point it out please?

And am I right to assume that the second C0 in each row at the bottom section is supposed to be C1?

Hopefully I'm able to at least give a partial answer. In the first step of the three equalities, there are three simultaneous steps taken:
$$Pr[M=m_0]=Pr[M=m_1]=\frac{1}{2}$$ and $$Pr[b'=b|M=m_0]=Pr[c\in\mathcal{C}_0]$$ and $$Pr[b'=b|M=m_1]=Pr[c\in\mathcal{C}_1].$$ (Yes it seems the second 0's should be 1's). The first one is clear why it's true, as the messages are randomly chosen. The second two however, are not so obvious.

Let's just look at $m = m_0$. What should be clear, is that $b'=b$ if and only if ${\tt Enc}(m_0)\in\mathcal{C}_0$, by the definition of the game and the strategy explained before the equations. So we can say that
$$Pr[b'=b|M=m_0]=Pr[{\tt Enc}(m_0)\in\mathcal{C}_0|M=m_0].$$
Writing $c={\tt Enc}(m_0)$, what remains to prove is that
$$Pr[c\in\mathcal{C}_0|M=m_0]=Pr[c\in\mathcal{C}_0].$$
Now compare this to Theorem 2.2 of the document you cite, which gives a criterium for perfect secrecy. It is not exactly the same, but it is very similar. This last equality I stated is really a consequence of perfect secrecy, and does definitely not hold in general.

Suppose for example that our encryption scheme gives our ciphertext the same least significant bit as the plaintext, and suppose that $m_0$ has lsb 0 and $m_1$ has lsb 1. Then we can easily choose $\mathcal{C}_0$ and $\mathcal{C}_1$ such that
$$Pr[c\in\mathcal{C}_0|M=m_0]=Pr[c\in\mathcal{C}_1|M=m_1]=1.$$
On the other hand, not both $Pr[c\in\mathcal{C}_0]=1$ and $Pr[c\in\mathcal{C}_1]=1$.


Best way, how to convert 32-byte Keccak hashes to positive numbers up to maximum? I have 32-byte Keccak hashes and I have some maximum number, for example 500, how to uniformly convert those hashes to pseudo-random positive numbers up to that maximum?
I mean I have for example 100 quite random hashes and I want to distribute them so the result would be something like 80 numbers hit once, 19 twice and 1 hit three times (I guess something like that), somehow uniform distribution.
The maximum can be over 32-bits, so I need to use 64-bit integers.

Some approaches come to my mind:
a) always take first 8 bytes, convert them to 64-bit integer and use modulo 500 on them,
b) sum 1st 8 bytes, 2nd 8 bytes, 3rd 8 bytes and 4th 8 bytes to 64-bit integer and use modulo 500,
c) something better?

I know that modulo is not the best for uniform distribution, because it slightly prefers numbers at the beginning of the range, but I think I google how to overcome that by myself and I think it's not even a big deal.

The other thing I am not sure about is whether all the bits in Keccak hashes are quite uniformly distributed, but I guess they should be. I hope that some bit doesn't favor 0s or 1s so some numbers don't get an advantage during my conversion.

Your "32-byte Keccak hash" doesn't look like a canonical, binary Keccak output, but rather appears to be encoded with some Base64 variant—to me it appears to be the MIME version.  Your comments on the matter confuse me whether that is the case or not; you should check your language or library's documentation.

If it's Base64 then it appears to be encoding a 18 bytes of raw binary output, which is 144 bits.  This is a unusual output size.  I would double check how your software is generating that output, and verify that all of that Base64 string really reflects a 144-bit Keccak output, and that there aren't some constant bytes being prefixed or suffixed to it.  Again, your description and comments are not helpful in this regard.

Taking the modulo is fine in practice if you do it over a large enough input set.
 Appendix B of NIST SP 800-185 contains a recommendation that uses modulo to convert the output of an extendable output or variable length hash function into a near-uniform natural number $0 ≤ n < R$ for arbitrary $R$.  The trick is that they make sure to do it over a hash output that is at least 128 bits longer than the number of bits needed to encode values in the output range:

Compute $k = \lceil\log_2(R)\rceil + 128$, where $\lceil\log_2(R)\rceil$ is the number of whole bits needed to encode $R$ distinct values.  For $R = 500$, this is $k = 9 + 128 = 137$.
Hash your input to an output $Z$ with length of at least $k$ bits.  Since your outputs are at least 144 bits, they meet this requirement.
Convert $Z$ to some "bigint" data type (arbitrary precision integers, check library support in your language; e.g., in Java it's BigInteger).  The bits_to_integer algorithm they detail in the document just parses $Z$ as a binary numeral with least significant bits first, although that later detail is not critical (e.g., Java BigInteger parses them in the opposite order, and that's just fine).
Take $N = \mathit{bits\_to\_integer}(Z) \mod R$ as your result.

The trick that allows them to use modulo is that they're willing to accept a biased distribution if they can guarantee the bias is astronomically small.  That's why they insist on taking a hash output 128 bits longer than the number of bits needed to encode $R$.  Suppose we used $R = 500$ but $k = 9$ (instead of the recommended $k = 137$).  The problem here is that since $2^k = 2^9 = 512$, when you take the modulo, 488 of the values have a probability of $1/512$ but 12 of them have a probability of $2/512$—they're twice as likely as the others.

Now suppose we take $k = 10$ instead, so $2^k = 1,024$.  Now when you take modulo 500, there are 476 values in the range have a probability of $2/1,024$ but 24 of them have probability of $3/1,024$—they're only 50% more likely than the rest.  For $k = 11$, $2^k = 2,048$ so you get 452 values with probability $4/2,048$ and 48 with $5/2,048$ (only 25% more likely), and so on.  By the time you get to $k = 137$ the bias is negligible; footnote 12 of the appendix gives:

$$
|\mathrm{Prob}(N=t) - 1/R| ≤ 2^{-w}
$$

...where $w ≥ \lceil\log_2(R)\rceil + 128$.


What happens when cbc+hmac get a replay attack? If it use AES-CBC and HMAC-SHA256 for message send online, and someone try to replay attack on this message. Can the attack be successful? what will be happen when attacking?

Rejecting replays is the duty of a higher level protocol. Simple authenticated encryption will accept any message with a valid MAC, even if you receive it several times. Decryption is a stateless process, but you need state to keep track of messages you already received.

For example you could associate an increasing counter with each message you send. The recipient then keeps track of the highest counter they have received so far and rejects any lower counters. You could send that counter in plaintext alongside the ciphertext, but make sure to include it in the data you MAC.

For other modes of encryption the IV/nonce can double as counter. This is the case for AES-GCM or XSalsa20Poly1305.


Is $F(x) =Ax+b$ a pseudorandom function or not? Consider the following keyed function $F$: For security parameter $n,$ the
key is an $n\times n$ boolean matrix $A$ and an $n-$bit boolean vector $b$. Define
$F_{A,b} : \{0, 1\}^n->\{0, 1\}^n$ by $F_{A,b}(x) = Ax + b$, where all operations are
done modulo $2.$ Show that $F$ is not a pseudorandom function.

I have thought for a whole day but could not conquer it, so hope to get the solution here. Thanks.

I have searched the similar question in network and drawn a solution as follows:

Let's consider the distinguisher $D$ that queries its oracle $\mathcal{O}$ on arbitrary. At first, let $x=0^n$, we can get $b=\mathcal{O}(0^n)$. Then, we access the $\mathcal{O}$ with $x_1$, $x_2$, $x_1+x_2$, output $1$ if and only if $\mathcal{O}(x_1 )+\mathcal{O}(x_2 )-b=\mathcal{O}(x_1+x_2)$.

If $\mathcal{O}=F$, $Pr\left[D^F{^{(\cdot)}}  (1^n)=1\right]=1$.
If $\mathcal{O}=F$ for f chosen uniformly from $Func_n$, $Pr[D^{f(\cdot)}  (1^n )=1]=2^{-n}$.

The difference is $|1-2^{-n}|$, which is not negligible. Therefore, F is not a pseudorandom function.


What does a vertical bar mean in this context? I'm doing a few exercises regarding Schnorr's identification scheme.
I have the exercise starting off like this, with the values defined:

Let $p = 311$ and $r = 31\ |\ (p - 1)$. Let $g = 169$, which has order $r$.

I just really can't figure out what the vertical bar means here?
Sometimes in discrete maths, a vertical bar means absolute value, sometimes two them are cardinalty? Programming would suggest that it means a logical or?
One place I saw something indicating that it might be xor, but I really have no idea.

The meaning of that $\ \vert\ $ in this context is divides (as in evenly divides, or is a divisor of), and that's a standard usage of this sign. The quote should be read as:

let $p=311$ and $r=31$, which divides $(p-1)$. Let $g=169$…

In other words: $r$ is a divisor of $p-1$. Or, exists integer $q$ with $r\times q=p-1$. Or, $((p-1)\bmod r)=0$, also writable as $p-1\bmod r=0$ or $p-1\equiv0\pmod r$ or $p\equiv1\pmod r$. In many common programing languages, (p-1)%r == 0. That's because $31$ (evenly) divides $311-1$, since $31\times10=310$.
That was correctly guessed by Aman Grewal in comment, but as noted, proximity with the assignment makes the notation confusing. Elision of the implied which is something I would try to avoid.

The end of the sentence says «Let $g=169$, which has order $r$». Does that mean that $g$ is really 169%31?

No. The term order is used in its meaning in group theory. In this context, it means that when we repeatedly multiply $1$ by $g$, reducing modulo $p$ after each multiplication, we'll first get back to $1$ after performing $r$ multiplications. That's related to $r\,\vert\,(p-1)$, because the order of any element in a finite group is a divisor of the order of the group, that is the number of elements in the group. Here the group is the multiplicative group modulo $p$, noted $\mathbb Z_p^*$ or $(\mathbb Z/p\mathbb Z)^\times$, which has $p-1$ elements since $p$ is prime. The powers of $g$ form a subgroup of order $r$, called a Schnorr group.


Oblivious transfer impossible from noiseless channels If computationally unbounded parties $A$ and $B$ have only a noiseless channel between them, why is information-theoretic oblivious transfer impossible even for the passive cheating setting?
Intuitively, the noiseless channel makes the views of $A$ and $B$ almost identical except for the private randomness that $A$ and $B$ use. An unbounded passive cheater shouldn't be able to guess this randomness. How do we provably rule out some clever usage of private randomness that allows the sender to hide one of their bits and the receiver to hide her choice bit?

Information theoretic OT cannot be achieved because OT can compute any function in a two party setting, that is, OT is complete (meaning, it is among the hardest problems in its complexity class)  as shown by Kilian[0]. We know that there are functions that cannot be information theoretic securely in a two party setting[1]. Hence, information theoretic OT is impossible.
[0] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.9265&rep=rep1&type=pdf
[1] https://eprint.iacr.org/2006/183.pdf


Have these compositions of block ciphers the same security? I'm interested by the compositions of the block cipher DES, instantiated with independent keys $k_1$, $k_2$ and $k_3$.

Are these 3 compositions equivalent in terms of security?
$$DES_{k_1}(DES_{k_2}(DES_{k_3}(.)))$$
$$DES_{k_1}(DES_{k_2}(DES^{-1}_{k_3}(.)))$$
$$DES_{k_1}(DES^{-1}_{k_2}(DES^{-1}_{k_3}(.)))$$

I'm also interested in the same question with two iterations (instead of 3). Are these equivalent in security?
$$DES_{k_1}(DES^{-1}_{k_2}(.))$$
$$DES_{k_1}(DES_{k_2}(.))$$

Yes, you can reasonably expect that these will provide equivalent security, if you choose all keys uniformly and independently at random.  The decryption operation is basically the same as the encryption operation, so it would be extremely surprising if there was any significant difference in security among these.

(Of course, if you don't generate the keys randomly, then this all goes out the window.  For instance, $DES_{k1}(DES_{k1}(\cdot))$ has very different security properties than $DES_{k1}(DES_{k1}^{-1}(\cdot))$.  I suspect this doesn't need saying, but I'm listing the caveat explicitly: it is important that you choose all keys uniformly and independently at random.)


Signing a document: which algorithm to use? What I want to do is to digitally sign a document. I am new to cryptography and was wondering what issues to take into account.
The only criteria is that a textual document signed should produce a code that is different if lines in the same document are shifted. I heard that MD5 is broken and that one should avoid SHA1 (because of NSA etc).

As I said, I am new to crypto. Any suggestions would be welcome!

I guess they would need to go to my website, find the document and check whether the signed code is the same as the document they want to check.

If you assume people are able to trust your website, you could simply list the SHA-256 (for example) hashes of your documents on your website. Perhaps include an URL in the signed document pointing to a particular page on your site that lists the hash for that file.

Trusting others to get the correct hash from your website when they visit the URL would remain unsolved. Someone could intercept the request and return a different hash that matches a modified document they've distributed.

The more complex option is public key signatures.

If you go that way you would use something like GPG/PGP to generate a key-pair, distribute the public key, then sign the documents using the private key. In this case an attacker couldn't produce a different signature that matches your key even if they controlled requests to the documents and your website.

However, you would still need to get your public key into the hands of anyone wanting to verify the signature. An attacker who could distribute their own key as yours could again forge signed documents in your name.


eXtended Merkle Signature Scheme (XMSS) vs Leighton-Micali Signature (LMS) Very briefly, how does eXtended Merkle Signature Scheme (XMSS) stack up against Leighton-Micali Signature (LMS)?

I'm asking this in the context of my article here.

I'm asking this in the context of my article here.

I don't see how your article has any reference to stateful signatures at all.

In any case, the differences are:

They have provable security in different models; XMSS in the concrete model, LMS in the random oracle model
LMS is about 3 to 5 times faster than XMSS (assuming that the messages are short)

I suspect that, if you use a stateful signature scheme in a block chain solution, neither difference is that significant.

The two standards also allow different sets of tree heights/Winternitz parameters, but there's nothing inherent in the two ideas to restrict things. I'm pretty sure that if have your heart set on one parameter set that works great for your application, you can ask the authors for it.


Is the RSA cipher alike to the Shift/Caesar cipher? I'm sort of a beginner on cryptography so this is probably a really elementary question. I only know the historic ciphers and the general background on cryptography as well as it's general meaning. I'm just starting to dive into modern ciphers like RSA and DES.

When looking at RSA, aside from using different keys for encryption and decryption, it seemed to me that the encryption process is sort of like a substitution cipher or better the shift or caesar's cipher (since this one does some kind of math at least), and that it operates on the characters' Unicode or ASCII instead.

Is there any way in which I'm correct or is there any way that the RSA could be sort of like a shift cipher that operates on the coded text instead of the normal one? I'm probably not correct so if so could you tell me the ways by which it makes it different or unique? Thanks in advance!

You are close but not exactly. In short, RSA is a trapdoor permutation.

Let $(n,e)$ is a RSA public key, then $y = f(x) = x^e \bmod n$ is a trapdoor permutation. RSA is a permutation since the function $f:\mathbb{Z}_n^*\to \mathbb{Z}_n^*$ is bijective.

RSA is a trapdoor permutation. Normally you can find the inverse a permutation if it is given explicitly. In RSA, however, given $x$ and the public key $(n,e)$, we can easily compute $f(x)$. If one is given a $y$ and the public key $(n,e)$, it is difficult to compute $f^{-1}(y)$. If one has the private key (the trapdoor),  can compute $f^{-1}(y)$.

RSA is not a shift-cipher. Although, a shift-cipher is also a permutation, seeing a randomly generated 2048-bit RSA public key that acts like just a shift-cipher will amuse any cryptographer. Actually, this is not possible with small public exponents.

Like any permutation, for textbook RSA, one can write a table and store it, so that you can revert it very easily. The encryption oracle is free. However, there are problems with this;

Today RSA requires at least 2048 or more bits to be secure. Therefore the table for the reverse permutation is infeasible. You cannot store it, however, you may perform short message attacks if textbook RSA is used. Generate all small short messages and compare them.
Textbook RSA is not used in practice and should never be used. For encryption there are padding schemes like PKCS#1 v1.5 padding or Optimal Asymmetric Encryption Padding (OAEP). The former is hard to implement and has attacks occur, again and again, Bleichenbacher and Manger attack. PKCS#1 v1.5 padding has no security proof, however, OAEP has one. If one ever consider encrypting with RSA should consider OAEP. These paddings have random bits that prevent getting the same result for the same input. Therefore with these paddings, the RSA permutation is randomized.

In practice, RSA is not used for encryption. It can be used for;

digital signatures with Probabilistic Signature Scheme (PSS)
Key encapsulation mechanisms
Hybrid encryption : RSA-KEM with Data Encapsulation Mechanism (DEM). Composition of a KEM and a DEM provides us the standard of IND-CCA2/NM-CCA2—ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack if an authenticated encryption mode is used like AES-GCM, ChaCha20-Poly1305, or
crypto_secretbox_xsalsa20poly1305


PRF that can be distinguished after $k$ queries? In adaptive attacks, if we design poorly, adversary can modify his queries and break the given pseudo random function (that is being able to distinguish it from uniform randomness).

Is there a poor way to design a PRF such that in one round of query, the adversary cannot distinguish but in two rounds the adversary can?

How about adversary failing to break at $k-1$ queries but breaking at $k$th query?

A $k$-wise independent hash family has the property that the joint distribution of $h(x_1), h(x_2), \ldots, h(x_k)$ is uniform when $h$ is chosen uniformly from the family (and $x_i$'s are distinct). Such families exist unconditionally (for fixed $k$), are efficient, and satisfy the condition you give.

The simplest example of a 1-universal function is $F(k,x) = x \oplus k$. Clearly the output of $F$ on one point is uniform (it's a one-time pad) but with two queries $F$ can be easily distinguished from a random function.


How to protect against ephemeral key reuse in some signature schemes? Given that some signature schemes (for instance Elgamal) use an ephemeral key that cannot be reused ever. How do people usually protect against this?

I'll elaborate more: if you reuse the ephemeral key in Elgamal for two different signatures you have (AFAIK) effectively given away your secret key. If the same public/private key pairs are normally used for long periods of time (sometimes years), how can you be sure that you never repeat the ephemeral key?

I know this key should be chosen randomly and given its length the probability of reuse is very tiny. But the risk is so big that I think it's worth taking some countermeasure.

Is there any standard way of dealing with this or am I totally missing something?

Would you say: the probability of mass life extinction on earth caused by asteroid impact is like $2^{-28}$/year; but the risk is so big that I think it's worth taking some countermeasure?

The applied cryptographer's position is that below a certain probability, like $2^{-40}$ lower than mass life extinction on earth, there's no need to mitigate the risk. It is best to spend effort on countermeasures against a stuck TRNG, by accident or attack.


Bluetooth Low Energy: Key generation I'm studying the BT core spec v5.1 to understand the security features and how everything fits together. I am looking at Secure Connections for now.

In the field "Key generation" it says it uses P-256 ECDH and HMAC-SHA-256 for this. However, when we read a little bit closer about the different functions themselves, it says that it uses AES-CMAC for key generation.

What's going on here?

The Diffie-Hellman key exchange is performed in the device pairing phase with P-256 elliptic curve to generate a shared secret DHKey. The function $\texttt{f}_5$ is then used to derive the long-term keys LTK and MacKey from DHKey according to this equation:

MacKey || LTK = $\texttt{f}_5$ (DHKey, N_master, N_slave, BD_ADDR_master, BD_ADDR_slave)

where N_master is the random number sent by the master to the slave, N_slave is the random number sent by the slave to the master, BD_ADDR_master is the device address of the master and BD_ADDR_slave is the device address of the slave.

This is very similar to TLS, where a master secret is generated using Diffie-Hellman key exchange and then the individual encryption keys are derived from the master secret using symmetric primitives.


Some doubts about GnuPG I've reading on GPG since yesterday and I have a doubt: the whole system of double key encryption does make sense but it looks to me like either way you are compromising something in terms of security.

If someone sends me an encrypted file using GPG and he/she wants to make sure that I'm the only one able to decrypt it then he/she will encrypt that file using my public key. Now, the only way to decrypt it is to use my private key, which supposedly I'm the only one in the world to have it. So far, so good.

However, if we also want to make sure that there are no forgers and that we're actually exchanging files between us (issue 1) then we would need to encrypt files using each one their own private key. This requires us to share our public keys. But here we go, another problem (issue 2): what if I published my public key on a website/blog/etc. some time ago and I had forgot about it? What if an intruder is able to intercept such messages and by using the public key (that he/she found online) is now able to decrypt files?

The way I see it you have to compromise, and you can't really mitigate 100% both issue 1 and 2. Did I misunderstood something about GPG?

At this point, why not simply try to rely on a 7zip encryption and use a (moderately complicated) passphrase that you both know?

Thanks!

You cannot encrypt a file with a private key. With RSA, that's not because of any technical obstacle (with other schemes private keys literally are not valid inputs to the encryption function), but because private keys are designated as "private" and using them in an encryption operation compromises the security of that message. To prove you wrote the message, you don't encrypt it with your private key.

What you do do is sign the message. Signatures take a private key; best practices are to use a different keypair for signatures than for encryption (a default GPG "keypair" is really at two keypairs; there's a master keypair that's tied to your identity which is used only for signing, and a different subordinate keypair which is signed with the master keypair and which is used only for encryption). If you use different keys for signing and encryption, there are no issues with compromising your encryption.

Signing with RSA is not "encrypt with the private key." It has a passing resemblance to that (as the primitive used for encryption, the one for signing, the one for decryption, and the one for verification are all the same operation with different inputs and outputs) but it is a conceptually distinct algorithm which is designed not to let someone with the signature recover the message.

An RSA signature is created by creating a preimage-resistant hash of the message, doing various operations (known as padding) to the hash value to increase security, and passing it through the signature primitive (raising it to the power of the private exponent modulo $n$). In the more modern signature padding algorithm (PSS), the hash of the message is itself not recoverable, because it is combined with a random salt and passed through another preimage-resistant hash, and that is part of what's passed to the signature primitive (the other part is the salt, obfuscated using the hash of the hash+salt). In the older system (PKCS 1.5 padding), the hash could be directly recovered, but as it's preimage-resistant that doesn't give much help to an attacker looking for the message. An attacker in either case can test whether a given message was the one sent, but they can't find the message if they don't already have a candidate message.


Update non-member witness in RSA accumulator According to study of "Universal Accumulators with Efficient Nonmembership Proofs", I don't understand exactly how to update non-member witness in construction 4.2.

In the addition step, I understood the point until finding $r$. I can't understand why new non-member witness $d' = d \cdot c^r$.

Can somebody explain how to obtain this result please?

Here is the link: https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf (Construction 4.2: Update of Nonmembership Witness)

Recall that for a set of elements $X=\{x_1,\cdots,x_n\}\subseteq\mathcal{X}$

the value of the accumulator is $c=g^u\bmod{N}$, where $u:=\Pi_i x_i$; and
the witness of non-membership for an element $x\not\in X$ is the pair $(a,d=g^{-b})\in\mathbb{Z}\times\mathbb{Z}_N^*$, where $a$ and $b$ are integers satisfying Bézout's identity $$au+bx=1,\tag{0}$$
which is verified by checking whether $$c^a=d^xg\bmod{N}.\tag{1}$$

We are considering the case where an element $\hat{x}\neq x\in\mathcal{X}$ has been added to $X$, i.e., the new set is $\hat{X}:=X\cup\{\hat{x}\}$, and this has resulted in the accumulator value
$$\hat{c}:=g^{\hat{u}}=(g^u)^{\hat{x}}=c^\hat{x}\bmod{N},$$
where $\hat{u}:=u\cdot \hat{x}$. We would like to update the witness of non-membership for $x$ to $(\hat{a},\hat{d}=g^{-\hat{b}})$, where $\hat{a}$ and $\hat{b}$ are integers satisfying Bézout identity
$$\hat{a}\hat{u}+\hat{b}x=1.\tag{2}$$
This could be done from scratch, but it is desirable to derive it efficiently from the previous witness $(a,d)$ and accumulator value $c$. I did not quite understand how it is done in the paper, but another way to accomplish the same would be as follows:

Find integers $\hat{a}_0$ and $r_0$ satisfying Bézout's identity
$$
    \hat{a}_0\hat{x}+r_0x=1.\tag{3}
  $$
Note that this is possible since $x$ and $\hat{x}$ are co-primes.
Set $\hat{a}=\hat{a}_0a$ and $\hat{d}=dc^r\bmod{N}$, where $r=r_0a\in\mathbb{Z}$ .

Let's see why Step 2 works. Our goal is to go from (3) to (2) and we do this using (0): let's multiply $(3)$ on the left by $au$ and on the right by $1-bx$ yielding
$$\begin{align}
    \hat{a}_0\hat{x}(au)+r_0x(au)=1(1-bx)
   &\Leftrightarrow \hat{a}_0a(\hat{x}u)+(r_0au+b)x=1\\
   &\Leftrightarrow (\hat{a}_0a)\hat{u}+(r_0au+b)x=1\\
   &\Leftrightarrow \hat{a}\hat{u}+\hat{b}x=1,
    \end{align}
$$
where we set $\hat{a}=\hat{a}_0a$ and $\hat{b}=r_0au+b$. Now, observe that although we can compute $\hat{a}$ we cannot compute $\hat{b}$ (since we don't know $u$). However, what we need is $g^{-\hat{b}}$ and it is possible to compute this from $c$ and $d$ as
$$g^{-\hat{b}}=g^{-r_0au-b}=(g^u)^{-r_0a}g^{-b}=c^{-r_0a}d\bmod{N}.$$


Is it secure to concatenate two 16-bit random numbers into a 32-bit one? I'm working on a security application for RF modules aimed to protect a communication between an autarkic sensor and a line-powered receiver against MITM (man-in-the-middle attacks). I decided to use a communication approach based on a unilateral authentication using a 32-bit random as Nonce with time limited validation. I'm using for that a specific development tool, a specific library written in C and a compiler(C51 of Keil microvision for those who heard about it).

This specific library is offering me the possibility to generate a 16-bit random number reading the noise of an ADC. I suppose it is a true random. So I thought of calling this function twice and concatenating the outputs to produce a 32-bit random but I'm not quite sure if it is a secure way to process a random number. So I'm asking you guys:

What is the entropy in the resulting value? (I read an Intel post
saying that it is 17 bits of entropy in my case but I'm wondering if
it's correct and I heard others saying that it is always 32 bits of
entropy.)
How to evaluate the distribution of the resulting values over the
whole range of 32 bit values [0...2^32]?
By calling my function twice to generate the 16-bit random values,
the noise of the ADC will be read twice but considering that the
process of generating these numbers is based on microscopic phenomenon  I  suppose it is unlikely to have two equal values such as 0x12341234 or 0xAABBAABB or whatever. It means maybe that these numbers are less likely to come than the others. Correct?
And last but not least, does using a cryptographic mixing (quadratic
residues maybe?) after concatenating the two improve the
level of security (entropy) of the resulting value or not?

The Intel post which I think you mean was discussed in this question and as I wrote there, the limitation only applies in the case of trying to combine PRNG outputs into values larger than the seed entropy (two 256-bit values in their case). Also mentioned there: cryptographic mixing does not increase the entropy you have, so if concatenation is insecure, just mixing is as well.

So, whether you can concatenate two 16-bit values depends on how the library/hardware works:

If you are getting raw noise readings it is unlikely it has 16 bits of entropy per value. You would need to collect many and mix them into a single value if you wanted truly random values. And you would need to find out what sort of correlations the data has to determine the entropy rate.
More likely, there is already some mixing/whitening going on that tries to assure full entropy for the output values. If that is the case, you can combine them just fine.
If the library uses a PRNG to generate more output values than the input entropy from the hardware you again cannot combine two values and retain full entropy.


How to make a hypothesis test for a simple statistical test for a certain RNG? I'm self-studying about hypothesis test in the context of RNGs.  I'm building a hypothesis test from scratch.  I'm taking the simplest statistical test I can think of: how many $1$s are there in the sequence sample?  My null hypothesis is that the RNG is uniform, so I expect the average number of $1$s to be close to $n/2$, where $n$ is the size of the sample.

I believe (or I guess) the sample averages should follow a normal distribution.  To implement the hypothesis test, I will have to know the variance, though.

What should I do here?  Should I look at a good RNG and come up with a variance relative to my simple statistical test?  This makes sense to me.  A good RNG will likely present averages close to $n/2$, specially if $n$ is large.  I could then empirically determine the variance this way.

Is there anything wrong with this construction?  Can you advise?  My main interest is not in testing real world RNGs.  My main interest is in knowing how to do hypothesis test, but I'm looking for an example in this precise context.

The number of one bits in a sequence of iid Bernoulli trials won't be normal: it will be binomial.  But you have the right intuition that, as the number of bits grows, the binomial distribution converges to a normal distribution—specifically, for fixed $p$, as $n \to \infty$, $$\operatorname{Binom}(n, p) \to \mathcal N\bigl(np, np(1 - p)\bigr),$$ or, more precisely and with less abuse of notation, if $X_n \sim \operatorname{Binom}(n, p)$, then $(X_n - np)/\sqrt{np(1 - p)} \to Z$ where $Z \sim \mathcal N(0, 1)$ is a standard normal.  This is a standard theorem of probability theory, the de Moivre–Laplace theorem; see, e.g., Feller, Vol. I, Ch. VII, ‘The Normal Approximation to the Binomial Distribution’, for an introduction.

That said, once you have decided on your test statistic and cutoff for a prescribed false alarm rate (‘statistical significance’), your job is not done: you should also have alternative hypotheses for the bugs you might have in your software, or physical defects you might have in your hardware.  For instance, will you detect deterministic alternating 0/1 bits?

The hypothesis test is valuable only insofar as it distinguishes plausible nonuniform distributions from uniform ones.  After all, if all you want is a hypothesis test with statistical significance 0.05 like any good little psychology journal, you could ignore the data altogether, roll a d20, and raise an alarm if you rolled a 1.

If you're talking about a pseudorandom generator, which is a deterministic function of a key, then your hypothesis test should be designed with knowledge of the function.
If you're talking about a hardware entropy source, which is a physical process, then your hypothesis test should be designed with knowledge of the physics.

If you just count bits and apply a test for goodness-of-fit in terms of the ratio of zeros to ones with significance level 0.05, and stop there, you've only made an entertaining way to implement a d20 in software.


Burmester-Desmedt (BD) key agreement protocols How do you perform the Burmester-Desmedt key exchange Protocol, in Diffie-Hellman
extension protocol?

I've been searching high and low, but couldn't locate an example on how to prove if all the party is getting the same session key.

Here is the explanation that I got from the net:

I don't really get all the formula, especially this calculation:

$k_i = (k_i + 1 / k_i - 1)^{x_i} \mod p$

Example:

$k_i = g ^{x_1} \mod p$

assuming $x_1 = 4, g = 2$ ( 2 is a generator from $Z_{11}^*$ ) and $p = 11$

$k_1 = 2^4 \mod 11$

$k_1 =  5$

therefore,

$k_1 = (k_1 + 1 / k_1 - 1) ^ x_1 \mod p$

$= (5+1 / 5-1) ^ 4 \mod 11$

$= (6 / 4) ^ 4 \mod 11$

= ...

How should I proceed from here on?

ADDITIONAL

And after the k1 is found, how can i prove that other parties (n = 3) are getting the same session key (K) ?

All this work is done modulo the prime $p$ (which is 11 in your toy example); in this field, addition, subtraction and multiplication is done in the usual way (except you do a modulo $p$ at the end); however division is defined differently.

We define $x = 6/4\  (\bmod 11)$ to be that value such that $x \times 4 = 6\  (\bmod 11)$.

Now, we see that $7 \times 4 = 28$ and $28 = 6\  (\bmod 11)$, hence $6/4 = 7$.  And, yes, if $p$ is prime, and if what you're dividing by is not zero, then it turns out that such division is uniquely defined; there will always be precisely one number between 0 and $p-1$ that meets this criteria.

How do we find such values $x$.  Well, when $p$ is small, you can just test the various possibilities (like I did in this case).  However, if $p$ is large, you can efficiently find such values using the Extended Euclidean Algorithm


Crypto hash function vs encryption algorithms Why is a cryptographic hash function generally faster to execute in software than conventional encryption algorithms such as DES?

The speed of individual algorithms strongly depends on their implementation. This goes for both hashing algorithms as well as encryption algorithms. This quickly becomes clear if you take a look at efforts like “eBACS: ECRYPT Benchmarking of Cryptographic Systems” and the results presented.

Also, you should not ignore that some algorithms have specifically been created with an eye on hardware implementation, while others were created with the clear goal of software implementation. This can result in the fact that an algorithm which was actually meant to be implemented in hardware, shows a low speed performance when being implemented and benchmarked as software version.

Therefore, you can not generally assume one algorithm to be slower or faster than another, without looking at their actually assumed implementation. Anything else practically results in rather incorrect (better: rather unfair) benchmarks.

Looking at DES

As you´ve mentioned DES… DES shows a bad performance as software implementation because it was intended to be implemented in an application-specific integrated circuit (ASIC). When you look at hardware designs of DES, you´ll see it perform pretty well in relation to speed.

Of course, things like its successor – AES – for example are able to beat DES out of the water both as hard and software implementation. But you have to remember that the Data Encryption Standard has been created more than 2 decades ago. As technology evolved, so did cryptographic algorithms.

Is it fair to compare DES with encryption algorithms like AES?

Not really. AES (First published in 1998) came around and about 20 years later than DES (First published in 1975, standardized in January 1979). In those 2 decades, both hardware as well as software evolved… and the creators of AES surely had the benefit of being able to look back at DES and its issues (both in relation to cryptanalysis as well as in relation to different implementations).

Is it fair to compare DES with hashing algorithms like SHA2?

Same as before: not really. SHA2 (First published in 2001) benefitted from similar things like AES. While we now may have access to cool things like personal computers et al, things looked quite different back in the 70´s… not only from a technological point of view. While DES includes several bit-oriented operations, SHA2 (and AES) were clearly designed with modern CPUs in mind, which logically results in better performance on modern computer systems (which they were designed for).

Wrapping it up

Whenever you compare speeds and something outperforms something else, the reason might be as simple as the fact that one of them is older and therefore slower due to not being as advanced as what you´re comparing it to.

In relation to cryptographic algorithms, looking at individual publication dates can tell a whole story…


Symmetric versus asymmetric self encryption I can encrypt my files with a symmetric encryption algorithm like AES, or with an asymmetric encryption algorithm like RSA or ECC (I encrypt my files with my own public key). No communication is involved in this scenario. The latter, which one may call asymmetric self encryption, might seem an unusual choice in situations where a key exchange is not required. However, it still does have some advantages: you don't need to type your passphrase for encryption (you need your public key); it works well with keys stored in a hardware token; also, an attacker apparently needs both to have the public key and brute-force the passphrase to decrypt the data. In GnuPG, these two encryptions are achieved via options gpg -c and gpg -e -r USERNAME.

Considering attacks on the asymmetric encryption, does hiding the public key increase the entropy required for a brute force attack? What information does the public key leak to the attacker?

The standard algorithms for symmetric and asymmetric encryption are AES-256, 4098-bit RSA. The answer to the above question helps compare the security level of these algorithms (in terms of the number of bits that needs to be checked).

called asymmetric self encryption

No, not really, you just made up that term.

  might seem an unusual choice in situations where a key exchange is not required

No it doesn't, although commonly a hybrid cryptography is used, especially for EC based cryptography.

  an attacker apparently needs both to have the public key and brute-force the passphrase to decrypt the data.

Of course not, the attacker requires the encrypted private key and a password to unwrap that key using password based encryption (PBE).

  Considering attacks on the asymmetric encryption, does hiding the public key increase the entropy required for a brute force attack? What information does the public key provide to the attacker?

Possibly, but the scheme should of course be secure even if the public key is known to the attacker. Generally the public key is not considered a secret, and that means schemes, but also the implementations of the public key operations are not protected against leaking the public key.

  The standard algorithms for symmetric and asymmetric encryption are AES-256, 4098-bit RSA. The answer to the above question helps compare the security level of these algorithms.

No, it really doesn't. In some situations asymmetric cryptography may be more secure, even though the key strength of the symmetric encryption is larger than the key strength of asymmetric encryption. However, it is impossible to quantify that advantage, so you cannot talk about a "level".


Reuse of TLS client key/certificate in challenge-response protocol The situation: We have a custom PKI with clients communicating with the server over standard SSL/TLS encrypted channel. PKI uses ECC, server certificate supports ECDHE_ECDSA key exchange mechanism and is signed using our custom CA. Clients are authenticated to the server using their client certificates containing ECDSA public keys.

In addition, clients also communicate with each other - this channel is not encrypted and we only use a simple challenge-response protocol for unilateral authentication (only one side needs to be authenticated). The challenge-response protocol is taken from the Handbook of Applied Cryptography (10.3.3(ii)2., PDF) and goes as follows:

$A ← B : r_B$

$A → B : cert_A , r_A , id_B, S_A (r_A, r_B, id_B)$

where:

$r_B$ is a random challenge generated by $B$.
$cert_A$ is $A$'s certificate.
$id_B$ is an identifier of $B$.
$r_A$ is a random number generated by $A$ to prevent chosen-text attacks.
$S_A(r_A, r_B, id_B)$ is a signature computed over concatenated values of $r_A$, $r_B$ and $id_B$ using $A$'s private key corresponding to $cert_A$'s public key.

So, $cert_A$ and corresponding $A$'s private key are reused in SSL/TLS and the challenge-response protocol. Are there any bad consequences of this approach? Any suggestions? Thanks.

No, there are no problems (which I could see) with re-using the signature key in this scenario.

There are two potential concerns:

It may be possible to learn something about the private key using the challenge-response protocol
It may be possible to re-use the signature of a run of the challenge-response protocol for TLS

The first concern is clearly invalid, as any decent signature won't allow you to learn anything about the private key just be asking for signatures of (chosen) messages (this is the standard security notion for signature schemes). The same argument holds for TLS' client authentication.

The second concern is also invalid as an attacker can't control the messages being signed in neither TLS nor the challenge-response protocol. In TLS, the client signs the complete transcript being exchanged yet, including the client's random and the server's random value, which the attacker can't control both. The same argument holds for this scheme. While the attacker can control $r_B$, he can't control $r_A$ and thereby he would have to hope that the random values repeat in the protocol (extremely unlikely) or that the hash to be signed is the same in TLS, which would imply a collision on the hash function, which is extremely unlikely if the hash function is chosen somewhat decently (like SHA-256).


Adding points on Elliptic Curves How do we add the integer  points $P=(-1, 4)$ and $Q=(2, 5)$ on the elliptic curve of the form $y^2=x^3+17$ ?

It happens that a line usually (not always) cuts three points in a elliptic curve by the Bezout theorem. This is the case for the points and the curve you are asking for.

So the sum of two points are defined like the inverse of the third point intercepted by the line that cut $P$ and $Q$ (let's name it $R$). So we need to find $-R$ because $P+Q=-R$ by definition (the inverse is calculated by multiplying the $y$ component of $R$ by $-1$).

The line equation that cuts $P$ and $Q$ has the form $y=ax+b$. So let's calculate $a$ (the slope) with:

$
a=\frac{5-4}{2+1}=\frac{1}{3}
$

To calculate b, we use the fact that we know the $x$ and $y$ values for $p(-1,4)$:

$
4=a*-1+b
$

Solving this equation we get $b=\frac{13}{3}$.
So, the equation line that cuts $P$ and $Q$ is $y=\frac{1}{3}x+\frac{13}{3}$.

The third point can be obtained by solving the next equation system (formed by the equations of the line and the curve):

$y=\frac{1}{3}x+\frac{13}{3}$

$y^2=x^3+17$

This system has three solutions (as expected):

$x=-1, y=4$ (this is the point $P(-1,4)$)

$x=2, y=5$ (this is the point $Q(2,5)$)

$x=-\frac{8}{9}, y=\frac{109}{27}$ (the point $R$)

So the sum of $P$ and $Q$ is $-R$, this is:

$P+Q=-R=(-\frac{8}{9}, -\frac{109}{27})$


SNFS: Quantifying the "small" parameters? The special number field sieve (SNFS) is an algorithm to calculate discrete logarithms and to factor numbers, given that the target has a special structure.

Now, all ressources always say something like

  The special number field sieve is efficient for integers of the form
  $r^e \pm s$, where $r$ and $s$ are small

So my question is:
How can "small" be quantified in this context?

Is an integer small if it is small than $2^{10}$ or rather $2^{40}$? Is there even a hard boundary or a heuristic boundary? Is there a way to estimate the (asymptotic) running-time which also uses these "small" values?

We summarize the discussion of parameters to express numbers suitable to be factored::

$$ N = C_1 r^t + C_2 s^u $$

by the Special Number Field Sieve (SNFS) from the paper "An Implementation of the Number Field Sieve" by Marije Elkenbracht-Huizing (1996).

She describes the Number Field Sieve this way:

  Let $n$ be the odd number to be factored.  It is easy to check whether $n$ is a prime number or a prime power ,and we assume that it is neither. Like [Multiple Polynomial Quadratic Sieve], the NFS tries to find a solution of the equation $v^2=w^2 \bmod{n}.$ For at least half of the pairs $(v \bmod n, w \bmod n)$ with $v^2\neq w^2 \bmod n$ and $v$ and $w$ relatively prime to $n$, the greatest common divisor of $n$ and $v-w$
  gives a nontrivial factor of $n$.

  To construct $v$ and $w$ we first choose two polynomials $$ f_1(x) = c_{1,d_1}x^{d_1} + c_{1,d_1-1}x^{d_1-1} + \ldots + c_{1,0} $$ $$ f_2(x) = c_{2,d_2}x^{d_2} + c_{2,d_2-1}x^{d_2-1} + \ldots + c_{2,0} $$ over $\mathbb{Z}$, with $f_1 \neq \pm f_2$, both irreducible over $\mathbb{Z}$ and having content $\text{cont }f_i := \gcd(c_{i,d_i},\ldots,c_{i,0})$ equal to $1$; we also choose an integer $m$ that is a common root modulo $n$ of $f_1$ and $f_2$.  In our implementation this is the only step in which the SNFS and the GNFS differ: in the SNFS we use the special form of $n$ to pick these polynomials by hand.  One
  polynomial will have very small coefficients compared to the coefficients of the polynomials we will use with the GNFS, where we search for a pair of polynomials with help of the computer.  This makes SNFS faster than GNFS.

Tying what makes "SNFS faster than GNFS" to a manual process of picking a pair of (integer) polynomials (so that "one polynomial will have very small coefficients" compared to the polynomials "where we search... with help of the computer") makes the distinction contingent on the (advancing) state of the art in computer search for polynomials.  Potentially the algorithms for polynomial selection will improve so far as to practically erase the distinction.

Analysis of what effect small coefficients have on the algorithm (in particular on the speed of the sieving phase) is beyond the limits of the present post.  However useful perspective comes from examining the cases set out by Elkenbracht-Huizing's paper.  Here are simplified tables of various factoring successes listed there:

Table 1: SNFS Example Polynomials and Timings
$$ \begin{array}{|l|c|c|c|}
\hline
n \text{ factor of } N & f_1(x) & f_2(x) &
\begin{array}{c} \text{sieve} \\ \text{hours} \end{array}
\\
\hline
\begin{array}{c} \text{C98 from } \\ 7^{128} + 6^{128} \end{array} &
x^4 + 1 & 6^{32}x - 7^{32} & 450
\\
\hline
\begin{array}{c} \text{C106 from } \\ 2^{543} + 1
\end{array} &
\begin{array}{c} 4x^4 \\+2x^2 + 1 \end{array} & x - 2^{90} & 250
\\
\hline
\begin{array}{c} \text{C119 from } \\ 3^{319} - 1
\end{array} &
\begin{array}{c} x^5 + x^4 \\ - 4x^3 -3x^2 \\+3x + 1\end{array} &
\begin{array}{c} 3^{29}x \\- (3^{58} +1) \end{array} & 800
\\
\hline
\begin{array}{c} \text{C123 from } \\ 2^{511} - 1 \end{array} &
\begin{array}{c} x^6 -10x^4 \\+24x^2 -8\end{array} &
\begin{array}{c} 2^{36}x \\- (2^{73} +1) \end{array} & 700
\\
\hline
\begin{array}{c} \text{C135 from } \\ 73^{73} - 1 \end{array} & x^5 + 73^2 & x - 73^{15} & 2150
\\
\hline
\begin{array}{c} \text{C165 from } \\ 12^{151} -1 \end{array} & 12x^5 - 1 & x - 12^{30} & \lt 1680
\\
\hline
\end{array} $$

Table 2: GNFS Example Polynomials and Timings
$$ \begin{array}{|l|c|c|c|}
\hline
n \text{ factor of } N & f_1(x) & f_2(x) &
\begin{array}{c} \text{sieve} \\ \text{hours} \end{array}
\\
\hline
\begin{array}{c} \text{C87 from } \\ 72^{99} + 1 \end{array} &
\begin{array}{c} 1.5E20x^2 \\ - 1.4E21x \\- 8.3E21 \end{array} & \begin{array}{c} 1.0E21x^2 \\ + 7.0E21x  \\- 7.4E22\end{array} & 2100
\\
\hline
\begin{array}{c} \text{C87 from } \\ 72^{99} + 1 \end{array} &
\begin{array}{c} 7.3E8x^2 \\ + 2.0E20x \\- 7.8E33\end{array} & \begin{array}{c} 2.2E9x^2 \\ - 7.9E21x  \\- 2.3E34\end{array} & 1500
\\
\hline
\begin{array}{c} \text{C97 from } \\ 12^{441} + 1 \end{array} &
\begin{array}{c} -3.0E10x^2 \\+ 4.4E23x \\+ 3.6E36 \end{array} &
\begin{array}{c} -5.4E11x^2 \\ - 4.8E24x  \\+ 6.3E37 \end{array} & 3500
\\
\hline
\begin{array}{c} \text{C105 from } \\ 3^{367} - 1 \end{array} &
\begin{array}{c} 3.4E11x^2 \\ + 8.7E25x \\+ 5.4E38\end{array} &
\begin{array}{c} 1.2E12x^2 \\ - 9.1E26x  \\+ 1.3E41 \end{array} & \lt 7680
\\
\hline
\begin{array}{c} \text{C106 from } \\ 12^{157} + 1 \end{array} &
\begin{array}{c} 1.9E11x^2 \\ - 1.0E26x \\- 3.2E40\end{array} &
\begin{array}{c} -7.9E11x^2 \\ - 4.0E26x  \\+ 1.6E41 \end{array} & 11900
\\
\hline
\begin{array}{c} \text{C107 from } \\ 6^{223} + 1 \end{array} &
\begin{array}{c} -5.4E11x^2 \\ - 4.3E26x \\- 4.7E40\end{array} &
\begin{array}{c} -2.4E11x^2 \\ + 7.6E26x  \\- 3.1E41 \end{array} & 11200
\\
\hline
\end{array} $$

I'll append some additional remarks, but the first columns describe the number of digits of a composite factor of an expression, the second and third columns give the pair of polynomials used (in "scientific notation" for the large integer coefficients of the GNFS; see paper for exact values), and the last column gives a rough timing for the sieving (of relations) step.


Is SSL broken? If so, what can I do about it? But recently, with the scandals about the (in)filtrations, I read that the NSA (and of course others, but I'm not particularly worried about NSA) is able to break SSL and track your data.

It is true? What can I do about that, given I do not know much about cryptography?

I don't think NSA can break the underlying encryption primitives. What they may do is record the whole SSL traffic and decrypt the whole traffic using server private key.
So you can use introduce perfect forward security as the blog article “SSL/TLS & Perfect Forward Secrecy” suggests.
In addition man in the middle can be performed with fake certificates. This is relatively easy and not only NSA, but also a hacker can do this. So if you consider other parties except NSA you should look in to this.


ElGamal and Schnorr groups As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime $p$ and use a multiplicative cyclic group with modulus $p$ and order $q = (p-1)/2$. However, generating safe primes of a large length can be quite time-consuming. Would it be safe to use a Schnorr group as an alternative?

If there is no safe way, what minimum size can I use for a safe prime so that it would be both secure and not terribly long to choose?

Note the obvious: for Elgamal signature generation you must share parameters between users. If I (re-)read Elgamal encryption then it seems to me that parameter $p$ or $q$ (the safe prime) need to be shared in advance as well. Even though the generation of safe primes may be time consuming, you don't need to do this for each signature generation or decryption - the parameters may be static.

As for the key size, the key size of the prime must be about as large as those for RSA and DH keys. This is because the security is related to the hardness of the Diffie-Hellman problem. This means that you may look up the sizes on sites like keylength.com and look for the sizes required for "Discrete Logarithm" or the sources, for instance of NIST (US) or ECRYPT II (Europe), it references.

So there is no need to use primes that have additional properties over those required for Elgamal signature generation or encryption. Any generation of large primes will take large amounts of time compared to encryption/decryption. If you want efficiency then you can share (named) parameters.


Understanding elliptic curve encryption I'm having a hard time understanding the elliptic curve encryption. One thing thing I don't understand is listing all the points on the curve mod p. Suppose I have the following elliptic curve: $y^2 = x^3 + 2x + 3 \pmod 5$.  To find the list of all the points you run through $0 < x \leq 4$ and solve for $y$.

I know the output is the following:

x = 0 => $y^2 = 3$ => no solution mod 5
x = 1 => $y^2 = 6$ = 1 => y = 1,4 mod 5
x = 2 => $y^2 = 15$ = 0 => y = 0 mod 5
x = 3 => $y^2 = 36$ = 1 => y = 1,4 mod 5
x = 4 => $y^2 = 75$ = 0 => y = 0 mod 5

So the points are: (1,1) (1,4) (2,0) (3,1) (3,4) (4,0) and the point at infinity. But I have no idea what is happening here, for example at x=1 solving $y^2$ becomes 6 (mod 5) is one. But why does it say y = 1 and 4 for x=1?

I'm also having trouble understanding point doubling, I'm using the following algorithm:

compute $m$:

$$m \equiv (3x_1^2)(2y_1) -1 \pmod p$$
for the new x and y:

$$x_3 = m^2 - x_1 - x_2 \pmod p$$
$$y_3 = m(x_1 - x_3) - y_1 \pmod p$$

Though this doesn't seem to work. Can someone give me an example of point doubling for e.g. the following equation $y^2 = x^3 + 2x + 1 \pmod 5$ with point P(1, 3) and compute 2P?

Note: For $y^2 \equiv x^3 + ax + b$, you want $$m\equiv(3x^2+a)*(2y)^{-1}$$ which is a shortcut that only makes sense once you understand how elliptic curves work.

"Why does it say y=1 and 4 for x=1?"

Like you said, plug in & solve: $$y^2 \equiv 1^3 + 2(1) + 3 \equiv 6 \equiv 1\space(mod\space5)$$
Ask yourself "Is there a square such that it is $\equiv 1 \space(mod\space 5)$?"
$$1^2\equiv1 \space \space and\space\space 4^2\equiv16\equiv1\space (mod \space5).$$
This means (1,1) and (1,4) are points on the discrete version (mod 5) of the curve.
If we weren't working (mod 5), plugging in 1 would give us (1,2) and (1,-2), which are points on the continuous version of the elliptic curve.
Below on the left is the continuous version of an arbitrary elliptic curve; on the right is what happens when you start working mod a number.

Example: Find 2P on the curve $E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$ where P = (1,3)

2P = (1,3) + (1,3).  When adding two points on an elliptic curve, there are two cases:
Case 1: The points are not the same: Find the line that includes both of the points on the curve.  This line will have a third point on the curve.  Find that point and reflect about the x-axis to have the final point.
Case 2: The points are the same: Find the line tangent to our point on the curve.  This line will intersect the curve at one more point.  Find that point and reflect about the x-axis to have the final point.
Now what is the line tangent to (1,3) on E?
Use implicit differentiation (simple calculus):
$$dy/dx = (3x^2 + 2)/(2y)$$.
Now at our point (1,3): $$dy/dx = 5/6 = 5*6^{-1} (mod \space5)$$
It is easy to see (and find) that $6^{-1} \equiv 1 \space(mod\space 5)$
So m = 5 is the slope for our line tangent to (1,3): $$L: y-3 = 5(x - 1)$$
So $$y = 5x - 2.$$
Now where else do E and L intersect?
We have

$E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$

$L: y = 5x - 2$

Plug L into E: $$(5x-2)^2 \equiv x^3 + 2x + 3$$
Expand: $$25x^2 - 20x + 4 \equiv x^3 + 2x + 3$$
There is a useful algebraic property for cubic polynomials that is fun and not hard to prove:  The summation of the polynomial's roots equal the negative of the $x^2$ term's coefficient.  That is,
$$\sum roots = -(coeff.\space of\space x^2\space term)$$
So in rearranging the polynomial further, we care only about the $x^2$ terms:
$$0 \equiv x^3 - 25x^2 ...$$
We already added (1,3) to itself, so it must be that 1 is a root of multiplicity 2.
$$1 + 1 + r_3 = -(-25) = 25$$ implies the last root is 23.  Recall we are working (mod 5) though, so our last root is 23 $\equiv 3$
Now plug $r_3$ into our linear equation: $$y = 5(3) - 2 = 13 \equiv 3\space(mod\space5)$$
Reflect
Lastly, reflect our point (3,3) about the x-axis to get (3,-3).  Recall again we're working (mod 5), so add the modulus to -3 until is it in the range $[0,4]$.
$\therefore$ 2P = (3,2)


How does GPG verify succesful decryption? How does GPG (or other programs using the OpenPGP file format) verify that it has succeeded with decryption (for symmetrically encrypted data)?

Is something appended to the clear text so there exist some expected data?

For example, I'm using these command lines:

gpg -c test.txt
gpg -d test.txt.gpg

The second command outputs

gpg: decryption failed: bad key

when a wrong key is entered.

How can the program know that it is a bad key? Why doesn't it simply return the random data generated by decrypting with a wrong key?

First I thought that maybe it used letter density to determine if it was plaintext, but then it manages to decrypt binary files too (and complain about wrong keys), and specially key files which should be completely random.

This is hidden well in RFC 4880, the OpenPGP message format specification.

Section 5.7 explains how message data is encrypted. (I'm using the values for a 16-byte block cipher like AES.)

A random block of data is created: $p_{1} \dots p_{16}$
The last two bytes of this block are repeated: $(p_{17}, p_{18}) := (p_{15}, p_{16})$.

These 18 bytes (in case of AES or another similar block cipher) are encrypted in CFB mode (with a zero initialization vector), i.e. $(c_{1} \dots c_{16}) = E_K(0, \dots 0) \oplus (p_{1} \dots p_{16})$, and $(c_{17}, c_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (p_{17}, p_{18})$.

When decrypting, we just have to decrypt these 18 bytes $c_1 \dots c_{18}$ (i.e. we calculate $p_1 \dots p_{16} = E_K(0) \oplus (c_{1} \dots c_{16})$, $(p_{17}, p_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (c_{17}, c_{18})$) and check $p_{15} = p_{17}$ and $p_{16} = p_{18}$. If these are not the same, we throw the "bad key" error message.

Of course, this is only a heuristic check: One in each $2^{16}$ keys will still look right.

If you need a more certain check of the right key, use either a digital signature (in the encrypted package), or use a "Symmetrically Encrypted Integrity Protected Data Packet" (section 5.13) instead of a plain encrypted packet.


Why require that public and private key each have length at least the security parameter? In Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3rd edition), the key generator of e.g. signature has

The key-generation algorithm $\mathsf{Gen}$ takes as input a security parameter $1^n$ and outputs a pair of keys $(\mathrm{pk},\mathrm{sk})$. These are called the public key and the private key, respectively. We assume that $\mathrm{pk}$ and $\mathrm{sk}$ each has length at least $n$, and that $n$ can be determined from $\mathrm{pk}$ or $\mathrm{sk}$.

I see why the minimum size of $\mathrm{pk}$ and $\mathrm{sk}$ must grow with $n$ (with some minimum rate) in order to meet any sound security definition, but not why that's made a requirement.

You're probably familiar with the convention of giving input $1^n$ to an algorithm as a way to indicate "this algorithm is allowed to run in polynomial time in $n$." Suppose you are writing about an encryption scheme and want to be very precise about this. You would write:

$\textsf{KeyGen}(1^n) \to (sk,pk)$
$\textsf{Enc}(1^n, pk, m) \to c$
$\textsf{Dec}(1^n, sk, c) \to m$

Now suppose you know (or insist) that $|pk| \ge n$ and $|sk| \ge n$, and that $n$ can be efficiently computed by looking at $pk$, $sk$.
Then $1^n$ can be omitted as input from $\textsf{Enc}$ and $\textsf{Dec}$ without loss of generality: these algorithms have enough information and running-time budget to efficiently reconstruct the string $1^n$ if needed.
In short, this requirement simplifies the notation without sacrificing any rigor.
It would have also worked to insist that $|sk|, |pk|$ are $\Omega(n^c)$, so that any polynomial function of $|sk|$ is also a polynomial function of $n$.
Basically, $|sk|, |pk|$ can't be exponentially smaller than $n$.
(The fact that $\textsf{KeyGen}$ is a polynomial time algorithm already means that $|sk|,|pk|$ can't be exponentially larger than $n$.)


Using a KDF (PBKDF2) properly I am new to crypto.

I have a password for my user, e.g. &&38:while:HAVE:havana:60&&
I want to encrypt several documents with 10 pages each with AES.

Now when do I run my salt, KDF and init vector functions?

As often as possible, e.g. for every page? (This is what I do now, but it gets too slow. I store salt and initialization vector with the encrypted page.).

Or KDF once at login (so I use the same derived key for all encrypted documents) and a different salt and initialization vector for every page?

PBKDF2 is deliberately slow (and gets slower and safer with more iterations, so you want to make it as slow as you practically can).  Because of this, you should generally avoid running it more times than you absolutely need to.

Using the same key and a different IV for each encrypted document is indeed OK — that's what the IV exists for.  Most encryption schemes do have limitations on how much data and/or how many distinct messages you can safely encrypt with a single key, and you should check the documentation for the scheme you're using to make sure you're not at risk of exceeding these limits.  But usually they're fairly generous, and if you limit yourself to, say, $2^{32}$ distinct documents per key, of up to $2^{32}$ cipher blocks each, you're probably fine.  (In fact, you might need to worry more about message length limits than about message count limits, depending on which encryption mode you're using, especially if some of the documents you're encrypting might be larger than 64 GB.)

Alternatively, if you'd prefer to use a distinct key for each document, you can achieve that efficiently in (at least) two ways.  One is to first derive a single master key from the password using PBKDF2 (with a high iteration count), and then derive the document keys from the master key using a faster KDF such as HKDF-Expand, with a distinct salt/info value for each document.  The other method is to generate a random key for each document, encrypt that key using the master key (derived from the password using PBKDF2, as in the first method), and store it alongside the encrypted document.

Ps. Your question seemed familiar to me, so I checked to see if I might have answered something similar here before.  While I didn't find any exact duplicates of your question, I did locate a couple of related questions that you might find useful, such as these:

Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it?
Suggestions for improving encrypt-then-mac flow
What is the correct way to implement PBKDF2 + AES CBC + HMAC?


Pseudorandom function library I'm wondering if there is any library supporting pseudo-random function, so I can specify the key length and output domain.

Is it correct that I need to use a block cipher for this purpose?

Any help with this would be much appreciated.

Quite a few message authentication codes are actually PRFs with arbitrary input domains.  For example:

HMAC, instantiated with a hash function satisfying the appropriate security properties (basically, for Merkle–Damgård hash functions like the SHA-2 family, that the internal compression function is itself a PRF), is provably a PRF.
CMAC, instantiated with a secure block cipher (i.e. a PRP), is provably a PRF.

In both cases, the security proofs are conditional on certain assumptions about the underlying primitives (hash function / block cipher) that cannot themselves be proven (at least not for any practical crypto primitives currently in use) without further assumptions.  Thus, the best we can do is choose a standard and well studied hash or cipher, like SHA-2 or AES, and hope that the fact that they've been studied by many skilled cryptanalysts, without any published successful attacks, is proof enough that they cannot be broken with current state of the art.

In general, these PRFs take an arbitrary string as an input, but produce a fixed-length bitstring as their output.  If a longer output is desired, one simple way to extend it is to re-run the PRF on the same input, but with a different (ideally, independent) key.  (There are other, potentially more efficient ways to extend the output length, but they require more involved security proofs; see e.g. Maurer & Sjödin (2007).)

As for the key length, this depends on the scheme in question; for example, the CMAC key size depends on the block cipher used, while HMAC technically accepts keys of any length, but keys longer than one hash input block are processed by hashing them first (which implies that the effective maximum key size, measured as resistance to brute force attacks, is limited by the hash block size).

Thus, the arbitrary key length of HMAC should be regarded as a convenience; it does not imply arbitrarily high cryptographic strength, but it does mean that, if you happen to have a long but low-entropy key, like a user-entered passphrase, you can feed it to HMAC without having to reduce it to a fixed length first.  This is a convenient feature for key-derivation functions, many of which are based on (or commonly instantiated with) HMAC.

(As for increasing the key length in the hopes of increasing cryptographic strength, it's worth noting that a brute-force attack on a 256-bit key is far beyond any existing or conceivable computational power, even if quantum computing turns out to be practical.  Thus, for all practical purposes, 256 key bits is more than long enough.  Also, if you still, for some reason, want higher brute force attack resistance, you'll need to pay close attention to the actual security bounds claimed for the primitives you're using, and the tightness of the security proofs, since even attacks usually seen as being only of theoretical relevance may become practical for hypothetical attackers wielding such implausibly high levels of computing power.)


Is there a secure multi-party computation (SMPC) scheme that doesn't use secret sharing? According to the Wikipedia article about SMPC:

  Secure MPC is closely related and builds on to the problem of secret
  sharing, and more specifically verifiable secret sharing (VSS), which
  many secure MPC protocols use against active adversaries.

So, is there an SMPC scheme that doesn't use secret sharing? Are any in popular use?

Context: I'm not familiar with the literature on SMPC, and I've only studied it as an extension of secret sharing.

Secret sharing captures a really wide set of techniques, and "not using secret sharing" is a bit ill-defined. Let me take an example: the seminal solution for two-party computation uses Yao's garbled circuits. It works as follows (very roughly):

The sender garbles the circuit of the target function, which gives the following guarantees: given an appropriate key for each bit of the input and the garbled circuit, the receiver can evaluate the full circuit without seeing anything but the end result.

The sender sends the key for each of his input bits, and the receiver uses oblivious transfer to retrieve the key for each of her own input bits, without revealing these input bits. Then, she evaluates the garbled circuit and sends the result back.

Unlike, say, GMW and it's variant, the above is not formulated in terms of secret sharing. However, it's easy to find "secret shares" hidden beneath the surface: for each gate of the circuit, the sender will hold two keys $(K_0, K_1)$, while the receiver will hold the key $K_b$, where $b$ is the result of the gate evaluation. In a sense, $(K_0, K_1)$ and $K_b$ form shares of the secret value $b$: each of them individually leaks no information about $b$, yet knowing both allows to recover $b$. In fact, they even "almost" form additive shares of $b$, since $K_b = b\cdot K_1 + (1-b)\cdot K_0 = b\cdot (K_0-K_1) + K_0$, hence $K_0$ and $K_b$ form additive shares of $b\cdot (K_0-K_1)$, where $(K_0-K_1)$ is a value known to the sender.

So, this was just to say that the notion of secret sharing is so fundamental that it does not make much sense to "not use secret sharing" whatsoever. However, if you're interested into protocols which do not directly build upon known secret sharing schemes, there are many:

Yao's garbled circuits, and all its modern improvements, are perhaps the most natural examples.
MPC protocols based on homomorphic encryption - some protocols from the 2000's used additive encryption, there are also many protocols relying on fully homomorphic encryption.
Some more theoretical MPC schemes achieving various "high end" properties do not inherently build upon secret sharing, like those based on indistinguishability obfuscation.

The reason why you see secret-sharing based techniques being used a lot out there is simple: the more you can rely on secret sharing, or other information-theoretic techniques, the more efficient your protocol will be in practice. Encryption, oblivious transfer, or any other public-key cryptographic primitive are expensive, since they use very heavy algebraic operations, or involve very large key size. On the other hand, secret sharing is as simple and efficient as it can get: a few XORs, perhaps some interpolation.

And the reason why we still hear a lot about garbled-circuit-based MPC, even though secret-sharing-based MPC is more computationally efficient, is because the former allow for secure computation with a constant number of rounds, while protocols built from secret sharing techniques will most of the time involve a much larger number of rounds. And in practice, if you're executing your protocol over the internet, the number of rounds matters a lot.

(actually, some of the latest state of the art MPC protocols get the best of both worlds by combining the two approaches)


What happens to the entropy of a password when you hash it? For example, if the entropy of a password is 30 bits, what is the entropy of the password when you hash it with MD5?

Still 30 bits.

A hash function does not add entropy. It could change the entropy rate though. For example if you had 30 bits of entropy in a 64 bit password and hashed it to a 128 bit digest, the rate has gone down ($\frac{30}{64}\approx 0.47$, but $\frac{30}{128}\approx 0.23$). On the other hand, if the password is 500 bits, the entropy rate goes up.

One way to see this would be to look at all the possible values that the password could be. That would be $2^{30}$ since any other character (or bits) are assumed to be known to the attacker (otherwise they would add entropy, right?). Those $2^{30}$ values would be fed into the hash function and result in $2^{30}$ different digests. So there are the same number of passwords as digests. No added entropy.


RSA factorization knowing N, e=65537 and g=d*(p-17) Having known the values for $N$ a large number, $e = 65537$ and another large number $g = d \cdot (p-17)$, how can I use that info to find out $p$ and $q$?

I guess that have something to do with Fermat's little theorem and I noticed that $e$ is the largest prime number of the form $2^k+1$. Can you give me some hint? I am not very familiar with some other theorems that may help.

Fermat's little theorem is useful indeed.

For instance, for almost any integer $m$, you have that $m^{P-1}=1 \mod{P}$.
Since then, you know that $A=m^{P-1}-1$ is a multiple of $P$. With that value, you can therefore compute $gcd(A,N)$ which should provide $P$ (knowing that $N=P \times Q$).

With the provided values, you may be able to build that special $A$. For instance, $(m^e)^g \mod{N}=m^{e \times g} \mod{N} = m^{P-17} \mod{N}$.

So $(m^e)^g \times m^{16} = m^{P-1} \mod{N}$ ! To conclude, you can finally compute the gcd between $N$ and $(m^e)^g \times m^{16}-1$.

As an example with small integers, let us define $P=11$, $Q=17$, $N=P \times Q = 187$, $\Phi(N)=(P-1) \times (Q-1) = 10 \times 16 = 160$, $e=3$, $d=107$, $g=d \times (P-17) = 158$ and $m=2$.

One gets $(m^e)^g \mod{N} = 38$ and thus $(m^e)^g \times m^{16} = 89$.
One finds $P$ by computing $gcd(89-1,187)=11=P$ ;-)


Are there any existing ASN.1 structures for transferring symmetric keys? Is there any reasonable ASN.1 standard to encode symmetric keys?

I found PSKC, but it seems extremely heavy, and I can't quite find any library (e.g. bouncycastle) that would simplify using it.

If all I need is to encode a symmetric key, would it be sufficient to just include:

algorithm ID
block size
key size
key bits

For the algorithm you should use the AlgorithmIdentifier type of RFC5280. Block size and key size can be derived from the algorithm id and the key itself, so there is no need to store them.

So, if you want something really lightweight, just store that into a sequence:

SymmetricKey ::= SEQUENCE {
  algorithm AlgorithIdentifier,
  key       BIT STRING
}


Is it hard to find a big random easy to factor number? Suppose that I give you the challenge of successfully factoring any very big random number. That is, you pick a big random number (say, 65536 bits) and try to factor it. If you manage to, you win. If you don't, you can keep trying, or pick another random number, until you factor any big number. How hard is to win this challenge?

To put it in another way, suppose that I offer you a lot of money if you give me a tuple (nonce, rnd, factors), where nonce is any number selected by you, rnd is the 65536-bit variable length SHA3 output of the nonce, and factors is the list of prime factors of rnd. Will you be able to take my money?

Yes, this is feasible. Just generate sufficiently many nonce, rnd values, and you will eventually stumble upon a prime (or a number that can be factored into a large prime and a number of small prime factors). This is how most probabilistic prime generators operate.