Can DNA computing to solve elliptic curve algorithms using this method The authors of this paper: Fast Parallel Molecular Algorithms for DNA-Based Computation: Solving the Elliptic Curve Discrete Logarithm Problem over $GF(2^n)$ proposed a novel algorithm based on DNA computing which they claim (in theory, at least) can solve elliptic curve algorithms in polynomial time.

An excerpt from the article:

  "We have constructed the algorithm above for parallel computing the point of the sum of two points. Then, we can solve the elliptic curve discrete logarithm problem as follows: consider point P and Q are given, and l is what we want to get which matches Q = lP. First, we amplify P into two tubes and add P in one tube. Check if 2P equals to Q; if not, note down the value of 2P and pour two tubes together. Then, amplify the tube into two tubes and add 2P in one tube. Check if any point equals to Q; if not, note down the value of 4P and pour two tubes together, or we get the value of l. Then, amplify the tube into two tubes and add 4P in one tube,…, while this loop executes n times, the value from 1 to 2n for l will have been checked, and the elliptic curve cryptosystem has been broken by the solved elliptic curve discrete logarithm problem."

I'm just starting to learn cryptography as a hobby, so I'm not too familiar with it yet. Can someone explain their strategy to me in simpler terms? Is their strategy practical in real life? The authors claim they can solve elliptic curve algorithms "in polynomial time" but I'm not so sure......

TL:DR; The algorithm is working in parallel, however not practical due to the number of DNA strands requirements for safe-curves. Generic Discrete logarithm algorithms can easily beat this, [see here].

The algorithm

The algorithms work in theory. The authors use $Q =lP$ let change it $Q = [x]P$.

Their method, actually, is highly parallelized like any DNA algorithms. DNA algorithms are actually very good at parallelization.

Let call their algorithm amplify-and-double-and-add;

t1 = P / here t is tube

while x not found:
   t1.amplify()
   t2.amplifyWith(t1)
   t1.add(t1)
   if t1 contains Q
     return matched value
   t1 = pour(t1,t2)

As one can see, the algorithm actually calculates the intermediate values, too. The while loop requires $\lfloor(\log x)\rfloor +1 \in \mathcal{O}(\log n)$-steps. The addition is performed by the AddTwoNode algorithm that requires $O(n^3)$ extract operations, $O(n^3)$ append operations, $O(n^3)$ merge operations, and $O(n)$ test tubes for parallel adder for elliptic curve.

The $n$ is the extension number of the Binary Galois Field $GF(2^n)$  under consideration. Therefore for a curve like Edwards25519 we have $n=255$

$\approx 2^{24}$ extract operations
$\approx 2^{24}$ append operations
$\approx 2^{24}$ merge operations
$\approx 2^8 $ test tubes.

The private random key $x$ is also around 255-bit $\approx 2^{8}$. Then in total the amplify-and-double-and-add requires;

$\approx 2^{32}$ extract operations
$\approx 2^{32}$ append operations
$\approx 2^{32}$ merge operations
$\approx 2^{16} $ test tubes (?).

The notes from the conclusion of the article

  so it is feasible in theory and inspirits the development of DNA computing. This indicates that the elliptic curve cryptosystems are perhaps insecure if the technique of DNA computing is skillful enough to run the algorithms efficiently as discussed in this paper.

Considerations

DNA computing is started with Adleman's novel work, or see here. The Adleman almost has written all the steps clearly since they performed a real experiment. In this article, there is no experiment or any calculations about it. I've looked for but couldn't find one, either.

This work is clearly a theoretical work and doesn't calculate anything about the timings or amounts of DNA computing. For example;

For example, a PCR can take around 1 hour, and it's not clear how many iterations are required by the algorithm?
How scales this algorithm is not clear. Now in practice, a test tube can contain $2^{18}$ DNA strands
The number of required DNA strands is not explained/calculated. What is the last tube's requirement for the final step? We can simply say that, if it was good it was in the paper.
how much their algorithm is requiring for a curve like edwars25519 is not calculated.
The timing of test tube operations - Extract, Merge, Amplify, Append, and Append-head- are not given.
Written in 2008 and has only 18 citations according to Google Scholar. That is too low for real groundbreaking work.
The timings of their 7 algorithms are not given at least the current stage of the technology when the article was written. Adleman spent 7 days in the lab for a graph with 7 cities and took 54 seconds.

The required number of DNA strands

Let call $\text{D-SPACE}$ for the required DNA strands for the running of any algorithm. The amplify-and-double-and-add algorithms in any step calculates values between $[2^k,2^{k-1}]$, while $1<k\leq x$.

Let forget about the intermedia steps and concentrate on the last step. We need around $2^{555}\text{-D-SPACE}$ so that all values can appear in the tube to be matched with $x$. This amount is too bighugehumongous even a little less than than the number of particles in the universe; and that is $3.28 \times 10^{80} \approx 2^{266}$.

The Conclusion

Not practical due to the $2^{555}\text{-D-SPACE}$ for a curve Edwards25519 or even 128-bit curves.


Do Korea and Japan have their own national hashing standard? I know China has SM3 and SM4 commercial cryptographic hash and block cipher standards, and I know Japan has Camellia block cipher and Korea has SEED. Do Japan and Korea have an industry standard for hashing? Are they available online (either paid or free)?

Korea has its own standard for hash and block cipher, such as LSH (for hash) and ARIA (for block cipher). Source code can be found in here. I cannot find the English page, but google translator seems to work well. You can find information about standardization and other documents on the website, e.g. here.
The above-linked site KISA is itself authoritative and a public institute. If you want a much formal standard document, you could find them from TTA or KSA. The standard is as follows.

LSH hash: KS X 3262 KS Link, previously TTAK.KO-12.0276 (expired)
LEA encryption: TTAK.KO-12.0223 TTA Link but the document is mostly in Korean. Source code is available here but its manual is also in Korean.
ARIA encryption: KS X 1213-1 KS Link

The documents on KS site are not free, and they are also written in Korean.


Number of possible access structure with $n$ person I want to count number of possible access structures in closed form(if possible) as a variable of $n$,the number of share holder. I have tried in several ways. Still no good progress. It is very hard to consider all cases and count it and I think there will be work by others on approximating the number. Is there any approximation of that count so that I can get some idea ?

All possible access contains $(k,n)$ - Secret sharing scheme( general access structures). Can anyone give any idea how to proceed?

Example:  In General access structure, we will call the set of collection of all people who can get the secret by $\Gamma_{qual}$ . Consider a case of $n=5$ , we have to consider the case like $$\Gamma_{qual}= \{\{1,2\},\{2,4\},\{1,3,5\}\}$$ but we can't have an access structure where a shareholder is not present, means we always need $$ \cup_{X\in \Gamma_{qual}}X = \{1,2,\cdots,n\}$$

An access structure is just a function $f:\{0,1\} ^n\to \{0,1\}$. It takes a subset of $\{1,\ldots,n\}$ as input (represented as it's characteristic vector) and returns 1 if authorized and 0 if unauthorized. Additionally, the function must be monotone, meaning that $A\subseteq B \implies f(A) \le f(B)$.

The number of monotone Boolean functions over $n$ variables is given by the Dedekind numbers (OEIS). It is a nontrivial formula!

Edit: You are interested in $f$ which are sensitive to all $n$ inputs. Let's call $f$ insensitive to input $i$ if there is a function $g$ (defined on subsets of $\{1,\ldots, i-1,i+1,\ldots,n\}$) such that $f(A) = g(A \setminus \{i\})$ for all $A$. If this is not the case then we say that $f$ is sensitive to $i$. Now say that $f$ is $k$-sensitive if it is sensitive to $k$ of its inputs. You can count the number of $n$-sensitive monotone functions using the inclusion-exclusion principle.

The idea is that $M(n)$ ($n$th Dedekind number) includes things you don't care about like $(n-1)$-sensitive functions. There are ${n \choose 1} M(n-1)$ Monotone functions of $n$ variables that are (at most) $(n-1)$-sensitive, so subtract them off. But since $M(n-1)$ also "overcounts" all the $(n-2)$-sensitive functions, you've subtracted them off too much and need to add them back. There are ${n \choose 2} M(n-2)$ of these. Etc etc etc. You finally get the thing you want as $\sum_{i=0}^n (-1)^i {n \choose i}M(n-i)$.


Can someone explain RSA-PSS to me? I can't find any usable resources about it online (at least ones that make sense to me right now), so any links to articles or if you could explain it to me would be greatly appreciated.

What I don't understand is what is PSS? I understand that RSA is an encryption type with two keys (usually public and private), but is PSS a signature (like the name suggests) and if so, how is it different from a hash?

A fixed hash function can be computed by anyone.

A signature depends also on a public key, and can be computed only by someone who knows a secret related to the public key.  Anyone can verify a signature on a message under the public key, but only knowledge of the secret enables creating signatures.  Signatures practically always involve the use of a hash function internally, combining the hash output (and sometimes hash input) with the public key using obscure mathematical spells.

RSA is not itself an encryption algorithm; it is a family of trapdoor permutations, which are obscure mathematical spells not really useful in isolation.  There are encryption schemes and signature schemes both built out of the RSA trapdoor permutation family, such as RSAES-OAEP and RSASSA-PSS.


How should I encrypt filenames in my scenario? I'm writting a tool to save files (to external drive, cloud,...), it can already crypt file content with AES/GCM/NOPADDING; and as I'm not an expert, I've read some documentation, and understand that I have to generate (for each file) a random IV, that I can store directly into the crypted data (prepend). This part is OK (I hope).

But now I want to "obfuscate" the filename. As I want that the resulting string is "secure" (so not use a easy rot13/caesar cipher, that can be hack), I've tried to use the same approach (base64 the crypted byte array). But if I'm doing this, my resulting filename will never be the same! Encrypt "test.jpg" can give "abc", but encrypt again the original string "test.jpg" will give another result like "drsdf"... as the IV is generated randomly each time. And so my backup tool can't compare "filename" to do its checks.

Is there a way to obfuscate in a secure way a string but giving always the same result?

Update

Ok, I continue with my questions / investigations. So I use AES/GCM for content encryption with unique random IV (for each file). As I understand, I can't really use IV for filename encryption (need to save the IV into the crypted filename, which is problematic).

So new question for filename encryption:
What is better to do:

Use AES/GCM (or CBC) with the same IV for all filenames?
Or use ECB mode which does not require IV?

And do I need to use or not use the same secret KEY for file content and file name encryption (as I will use 2 different approachs)?

With a good encryption mechanism, knowing any number of plaintext-ciphertext pairs $\{(P_i,C_i)\}$ should reveal nothing about the plaintext corresponding to some extra ciphertext $C$, other than its length. In particular, given the knowledge that $P_1$ encrypts to $C_1$, an adversary should have no way to know whether some ciphertext $C$ also decrypts to $P_1$. This is a consequence of semantic security.

You may wish to weaken the security of the system to allow recognizing ciphertexts corresponding to a previously processed plaintext. That is, knowing plaintext-ciphertext pairs $\{(P_i,C_i)\}$ reveals no information about some ciphertext $C$ which is not one of the $C_i$.

This has dangerous implications that may not be obvious at first glance. In many cases, an adversary can convince the user to encrypt some plaintext (e.g. arrange for the user to download some files). So an adversary who wanted to decrypt some ciphertext file names could make guesses for the plaintext, arrange for the user to create files with this name, and compare the resulting ciphertext to verify these guesses.

Using non-repeated IVs in encryption algorithms avoids this by causing two plaintexts to never be encrypted to the same ciphertext, even if the plaintexts are equal, because the IVs will differ.

If you don't mind considerably weakening the confidentiality of file names, you can use a deterministic IV. Beware that you can't just use any old IV; for example, with CTR or GCM mode, repeating a counter value reveals the xor of the corresponding plaintext blocks, which leaks a lot of information. One method that is safe, other than enabling the encryption oracle guessing method I described earlier, is to make the IV a cryptographic hash of the file name. If the hash function is independent of the block cipher (which it typically is in practice, e.g. the SHA families are independent of AES) then the hash function can be idealized as a random oracle and so using a hash as the IV is equivalent to using a random IV as long as plaintexts are not repeated.

However, I wonder why you need to be able to recognize identical ciphertexts. Your backup tool has the symmetric key, so it can decipher the name of previously backed-up files. To avoid downloading ciphertexts from the server for local decryption, you would keep a local log of what has already been backed up, but backup programs usually have this anyway in some form.

Regarding your updates:

  Use AES/GCM (or CBC) with the same IV for all filenames?

No. GCM requires a unique IV. Repeating the IV with GCM can not only break the confidentiality and integrity of the message, but can even leak information about the key. See How bad it is using the same IV twice with AES/GCM?

CBC with a repeated IV, in addition to making common prefixes obvious, leaks a little information about the plaintext. It also doesn't guarantee integrity.

  Or use ECB mode which does not require IV?

No. ECB is not a proper encryption mode. It is implemented in some libraries for convenience but does not provide any security.

  I can't really use IV for filename encryption (need to save the IV into the crypted filename, which is problematic)

You generally can't use the encrypted filename as a filename anyway, because the encrypted filename is longer than the original, even without counting the IV. Filesystems have forbidden characters, so you'd need some encoding scheme, which costs you bytes in the filename. Most filesystems have a limited filename length. The only case in which you can map plaintext filenames to encrypted filenames is if the source filesystem's filename length limit is sufficiently smaller than the target filename filesystems's length limit.


Signature scheme against an unbounded rival I've seen this:
Can a computationally unbounded adversary break any public-key encryption scheme?

And I've read the following theorem:

Theorem (Lamport, GMR, Naor-Yung, Rompel, Goldreich)
If one-way functions exist then there are signature schemes which are
existentially unforgeable under chosen plaintext attacks.

I was wondering if this implies, that given an unbounded rival, no signature scheme exists that this rival can't break. This is due to the fact that the rival can inverse the 'OWF'.

Any thoughts? Corrections?

Actually, the conclusion you drew doesn't follow from the theorem; the theorem says "if you have a OWF, then a secure signature scheme exists"; it doesn't say "if you don't have a OWF, then there are no secure signature schemes".  As far as the theorem goes, there might be another way to generate a signature scheme; the proof implied by the theorem doesn't work, but there might be another proof that does.

However, it turns out that your conclusion is indeed correct; if you have an unbounded rival, then with the public key, he can forge the signature for any message he wants.

The proof needn't be fancy; all the unbounded adversary does is consider all possible signatures, check each one against the public key, and selects the one that validates.  This obviously works no matter how the signature algorithm works internally.


Key sizes supported by 3DES I read about 3DES encryption but I don't understand exactly what the specific meaning of key size is. For example I found that 3DES supports 64, 128, 192, and 256 bits key size. What are all the possible key sizes supported by 3DES?
Is there any function to determine if a key is valid for 3DES or not ?

The triple DES (3DES) block cipher works by essentially running the block through DES three times. Triple DES is also known as "DES EDE" (encrypt-decrypt-encrypt) and under the name given by the standard document: "TDEA". The TDEA algorithm is described in FIPS NIST Special Publication 800-67
 Revision 1 where paragraph 3.2 describes the TDEA Keying Options.

In triple DES you take the block and then:

Send it through DES once with a DES key $k_1$
Send the result of that through DES a second time with a DES key $k_2$ (for this second time we generally run DES backwards; in decrypt rather than encrypt mode, however, that's not important for this question)
Send the result of that through DES a third time with DES key $k_3$.

The result of that is the result of the 3DES block operation.

Now, 3DES comes in two main flavors:

The "2 key" version; in this version, the 3DES key consists of two DES keys; $k_1$ and $k_2$, and we implicitly assume that $k_1 = k_3$.  DES keys are typically represented in 64 bits, and so this version of 3DES has 128 bit keys.
The "3 key" version; in this version, the 3DES key consists of three DES keys; $k_1$, $k_2$ and $k_3$.  Because all three 3 DES keys are explicitly represented, this version of 3DES has 192 bit keys.

The keys are sometimes also referred to as key A, B and C. The key for the 2 key version is then referred to as an ABA key and for the 3 key version as ABC key.

Those are the only standard versions of 3DES; you might have an API which allows 64 bit keys (which likely emulates DES in that case); if it allows 256 bit keys, I have no idea what it would do with them.

In case you're wondering whether DES keys are 56 bits or 64 bits, well, they are considered 56 bits of cryptographic strength (because we can run through all possible DES encryption operations by trying $2^{56}$ different values); however when we represent a key, we typically express it as 8 bytes (or 64 bits).  In that case we essentially ignore the least significant bit of each byte (originally, they were "parity bits" for each byte, however since no one manually enters DES keys anymore, most implementations end up ignoring them instead). That's the way the DES designers did things; most everyone follows tradition.

So sometimes the (triple) DES key lengths are referred to as 56 bit, 112 bit or 168 bits instead of 64, 128 or 192 bits respectively. Usually cryptographic API's still require you to enter 8, 16 or 24 bytes despite of this. AES fortunately does away with all this.


Is there a cryptographic protocol that let's me prove someone has a large binary? I'm working on a system that has a P2P component. When an individual downloads a binary and decides to mirror it, they advertise themselves in a providers set. The binaries can range from 1-1000MB. I need a mechanism to prevent the abuse use case where they flood the provider set without ever having the binary, and serving up bad data.

The client trying to prove the blob only has some small metadata about the blob <1MB. They need to ensure that the provider actually has the blob before initiating download.

Alice, Bob, and Malorie

Alice, Bob, and Malorie are trying to share large files. Both Alice and Bob have high bandwidth links to Malorie. There also exists an unencrypted HAM radio link between the three agents, so Malorie can see everything Bob and Alice send to one another.

Sometimes Malorie lies. Everyone knows the SHA1 hash of the file. Bob shares the file with Malorie. How can Alice check if Malorie has the file once Bob goes offline, without transmitting the entire contents of the file from Bob to Alice?

Is there a protocol for this?

Like Thomas suggests in the comments, a Merkle tree would help here. As would a simple hash list.

Calculate the hash tree/list over suitably sized blocks of the file and let the recipient know it. As data comes in it can be verified to match. With file size $n$, block size $b$ and SHA-256 as the hash, a hash list takes about $n/b \cdot 256$ bits. So with up to gigabyte files you would want to use at least 2 MB blocks to keep the metadata below 1 MB.

This is similar to how BitTorrent works.

If you need to verify someone has the file you can request they produce a random block. If they have fraction $p$ of the blocks, they will be able to do it with probability $p$, so if that is a problem you can request $m$ blocks for a probability $p^m$.


RSA with shared modulus multiple primes It was suggested to choose $k$ large Blum primes
($k > 2$), and compute $m = p_1\cdot p_2\cdots p_k$.

The trusted center (TC), who knows the prime factors of $m$,
computes for each user $U$: $(e_U , d_U )$ and sends it to him. Each user publishes $e_U$ and keeps $d_U$.

The question is whether someone apart from the TC can find the factorization of $m$.

One weakness of the scheme is that if the same message $x$ is transmitted to two different users an eavesdropper can obtain $x$ using Bezout's identity, which is also a weakness of the regular RSA in a shared modulus system.

In a 'two primes RSA' system with shared modulus a user can find $p,q$ with very high probability using his public and private key.

But what can be said with $k$ primes? I don't see how to use a similar approach like I used in the two primes case in order to obtain $(p,q)$, nor do I know how to prove the security of it.

The question is whether someone apart from the TC can find the factorization of $m$.

Yes, however I will first address the easier to answer question of "could the holder of private key $a$ decrypt traffic to the holder of private key $b$"

The answer to that is "yes"; Alice, the holder of the private key $a$ has $e_a$, $d_a$, and $e_b$ (Bob's public key).

We know that $e_a d_a \equiv 1 \pmod {\lambda(n)}$ (where $\lambda(n) = \text{lcm}(p_1 - 1, p_2 - 1, ..., p_k-1)$, that is, $e_a d_a - 1 = m\lambda(n)$ for some integer $m$.  So, what Alice can do is compute $d'_b = e_b^{-1} \bmod{ e_a d_a - 1} = e_b^{-1} \bmod{ m\lambda(n)}$; it is easy to see that $e_b d'_b \equiv 1 \pmod{ \lambda(n)}$, that is, $d_b'$ will work as a decryption key for traffic to Bob.  It likely not to be larger than Bob's key $d_b$, however it is not so large that Alice can't practically use it.

However, to address the question "could Alice factor $n$ (even though the above argument shows she doesn't need to)", the answer is "yes"; the same probabilistic method that works against two factor RSA primes also works in this case (it just may take more iterations to complete the factorization).

To review: Alice computes $e_a d_a - 1 = 2^k z$ for $k$ large enough to make $z$ odd.  Then, she selects a random value $g$ and computes:

\begin{align*}
  h_0 &= g^z \bmod n \\
  h_1 &= h_0^2 \bmod n \\
  h_2 &= h_1^2 \bmod n \\
      &\vdots \\
  h_k &= h_{k-1}^2 \bmod n
\end{align*}

It should be clear that, unless the original $g$ just happened to not be relatively prime to $n$, that the final value $h_{k} = 1$; we look at the largest $i$ where $h_i \ne 1$.  If $i > 0$ and $h_i \ne -1 \pmod n$, that gives us a nontrivial factor $\gcd(n, h_i - 1)$.

It can be shown that at least half the possible initial $g$ values will yield a factor, and that this factor is effectively random over the possible factorizations, hence rerunning this test using different $g$ values will quickly reveal all the factors.


Knowing interval of discrete log for elliptic curve Are there any special attacks I can apply if I know the upper bound for $n$ (meaning $0 \le n \le \text{Upper Bound}$) in the equation $Q = nP$, where $P$ is the base point and I'm trying to solve for $n$.

As mentioned in your answer to your other similar question, Pollard's $\lambda$ algorithm is still a good choice. If your search interval is $[a,b]$, then it may find the result in $O(\sqrt{b-a})$ time using very small storage.

That "may" in the previous paragraph illustrates the trade-off you must consider. Baby step, giant step requires more memory, but it is deterministic and thus guaranteed to finish in $O(\sqrt{b-a})$ time. Pollard's $\lambda$ can be parallelized which could speed up the run time (depending on your resources), but as it's probabilistic, the run time is not guaranteed at all.


Is it more weak to encrypt with the private key RSA? I have a simple question.

Is it more weak to encrypt with the private key against the public key with RSA ?

Like is it easier to "crack", "brake", "solve", "decrypt" when I encrypt with the private key against the public key. Is it really the same process of encryption?

(In both cases we assume that the "breaker" doesn't know any of the keys)

Edit:

To be more precise, is there something that differs in the process of encryption with any of these two keys.

Is the only difference between the public and private is that the private can generate public keys but the public key can not generate private? If I want to encrypt with the private or the public key the result is the same, the encryption is passing by the same steps and then results in a difficult breakable encrypted output?

RSA key generated with puttygen
PGP encryption / decryption

the "breaker" doesn't know any of the keys

That goes against the very name of the public key, and rationale for using RSA or any asymmetric cryptography. Let's assume it nevertheless in the first section of this answer.

  Is the only difference between the public and private (keys) that the private can generate public keys but the public key can not generate private?

No.

The two keys typically are not in the same format.
Further, in RSA

The exponent in the public key is customarily small.
The most common formats for private key include the factorization of the modulus, when the public key never does.
Depending on format of the private key and method of generation of the key pair, the private key allows to generate a matching public key, or not. Neither constitute a weakness of RSA.

The public key of any secure asymmetric cryptosystem never allows to generate a matching private key.

  (assume):

  RSA key generated with puttygen
  PGP encryption / decryption

PGP does not give any way to encrypt with a private key, nor decrypt with a public key. Neither does GPG, nor any reasonable OpenPGP implementation. The closest it allows is producing a signature, which leaves the message in clear or removes it. That's totally unsafe or dysfunctional from the perspective of confidential transmission of a message.
Note: When creating or importing a private key, PGP/GPG also generates or import the public key, and that what it uses to encrypt. Correspondingly, the passphrase normally required for private key use is not asked for encryption.

The closest feasible thing matching the question's description would be to swap the public and private key generated by puttygen, before somewhat feeding them to the encryption program. That's not quite trivial, because the two keys are not in the same format. But that's feasible: we change $e$ of the formerly public key to $d$ from the formerly private key, and change $d$, $d_p$ and $d_q$ of the formerly private key to the former $e$, that is $37$ as explained here.

If we do this, the newly made public key will look about normal, except for a large exponent instead of a customary short one ($37$ and $65537$ are common). Encryption will be possible (and measurably slower than usual). Decryption with the newly made private key will be possible (and measurably faster than usual). The question asks if that's less safe than normal encryption is.

Yes, that's less safe in the sense that now an adversary knows the normally secret $d$ in the private key (that's $37$). Thus if somewhat the normally public modulus $N$ gets public, it becomes trivial to decipher. Normally $N$ is in both keys, thus public; and further, encryption programs make no effort to keep $N$ secret: we can't rule out that with some encryption option, $N$ is sent in clear along the plaintext. Or that some attack allows the attacker to know $N$. For a start, PGP and GPG store $N$ in clear in the pubring file, not protected by a passphrase.

If we hypothesize that an attacker only has one ciphertext without $N$, I see no way to obtain $N$ or otherwise decipher or get any useful information about the plaintext.

This perhaps remains true if the attacker has multiple ciphertexts and knows some corresponding plaintexts, assuming hybrid encryption is used (as in OpenPGP). However, with textbook RSA encryption, $N$ can be recovered and security is lost.

[From this point onwards, we again assume the public key is public]

  Is it more weak to encrypt with the private key against the public key with RSA ?

Often that's impractical or/and unsafe (see above); but not necessarily. In fact, RSA as taught and practiced today reverses the public and private key compared to the key generation procedure of original RSA (Ronald L. Rivest, Adi Shamir, and Leonard  Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978). That reversal was originally made for performance reasons, and it turns out that it improves security compared to that in original RSA!

Original RSA has an almost unique characteristic among asymmetric cryptosystems: we indeed can exchange public and private key, and that does not compromise security (including when we reveal the key used for encryption, as designed, see final section). That's because original RSA

first selects the decryption exponent $d$ mostly randomly in a large set, then computes the encryption exponent $e$ from that, per the symmetric equation $e\,d\equiv1\pmod{\phi(N)}$
public and private keys are in the same format: the public modulus $N$ and an exponent.

It quickly became standard practice to first choose the encryption exponent $e$ (that is, reverse public and private key compared to key generation of original RSA): in Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977), Rivest's MIT group used $e=9007$ in a then difficult challenge, implying that $e$ was chosen before $d$. Such small $e$ speeds computations involving that exponent (encryption and signature verification) by a large factor, broadening the practical uses of RSA; but it becomes unsafe to exchange public and private exponents.

It took some time to fully realize that original RSA's prescription "It is important that $d$ should be chosen from a large enough set so that a cryptanalyst cannot find it by direct search" is necessary, but insufficient for security. Selecting a random $d$ in $[2^{135},2^{136}]$ with $\gcd(d,p-1)=1=\gcd(d,q-1)$ blocks direct search of $d$, but would be unsafe for $p$ and $q$ 512-bit or larger primes (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

In original RSA, decrypting is the same as signing, and both are encrypting with public key replaced by private key. However:

Original RSA's enciphering is insecure (among reasons: correct guess of the message can be verified with the public key, thus it is insecure to encipher a name on the class roll, a password, or a credit card number).
Original RSA's signing is insecure (for different reasons, including: an adversary can find signature of a message showing as any short desired text when printed as a C string; a few rightful signatures of some selected meaningful and sizable messages can be turned into forged signatures of other meaningful and sizable messages).

Weaknesses of original RSA have been fixed, but with modern RSA as practiced (or PGP/GPG and RSA keys), signing is markedly different from encrypting with public key replaced by private key. And many other common signature schemes have no encryption counterpart.

While modern RSA practice distinguish signing from encrypting with public key replaced by private key, it's possible to have the two use essentially the same padding. See Jean-Sébastien Coron, Marc Joye, David Naccache, Pascal Paillier, Universal Padding Schemes for RSA, in proceedings of Crypto 2002 (also there). Note: AFAIK it is not used in practice.

Glossary of things properly named:

In public-key cryptography, the public key is made public (the private key is kept secret).
In public-key encryption, encryption is with the public key (decryption is with the private key).
In public-key signature, signature verification is with the public key (signing was with the private key).


SHACAL-2 vs. AES as underlying block cipher for Secure Hash (aka SHA-256) The hashing scheme SHA-256 (for instance) is based on Merkle-Damgård construction with the underlying compression function based on the block cipher SHACAL-2 configured in Davies Meyer mode. SHACAL-2 has 80 rounds, per 512 bit block of data (which is inserted in the key input of the block cipher). As an alternative, one could use AES with 256 bit key (so the hashed data should be divided to 256 bit blocks, inserted as a key) and using Davies Meyer principle in the same way. Seemingly, this would be much more efficient, because AES-256 requires 14 rounds, or total 28 rounds in order to process 512 bit of data, while theSHACAL-2 requires 80 rounds. Is there any standard that does this?

Using AES as a Davies Meyer compression function is a bad idea:

It has a block size of 128 bits, which limits its collision resistance to 64 bits, which is rather weak.
This limitation could be overcome by using Rijndael with a 256 bit block size, but then you'd need to use a higher number of rounds.

AES has been designed to work with randomly chosen keys, not with attacker chosen keys.
AES suffers from related key attacks. While I'm not aware of published a way to exploit this to find collisions, it certainly undermines my confidence is such a construction. You could increase the number of rounds to compensate for this, but that'd decrease performance.
See Are AES-256's related-key weaknesses exploitable if it is used to build a hash?

Block ciphers designed for use in hash functions have very cheap key setups. While AES isn't as expensive as Blowfish, changing the key still has a noticeable performance impact.

Fewer rounds doesn't necessarily mean more efficient:
Comparing the absolute number of rounds of different cryptographic primitives is meaningless. You can design a primitive to have many cheap and simple rounds or fewer more expensive and more complex rounds, resulting in similar performance.
See Why does SHA-1 have 80 rounds?
AES isn't that fast on a CPU without special instructions, like AES-NI, probably even slower than SHA-2 on some CPUs.


What are the problems of IKEv1 aggressive mode (compared to IKEv1 main mode or IKEv2)? I would like to seek confirmation/clarification of the following statements about IKE:

IKEv1 aggressive mode is supposed to be “insecure” if used with PSK. But as far as I can see, correct (or more correct) would be the following

IKEv1 aggressive mode, IKEv1 main mode and IKEv2 are pretty much the same if the attacker knows the PSK and is man-in-the-middle (i.e. he can decipher the entire flow)

this is always possible if the attacker is man-in-the-middle and can authenticate itself as real to both sides

IKEv1 aggressive mode sends the identifier of both sides in clear text, but

the identifier does not carry any real secrets, i.e. the strength of IPsec does not conceptually lie on keeping identifiers secret
an IKE identifier is like a TCP port number: it helps to select the right service/configuration, it has no influence on integrity of the authentication
IKEv1 aggressive mode always sends those IDs in clear text, independent of the fact that PSK or pubkey is used for authentication

IKEv1 aggressive mode, IKEv1 main mode and IKEv2 are equally good if the attacker is man-in-the-middle (but doesn’t know the PSK)

he can not successfully authenticate → he can’t decipher the flow
but he can see the identifiers
and he does see “the hash”, in which the only unknown component is the PSK

he can do an offline (dictionary) attack on the PSK now

only IKEv1 aggressive mode reveals “the hash” to passive attackers (i.e. eavesdroppers)

→ possible offline (dictionary) attacks

As far as I understood the problem, the difference between IKEv1 Aggressive and Main Mode is how the hashed PSK is sent.

Of course, the PSK itself is never sent to the other side as both sides need to prove to each other that they know the PSK and if one side was sending it to the other one, of course, the other one will now know it. Instead, each side calculates a hash value out of several session related values and the PSK, and sends this hash to other side which is also able to calculate the same hash using the same session values and its own PSK. If the PSK used on both sides was the same, the hashes will match. The way how initiator and responder calculate that hash is slightly different, of course, so one side cannot simply send back the hash it received from the other side as that would also prove nothing. Yet, all values used to calculate the hash must be values that the other side will know just from the data of the current or previous exchanged packets, except for the PSK that each side must simple know.

Main Mode first performs a DH Key Exchange, resulting in secure key on both sides. After that has happened, all communication between both sides is always encrypted and thus not readable by an attacker who is only able to capture traffic between those two sides. The PSK hash is transferred after the key exchange, that means the calculated hash is already encrypted. Also some of the session values required to calculate that hash are sent in the same packet at the hash itself, so these values are also encrypted. An attacker who can just read interchanged traffic will not be able to see the hash, nor will he be able to get all the session related values required to even calculate it. He first had to break encryption or the DH Key Exchange.

Aggressive Mode on the other hand, sends the hashed PSK together with the DH Key Exchange payloads, as well as all the values required to calculate the hash in the very first responder packet and this packet cannot be encrypted because the key exchange has not yet completed. So an attacker, who can just read interchanged traffic, will get the unencrypted hash and also has access to all values that are required to calculate it, except for the PSK itself, of course. Now all that an attacker has to do is brute forcing the PSK, which can be very easy, if it is a poor PSK that is either very short, very simple or cannot stand up to a dictionary attack.

A man-in-the-middle attack is not required for this attack scenario as you are not trying to break the key exchange, you are trying to guess the PSK and you can do so "offline", as you have all the other values required for calculation and a hash that will tell you when you've found the right one. To perform the same attack on a Main Mode connection, you must perform a man-in-the-middle attack which means it's not enough to just see the traffic, you must be able to capture, manipulate and then forward the traffic to break yourself into the DH Key Exchange in realtime. Only then you will get an unencrypted version of the hash and the other values required to calculate it. While also possible, that's a lot harder than just sniffing some outgoing traffic somewhere.

Of course, it all depends on the strength PSK. If your PSK is 64 totally random alphanumeric characters, well, good look brute forcing that. Winning the same lottery ten times in a row is probably more likely than guessing that PSK and trying all possibilities will need more time than our sun is going to exist. The problem is rather that a lot of people don't even understand what a PSK is and consider 1234 secure enough.

Summary: Aggressive Mode is not really less secure than Main Mode. Both can be broken and both can be broken by the same attack. The difference is only, to get the values required for such an attack, it's enough to be able to sniff some traffic in Aggressive Mode (just sniffing two packets is enough), whereas in case of Main Mode you must perform a man-in-the-middle attack on the DH Key Exchange to even get the required values to make the attack possible. Once you have the value, it's equally hard to guess the PSK.


Offline app authentication - embedding hashed password inside an encrypted file I am working on an occasionally connected app.  To allow the users to authenticate I created a profile which is encrypted and placed on the users machine.

The first byte of the file contains the IV length followed by the IV and then encrypted using Aes where the key is the users password hashed using SHA256.

Within the contents of the profile is the SHA512 hashed user password which I use to authenticate the user and (I think) acting as a mac.

So, the users enters their password, it is hashed into the Aes Key and used to decrypt the profile.   Then I authenticate the user by hashing the entered password and comparing it to the stored hashed password.

Am  introducing a security problem by embedding the hashed password within the profile file and does this ensure message integrity?

Yes, the scheme is weak, and made weaker by adding the SHA-512 hash of the password.

The ciphertext being assumed known, this scheme allows testing if a user password is genuine with little effort:

compute the SHA-256 hash of the password to be tested
using that as the key, decipher at least the portion of the ciphertext corresponding to the SHA-512 hash of the password
compute the SHA-512 hash of the password to be tested, and compare it to the above. If it matches, the password guess is most likely correct (is not, it is certainly wrong).

There is no attempt to make any of this process slow. Therefore the scheme is awfully vulnerable to a password cracker such as these, which will simply test likely passwords using this procedure (or, most likely, a simpler version thereof using another redundancy in the plaintext, but we can't tell which from the question). With the exponential progress of CPU power, it is safe to say that most passwords humans will use are vulnerable to password cracking in such a scheme; this trend will only get worse with hardware progress.

Main problem is: building a key from a password is the job for a properly parameterized Password-Based Key Derivation Function, such as scrypt. As an aside, passwords must be salted. Failures in this regard are common mistakes in amateur encryption programs (and a number of others).

No, the scheme does not insure message integrity, and adding the SHA-512 in the plaintext does not help towards that.

The adversary can simply alter another portion of the ciphertext, and with many common modes (CBC, OFB, CTR), or if the SHA-512 hash of the password is at the beginning of the ciphertext, this will not prevent decryption. Plaintext might be garbled, but this still goes against the definition of message integrity.

Further, with many common modes (OFB, CTR, and CFB for the last block of the file), if the adversary knows some section of the plaintext (e.g. TWO), she can change it to anything of the same length that she wishes (e.g. to ONE).

For encryption and authentication, use an authenticated encryption mode, such as AES-GCM. Or a more traditional MAC, using a different key than the one used for encryption, especially if this MAC is based on the same block cipher as used in the encryption. In password-based encryption with integrity protection, that different integrity key can be derived from the same password as for encryption, but a different salt.

And of course, if the adversary succeeds in finding the correct password, she can encipher any message she wishes even with the best such schemes.


How can a company have its own Certificate Authority for internal use? It is possible for a company to deploy its own CA ? How would browsers accept the certificates ?

Supposing a company does not want to use the role of a commercial server like Windows Server or any other as a CA, how can a company deploy its own CA ?

Are there any reliable free projects that can help?

Or the company needs to hire high-level experts, get its CA approved by top level CAs and then the browsers will accept its certificates.

This is done fairly often in companies, but any browser, client, or device which is to trust the internal CA needs to have the internal CA's root key added to its trust store. Browsers which haven't been set to trust the company's CA will not see its certificates as valid.

It's possible to run a CA using only openssl, but very painful. There are projects which make it significantly easier, such as FreeIPA.


Does hashing require non-linearity? I know that for encryption we require non-linearity because it impedes the ability to attack the cipher by solving for the key with linear equations.

Does hashing require non-linear components as well? I presume it does, but I do not know why.

How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search?

I would like to work with the assumption that the linear permutation has appropriate diffusion and is sufficiently complicated/iterated enough to preclude trivial attacks.

Does hashing require non-linear components as well?

Yes

  How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search?

You could find a preimage by solving for the preimage with linear equations; that is, for a linear function, each output bit is a linear function of the input bits.  We would express the entire output as a set of linear equations (with the preimage bits being the unknown), set the right side to be image we're looking for, and solve that set of linear equations, giving us the preimage.


Is there any identification for common encoding/encryption? I come across lots of tokens which might be simply encoded and not random, but I don't know any way to identity if they are encoded or random, how to find is there any cheatsheet for the same.

For example, I know about base64 encoding, I can tell just by looking if its base64 or not. Identification for base64 is it would be in pair of 3 so total count of the characters would be in multiple for 3, if for some reason say there are 19 characters then to make it multiple of 3 two "=" (without quotes) would be added at the end.

Like this are you aware about identification of other encoding/encryption?

I'm not aware of any scheme. Of course, an encrypted value is often indistinguishable from random (or close to indistinguishable for most asymmetric algorithms).

You can use heuristics to determine the type of encoding, but even then you cannot always tell e.g. base 64 from encrypted base 64, or even base 64 from hex (ABCD is both valid in base 64 and hex, to name just one example). It is also generic text. Even if you determined that something is base 64 encoded then you'd be not much further. You can decode the binary value inside, but now you'd have to test what kind of value it represents.

If we suspect hashes then commonly 16 bytes is used for MD5, 20 bytes for SHA-1 and 32 for SHA-256 and so on. However, even then RIPEMD-128, RIPEMD-160 and SHA-512/256 (or SHA3-256) would have the same size, and it is possible to simply use, say, 128 bits off a larger hash function as well.

There are of course encodings that explicitly tell you what they are, such as PEM or XML encoded keys. ASN.1 / BER encoding is used a lot so testing if it complies with that is always a good idea. EC public keys (also used for ECIES encryption) commonly start with a byte valued 02, 03 or 04 and so on and so forth. PGP container format is usually easy to distinguish as well.

The type of ciphertext can usually best be determined by a human being. I'd expect the NSA to have some kind of application to guess encodings or test against classical ciphers, but commonly you need info on the protocol used to do anything useful with it.

A lot of times the used scheme is not kept as a secret if just because of the Kerckhoff principle. In that case guessing is not required.


Best practices: AES-GCM parameter (initialization-vector, ...) transport Apparently there is no mandatory method to transport AES-GCM parameters. I only read that the initialization vector often will be prefixed to the ciphertext. So, regarding the other parameters too, I could send a string like this

my_string = ':'.join([
  'a_unique_iv',              # initialization vector
  '128',                      # the tag size in bits
  'id-1234',                  # associated_data
  'the_cipher'                # cyphertext (converted to string)
])

to a REST API endpoint that stores the data. Or another example (that I would prefer because I already use json objects): Add all parameters as json fields:

my_json = {
  'field_a': 'value b',
  'field_c': 'value_d',
  ...
  'aes_gcm_parameters_and_data': {
    'nonce':           'a_unique_iv' ,
    'tagBits':         128,
    'associated_data': 'id-1234',
    'cyphertext':      'the_cipher'    // converted to string
])

Regarding best practices: Are both approaches fine? Is there a better way? Thx.

Are both approaches fine?

Both are fine.  The entire point of GCM is that the ciphertext (and nonce and ciphertext) is protected, and so any method of transporting them is fine.

I do want to add one note: what the 'associated data' is typically used for is binding a ciphertext to a context.  For example, if you're encrypting database records, one thing you want to prevent is someone taking the ciphertext in one field, and copying it to another.  The associated data is designed to protect against that; if the associated data may be the record key, then the attacker can't do that; the record that the ciphertext is copied to would have a different key, and so the decryption would fail.

Because of this, the associated data typically has meaning to the application; depending on what you're protecting with GCM, what you have may be fine (e.g. if the application knows to look into the associated data you provided to verify the context), or it might not be.

  Is there a better way?

Cryptographically, you're fine, as I said.  As for whether there's a method that would work better (faster, cheaper) for what you're doing, well, you're actually more qualified to say than we are...


Whats the deal with argon2? So I recently read an article about the Argon2 hash function.
Now some Questions:

I heard that it was developed in 2015 so why is it not implemented yet?

If so where is it implemented? ( I think I saw it in KeePass2 )
How strong is it in comparison aginst bcrypt or sha512 or whirlpool?

Is it really that strong against gpu clusters?

It has been implemented, of course. In addition to the reference implementation, there are some crypto libraries with it like libsodium.
It has not yet seen much use in applications or protocols, because it is relatively new and security people tend to be conservative. (And two years simply is not that long.)

Stronger, at least in theory. The resistance to GPGPU does depend somewhat on parameter choices. E.g. the more memory you use, the harder time GPUs have using all their execution hardware.
The argon2d variant is meant to be even more resistant to GPU compute, at possible expense of side channel resistance in comparison to argon2i.


AES-GCM secure against IND-CCA2 How would you prove that AES-GCM is secure against a chosen ciphertext attack (IND-CCA2), assuming that the attacker cannot forge AES-GCM MAC tags in less than brute force?

You would prove it the same way that you prove encrypt-then-MAC in general. In fact, since there are already generic proofs of the encrypt-then-MAC paradigm, and since AES-CTR is already proven as being CPA-secure, all you really need to do is to prove the security of GMAC as a MAC, and then you can apply the general theorem. However, note that your assumption about AES-GCM MAC tags is not an acceptable one. You cannot assume that the "best" is brute force. Rather, you have to take the security based on AES.

Note also that you are better off proving that it achieves authenticated encryption, since this is stronger than CCA security.


Pohlig-Hellman algorithm I'm trying to use the Pohlig-Hellman algorithm to solve for $x$ where $15^x=131 \bmod 337$.  This is what I have so far:

Prime factors of $p-1$: $336=2^4\cdot3\cdot7$

$q=2$: $x=2^0\cdot x_0+2^1\cdot x_1+2^2\cdot x_2+2^3\cdot x_3$

$x_0$: $131^{168}=15^{168*x_0}$, $-1(\bmod 337) = (-1)^{x_0}(\bmod 337)$, $x_0=1$

$x_1: 131*15^{-1}=131*45=166 \bmod337$, $166^{184}=15^{168\cdot x_1}$, $148 \bmod 337= -1^{x_1}\bmod 337$

However, from there, $x_1$ has no answer.  So I know I've done something wrong, I just don't see what.  I've double- and triple-checked every computation, so I assume I misunderstand something about the algorithm.

When solving for $x$ in the equation $g^x \equiv h \text{ mod } p$ the idea behind Pohlig Hellman is to solve discrete logs  on group elements with smaller orders and then recombine those results to obtain $x$. For each prime factor $q^e$ of $p-1$ you do the following:

Find an element with order $q^e$. You can do this via $g' = g^{\frac{n}{q^e}} \text{ mod } p$.
Compute $h' = h^{\frac{n}{q^e}} \text{ mod } p$.
Now, via e.g. brute force find $x'$ such that ${g'}^{x'} \equiv h' \text{ mod } p$. Note that since the group order of the group is $q^e$ this should be fairly quick as long as $p-1$ is smooth.

Using your example we obtain:

For $q^e = 2^4$:
$$g_1 = 278, h_1 = 148, x_1 = 12$$
For $q^e = 3^1$:
$$g_2 = 208, h_2 = 128, x_2 = 2$$
For $q^e = 7^1$:
$$g_3 = 79, h_3 = 53, x_3 = 5$$

We now need to use the Chinese remainder theorem to recombine all our $x_i$ to solve for $x$ using the follow congruences:

$$x \equiv 12 \text{ mod } 2^4$$
$$x \equiv 2 \text{ mod } 3$$
$$x \equiv 5 \text{ mod } 7$$

This yields $x = 236$. We can verify this is correct by observing that $15^{236} \equiv 131 \text{ mod } 337$.


Can you help me prove perfect secrecy? I'm actually new to cryptography and a friend of mine requested that I should read the Katz and Lindell book – “introduction to modern cryptography”.
As I read the book I found it very interesting but I'm finding some problems answering a few questions from the book,(for someone new like me I managed to to answer section 1 and almost section 2), but enough talk I'm getting straight to the questions:
First of all, I needed to prove witch of these two assumptions is perfectly secret :

The message space is $M = \{m \in \{0, 1\}^l \text{ | the last bit of }m \text{ is }0\}$.
Gen chooses a uniform key from $\{0, 1\}^{l−1}$. $Enc_k(m)$ returns ciphertext
$m \oplus (k || 0)$, and $Dec_k(c)$ returns $c \oplus (k || 0)$.

The message space is $M = \{0,..., 4\}$. Algorithm Gen chooses
a uniform key from the key space $\{0,..., 5\}$. $Enc_k(m)$ returns
$[(k + m) \bmod 5]$, and $Dec_k(c)$ returns $[(c − k) \bmod 5]$.

Suppose that we have $\pi(Gen,Enc,Dec)$.
For the first one I guess that I answered it but I need you guys to correct me since I'm not sur if my method is true or not :

$M = \{0, 1\}^l$
$n$ and $k = \{0, 1\}^{l-1}$
with $Enc_k(m)$ outputting $c = m_{[1,ℓ-1]} \oplus (k||0)$, i.e the xor of the first $(l-1)$ bits of $m$ with the key $k$.
The decryption outputs $Dec_k(c)$ as $c \oplus (k||0)$ concatenated with a random 1 bit string (0 on each of the cases $Enc$ & $Dec$).
This scheme satisfies the $2^{−1}$ property that
$Pr[Dec(Enc(m)) = m] \geq 2^{-1}$ for every $m$, which means that in the first assumption the scheme is perfectly secure.

For the second case I have no idea how to put that proof on the line.

It would be good if you revisited the definition of perfect secrecy in the book. What you are proving for the first candidate scheme is a correctness property, not a security property (in general), and not perfect secrecy in particular.

Informally, what you are proving is that encrypting and then decrypting will preserve the original message. What you need to prove is that guessing $m$ knowing $c$ (where $c=Enc_k(m)$) the is as hard as guessing $m$ without seeing $c$.

As a general strategy, a good way to prove something secure is to base your proof on similar, already proven constructions. Scheme 1 is very similar to one-time pad, so the proof should be adaptable.

For proving something insecure, it's often simpler to describe a specific attack or even a counterexample. Scheme 2 for example is not perfectly secret. Since you are given small, concrete values, you can try and work out some example encryptions using pen & paper to see if something's wrong.


Detecting encryption in real-time? Is there anyway to detect encryption in real-time through a common signature or pattern recognition.

Say, a file is being encrypted using an AES-256 cipher, if I have access to the file stream - can I reliably detect an encryption operation?

I am making some assumptions as to the context of the question here, but I think I understand why/what you are asking. The term you are using, "file stream", to me means an ongoing encryption operation on a computer, so I will word my answer accordingly.

Assume you are a filesystem filter driver, and you can view data as it is read from/written to the filesystem, regardless of the specific filesystem used, or the application that is accessing it.

In this case, an encryption operation may appear as both a read operation and a write operation to the same file, or it may appear as a write operation to a different file (temporary) which then takes the place of the original once the operation is complete (through delete and rename).

There are of course some ways you can determine if the file is being encrypted. If there appears to be a sequential series of reads on a specific file, followed either by sequential writes to the same file, or to another file, and the data being written appears to be random (through statistical analysis), then you can assume an encryption operation is taking place, and then perform more detailed analysis on all open files to the process that is accessing the file.

If there is not a corresponding write operation, but rather a similar amount of bandwidth over a network, the same logic applies. Reads may be buffered before writes or network transmission, but there should be a similar averaged amount of data (unless encoding occurs after encryption), and the bandwidth will probably be easy to spot on large files or groups of files.

Looking at individual files may get you nowhere, but sequential file access (maybe by name or date) with corresponding writes or network transmission is more likely to raise flags, especially if what you are looking for is the signature of someone encrypting large amounts of data. Encryption on a small individual file will be difficult to spot if you do not have a historical trend of data access for all processes. Building a record of those trends and a method of analyzing them will be very similar to the heuristics used by antivirus programs when looking for something that is not in their signature database.


Keccak padding implementation, and bit ordering I am trying to implement Keccak in Java for my school work. And I am getting stuck in two places:

On the summary page the padding is shown as

  P = M || 0x01 || 0x00 || … || 0x00
  P = P xor (0x00 || … || 0x00 || 0x80)

However on the specification page section 1.1.2 they mention the variable rate padding as 10*1.

The way I read it, to prepare message for absorption phase, you cut your message into pieces of size r (bit rate). To get message length multiple of r you would append or concatenate the message with just, (for simplicity I am considering just bytes) in case just 1 byte padding required it will be 0x81. And if more than one byte required then it would be 0x80...0x01. So my padding implementation would be something like

  P = M || 0x80...01

Where am I reading the specification in wrong way?
How is the placement of the bits in the state? I mean if I have a message of say 2 bits, then my bit goes to state position S[0][0][0], but then where should I place the next bit in the same row that is S[0][1][0] or in the same lane that is S[0][0][1]. I would have assumed to go with placing the bit in next cell in the row, and then when you are finished with bits from one slice, then you again start with [0][0] position in next slice. But the way most of the functions are defined with respect to slices, makes me think, it could be other way around. I am unable to find in specification, where they clearly mention this.

Please just point me to places in specification which can resolve my confusion. Thanks.

Both are correct, it is confusing because the summary page is discussing the state in terms of bytes, and the spec doc in terms of bits. The actual state for Keccak-1600 is built from 64-bit words.

During the transfer of the input message to the state, the bytes are essentially put into the words in reverse order, which now makes the summary page correct. This is related to the endianness of the specification and how the input message is placed into the state.

Here is an example of the first 576 bits of the input state of Keccak c=1024,r=576 AFTER padding for a simple message "test".

0000000174736574
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
8000000000000000

It can be seen that the 0x01 byte appended to the message precedes the message inside the first 64-bit word, and the final 0x80 byte occupies the highest bits of the final 64-bit word, exactly as how the 10*1 padding scheme says it should.

The resultant output digest after 24 rounds of permutation is:

1e2e9fc2002b002d75198b7503210c05a1baac4560916a3c6d93bcce3a50d7f00fd395bf1647b9abb8d1afcc9c76c289b0c9383ba386a956da4b38934417789e

I believe somewhere in the NIST submission document there is notation describing the bit/byte ordering, as NIST used a different bit ordering for the SHA-3 API.


On AES, is a true random string enough for a key? The string (32 ASCII characters) is entered by a human, and considered truly random. Should a key derive from this string, or it is secure to use this string as a key directly? In other words, does deriving a key from this string makes the encryption more secure?

Even if the 32 characters are completely random, they won't contain non-printable characters. Actually, there are only about 107 printable characters in ASCII (out of 256 values for a full byte) and that even includes the space character. So if all the printable characters are used, it would result to a security level of about $log_2(107^{32}) = 215$ bits, which is quite a lot.

AES reaches the highest level of security for random keys, so in general it is better to put the value through a KDF (Key Derivation Function) together with a salt, possibly a label (OtherInfo) to derive a specific key and possibly - for a Password Based Key Derivation Function such as PBKDF2 or Argon2 - a work factor. That way the security of the key may get closer to the 256 bit strength that e.g. AES-256 promises.

So yes, deriving a key would be more secure. Doubly so since your first sentence "The string (32 ASCII characters) is entered by a human, and considered truly random" is usually not correct in practice. Humans are horrible with regards to entering truly random numbers, even if just because of the typo's when entering it from another screen.


What are the benefits of being able to choose (most of) the public key in a PKC? We're developing a public key cryptosystem whose ciphertexts are actually much more long than the plaintexts (which, according to this question, is more a benefit than an issue).

However, we have a particular property. Most part of the public key can be chosen by the user. More precisely (in a high level explanation), the public key is $n+n^2$ bytes long where $n^2$ of them are chosen at random and the other $n$ bytes are certain function of these values and the secret key.

I was thinking that maybe we could choose these values not at random, but with certain structure: as we wish. For instance, it could be user's mail address or some function of it (expansion function, since $n^2$ is not small). I think this is close to ID-based encryption, but I don't understand this concept so deeply to state a relation. Moreover, not all the public key can be chosen so I'm not sure whether or not this is useful at all, or meet any requirements.

  Is this property useful in any sense? can we get something good from this?

Having so long public keys is a storage problem, that we would like to balance with a good property from this "free choice" fact.

That property lets a trusted n2-byte random string be
enough to make the rest of public keys fit into n bytes.
In particular, forward secrecy can be more efficient if the sender can store such a string, since the string can have been generated by the same party as generates the rest of the public keys.

Also, if for random private keys and independent n2-byte random strings r0 and r1,

the distributions
$\langle$ rest_of_public_key_(r0,priv_key) , r0 $\rangle$    ,    $\langle$ rest_of_public_key_(r1,priv_key) , r0 $\rangle$
are indistinguishable

and

"encryptions" with   $\langle$ rest_of_public_key_(r1,priv_key) , r0 $\rangle$

provide confidentiality even against the private key holder

,   then you get a one-message-in-each-direction

oblivious transfer protocol against semi-honest receivers.


How to prove knowledge of discrete logarithm in a product? Definitions

Suppose I have two large safe primes $p$ and $q$, and a composite number $N=pq$. I have $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$; $g$ and $h$ are generators of $G$. I commit to $x$ using a random value $r\in{_{R}\mathbb{Z}_{N}}$ as $(x,r)=g^{x}h^{r}\mod{N}$.

I have a set of valid messages $S=\{p_{1},p_{2},...,p_{m}\}$, and a message $x\in{S}$. The set $S$ is public, while $x$ is private.

Problem

I must prove knowledge of two secret integers $\mu$ and $\nu$: $$\mu=(\prod^{m}_{j=1}{p_{j}})/x$$ $$\nu=\mu r$$ using the commitment: $$C=g^{\prod^{m}_{j=1}{p_{j}}}h^{\nu}$$ I know this supposedly can be done using a combination of two Schnorr signatures. I just need a little guidance as to how to utilize those two signatures to prove knowledge of $\mu$ and $\nu$.

What I have so far

Given the definition of $\mu$ I have $C=g^{\mu x}h^{\nu}$. I also know I can express $g^{\mu x}=h^{-\nu}C$ and $h^{\nu}=g^{-(\mu x)}C$, so that gives me $$\mu x=\log_{g}(h^{-\nu}C)=\log_{g}(h^{-1})\log_{g}(\nu)+\log_{g}(C)$$ $$\nu=\log_{h}(g^{-(\mu x)}C)=\log_{h}(g^{-1})(\log_{h}(\mu)+\log_{h}(x))+\log_{h}(C)$$ I'm really not sure where to go from here, because I seem to be making it more complicated instead of less...

$$(x,r) = g^x h^r$$
$$C = (x,r)^ \mu$$

Now you have two standard proofs of knowledge.


Is Fibonacci-XOR-rotate one-way-ish? Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method.
Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the following algorithm (C code is given below):

Let r = x1 ^ x2 (bitwise XOR; the "Fibonacci" step).
Rotate r to the right by 1 position.
Let x1 = x2 and x2 = r.
Output x1 and repeat.

Question. Given some output of unknown seeds after an unknown number of steps, is it "computationally hard" to find a pair of seeds that produce the given output after a number of steps?
Here's the C code:

#include <stdio.h>

unsigned rotate (unsigned n, int len);
       // len == length of rotation (number of bits rotated)
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len);

// ---------------------------------
unsigned rotate (unsigned n, int len) // l == length
{
  unsigned b = n & 1; // get right-most bit
  n = n >> 1;
  n = n | (b << (len-1));
     // insert right-most bit at left end
  return n;
}
// ---------------------------------
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len)
    // Fibonacci XOR and then rotate
{
  unsigned result = n1 ^ n2; // "Fibonacci" step
  return rotate(result, len);  // "Scramble" step
}
// ---------------------------------
int main()
{
  int i = 0;
  unsigned x1 = 0xd;  // seed 1
  unsigned x2 = 0x80; // seed 2
  unsigned h; // helper variable
  int my_len = 8; // length of rotation, here: 8 (-> byte length)
  while (i < 100)
  {
    printf("%x,", x2);
    h = x2;
    x2 = fibo_xor_rotate(x1, x2, my_len); // fibo xor rotate
    x1 = h; // set x1 to "old" x2
    if (i % 10 == 9) {
       printf("\n"); // newline after 10 prints
    }
    i++;
  }
  return 0;
}

Given some output of unknown seeds after an unknown number of steps, is it "computationally hard" to find a pair of seeds that produce the given output after a number of steps?

Nope; two observations:

With two successive outputs, you can compute the internal state; if you see the outputs $y_1, y_2$, then the internal state immediately after the first output was $x_1 = y_1, x_2 = y_2$

Given the internal state, you can compute previous states; if the state at time $t$ was $x_1 = y_1, x_2 = y_2$, then the state at time $t-1$ was $x_1 = rotl(y_2) \oplus y_1, x_2 = y_1$ (where $rotl$ is 'rotate shift left by one')

These two observations allow an attacker to revert this generator as far as he needs to.
Actually, for reverting arbitrarily long distances, there are other tricks that reduce the number of computations needed (logarithmic in the size of the time delta; constant time is likely possible, but I don't want to promise that), however we don't need to go to that extent to show that this is weak.


Can you point me to an MDS table reference for the Kalyna cipher? I'm working with cipher Kalyna.

Kalyna — like AES — has MDS tables in its MixColumns step. But Kalyna's documentation doesn't list these MDS tables.

Could you give me a hint where to find proper documentation or the particular MDS tables?

The Kalyna paper does contain the elements on page 6, but it is not formatted in the familiar table manner, rather it describes it via mathematical formula and rotations, as the matrix is circulant:

$w_{i,j} = (υ \ggg i) ⊗ G_j $

$ υ = (0x01,0x01,0x05,0x01,0x08,0x06,0x07,0x04)$

Where $G$ is the input matrix and $W = (w_{i,j})$ is the output matrix

Additionally, the finite field is reduced modulo $x^8 + x^4 + x^3 + x^2 + 1$ or $0x11D$, which is the same field as the whirlpool hash function.

The familiar matrix format for $v$ would be as follows:

$$
 \begin{bmatrix}
1& 1& 5& 1& 8& 6& 7& 4 \\
4& 1& 1& 5& 1& 8& 6& 7 \\
7& 4& 1& 1& 5& 1& 8& 6 \\
6& 7& 4& 1& 1& 5& 1& 8 \\
8& 6& 7& 4& 1& 1& 5& 1 \\
1& 8& 6& 7& 4& 1& 1& 5 \\
5& 1& 8& 6& 7& 4& 1& 1 \\
1& 5& 1& 8& 6& 7& 4& 1 \\
 \end{bmatrix}$$

I believe the inverse matrix is as follows:

$$
 \begin{bmatrix}
AD& 95& 76& A8& 2F& 49& D7& CA \\
CA& AD& 95& 76& A8& 2F& 49& D7 \\
D7& CA& AD& 95& 76& A8& 2F& 49 \\
49& D7& CA& AD& 95& 76& A8& 2F \\
2F& 49& D7& CA& AD& 95& 76& A8 \\
A8& 2F& 49& D7& CA& AD& 95& 76 \\
76& A8& 2F& 49& D7& CA& AD& 95 \\
95& 76& A8& 2F& 49& D7& CA& AD \\
 \end{bmatrix}$$


Does the authentification in GCM serve the same purpose as CRC32? The purpose of the authentification is to ensure the data integrity. Let's just focus on the authentification part of the GCM which is using the Galois field multiplication to create an authentification tag. Eventually, this tag will be verified on the receiver side.

Say today I already have a CRC32 scheme that used in my system. May I know if they are serving for similar purpose. I do read some article saying, the hacker is able to alter the data which can still result the same CRC computed value in the end.

Does this mean Galois Field multiplication is doing better job for this?

I do read some article saying, the hacker is able to alter the data which can still result the same CRC computed value in the end.

Obviously, yes.  The CRC32 function is completely public, with no secret inputs.  Hence, the attacker can compute the CRC32 of any modified data he wants, insert the tag, and it would validate.  In contrast, GCM does have a secret input (that we need to assume the attacker does not know).  Hence, the attacker cannot evaluate the GCM on his modified data in the same way.

Actually, the real answer is a bit deeper (and makes the contrast even stronger); CRC32 has a lot of symmetric internal properties that make it easy to compute the tag on modified data (even if the attacker doesn't see all of the data).  In addition, with GCM, if we assume that the attacker does not know the key, and cannot break AES (and we never repeat nonces), then he has a provably tiny probability of being successful with any modification.

  May I know if they are serving for similar purpose.

Similar?  Well, CRC32 is a fine function if you want to detect accidental (not generated by an intelligent adversary) modifications with pretty decent probability.  In fact, if most of the accidental modifications are burst errors (that is, the errors are limited to a few consecutive bits, and the rest of the message is unmodified), then it is actually better - CRC32 will detect all errors that are contained within a sequence of 32 consecutive bits.  However, once you start talking about strength against an intelligent adversary, that's a completely different story.

  Does this mean Galois Field multiplication is doing better job for this?

It's not about the multiplication, per se.  Actually, you could modify CRC to have similar integrity properties as GCM (you'd need to expand the CRC, make the feedback polynomial secret, and stir in a per-message secret xor-mask).  Instead, it's both the secret key, and the structure (that makes it so that if the attacker makes a modification to an existing message, the change that makes to the tag is unpredictable).


Does hashing a compromised rng and a secure rng give cryptographically secure random output? If I have a compromised random source and a cryptographically secure one, is hashing them together makes a cryptographically secure random output?

Example:

The compromised random output: ABC

The cryptographically secure random output: DEF

Hashing them together:

printf 'ABCDEF' | sha512sum
569350085b223ba854dfc5d607643ceb85e4607e46e5a9ad3696f898e29d8a3fe22610956167cefb7e2ba769e740f94b31e4e3c52195ba65e64ba40d82343591

Is this hash a cryptographically secure random output?

If I am not clear enough, please ask and I will update the question.

If you have a cryptographically secure hash function and you use as much input from each of the sources as there is output i.e.

for $H: \{0,1\}^* \rightarrow \{0,1\}^n$ you use $n$-bits of input from each RNG it will work.

However, in your specific example if you only use 3 letters to generate 512 bits of output, when the DEF repeats the entire 512 bits of output will repeat and this will happen with pretty high probability and after detecting it the rest of the 512 bit are known to an attacker.


Can cryptography be used to hide routing information from the router? If Alice wants to talk to Bob and she has to involve a third party system run by Carol to establish, and possibly maintain, communications, then Carol knows that Alice and Bob communicated with each other.

Chuck sneaks into Carol's exchange, and now knows that Alice and Bob are talking to each other.

Carol decides to start a new exchange with new technology, with the primary purpose of never knowing who is talking to who, and she needs to figure out how to do this.

If Carol runs an exchange that is unlimited communications (meaning no per-transaction billing) then she has no business need to know who talked to who, or for how long, as long as both ends are authenticated to her servers.

So the question is:

Is there a way for Carol to design her new network/exchange/endpoints so that her equipment can route and connect two individuals on that service without knowing who is talking to who?

Obviously the service would need to be handling a lot of traffic, and the traffic would need small random delays so you couldn't simply watch the time that Alice puts in a request to the time another request is output and assume that's her outgoing connection.

But I still don't see a way to handle the actual routing and call connection in a way that prevents anyone from seeing who is communicating to whom.

I'm wondering if there's some cryptographic principle or method that might help with this.  So far all my attempts result in one point in the process where both the sender and recipient are known.

The solution is called onion routing; the gist of it is that there are a number of anonymising servers; when Alice wants to send a message to Bob, she picks a random route through a number of the servers; she then repeatedly encrypts the message for each hop, and sends the encrypted message (which states only the first hop in the clear) to the first server.

The first server then decrypts the message, which reveals the second hop.  It then sends the message to the second hop (batching it with a number of other messages, so someone cannot correlate incoming and outgoing messages).

The second server, again, decrypts the message, which reveals the third hop; and then batch-forwards it to the third hop.

This continues until we get to the last server, which decrypts the message, which reveals the actual destination (Bob) it then batch-forwards it to B0b.

Bob then decrypts the message, this reveals the message that Alice originally sent.

There are a number of subtle points; these points are well studied in the literature.

Now, because of all the above 'batch-forwarding', this doesn't work for real-time communication; for messages that don't mind some unpredictable delay, it's workable.


What does it mean to have "signature verification with RSA-4096" if the key is only 3072 bits long? Trying to understand some crypto terminology while looking at processors.  I figured if a processor supports "up to RSA-4096 signature verification", that it would use a key that is 4096 bits long.  However, in the same reference manual it says that the RSA key sizes supported are 1024, 2048, and 3072 bits.  Does this make sense, or is this a typo in the manual?

Two possible interpretations:

"The RSA key sizes supported are 1024, 2048, and 3072 bits" could mean that RSA key generation and/or private-key operations (signature generation, perhaps decryption) is supported only for 1024, 2048, and 3072-bit key (really, public modulus) size; while "up to RSA-4096 signature verification" would apply only to signature verification, or more generally public-key operations (also including encryption).
The restriction to 1024, 2048, and 3072 bits could apply only in the so-called "FIPS mode", because FIPS 186-4 section 5.1 and by extension FIPS 140-2 conformance only allows these particular key sizes when using RSA.


Is there a PAKE algorithm that is fully resistant to a server data leak? I'm looking to build an authorization system with a completely "public" server which involves two assumptions:

The server's data is public
The server is incorruptible and uncrackable i.e. nobody can pose as or hijack the server.

I've found SRP which is a pretty nifty concept, but even that one relies on the privacy of the server to be effective. By obtaining the verifier and salt, brute force attacks can be mounted offline without any additional input from the server.
My goal is to have a system that requires interaction with the server to check for the correctness of the password, with all server-side data assumed to be visible.

I understand that may be very difficult if not outright impossible. Perhaps leveraging its other features (the server is verifiably legit, client can hold secrets) could be key? Or perhaps there is a way of securely encrypting the verifier.

The server's data is public

That assumption makes the idea of a PAKE undoable.

If the attacker has access to all the server's data, here's what he can do: clone the server, place the clone in his lab, and then have his client perform attempted negotiations based on all the passwords in his dictionary.  Because the clone works exactly like the original server, the clone would access the correct entry in his dictionary, and so the attacker now knows the password.

What this means is that you need to change an assumption somewhere.

People have attempted to solve this problem; attempted solutions include having an uncopiable HSM hold a piece that the server needs to perform the authentication, and having multiple servers jointly perform the authentication (so that no one server knows enough, so that the adversary would need to break into all of them).  Since I don't know what your limitations are, I don't know if these ideas would work for you (I suspect not).

As for your idea:

  client can hold secrets

That feels like it's in the right direction; if the client can hold a private key (and the server would hold the corresponding public key), well, you still need to address MITM attacks (how does the client know he's actually directly talking to the real server), but you have solved the 'cloning the server allows someone to test passwords' problem.  Of course, this direction is getting pretty far from the concept of a PAKE (which assumes that the client's knowledge of the password is the only thing it can use to authenticate).


Why are PAKE protocols not widely used? While there are plenty of PAKE protocols, especially those augmented ones which are practical in C/S model, actually they seem to be not widely used. Even TLS-Standardized SRP, the most popular one among them, I just know it's used in apple's iCloud. In addition, J-PAKE was used in Mozilla's synchronization but aborted for its weird usage.

So, Is there any situation or famous system in which PAKEs are widely used that I don't know? If no, why are they not used even when their patents are expired?

I see three main reasons why PAKEs are not widely used yet:

The lack of IETF standards. SRP has limitations discussed in the link @fgrieu posted above. Many PAKE protocols have been designed, but they lack a convincing security proof, or properties some applications may expect. This is being solved as we speak. The CFRG is currently having a selection process, existing PAKEs are being carefully reviewed, and the outcome will be a small set of recommendations for each use case.
The lack of implementations. Possibly due to the above.
The lack of awareness. Most people have never heard of PAKEs.


What is definition of "adversary"? And what do they do? Currently I am writing my last assignment about secret sharing. But I don't clearly understand adversary. I know this is a fundamental concept in secret sharing. But I couldn't find references that clearly definite adversary. Moreover, what is passive attack and active attack? What are the differences between them?

Formally, an adversary is simply a (probabilistic) algorithm, which we usually assume to run in polynomial time in $n$, the security parameter.
From a more intuitive point of view, an adversary is the model of an attacker on the real life, since every attacker follows an strategy that boils down to an algorithm.

Now, at a high level, a passive attack is an attack where the adversary simply "sees" the information (encrypted data, signatures, etc.) and try to find the secret data from the information gathered. By contrast, in an active attack, the adversary has the ability to "interact" somehow (for instance, by encrypting messages of his choice or even decrypting messages of his choice).

Of course, each one of these notions has its formalization (e.g. Computational indistinguishability, CPA-security, CCA-security).


ECDSA threshold signing I searched "ECDSA threshold signing" recently and found a lot of papers where it is said that their authors solved the problem of ECDSA threshold signing efficiently: e.g. here  and here. Why there are no practical implementations of those (e.g. in cryptocurrencies)?

I just saw this question now. There is no reference implementation of the 2-party threshold ECDSA protocol since this was joint work with Unbound Tech (previously Dyadic Security), and they did the implementation. In general, I am a strong proponent of open source, and all pure academic work that I do is published with open source code (see https://github.com/cryptobiu). However, in some cases, research is carried out in collaboration with industry, and where they do the implementation it is limited by them. I believe that this is a reasonable balance.

Note that Unbound Tech does have a commercial offering using this for protecting cryptocurrencies (but at the level of enterprises, and not individual wallets).


Can I use modulo $n^2$ arithmetic where $n=p \cdot q$ for ElGamal encryption? In the paper which I was reading, the authors were using ElGamal encryption with modulo $p$, where $p$ was a prime.

Do the commitment properties still hold if we use modulo $n^2$ where $n=p \cdot q$ and $p$ and $q$ are large primes?

I was asking this because a number of other commitment schemes use modulo $n^2$ arithmetic.

To completement the answer of SEJPM, note that ElGamal should not be used directly over the ring $\mathbb{Z}_{n^2}$ (more precisely, over the multiplicative group $\mathbb{Z}_{n^2}^*$), because it is insecure here. To be more precise, it is still one-way, which means that if you get an encryption of a random plaintext, it's hard to recover the plaintext. However, it is not IND-CPA secure anymore, because the IND-CPA security property of ElGamal reduces to the Diffie-Hellman assumption - but the Diffie-Hellman assumption does not hold over $\mathbb{Z}_{n^2}^*$. Intuitively, the reason behind this is that computing the Jacobi symbol is easy, and given $(g^a, g^b)$ where $a,b$ are some exponents, and $g$ is some element of $\mathbb{Z}_{n^2}^*$, it holds that

JacobiSymbol$(g^{ab}) = $ JacobiSymbol$(g^a)\cdot$JacobiSymbol$(g^b)$

which allows to break the decisional Diffie-Hellman assumption with non-negligible probability (with probability 1/2, this relation will not be satisfied with a random tuple, while it is always satisfied for a Diffie-Hellman tuple).

This can be fixed by working into proper cyclic subgroups of $\mathbb{Z}_{n^2}^*$ where elements have all Jacobi symbol 1 - the DDH assumption is believed to hold over such groups, so ElGamal should be secure. However, note that it will be far less efficient than standard ElGamal over prime order groups, and should only be used if it is part of a larger system where you really need to use the specific structure of $\mathbb{Z}_{n^2}$.


Most efficient way to crack a monoalphabetic substitution cipher with spacing intact I've got a cipher I've been challenged to crack by hand. It's a monoalphabetic substitution cipher, and the English spacing is intact, so all of the words are the right size.

Is there a more efficient way to crack this cipher than frequency analysis?

Since you know where the word boundaries are, you can use word frequency analysis (either alone or combined with normal letter frequency analysis).

For example, in English text, the most common three-letter word is normally "the".  Identifying it gives you the encryptions of three very common letters, and also some useful hints about the grammatical structure of the plaintext.  Meanwhile, a single-letter word occurring several times in the middle of normal text (i.e. not close to other single letters, not always after the same preceding word) is very likely either "a" or "I", either of which gives you one more common letter.

Also, once you've identified "the", you can look for other short words that begin with the same letters. A four-letter word beginning with "the" is probably "they", "them" or possibly "then". If it begins with "th" but the next letter isn't "e", it's most likely "that" or "than" (and you'll know which, because you know what "t" encrypts to). Once you know what ciphertext letter stands for "a", you can start looking for three-letter words that begin with it, such as "and", "any", "all" and "are". Knowing a few other ciphertext/plaintext letter pairs will let you tell those apart.  ("All" is easy to recognize anyway, because the last two letters are the same.)

Finally, once you've managed to determine the encryptions of a few common plaintext letters, you can start pattern matching longer words containing those letters with a dictionary.  For example, "enQRSTtiUn" (where uppercase letter stand for yet unknown ciphertext letters) is almost certainly "encryption", while "XYtheXYtZQW" (note the repeating ciphertext letters!) most likely stands for "mathematics".

To make this easier,  you may want to write a simple program (in whatever programming language you prefer) that reads a list of possible plaintext words (e.g. from any commonly available English word list) and one or more partially decrypted ciphertext words like above, and prints out all possible matches between them.


RSA attack with continued fractions (Wieners attack) I found an article on the internet about an RSA attack with continued fractions.

Given are the following numbers:

$n = 205320043521075746592613$
$e = 70760135995620281241019$
$\frac{e}{n}=[0;2,1,9,6,54,5911,1,5,1,1,...]$

The method says that if $d<n^{\frac{1}{4}}$, then $\frac{e}{n}$ is an approxiation of $\frac{k}{d}$

In an example of these method, they take $\frac{k}{d}=[0;2,1,9,6,54]$.

They say that they stop the continued fraction before 5911, because it's a big number. Can someone please explain me why?

Let $n=pq$ be an RSA modulus.  Let also $e$ be the public exponent and $d = e^{-1} \bmod (p-1)(q-1)$ the matching private exponent.

From $ed \equiv 1 \pmod{(p-1)(q-1)}$, there exists some integer $k$ such that $$ed = 1 + k(p-1)(q-1) = 1 + k(n-p-q+1) \iff kn-ed=k(p+q-1)-1$$  Dividing through by $dn$ yields
$$\frac{k}{d}-\frac{e}{n} = \frac{k}{d}\Bigl(\frac1{q}+\frac1{p}-\frac1{n}\Bigr) - \frac1{dn}$$

Furthermore, we have the following theorem.

Theorem   If $|\frac{a}{b}-x| < \frac1{2b^2}$ then $\frac{a}{b}$ is a continued fraction approximant for $x$.

So, if the condition of the previous theorem is fulfilled then $k/d$
is a continued approximant for $e/n$. Since $e/n$ is public and since continued fractions can easily be computed, it is possible to find the secret
exponent $d$ (again provided that the condition of the theorem is satisfied).

In particular, assuming $p \sim q \sim \sqrt{n}$ and $e \sim n$, the condition of the theorem is satisfied for a private exponent $d$ of order up to $n^{1/4}$.

Proof. First, we note that if $e \sim n$ then $k \sim d$.  Moreover, we have
$$\Bigl|\frac{k}{d}-\frac{e}{n}\Bigr| \le \frac{k+1}{dn}+\frac{k}{d}\Bigl(\frac1{p}+\frac1{q}\Bigr) \sim \frac1{n} + \frac1{\sqrt{n}} \sim \frac1{\sqrt{n}}$$

Therefore $|\frac{k}{d}-\frac{e}{n}| < \frac1{2d^2}$ if $d$ is of order at most $n^{1/4}$.

Back to your example, the continued fraction development of $e/n$ is $[0,2,1,9,6,54, 5911, \dots]$. Hence, the successive convergents for $e/n$ are
$$\frac{0}{1}, \frac{1}{2}, \frac{1}{3}, \frac{10}{29}, \frac{61}{177}, \frac{3304}{9587}, \frac{19530005}{56668934}, \dots$$

Provided that the conditions of Wiener's attack are met (i.e., $d$ of order up to $n^{1/4}$), we know that $k/d$ is among them.  Actually, you can check that $d = 9587$ is the corresponding private exponent.

In this example, we also have $n^{1/4} \approx 674144$ and $56668934 \gg 674144$.


Good layperson analogy for password and encryption keys NOTE: QUESTION UPDATED. SEE BOTTOM OF THIS POST.
I'm writing something where I need to make someone come across as though they know cryptography. I don't know enough, but as cryptography plays only a very minor role in what I'm writing, there's very little I need to know.
As I understand it, a password is a (preferably) mnemonic string that is fed into a function that generates a much longer and complex string that nobody knows, the user included. The encryption key is what is actually used to encrypt and decrypt a file.
Again, as I understand it, if you want to break an encrypted file, you can either try to brute-force the password, or the encryption key (there may well be other ways I'm not aware of). I learned this many years ago when I had forgotten my password to a document and the recovery tool I used claimed that it wouldn't try to crack the password, but rather the encryption key (it did work, in case you're wondering). I don't know where I picked this up from, but for years I was convinced that brute-forcing the encryption key is a better option to crack an encrypted file than going after its password. Possibly, the very software I used claimed it.
Years later, I realised I'm actually not sure if it's true. Is it actually generally faster/more efficient to brute-force the encryption key rather than the password itself? Considering the definition of the password and encryption key I gave above, you'd think the opposite is true.
Also, would you say that, if brute-forcing a password is like trying a bagillion keys to see which one opens a door, finding the encryption key of a file is like removing the lock from the door? I'm looking for a good analogy but I'm not sure this one works at all—especially because doors are rarely scrambled when they're locked...
UPDATE
After reading Gilles 'SO- stop being evil' answer below, I realised I didn't ask the right question. The right question is here. Probably more about information security than cryptography per se.

A cryptographic key is a string of bits. For example, AES-128 uses 128 bits, each one of them being either 0 or 1. To be able to encrypt or decrypt, each one of those 128 bits must be set correctly. This key is the input to the encryption algorithm. For AES-128 it has to be exactly 128 bits - not more nor less.
For humans, remembering 128 bits (= 16 bytes) is very difficult and impractical. It's much easier to remember (and type) a passphrase such as "mary had a little lamb" than an AES-128 key such as 0a fc 5d e7 43 21 9c b3 6f 1b 93 c7 70 55 24 18. Furthermore, a requirement that all passwords must be exactly 16 bytes is silly. For AES-256 you woud need twice as much. And of course, the true entropy of a 16-character password is much less than 128 bits because of language redundancy and the fact that an ASCII character takes up only 7 bits.
This is why we have key derivation functions (KDF). You input a password of any length into a KDF and tell it how many bits you need for key. The KDF takes the bits from the password, adds some magic spices (called salt) and mixes them up using some cryptographic hash function. You get out just as many bits as you wanted which have the same statistical properties as if they were random. They are based on password, so the same password will always give you the same key. As such, KDF are a perfect "converter" of passwords into cryptographic keys.
If an adversary wants to break the encryption, he/she ultimately needs the encrption key (e.g. 128 bits for AES-128). With a truly random key, this means trying 2^128 combinations, which is an awful lot. Because passwords have less entropy, it would make more sense to attack the passwords as this would reduce the needed effort by several orders of magnitude. However, good key derivation functions such as PBKDF2 are designed to counter this by requiring to do a long computation (basically applying the hash function 10000 times). This "computational cost" slows down the attack on passwords significantly and makes it unfeasible.
As an analogy:

Cryptographic key is a key that actually opens the door.
Password is the secret word that you tell to the locksmith (KDF) so that he can make a key for you. If you tell the same password to the locksmith, you get the same key.


Diffie-Hellman explicit key confirmation Suppose I wanted to add explicit key confirmation to Diffie-Hellman key exchange, would the following scheme be secure?

Alice selects a random $a$ and sends $g^a \mod p$ to Bob
Bob selects a random $b$, computes the shared secret $S = (g^a \mod p)^b$
Bob computes two keys using HKDF ($H(k, m)$ denotes the HMAC of message $m$ using key $k$):

Compute $k = H(salt, S)$
Compute $k_1 = H(k, CTX || 0)$ and $k_2 = H(k, CTX || 1)$

Bob sends $g^b \mod p$, $H(k_1, k_2)$, the salt, and the string CTX to Alice
Alice computes the shared secret $S = (g^b \mod p)^a$, computes $k_1$ and $k_2$ using HKDF given the salt and the string CTX
Alice computes $H(k_1, k_2)$ and verifies whether it's the same as the value that she received from Bob.

The major thing missing from Diffie-Hellman is that it provides no protection from someone running a man-in-the-middle attack.  Your changes don't actually do anything to prevent that.

That is, suppose Eve was between Alice and Bob; when Alice sends the first message to Bob, Eve intercepts the message, and performs the exchange with Alice.  At the same time, Eve forwards her own exchange to Bob.  If Alice and Bob were attempting to perform this exchange to create secret keys, well, they will really share keys with Eve; when Alice sends a message, Eve will receive that encrypted message, decrypt it with the key she shares with Alice, examine it, and then encrypt it with the key she shares with Bob, and forwards it.  That way, Eve sees all the traffic between Alice and Bob without being aware of it.

There is nothing that this key confirmation does that makes this any more difficult for Eve; she can compute $H(k_1, k_2)$ just as well as Alice and Bob, and so she will be able to impersonate Bob to Alice (and impersonating Alice to Bob).

Now, if the question was "is it secure if we don't have to worry about man-in-the-middle", the answer is "well, straight Diffie-Hellman is secure in that scenario; your additions don't appear to have made anything worse".