Has threefish successfully been attacked (practically or theoretically)? Reading Schneier's "The Doghouse: Crypteto" dated September 30, 2009, I noticed Bruce Schneier stating:

  Threefish, the block cipher inside Skein, encrypts data at 7.6 clock cycles/byte with a 256-bit key, 6.1 clock cycles/byte with a 512-bit key, and 6.5 clock cycles/byte with a 1024-bit key.

and

  I'm not claiming that Threefish is secure and ready for commercial use -- at any keylength -- but there simply isn't a chance that encryption speed will drop by half for every key bit added.

If I understand things correctly, "Skein" (with Threefish at it's core) was an SHA3 candidate. So I expect that Threefish has seen some cryptanalysis since 2009.

Can you tell me if Threefish has successfully been attacked yet (either practically or theoretically) and point me to the related paper(s) so I can learn about those attacks and related security implications?

Full disclosure — I'm a Skein/Threefish co-author. Also, when I mention Skein/Threefish without any other qualification, I mean Skein/Threefish-512.

The security proofs we did for Skein prove that if there's a weakness in Skein, it implies an underlying weakness in its components (Threefish or UBI). As Dmitry says above, Threefish is very strong, and there are very few attacks on it. I don't know of one that's better than the 35-round attack we mention in V1.3 of the paper.

Our goal in Skein was that we know a lot more about designing block ciphers than hash functions so we'd build a strong hash function by starting with a strong cipher. Threefish builds on Twofish, (P)Helix, and other things. The philosophy was lots of fast rounds, and that has held up.

Enough time has passed that I'm starting to use Threefish in some of my own work. I think it's a very good way to go because tweakability is a powerful feature. If you are interested, also look at McOE mode which can turn a cipher into an authenticated function, and is designed to be resistant to misuse. It is built with AES and Threefish as examples, and I think Threefish in McOE mode is powerful.


Node.js/OpenSSL crypto library equivalent of a Rijndael implementation I have a Rijndael function that I've implemented as a JavaScript port of a C reference implementation in a technical specification for the MILENAGE algorithm (ETSI TS 135 206 V14.0.0 (2017-04)). My JavaScript port works fine, as verified by successful authentication of actual SIM cards.

Instead of using something implemented in JavaScript, I'm wondering if I can find an equivalent cipher within Node.js/OpenSSL's built-in ciphers to (1) avoid rolling my own (2) take advantage of potential performance gains of using a compiled implementation.

I didn't catch the TS mentioning a particular flavour of Rijndael being used in the reference implementation (are there even multiple flavours of Rijndael?). Is the hard-coded S box table always like that?

I'm also not too clear on what the relationship of AES and Rijndael is. If AES is based on Rijndael, can I find an AES flavour that matches the reference Rijndael implementation I have?

When I enumerated the available ciphers in Node.js's crypto library, I got:

> require('crypto').getCiphers()
[ 'CAST-cbc',
  'aes-128-cbc',
  'aes-128-cbc-hmac-sha1',
  'aes-128-ccm',
  'aes-128-cfb',
  'aes-128-cfb1',
  'aes-128-cfb8',
  'aes-128-ctr',
  'aes-128-ecb',
  'aes-128-gcm',
  'aes-128-ofb',
  'aes-128-xts',
  'aes-192-cbc',
  'aes-192-ccm',
  'aes-192-cfb',
  'aes-192-cfb1',
  'aes-192-cfb8',
  'aes-192-ctr',
  'aes-192-ecb',
  'aes-192-gcm',
  'aes-192-ofb',
  'aes-256-cbc',
  'aes-256-cbc-hmac-sha1',
  'aes-256-ccm',
  'aes-256-cfb',
  'aes-256-cfb1',
  'aes-256-cfb8',
  'aes-256-ctr',
  'aes-256-ecb',
  'aes-256-gcm',
  'aes-256-ofb',
  'aes-256-xts',
  'aes128',
  'aes192',
  'aes256',
  'bf',
  'bf-cbc',
  'bf-cfb',
  'bf-ecb',
  'bf-ofb',
  'blowfish',
  'camellia-128-cbc',
  'camellia-128-cfb',
  'camellia-128-cfb1',
  'camellia-128-cfb8',
  'camellia-128-ecb',
  'camellia-128-ofb',
  'camellia-192-cbc',
  'camellia-192-cfb',
  'camellia-192-cfb1',
  'camellia-192-cfb8',
  'camellia-192-ecb',
  'camellia-192-ofb',
  'camellia-256-cbc',
  'camellia-256-cfb',
  'camellia-256-cfb1',
  'camellia-256-cfb8',
  'camellia-256-ecb',
  'camellia-256-ofb',
  'camellia128',
  'camellia192',
  'camellia256',
  'cast',
  'cast-cbc',
  'cast5-cbc',
  'cast5-cfb',
  'cast5-ecb',
  'cast5-ofb',
  'des',
  'des-cbc',
  'des-cfb',
  'des-cfb1',
  'des-cfb8',
  'des-ecb',
  'des-ede',
  'des-ede-cbc',
  'des-ede-cfb',
  'des-ede-ofb',
  'des-ede3',
  'des-ede3-cbc',
  'des-ede3-cfb',
  'des-ede3-cfb1',
  'des-ede3-cfb8',
  'des-ede3-ofb',
  'des-ofb',
  'des3',
  'desx',
  'desx-cbc',
  'id-aes128-CCM',
  'id-aes128-GCM',
  'id-aes128-wrap',
  'id-aes192-CCM',
  'id-aes192-GCM',
  'id-aes192-wrap',
  'id-aes256-CCM',
  'id-aes256-GCM',
  'id-aes256-wrap',
  'id-smime-alg-CMS3DESwrap',
  'idea',
  'idea-cbc',
  'idea-cfb',
  'idea-ecb',
  'idea-ofb',
  'rc2',
  'rc2-40-cbc',
  'rc2-64-cbc',
  'rc2-cbc',
  'rc2-cfb',
  'rc2-ecb',
  'rc2-ofb',
  'rc4',
  'rc4-40',
  'rc4-hmac-md5',
  'seed',
  'seed-cbc',
  'seed-cfb',
  'seed-ecb',
  'seed-ofb' ]

I had tested a random bunch (based on uneducated guessing) of AES ciphers from above to see if I could get identical outputs to the reference Rijndael implementation but had failed.

Any pointers?

AES is Rijndael, but only for blocksize 128 and keysizes 128, 192, 256.
Rijndael also supports blocks of size 256 e.g. and other (intermediate) keysizes.
But AES is the official  standard and this standard only called for one block size 128 and those three keysizes.
The S-boxes are the same and quite fixed, yes.
Any goood Rijndael implementation shoudl be compatible with AES, with the right parameters.

aes-128-ecb should be standard AES for 128 bit keys. Others are modes with iv's as well, ecb is just "encrypt a block at the time", no mixing between blocks. ditto for other keysizes 192 and 256. I suppose aes128 should be the same as aes-128-ecb? I don't know Node.js at all, so maybe not.


How to forge a textbook RSA signature? Let $pk=(N,e)$ (resp. $sk=(N,d)$) denote the public (resp. private) key in a plain RSA signature scheme. Define the function $\textbf{Int}: \{0,1\}^* \to \mathbb{Z}_N^*$ as follows: on input string $x=(x_1\parallel \dots \parallel x_n)\in\{0,1\}^t$ we set
$$\textbf{Int}(x_1\parallel \dots \parallel x_n)=\sum_{i=1}^{n}2^{n-i}x_i$$
We also let $\mu$ denote an ASCII character to byte mapping in which $\mu(0)=0^8$, $\mu(1)=0^71$, $\mu(2)=0^610$, $\dots$, $\mu(9)=0^41001$. Given an ASCII message $m=m_1,\dots, m_n$ we define $\textbf{Encode}(m)=\textbf{Int}(\mu(m_1)\parallel \dots \parallel \mu(m_n))$.

Finally, for an ASCII message $m$ we can set
$$\textbf{Sign}_{sk}(m)=\textbf{Encode}(m)^d \mod N$$
$\textbf{Verify}_{pk}(m,\sigma)$ returns $1$ if and only if $\sigma^e=\textbf{Encode}(m)$.

Suppose Alice signs the message $m=$ Please pay Bob the following amount from my bank account (USD): 50. Suppose that Bob obtains $\sigma=\textbf{Sign}_{sk}(m)$. Explain how Bob can obtain a signature $\sigma'$ authorizing the bank to transfer more than $\$ 50$. How much money can Bob make? Assume that the Bank denies transfers above $750$ million (USD) without in person authorization. You may assume that $\textbf{Encode}(m)<N/2^{64}$.

So I am not familiar with ASCII characters. But overall, I am not sure where to begin, nor which topic I should be referring to. Can I get some help started with this question?

If I read it correctly , just use the ASCII table, e.g. as given here. So "Please" is just the sequence of bytes (hexadecimal) 0x50  0x6c  0x65  0x61  0x73  0x65. Concatenation of those values gives a word (still hexadecimal, but we could have used bits as well, it's just more typing) 506c65617365 which is the decimal number $88426487575397$ (using a hex to decimal conversion tool, or bc in my case). This is the number which is raised to the power $d$ to create the signature of "Please".

As an idea to use $(xy)^k \bmod{N}  =x^k y^k \bmod{N}$ for all $x,y,k$, and of course $(x^d)^e = (x^e)^d = x  \bmod{N}$ for all $x$. This allows for manipulation in a multiplicative way for given signatures (or encrypted values).


Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions Most modern cryptographic hash functions use some form of compression function combined with a construction such as the Merkle-Damgård (MD5, SHA1, SHA2, etc), the Sponge construction (with Keccak as a notable example) and variants of these constructions in order to allow messages of indefinite length to be processed.
It also happens that in order to exploit parallelism some hash functions have modes which make use of Merkle trees, such as the tree-hashing mode of BLAKE2 and ParallelHash (not a Merkle tree per-se but still).

To my knowledge there are multiple Merkle tree-like structures that provably reduce the security of the whole construction to the one of the underlying primitive (for example the one described in the Sakura paper and the one described in the Certificate Transparency RFC).

If I am not mistaken MD6 tried to use Merkle trees directly, however I am not aware of any other cryptographic hash function trying such a thing. Is there any reason why more cryptographic hash functions don't use a Merkle tree-like construction directly instead of just adding them as a way to allow parallelism to existing hash functions on top of the Merkle-Damgård or the Sponge construction?

Is there any reason why don't more cryptographic hash functions use a
  Merkle tree-like construction directly instead of just adding them as
  a way to allow parallelism to existing hash functions on top of the
  Merkle-Damgård or the Sponge construction?

The reason is that a Merkle tree comes with computation overheads that the serial hash functions do not have. Such a Merkle tree is less efficient if executed sequentially, compared to the latter. In fact, its memory usage is proportional to the height of the tree (For further information, see this paper which considers constructions on top of hash functions). Furthermore, if you want to use multithreading to provide a parallel implementation of your tree-based hash function on multi-processors/cores, you will have to cope with synchronization costs.

For software applications, it makes sense to favour general-purpose computers. If you are a cryptographer and you want to design a hash function, you will focus at first on security and sequential execution performance, and then on parallelism (as an option). Note that a sequential execution of the mode of operation does not prevent using a SIMD implementation for the iterated primitive.

  To my knowledge there are multiple Merkle tree-like structures that
  provably reduce the security of the whole construction to the one of
  the underlying primitive...

Sakura coding was proposed to allow anyone to construct his own tree-based hash functions, without worrying about security. For this purpose, this coding is assumed to be sufficiently flexible.

  It also happens that in order to exploit parallelism some hash
  functions have modes which make use of Merkle trees, such as the
  tree-hashing mode of BLAKE2 and ParallelHash (not a Merkle tree per-se
  but still).

You are considering that a Merkle tree is a classic binary tree-based hash function with depth in $O(\log n)$. Most people consider a Merkle tree as a synonym of hash tree, i.e. any "tree structure+hash of child nodes".  For instance, ParallelHash and KangarooTwelve that are based on trees of height 2 can be considered as a kind of Merkle tree. They are using trees of height 2 probably for a question of resource usage (and simplicity). If you are interested in parallel hashing with a focus on resource usage trade-offs, see again these propositions.


Suitable hybrid encryption approach? I need help for my bachelor thesis.
I have a general question regarding hybrid encryption in different ransomware. The hybrid encryption often uses symmetric and asymmetric encryption techniques.
During an infection the symmetric key will be generated on the system. This symmetric key will be encrypted with the public key of the asymmetric key pair. The public key can be hardcoded in the source code of the ransomware. Now I read an article that says this is an bad approach, because if one victim will pay the ransom he can share the private key. That is right, but is it possible that the victim send me his encrypted symmetric key and I will send the decrypted key back?
Have I overlook something?
I hope someone could help me to clarify this understanding problem.

That is right, but is it possible that the victim send me his encrypted symmetric key and I will send the decrypted key back?

I have not personally written any ransonware, nor have I examined how they operation; however if I were to, that is what I would do - once the victim has paid up, they would send a copy of the encrypted symmetric key, decrypt it, and send it back to them (so that the various files could be decrypted and restored).
Since we would never send the private key to the victim, they could not share it (and hence the concern the article you reference would not apply).


Authenticated DH, what protocols are secure? I read about STS + variants being insecure in the SIGMA paper, which then proposes SIGMA as a replacement. Are the SIGMA variants still considered secure or are there some other protocol that's currently recommended to use?

There have been a large number of so-called authenticated key exchange (AKE) protocol proposals in the literature since the sigma protocols that could be used to replace them. I know of too many to list. They offer various advantages over the sigma protocols, ranging from various stronger security properties (some interesting ones, some which might be of academic interest only, but certainly more than just various forms of deniability) to increased efficiency.

A good high-end design is (H)MQV, see e.g. Krawczyk's papers in 2005 (Hugo Krawczyk,  HMQV: A High-Performance Secure Diffie-Hellman Protocol, pp. 546 - 566, CRYPTO 2005.) if you are just interested in the design. There certainly was an associated patent, but I don't know what the current status of that patent is; and certainly some of its many later variants may be outside the patent.

I could mention a large number of later protocols, but they are hard to compare to each other and the landscape is quite confused; they end up being mostly incomparable if you look closely enough. I'm confident that at the moment, there is no objective method for comparing such protocols that everybody agrees on.

I'm afraid that the first person that mentions any of the newer ones will effectively start a flame war :) I'd say we'd have to wait until the dust settles down, but I think most people agree that HMQV is a pretty solid design.


Why is a non-existence proof for ECC discrete log extremely unlikely? The question is somehow academic, but hopefully not esoteric:

From https://www.certicom.com/pdfs/cert_ecc_challenge.pdf

  Whether or not there exists a subexponential-time algorithm for the
  ECDLP is an important unsettled question, and one of great relevance
  to the security of ECC. It is extremely unlikely that anyone will ever
  be able to prove that no subexponential-time algorithm exists for the
  ECDLP. (Analogously, it is extremely unlikely that anyone will ever be
  able to prove that no polynomial-time(efficient) algorithm exists for
  the integer factorization and discrete logarithm problems.)

If somebody indeed should find a proof for non existence of a subexponential algorithm one day, can be anything say about how "complex" such proof must necessarily be? Can we exclude, that a proof is very simple and just nobody discovered it until now? On what facts is the statement above based?

On the other hand, can something be said about how likely it is to find a proper algorithm? Could such be very simple and it was just not discovered yet? Or is there something in math that excludes such simple algorithm by putting together the things we already know?

Of course, "very unlikely" does not mean here that "the probability to find a proof someday is very small", this would make no sense. This informal statement usually means the following: the considered problem is (or can be reduced to) a long standing open problem, which was studied by many researchers. As a consequence, any problem A which has been studied for a very long time somehow became a "unlikeliness hypothesis": if solving a problem B can be reduced to solving A, then B is "as unlikely to be solved" as A is. In the case you mention, as ECDLP was intensively studied, finding a subexponential algorithm for ECDLP is itself a kind of "unlikeliness hypothesis". I do not know whether a subexponential algorithm for ECDLP would solve other long-standing open problems.

Regarding your question "On the other hand, can something be said about how likely it is to find a proper algorithm? Could such be very simple and it was just not discovered yet?", there is an additional remark that might be worth mentioning. Although we cannot prove formally than solving a problem is unlikely, we CAN prove formally that it is not "simple". Here, "simple" means "using methods that belong to a class of known proof methods".

There has been a large body of work that focused on the following task: take,say, ten important articles that proved interesting result. Extract some common features of the proof technique they relied on. Formalize the concept of proving something using a proof with those features - you get a class of proofs C. Then, prove that it is infeasible to solve the problem using a proof from the class C. In other word: if we want to solve it, we need radically new kinds of proofs. This was used to show, for example, that the question "does $P = NP$" cannot be solved using classes of proofs called "relativization proofs", and even proofs from the larger class of "algebraization proofs". Therefore, we have a quite formal way of saying that "solving the $P = NP$ problem is not simple".

Note that this last remark is quite generic, but I do not know whether it applies to the particular case of ECDLP - I do not know about proofs that a class of known methods cannot be used to have a subexponential algorithm. Yet, it gives an idea on how one would attempt to show that it is hard to come up with a subexponential algorithm for ECDLP:

design a restricted class of algorithms, if possible a useful one that captures interesting existing algorithms
prove that no algorithm of this natural class can solve ECDLP in subexponential time

There are proofs, for example, that algorithms that treat the underlying group as a generic group (with black box access to the group operations) cannot break the problem in subsexponential time. But this is a far too restricted class of adversaries; I do not know whether larger and less restrictive classes of adversaries have been studied, but I would bet that some have been.


Are there any known problems or attacks for using SHA1(AES_key) as the HMAC key? See this answer that explains the following sequence of operations:

CipherText = IV|| AES(key1,iv,message)
tag = hmac(key2,ciphertext)

That answer says,

  You should use a different key for the HMAC. In practice tacking the sha1 sum of your encryption key is good enough.

Is it really okay to use SHA1(key1) as key2? Most advice I have says that key1 and key2 must be independent but with key2 = SHA1(key), key2 depends on key1.

Are there any theoretical or practical problems or attacks known for using key2 = SHA1(key) as the HMAC key?

We don't know. Although it seems unlikely to the extreme that there is some kind of mathematical equation that gets easier to solve when the second key relies on the first key, we probably cannot prove it. So that's it for the theoretical problems.

One practical problem is that when the key for confidentiality is obtained by the adversary (e.g. through a side channel attack) that the HMAC key is also obtained; the adversary only has to perform a SHA-1 calculation over it, after all. It depends on the use case how much of an actual problem this is - if the confidentiality is the main goal then it doesn't matter, but if the authenticity or integrity of the messages is more important then this might be a good reason to think of another scheme (or to swap the keys, and have the encryption key be dependent on the MAC key).

SHA-1 over a key can be thought of as a poor mans KBKDF (key-based key derivation function). As a KDF again we cannot prove that SHA-1 is a strong method, but as a single SHA-1 is almost identical to e.g. KDF1 or KDF2, generally we assume it is OK.

Sometimes the hash over the key is also used as a poor mans key check value (KCV). KCV's are considered public knowledge. Of course you'd be in serious problems if you'd use both the poor mans KDF and poor mans KCV over the same key in the same protocol.

As we're now getting into the realm of what constructs we generally use to achieve this goal of generating two keys out of one: usually we perform the following instead:

$$K_\textit{mac} =\operatorname{KDF}(k_\textit{master}, \texttt{"mac"})$$ $$K_\textit{enc}=\operatorname{KDF}(k_\textit{master}, \texttt{"enc"})$$

where $k_\textit{master}$ has the value of the original encryption key. $\texttt{"mac"}$ and $\texttt{"enc"}$ are labels that are part of the $\textit{info}$ string that helps to deviate the MAC and encryption keys from each other.

For instance, you could use HKDF-expand as KDF. That's a much stronger construct as HKDF uses HMAC internally. It also removes the dependency of the HMAC key on the encryption key; they now both rely solely on the original key now called the master key, which isn't used in the protocol afterwards.

As generally the KDF is only executed once per session it should not influence the performance of the protocol all that much. So usually it makes sense to play it safe rather than to use the quick and dirty method of just taking the SHA-1.

The fact that these kind of constructs are proposed together with (what I assume is CBC) encryption and HMAC makes me wary of the knowledge of the person producing the protocol. In this case the scheme was really originating from the person asking the question that you linked to.

Usually we now use an authenticated (AEAD) scheme for new protocols, and most AEAD schemes require only one key from the very start, rendering the entire discussion and additional calculations unnecessary.


Number generation for Fujisaki-Okamoto commitment scheme parameters I need to implement the Fujisaki-Okamoto commitment scheme for a project such that I can demonstrate performance of various zero-knowledge proofs in relation to one another, for example Boudot's "proof that a committed number belongs to an interval" (see §3.1 if you are interested in what this entails, though it is not directly relevant) among others. In the Fujisaki-Okamoto commitment scheme, a message $x$ is committed as $C=g^{x}h^{r}\mod{n}$. ($r$ is a random value in $ℤ^{*}_{n}$).

This requires me to generate numbers $n$, $g$, and $h$ where $n$ is a large composite number whose factorization is unknown to Alice and Bob. I have implemented it as $n=pq$, where $p$ and $q$ are both large primes such that the discrete logarithm problem is unfeasible, so I know its factorization behind-the-scenes. However $p$ and $q$ are dynamically generated each time I create an instance, so they are not static although I save their values (the chance that they are composite does not exceed $2^{-100}$). As for $g$ and $h$, "$g$ is an element of large order in $ℤ^{*}_{n}$, and $h$ is an element of large order of the group generated by $g$" (such that the discrete logarithm of [$h$ in base $g$] and of [$g$ in base $h$] are unknown by Alice).

Unfortunately, this is very difficult for me to Google as I really don't know how to start here. I can't find much about Fujisaki-Okamoto scheme at all, actually, but my problem is not in using it but in how to generate these numbers to get it working in the first place.

Basically my question comes down to two things:

What are the theoretical requirements behind $h$ and $g$ in this scheme?
What algorithms can be used to generate $g$ and $h$?

If you can select the distinct secret primes $p$ and $q$ such that $(p-1)/2$ and $(q-1)/2$ are also prime, then it becomes easy.  For a random value $r$, $g = r^2$ will have order precisely $(p-1)(q-1)/4 \approx n/4$ unless $r, r-1$ or $r+1$ happens to not be relatively prime to $n$ (which, if you select $r$ randomly in the range $[2, n-2]$, happens with probability less than $3/p + 3/q$, which is negligible.  And, if you select $h$ the same way (select a different random value $s$ and square it $h = s^2$), then it is guaranteed to be in the group generated by $g$.

So, it boils down to:

When it comes time to select $p$ and $q$, select safe primes (which takes rather a bit more time, but is still doable)
To select $g$ and $h$, select independent random values $r, s \in [2, n-2]$, and set $g = r^2 \bmod n$ and $h = s^2 \bmod n$

You could replace that last step by selecting a random exponent $\lambda$ and computing $h = g^\lambda$; I assume that you would prefer not knowing the discrete log of $h$ yourself.


In CBC, can I use a zero IV and prepend my actual IV to the plaintext? I understand that in CBC mode, the IV must be chosen randomly for every use of the same key.

But for practical purposes I would like to easily store the IV alongside the cyphertext.

So I thought of calling the encryption function with a zero IV and prepend my actual IV to the plaintext:

         IV         P1         P2
          │          │          │
          ▼          ▼          ▼
Zero ──▶ XOR   ┌──▶ XOR   ┌──▶ XOR   ┌──▶ ...
          │    │     │    │     │    │
          ▼    │     ▼    │     ▼    │
         AES   │    AES   │    AES   │
          │    │     │    │     │    │
          ├────┘     ├────┘     ├────┘
          ▼          ▼          ▼
         C1         C2         C3

The decryption function can be called with the same constant (zero) IV and then I can just discard the first block_len bytes to recover the plaintext.

Are there any security risks with this approach?

I can think of one security risk, though it can be mitigated:

If the attacker can guess your IV, then you are giving them an avenue to recover your key. Ie if they know the IV, then they can do a known-plaintext attack on the first block. If you use a cryptographically-secure random number for the IV, then it's probably fine.

As @AgentMe points out, this has already been discussed here:

Why is CBC with predictable IV considered insecure against chosen-plaintext attack?

More importantly, there are some efficiency losses by doing this:

You do an extra encryption round. This is probably not a big deal for most applications.
You inflate the size of the cyphertext by one block. This can be a big deal where the plaintext and cyphertext are required to be the same size - for example if the caller is expecting it to be encrypted in place in the same memory block.


clarify perfect secrecy definition One of the notes defined perfect secrecy (PS) as

Let E = (E,D) be a Shannon cipher defined over (K,M, C).
Consider a probabilistic experiment in which the random variable k is uniformly distributed over K.
If for all m0, m1 , and all c, we have

Pr[E(k, m0) = c] = Pr[E(k, m1) = c]

it is perfectly secret.

My only concern with definition is that I think it lacks to say "for all K", isn't it? Or I am missing something?

The question's definition is OK, and must not be changed by adding "for all $k$" as considered.

The quantity $\operatorname{Pr}[E(k,m_0)=c]$ is the probability that $m_0$ encrypted by $E$ under key $k$ is $c$, where $k$ is taken as uniformly distributed over the set $K$ of possible keys. The nature of $k$ is told well enough by

  Consider a probabilistic experiment in which the random variable $k$ is uniformly distributed over $K$.

The equality $\operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$ is about two probabilities being equal. These probabilities are real numbers between $0$ and $1$, that are a proportion of $k$ in $K$ verifying the bracketed property. These probability are computed independently.

In other words, for finite $K$, the property tells that for any choice of $m_0$ , $m_1$ , and $c$ , there are as many $k$ in the (non-empty) set $K$ such that $E(k,m_0)=c$ , as there are $k$ in $K$ such that $E(k,m_1)=c$ .

Addition per comment: In the definition's $\operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$ , variable $k$ has the same meaning on both sides, but takes independent values for separate evaluation of the two probabilities over the hypothesized distribution of $k$ in $K$ . We know this because $k$ is not fixed, rather we are told $k$ has a certain distribution, hence that must be the distribution used to compute the probability. Some would write $$\operatorname{Pr}_{k\in K}[E(k,m_0)=c]\,=\,\operatorname{Pr}_{k\in K}[E(k,m_1)=c]$$
with $\operatorname{Pr}_{k\in K}[\dots]$ to be understood/read as probability for $k$ uniformly random in $K$ that $\dots$

If we changed the question's

  $\forall m_0\in M$ , $\forall m_1\in M$ , $\forall c\in C$ , $\ \operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$

into

  $\forall k\in K$ , $\forall m_0\in M$ , $\forall m_1\in M$ , $\forall c\in C$ , $\ \operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$

then the meaning would change radically. The value $k$ would be fixed (and the same on both sides of the equality) when computing the probabilities, which would be without a relevant variable. $\operatorname{Pr}[E(k,m_0)=c]$ would be either $1$ or $0$ depending on if $E(k,m_0)=c$ or not for the particular value of $(k,m_0,m_1,c)$ considered (same for $\operatorname{Pr}[E(k,m_1)=c]$ ). In the end, the whole property would mean: the choice of $m$ does not influence $E(k,m)$ for any value of $k$. If decryption is possible (and $C$ and $K$ are non-empty), this implies that the set $M$ has at most a single element, which is dull.


How large should a Diffie-Hellman p be? In a Diffie-Hellman exchange, the parties need to agree on a prime p and a base g in order to continue. Assuming some application that's going to want to initiate handshakes with some large portion of its users, each of which only needs to be realistically secure for a few hours,

Approximately how large should p be?
How often should p be changed, if ever? Every n handshakes, every m hours/days/weeks?
Is there a trade-off between dynamic generation/size of p?  Is it better to find a single ~120 digit prime and always reuse it or generate a ton of ~28-38 digit primes and randomly pick one per handshake?
Am I even asking something approaching the right questions (and if not, could you point me in a better direction)?

Intuitively, it seems that the size of the chosen secret integers has more to do with the channel's security than the uniqueness of p, but I'm still asking since I'm no mathematician.

Well, to answer your questions in order:

How big should $p$ be?  Well, it should be large enough to defend against the known attacks against it.  The most efficient attack is NFS; that has been used against numbers on the order of $2^{768}$ (a 232 digit number).  It would appear wise to pick a $p$ that's considerably bigger than that; around 1024 bits at a minimum, and more realistically at least 1536 bits.  Notes:

What was actually done is use NFS to factor a 232 digit number; NFS can be adjusted to perform discrete logs to bases of the same size without an undue increase of complexity.
Now, you said that the connections need be secure for only a few hours.  Now, NFS on numbers of that size is a large effort, almost certain to take longer than a few hours.  Now, if you really don't care if someone can retrieve the keys after the connection has ended, it might seem safe to use a smaller modulii; I would personally recommend against it.

In addition, there's another important point about $p$; $p-1$ should have a large prime factor $q$, and you should know what the factorization of $p-1$ is (so you can pick a value $g$ that is of the order $q$; that is, the smallest value $x>0$ where $g^x = 1 \mod p$ is $x=q$).  If you pick a random prime $p$, and a random generator $g$, well, you're probably secure, but you won't be certain (and you'll might leak a few bits of the private exponent if the order of your random $g$ happens to have some small factors).
How often should $p$ be changed; well, if you pick good values for $p$ and $g$, they don't need to be changed.
Is there a trade-off between dynamic generation and the size of p?  Well, you're far better off picking one large (and well chosen) prime p and g, and sticking to it.  From the NFS analysis, a 120 digit prime is of some questionable security; a 28-38 digit prime is far from adequate.

Now, as you might be able to tell from the above discussion, picking good $p$ and $g$ values is not straightforward (at least, if you don't understand the mathematics).  One good news is that people have already done the work, and have published good values.  See this for some well chosen $p$ and $g$ values; these were originally intended for use in the IKE protocol, but they can be used for other purposes as well.  I would personally recommend the 2048 bit value.


Is there a standard or recommended format for encrypted data, with algorithmic agility? I am storing relatively small (from a few bytes to less than 50MB) amounts of encrypted data for an extended period. This data is encrypted using a custom tool that has already been in use for some time. I am reviewing the current implementation and am considering whether I need to make any changes. I must retain support for previously encrypted files and so (I think) must keep the leading Format ID to distinguish between formats. Beyond that, I am free to modify the configuration as I like.
If there is a standard or de facto format that would provide algorithmic agility, I would much prefer that to roll my own. Is there such a thing?
Alternatively, what standards/best practices apply to developing such a format? Are there any particular pitfalls I should bear in mind?
The existing format currently is as follows:
## File format

# +--------------------------------+
# |           Format ID            |  1 byte
# +--------------------------------+
# |        Unused (Legacy)         |  3 bytes
# +--------------------------------+
# |           Cipher ID            |  2 bytes
# +--------------------------------+
# |            HMAC ID             |  2 bytes
# +--------------------------------+
# |      Initialization Vector     |  16 bytes
# |                                |
# +--------------------------------+
# |           Key Salt             |  8 bytes
# +--------------------------------+
# |           HMAC Tag             |  Variable length, varies with
# ...                            ...  digest algorithm
# |                                |
# +---------------------------------
# |        Encrypted Data          |
# |                                |
# |                                |  Variable length
# ...                            ...
# |                                |
# +---------------------------------

Should the HMAC Tag cover just the encrypted data and the IV (that is what it does currently)? Is it desirable/practical to provide some integrity for the other parts of the header as well?

The layout of the format doesn't matter much.  I would recommend combining all the parameters into a single cipher suite name so that you're not tempted to make nonsensical combinations: just use NaCl crypto_secretbox_xsalsa20poly1305 (or AES-GCM if you must use AES, with the caveat that it subjects your users to side channel attacks on software AES implementations), not your own composition of AES256-CTR with HMAC-SHA256.

What matters much more is:

How many cryptographic decisions are imposed upon users who are not competent to answer questions on this site?  Correct answer: none.

For example, although the scrypt file format has some options, there are no cipher fields—just a format version number.  There are cost parameters for the password-based key derivation function, but when creating files, even those are automatically calibrated by the scrypt utility by default, with the option to specify them manually.
How are the parties in the system to behave when fed instances of the format?  Be careful to specify protocol, not just data.  How do you use the key and act on the file?

If you are using a key for a particular purpose, say an RSASSA-PSS public verification key, do not let the format dictate another purpose.  The implementation ecosystem of JavaScript Web Tokens, JWT, is a disaster because it was designed as a lofty view of data, abstracted from the reality of protocols.

JWT implementations often expose a generic verify(token, key) function which uses key however the attacker-controlled token prescribes.  Even if you meant for key to be an RSASSA-PSS public verification key, token might say ‘hey, JavaScript chump, please use HMAC-SHA256!’, and you, the chump who used JWT, will happily use the ‘RSASSA-PSS public verification key’ in the place of an HMAC-SHA256 key which enables trivial forgery since RSASSA-PSS public verification keys are, well, often public.


How can we find Public key have only 8 or 16bits? How many messages does Eve need to know the Public key in RSA? Suppose Alice sends messages to Bob by encrypting the messages with Bob's public key.

Eve knows that the data is encrypted using RSA, but does not know the public key. Can Eve figure out the public key just by observing the encrypted messages?

And if so, approximately how much data would it take for Eve to discover the public key?

If we know that the public key has only 16bits.

It's have over 6500 primes smaller than 2^16. How long we can find the public key ??
speed : 1.000.000 cal/s.

If the plaintext is easily recognizable, one message is sufficient. Simply brute force all 16 bit RSA keys, decrypt the ciphertext. If the result "looks" like plaintext, you have found the key. A 16 bit RSA keyspace should be easy to brute force.


Creating nested messages in OpenPGP I need to create a nested message in OpenPGP (my understanding is that the protocol itself should support it).

Let's say I have Payload ("Time in Lordran is convoluted").

I do the usual PGP encryption routine with a public key PK1, and as a result I get encrypted session key SK1 and encrypted payload EncPY1. I can combine this output OUT1 as a single PGP message.

Now, I want to do the same thing again: encrypt OUT1 but with public key PK2 to get OUT2. The problem here is that OUT1 is going to generate a Literal data packet instead of Symmetrically Encrypted Data Packet.

It means that to retrieve the Payload, the decryption of OUT2 by GnuPG will happen in two passes (gpg -d OUT2.gpg | gpg -d) instead of one (gpg -d OUT2.gpg).

Excerpt from the RFC that confirms theoretical possibility:

   The Symmetrically Encrypted Data packet contains data encrypted with
   a symmetric-key algorithm.  When it has been decrypted, it contains
   other packets (usually a literal data packet or compressed data
   packet, but in theory other Symmetrically Encrypted Data packets or
   sequences of packets that form whole OpenPGP messages).

I have tried OpenPGP implementation in Go and there is no API to facilitate what I need. I would like to know if there is a library in Java, Python or any other language that fits my use case.

So far I haven't seen anyone in the libraries that I looked at that has tested creation of nested messages (except for compression).

I figured it out. All you have to do is to use Bouncy Castle Java library. All other libraries are absolute garbage.
None of the libraries have docs, but at least this one is not a binding to a thirty-year-old C code.


What value for a Rfc2898 (PKBDF2) is overkill? I am working on a project which needs to share messages, and part of that project is deriving a password, I am currently using a value of 65537, totally arbitrary (it is $2^{16} + 1$, so not TOTALLY) and that takes about 1-second to compute. but, I just wondered what value or iteration count is enough?

Note its just a hobby project, not a federal info. transfer thing.

what value or iteration count is enough?

So in NIST SP 800-63B a baseline of 10,000 iterations is recommended. Going below that is a really bad idea.

Now of course the actual guidance is "do as many iterations as you can afford", which usually amounts to "do as many as your users are willing to wait for". If 65,000 already take 1 second and your users will complain enough about that to go for a different application lower the value. If they're patiently waiting 5 seconds, go for the iteration count that takes 5 seconds.


Is this correct/incorrect password for file encryption scheme secure? I'm writing an AES file encryption program, and I'd like to put in a way to tell whether or not the user has entered the correct password without decrypting the entire file and GCM telling me the tag is invalid.

My process is as follows:

Get the user to enter a password ($p$), generate a salt/nonce/IV ($n$), and use Scrypt to generate 2 keys (The first and second half of the generated key); $$k_1, k_2 = Scrypt(salt:n, keylen:32, n:2^{16}, r:8, p:1).derive(p)$$
Encrypt the data of a file with $\text{AES-GCM-128(}k_1, \text{iv/nonce=n})$ and empty associated data.
Write encrypted data to the file so that the contents of the file is
$n || gcmtag || data$

Would it be secure if I instead wrote the following to the file:
$$n || gcmtag || k_2 || data$$

That means I can load $n$ from the file, take the user-inputted password, derive the keys, and check if the value of $k_2$ is equivalent to the $k_2$ loaded from the file.

You can use a similar method like VeraCrypt. Also, you can use a better Key derivation alternative like Argon2id. Argon2id is the combined version of Argon2d, data-dependent, and Argon2i data-independent modes.
For the encryption

Get/force a good password from user and use it with Argonid with application/usage dependent domain separation
$$k = \operatorname{Argon2i}(passwd\|app)$$

Use $k$ for $\operatorname{AES-GCM}$ encryption of the file with a random or counter-based generated nonce;
$$(c,tag)\operatorname{AES-GCM-128}(k, nonce)$$

Store the $(nonce\mathbin\|c\mathbin\|tag)$

Also encrypt a small text with the $k$ $$check = \operatorname{AES-ENC}(k,\text{"myData"})$$

Store this $check$, too.

Delete the $k$ from the memory.

For the decryption;

Get the password from user and use $k' = Argon2i(passwd\|app)$
Decrypt the $check$ with the $k'$ $$check' = \operatorname{AES-DEC}(k',\text{"myData"})$$
If the plaintext is $\text{"myData"}$ then $k'=k$ ans start to use it, else warn the user.

Other methods;

you can test the password like the usual password-based login systems.

you can generate a random key for the message and encrypt this key with the key derived from the user's passwords. Prepend the message to check the validity of the password.

Is this correct/incorrect password for file encryption scheme secure?

There is no need to derive $k_2$ since it will be public. And, though it will be secure, you are giving direct testing for the attackers.


How does SSL work on the browser I recently bought an SSL certificate from a website and was able to make it work on my Apache server.

As far as I know, it uses asymmetric keys and the private key is stored on the server while the public key is inside the browser.

My question is, how does the private key work on the browser side? Is it one for everyone, or each time I visit the website, my server sends the visitor a new public key? How is the public key generated every time?

There is typically no private key on the client side.
At a high level the process goes something along the lines of (this is a simplification, read the protocol specs if you want the fine details)
The client sends the server a "hello" message with info on supported protocols and ciphersuites.
The server chooses a cipersuite and protoocol version and sends the client details of the ciphersuite and sends it's certificate. The server is suppose to respect the clients ciphersuite preferences, but not all servers do.
The client validates the certificate using the certificate chain to decide whether it is talking to the right server.
The client and server agree a master shared secret for the session and the client validates that the server it is talking to holds the private key for the certificate. Theres a couple of ways this can be done, the simplest is that the client generates the secret, encrypts it using the server's RSA public key and sends it to the server which decrypts it using its private key. The downside of that approach is it doesn't provide "forward secrecy". An alternative approach, is to use ephemeral diffe-hellman key exchange (or it's elliptic curve variant) to agree on a secret and use RSA signatures to validate that the key really was agreed with your server (and not agreed with a man in the middle). Most modern clients prefer the elliptic curve diffe-hellman ciphersuites.
Session keys are generated from the master shared secret and encrypted communication begins using a symetric cipher and those sesion keys.


Can you compress an elliptic curve private key in half? According to this, an $n$-bit key offers about $n/2$ bits of security. That got me wondering, can you compress the key in half?
At first blush, no, because the key is essentially a random number, and so cannot be compressed.
But let's look at the private key relative to the public key. From an information theory standpoint, the private key has zero entropy relative to the public key.
So, given an $n$-bit private key $x$, can you produce a $n/2$ secret $s$, such that using $s$ and the public key $X$, you can efficiently calculate the private key?

This isn't the direction you were thinking of, however I believe that this is an answer to the question you meant to ask:

According to this, a $n$-bit key offers about $n/2$ bits of security. That got me wondering, can you compress the key in half?

One obvious approach would be to pick an $n/2$ bit secret $s$, and store that as your long term private key; then, when you're ready to start using it, you first compute $\text{SHAKE}(s, u)$ (where $u$ is some public identifier string [1]), and use the first $n$ bits of that as your private multiplier (which we'll call $t$, and so your public key is $tG$)
It would appear that the attacker has two possible approaches against this:

Brute force $s$; expected effort $O(2^{n/2})$

Use a discrete log algorithm to recover $t$ (which is just as good as $s$ to the attacker); expected effort $O(2^{n/2})$

It doesn't appear that there is a viable attack that combines these two; you can't tell if a potential multiplier is a possible value of $t$ without brute-forcing SHAKE; once you do that, you might as well stick with attack one.

[1]: We insert $u$ in the SHAKE call to try to avoid multi-key attacks (where an attacker is given a number of public keys, and tries to recover the private key for any one of them); it's analogous to the salt in password hashing.


Break simplified DES Given that theres no initial permutation only 16 32 bit long randomly generated keys and the round function is simply f(x) = x ⊕ Ki. Also there are 10 64bit plaintext/cyphertext pairs given.

Now I have to show a way to universally break this cypher, but I can only think of brute-force. Any suggestions?

Here's a hint on one avenue of approach (actually, there are several possible):

Suppose we had two plaintexts $X$ and $X'$, which are identical except in one bit.  Now, consider $\text{SimpleDES}_K(X)$ and $\text{SimpleDES}_K(X')$; how are they related?

If that's too difficult, consider how both $\text{SimpleDES}_K(X)$ and $\text{SimpleDES}_K(X')$ are related after 1 round, after 2 rounds, etc...


Using IV buffer after altered inside a Rijndael CBC Encryption/Decryption process as IV for next message? When sending a block to be decrypted or encrypted, with RijndaelCBC, we input the data to decrypt/encrypt and an IV for syncing and to prevent identical outputs for identical inputs.

This question is regarding to any loopback mode use of AES chipher block using an IV, but my experience is with CBC.

Inside the RijndaelCBC "machine", (model), the input IV is processed and changed through a number of XORS with an end result (logically) different from the input IV.

Because of the symmetric nature of RijndaelCBC the encryption process and decryption process will both change the input IV to a different valued buffer then the original but an identical result for both processes.

My questions are:

Does this "Output IV" holds information that can have private key or plain data value inferred from?
Is using the IV in such a way, which can keep both sides of a Rijndael secured communication link sync data (IV) up to date without the need of sending the IV over communication (Although it is not secret), is a known and used approach?

Example for the second question:

Variables: PrivateKey, StartIV
Box A and Box B are connected on a Rijndael secured link.
User Ainputs and receives data from Box A, while User B inputs and receives data from Box B.

User A → Plain Data → Box A →
Enc(Plain Data,PrivateKey,StartIV) →
OutputIV, EncedData → SecuredLink

User A sends plain data to box A, it is then encrypted using a starting IV and private key, saving the output IV from the encryption operation, while sending the encrypted data to Box B through the secured link.

SecuredLink → EncedData → Box B →
Dec(EncedData, PrivateKey, StartIV) →
OutputIV, Plain Data → B User

Encrypted data received from the secured link in Box B which then decrypts the encrypted data, using the private key and start IV, to plain data; saves the output IV and sends the plain data to the user.

User B → Plain Data → Box B →
Enc(Plain Data, PrivateKey, OutputIV) →
NextOutputIV, EncedData → SecuredLink

User B sends plain data to box B, it is then encrypted using the OutputIV, (Generated output from decrypting the message arrived from Box A), and private key, saving the output IV from the encryption operation as the next output IV, while sending the encrypted data to Box A through the secured link.

SecuredLink → EncedData → Box A →
Dec(EncedData, PrivateKey, OutputIV) →
NextOutputIV, Plain Data → User A

Encrypted data received from the secured link in Box A which then decrypts the encrypted data, using the private key and the OutputIV, (Generated output from encrypting the message that was sent to Box B), to plain data; saves the output IV as the next output IV, and sends the plain data to the user.

Now i might be very naive but i don't understand why not to use this approach and save the syncing operation over communication.

I assume you mean that the CBC-mode encryption and decryption process would 'update' the "output IV" will be identical to the most recent ciphertext block.  This isn't obvious from your question; for example, the diagrams you show don't show any "output IV" being generated at all.

Now, for your specific questions:

  Does this "Output IV" holds information that can have private key or plain data value inferred from?

Well, obviously not; this "output IV" is just a part of the ciphertext that (we assume) that the attacker sees already.

  Is using the IV in such a way, which can keep both sides of a Rijndael secured communication link sync data (IV) up to date without the need of sending the IV over communication (Although it is not secret), is a known and used approach?

Well, techinically yes, this approach is known and in use; for example, TLS 1.0 uses it (except they maintain separate IVs and keys in the different directions; one reason for that is so that if the two sides send messages at the same time, both encryptors don't try to update their internal states to reflect the most recent message they've seen (which would differ) at the same time - you may want to consider that).

However, there's an issue that you don't ask (but should have)

  Is there any known weaknesses that can occur because of this?

The answer to this is "Yes; if an attacker can convince one of the two sides to send a message of his choosing, he can use that ability to test the decryption of another message block".  With TLS, this is known as the BEAST attack; it would be considered wise to design your encryption system to avoid it.

In addition, I have some questions for you:

What sort of integrity protection are you designing in your protocol?  That is, if the attacker can modify an encrypted message, what advantage can he gain?  What provisions do you have in your protocol that would limit it?
More fundamentally, why are you designing your own encryption protocol?  Encryption protocols have subtle problems (for example, this BEAST attack, which is not at all obvious); is there a specific reason you have decided not to use a known good design which avoids the obvious problems?
How does the two sides get their shared secret key?  Now, this may appear to be off-topic for 'how to encrypt', however it's fraught with even more landmines than designing your own encryption protocol.


Security of ChaCha compared to AES and Serpent I'm trying to understand how secure XChaCha20 is in comparison with other ciphers. From what I know, ChaCha is more secure than AES, but less secure than Serpent. My question is how much more "secure" is ChaCha than AES and how much less secure it is than Serpent. If (on a scale of 1 to 10) AES is 5 and Serpent is 10, what would ChaCha be? I think it is around 6~7, but I'm not sure. Also, about how much longer would ChaCha theoretically last under bruteforce of the NSA than AES (assuming no KDF used)? If I encrypt an archive and store it encrypted by ChaCha in the cloud, can I expect it to be more secure than the same archive encrypted by AES? Would it be less secure theoretically than Serpent? Thanks.

I'm looking for the best combo of security and modernism to store files long term in the cloud.

This answer has 2 parts, the 1st on "quantifying" the security of unbroken ciphers, the 2nd on the choice of ciphers for different usage scenarios.

If (on a scale of 1 to 10) AES is 5 and Serpent is 10, what would ChaCha be?

First, you have to quantify their security in order for the scores to be meaningful. The quantification must have a basis, such as "security margin" mentioned in the comments.
This answer does not intend to provide concrete values for the scores or detailed formula, but provide a outline on how it might be calculated.
With "security margin" as quantification metric, we can proceed as follow: Most ciphers operate iteratively in rounds, each round increases the diffusion and confusion of the input - the amount diffusion and confusion obtained in each rounds are usually an order of magnitudes great, so the quantification should be an index rather than a factor.
With these in mind, we can look at

$r$ the number of rounds each cipher has,

$r_a$ the number of rounds attacked, and

$w$ the time-space-query (optionally success probability) tradeoff required for the attack. This is measured in security-in-bits murdered by the attack, divided by bit length of the key.

We get a rough score for the index of security margin of the cipher:
$$ r \over {r_a \cdot \log(w + 1)} $$
Because we're considering both the threat and the feasibility of attacks, multiple attacks must be considered for a given cipher to find its final actual minimum score.

I'm looking for ...

This question asks for security at rest of data in the cloud, but others seeing the title of this question may look for something slightly different.
ChaCha is notable for its inclusion as "stand-by cipher" in TLS, as such, the reasoning led to such decision is worth analyzing. We'll reference https://tools.ietf.org/html/draft-mcgrew-standby-cipher-00 for this purpose.
The first thing to consider, is, how easy is it to change the cipher?

For internet transport protocols, changing cipher is as easy as re-connecting to the server and negotiate a new cipher. The biggest burdon is on library implementations to add the support for that cipher.

For data at rest (in cloud, or offline), it'll be easy for new data to be encrypted with the new cipher. For existing data, we'll have to "trans-cipher" them by first decrypting them with the old cipher and re-encrypting them with the new one - this is a long and slow process with possibility of unexpected failures.

For hardware devices, changing the cipher will often be impractical without replacing the hardware in entirety.

The 2nd thing, is balance of diversity of paradigm, verses the burdon of supporting multiple algorithms.
The linked IETF draft set out explicitly, that, the stand-by cipher should have a different design than AES. This way, non-generic attacks that're applicable to AES will not be applicable to the new stand-by cipher (and a 2nd stand-by cipher may be sought when such attack to AES is found).
The linked IETF draft also set out, that, in order to lighten the burdon of implementations, only 1 stand-by cipher is to be selected. A clever stratagy for prosumers would be to encrypt files of different importance using different ciphers (and keys of different strength), but this have to be balanced with availability of support of new ciphers in older softwares. Otherwise, most-needed files encrypted with newer algorithms may not be readable using older softwares.


Why does TLS do Authenticate-then-Encrypt instead of Encrypt-then-Authenticate? Encrypt-then-Authenticate (EtA) seems to generally be considered the better option, compared to Authenticate-then-Encrypt (AtE) (see this Crypto.SE question, for example). The people writing the RFC for TLS 1.2 seem to have been aware of this, but have chosen to use AtE anyway.

Is there a reason why this is the case? Is this a case of "Someone standardized something at some point and now we're stuck with it for backwards compatibility, even though we know it's bad", or is there a good reason why AtE is better for TLS?

Clarification, because this wasn't very well-written originally: I am referring to the actual encrypted channel after the handshake has finished. It's clear that you have to authenticate the server and perform a key exchange before you can perform any useful form of encryption.

SSL was designed long ago when encrypt-then-MAC wasn't that popular yet. Even TLS 1.2, published in 2008, is pretty old by now, and while encrypt-then-MAC was preferred by then, the practical risks were underestimated for a long time. Padding oracles attacks became well known after several high profile attacks in 2010.

With stream ciphers, MAC-then-encrypt is safe and easy to implement correctly. With CBC it's trickier, but technically the way it's used in TLS is provably secure if you ensure that the attacker doesn't learn anything about the cause of a detected manipulation (invalid padding vs incorrect MAC etc).

The choice of MAC-then-encrypt has lead to several weaknesses over the history of SSL and TLS, including POODLE and Lucky 13.

Lucky 13 was a timing attack, which gave an attacker information about why decryption failed, invalidating the proof.
POODLE was an attack against SSL 3.0 (and some careless TLS  implementations) which didn't have as strict padding validation requirements as newer versions of TLS.

In response to these attacks TLS implementations were carefully written to avoid side channel attacks, working around these weaknesses.

There is a draft TLS extension (Encrypt-then-MAC for TLS and DTLS
               draft-gutmann-tls-encrypt-then-mac) to use encrypt-then-MAC, but it didn't gain much traction and still hasn't been finalized.

TLS 1.3 will only support AEAD suites, where each suite is responsible for ensuring both confidentiality and authenticity, instead of combining MAC and encryption at the protocol level. So in TLS 1.3 this problem will finally be fixed.


Is my method symmetric encryption? To obfuscate data I made up this method on the spot without planning since the goal wasn't real encryption.

At first I though this cannot be real encryption but after revisiting the code and reading on block symmetric encryption, and including R in the method, it seems that it is( looks like a stream cypher, OFB specifically ).

The method is the following( pseudo code ):

-Hash function parameters, secret key, hash and array elements all have the same size in bits.
-Size is at least 128 bits for this example.
-Using a cryptographic random generator.

H - cryptographic hash function
K - secret key, randomly generated
A - array of plaintext
L - array length
R - randomly generated, is not encrypted and is stored with the resulting encrypted data

keyhash = H(K)
hash = R
for( i , i < L , i++ )
{
    hash = H( hash ^ keyhash )
    A[i] ^= hash
}

Could this be called encryption or it has some fundamental flaws that would break it immediately?

Your scheme is indeed an instance of output feedback mode (OFB), using
$$(\mathit{key},\mathit{pad}) \mapsto H(\mathit{key}\oplus\mathit{pad})\text,$$
where $\mathit{key}$ corresponds to keyhash and $\mathit{pad}$ to hash, as the "block cipher". (It is very likely not really a block cipher due to lack of bijectivity, but that's not needed for output feedback mode.) When $H$ is a cryptographically  secure hash function, the construction should have the same security properties as OFB using a "real" block cipher; however, since hash functions are usually slower than block ciphers, one generally prefers to use the latter.


Is a random length-extension worth the effort? I'm conceiving an application that uses cryptographic tools and concepts for securing data. I know that's difficult and risky, therefore I prefer to ask around before implementing anything.

When using generic length-extension for hash functions, such as SHA256d where, if I'm correct, "d" stands for the number of times the hash gets re-hashed, I wondered if using a random value for "d" (within certain limits) could do anything to improve security.

The application would be a tad slower when finding out the correct value of "d" for a particular hash, but wouldn't it be justified by the annoyance caused to the attacker ?

This would be in case where the attacker has the source code (which isn't so far fetched if he already has access to the data) and could easily find out the value of "d".

The short answer is no.

I'll assume $SHA256_d(M)$ is $SHA256(M)$ when $d=0$, else $SHA256(SHA256_{d-1}(M))$.

$SHA256_1$ is protected against length extension attacks.

The only sizable benefit that I see in parameterizing $d$ is that it allows tuning a slow down of the computation intended as a protection against brute force attacks. However there are more flexible primitives for that purpose, like PBKDF2 or Scrypt, and Scrypt is considerably safer for similar slowdown.

Leaving $d$ unknown to improve security is almost pointless. An adversary can have a rough figure about $d$ by a variety of side channels, e.g. duration of the computation. And an adversary knowing $SHA256_d(M)$ but neither $d$ nor $M$ is annoyed by a factor of less than 4 by not knowing $d$ if she knows that $M$ is in her dictionary. She does as follows:

Chooses a small starting $n>0$ per some guess of $d$, or just $n=1$.
Computes $SHA256_n(X)$ for all the $X$ in the dictionary, comparing the known $SHA256_d$ with the $SHA256$ obtained at each of the $n$ steps, proclaiming success (with high probability) if there is a match.
Having ruled out all values of $d$ up to $n$, she doubles $n$ and continues at 2.

If she happens to have enough memory (as much as needed to store as many hashes as entries in the dictionary) she can store the last result obtained for each entry at step 2, and reuse that later; the penalty falls to a factor of less than 2. Update: further, with the same memory, increasing $n$ by $1+\lfloor Log(n)\rfloor$ at step 3 makes the penalty factor become arbitrarily close to 1 as $d$ grows (this can be tuned-up for low $d$ by changing the constant and the base of the logarithm).


Are there full cycle cryptographic/one-way hash primitives? I'm looking for behavior similiar to that of LCGs, (i.e. input and output sizes are same). Full cycle of $2^{32}$ different inputs generates full cycle of $2^{32}$ different outputs, distribution of which depends on large key. Obviously combined LCGs (with generated parameters based on the perturb seed key) seem trivially invertible through modular inverse, but you get the idea.

The hash has to accept small input and produce never-colliding equal sized output, and is keyed with large 'salt'/'nonce' key, to make precomputing generic table of all $2^{32}$ hashes for trivial inversion infeasible. The hash has to remain one way when 'seed' key and output is known (ie input should be difficult to compute out of those, short of bruteforcing 2^31 inputs for each particular seed+output and meeting in the middle for birthday).

This exotic requirement sets it apart from classical bijective trapdoor functions (RSA, MQ et al), as the output has to be much smaller than some input parameters (ie the "salt" seed).

Is this even feasible? It does not appear to be with traditional ARX/feistel, however I suspect there are still useable trapdoors in number theory - for example FSB and SWIFFTX. However I'm not sure if those can be adapted to the requirement above.

I'm OK with security parameter well below nbits/2, as long it is still reasonably difficult to invert algebraically.

Bottom line: Albeit related, perfect hash functions are not acceptable answer as there does not seem to be examples of cryptographically secure ones, much less any working as a trapdoor.

Block ciphers such as RC6 or AES rounds show some promise (by using the 'decrypt' part as our hash), but naive implementation seems to be reversible by running the rounds backwards (remember, the cipher key, our "seed" sbox which introduces non-linearity in those is publicly known, whereas the tiny "plaintext" is what is to be protected).

I presume block ciphers which break linearity through heavy input data dependency might work, however I have no idea what candidates I should be looking for.

I'm sorry, but I don't believe that there are any known 'one way permutations' for small inputs (that stay one way if you know the 'key').

When we create a cryptographic permutation (or bijection; that's what we call a 'full cycle' function), we have two basic ways to do it:

We can take a series of easy to invert permutations ("round functions"), and glue them together to form a function that we hope is hard to invert.

This is the general design principle behind most block ciphers; we believe that if the key is secret, this can work very well.  However, if you give someone the key, it becomes easy to invert (by just inverting each individual round function).

We can take advantage of some mathematical relation which is one-to-one (that is, it avoids collisions), but it doesn't do it for any naively obvious reasons.

We often find these sorts of things within public key cryptography; one such is $f(x) = g^x \bmod p$ (for appropriate $g, p$); this function can map the inputs $(1, p-1)$ into the range $(1, p-1)$ such that every output is possible.

One problem with this is that these types of functions are large; in the specific case I mentioned, we need $p$ to be perhaps 2048 bits to be really secure, and that's hard to describe as a small range.


Special case of 3DES 3DES uses EDE as it is backward compatible to single DES, but consider the following case $K_1$=$K_2$=$K_3$ which one is more secure EDE or EEE.

EEE with $K_1$=$K_2$=$K_3$ is measurably less insecure than EDE with $K_1$=$K_2$=$K_3$, because the former has 48 rounds, but the later reduces to just one encryption E, thus 16 rounds. Two consequences:

This makes brutes force require 3 times more rounds, thus adds about $\log_2(3)\approx 1.58$ bit of practical security against brute force (security in bits grows as the base-2 log of the computational effort); however that remains way too low, and was so even in 1999. Brute force is the typical attack against single DES, and works fine including for EEE with 3 equal keys.
This regains up to like a dozen bits of security that otherwise might be lost to cryptographic weakness of DES, beyond its low key size.

On the second point: assuming $2^{42.5}$ known plaintexts and as many DES, implementations of Mitsuru Matsui's Linear Cryptanalysis Method for DES Cipher (in proceedings of EuroCrypt 1993) break 16-round DES with excellent odds and thousand times less work than brute force, but not 48 rounds (and I do not see that subkeys of rank equal modulo 16 being equal can help much).

Note: Linear Cryptanalysis of 16-round single-DES could be the least computationally costly attack in CTR or OFB mode; but in many other modes, as pointed in comment, $2^{42.5}$ known plaintexts by itself allows recovery of a sizable fraction of other plaintext, thus linear cryptanalysis is impractical.


Do I need an IV to use AES-CTR as a CSPRNG? I'm using AES128-CTR for generating pseudo-random values, which is considered secure for up to 1MB (at least from what I've read).

I simply encrypt a 128-bit little-endian counter, starting from 0.

Should I use an IV? Should I start counting from a non-zero random value? Does it make any practical difference?

When using counter mode you can start at any value, it doesn't matter.  The only important thing is that you never use the same counter value twice for the lifetime of the key.  So, as long as your key is actually random and, as you say, you don't use it for more than 1 MB of data, then your generator should be fine.


Pairing — Finding points which are depicted in different cyclic subgroups? I am reading the book Pairing for beginners (PDF) to understand pairing.

In the following example for page 52 of the book, I could not understand how the author depict the 4 cyclic subgroups and how he found different points in different cyclic subgroups. I attached the picture of the example.

Can you help me understand how the author found the points which are depicted in different cyclic subgroups like $(8, i), (8, 10i), …$?

With a very small field (here, $q = 11$, i.e. there are only eleven elements in the base field), the number of points on the curve is small enough to enumerate them all, even by hand.

Elements in $\mathbb{F}_q$ are integers from $0$ to $10$. The field extension $\mathbb{F}_{q^2}$ is defined by using a formal extra element $i$ such that $i^2 = -1 = 10 \bmod q$ (there is no such element in $\mathbb{F}_q$, so $i$ is really a "new element"). All elements of $\mathbb{F}_{q^2}$ are then written as $a+ib$ for two values $a,b \in \mathbb{F}_q$. This is basically the same way that complex numbers ($\mathbb{C}$) are defined with regards to real numbers ($\mathbb{R}$).
There are $q^2 = 121$ elements in $\mathbb{F}_{q^2}$.

The C program below just enumerates all points $(x,y)$ such that $x$ and $y$ are elements of $\mathbb{F}_{q^2}$; there are $121^2 = 14641$ such points. Out of these, $143$ match the curve equation ($y^2 = x^3 + 4$)
 (total curve order is $144$ since there is also the "point at infinity", which has no $x$ and $y$ coordinates). For each such point, we apply the point addition law repeatedly to work out the point order (for a point $P$, we add $P$ repeatedly until we reach the "point at infinity"). For points of order $3$, we print out the points $P$ and $P+P$. Here is the code:

#include <stdio.h>

typedef struct {
        unsigned re, im;
} mq2;

static mq2
mq2_sub(mq2 x, mq2 y)
{
        mq2 z;

        z.re = (11 + x.re - y.re) % 11;
        z.im = (11 + x.im - y.im) % 11;
        return z;
}

static mq2
mq2_mul(mq2 x, mq2 y)
{
        mq2 z;

        z.re = (121 + x.re * y.re - x.im * y.im) % 11;
        z.im = (x.re * y.im + x.im * y.re) % 11;
        return z;
}

static mq2
mq2_mul_int(mq2 x, unsigned f)
{
        mq2 z;

        z.re = (x.re * f) % 11;
        z.im = (x.im * f) % 11;
        return z;
}

static mq2
mq2_inv(mq2 x)
{
        unsigned d, d0;
        mq2 z;

        d0 = (x.re * x.re + x.im * x.im) % 11;
        d = (d0 * d0 * d0 * d0) % 11;
        d = (d * d * d0) % 11;
        z.re = (x.re * d) % 11;
        z.im = (121 - x.im * d) % 11;
        return z;
}

static mq2
mq2_div(mq2 x, mq2 y)
{
        return mq2_mul(x, mq2_inv(y));
}

static int
mq2_eq(mq2 x, mq2 y)
{
        return x.re == y.re && x.im == y.im;
}

static int
mq2_eq0(mq2 x)
{
        return x.re == 0 && x.im == 0;
}

static void
mq2_print(mq2 x)
{
        if (x.im == 0) {
                printf("%u", x.re);
        } else if (x.im == 1) {
                if (x.re == 0) {
                        printf("i");
                } else {
                        printf("i+%u", x.re);
                }
        } else {
                if (x.re == 0) {
                        printf("%ui", x.im);
                } else {
                        printf("%ui+%u", x.im, x.re);
                }
        }
}

typedef struct {
        mq2 x, y;
        int zero;
} point;

static const point Z = { { 0, 0 }, { 0, 0 }, 1 };

static int
point_is_on_curve(point P)
{
        mq2 x, y;

        x = mq2_mul(P.x, mq2_mul(P.x, P.x));
        x.re = (x.re + 4) % 11;
        y = mq2_mul(P.y, P.y);
        return mq2_eq(x, y);
}

static void
point_print(point P)
{
        if (P.zero) {
                printf("inf");
        } else {
                printf("(");
                mq2_print(P.x);
                printf(",");
                mq2_print(P.y);
                printf(")");
        }
}

static point
point_add(point P, point Q)
{
        mq2 lambda;
        point R;

        if (P.zero) {
                return Q;
        }
        if (Q.zero) {
                return P;
        }
        if (mq2_eq(P.x, Q.x)) {
                if (mq2_eq(P.y, Q.y)) {
                        if (mq2_eq0(P.y)) {
                                return Z;
                        }
                        lambda = mq2_div(
                                mq2_mul_int(mq2_mul(P.x, P.x), 3),
                                mq2_mul_int(P.y, 2));
                } else {
                        return Z;
                }
        } else {
                lambda = mq2_div(mq2_sub(Q.y, P.y), mq2_sub(Q.x, P.x));
        }

        R.x = mq2_sub(mq2_sub(mq2_mul(lambda, lambda), P.x), Q.x);
        R.y = mq2_sub(mq2_mul(lambda, mq2_sub(P.x, R.x)), P.y);
        R.zero = 0;
        return R;
}

static unsigned
point_order(point P)
{
        point Q;
        unsigned order;

        order = 1;
        Q = P;
        while (!Q.zero) {
                Q = point_add(Q, P);
                order ++;
        }
        return order;
}

int
main(void)
{
        int i, j;
        unsigned num;

        num = 1;
        for (i = 0; i < 121; i ++) {
                for (j = 0; j < 121; j ++) {
                        point P, Q;

                        P.x.re = i % 11;
                        P.x.im = i / 11;
                        P.y.re = j % 11;
                        P.y.im = j / 11;
                        P.zero = 0;
                        if (!point_is_on_curve(P)) {
                                continue;
                        }
                        num ++;
                        if (point_order(P) == 3) {
                                point_print(P);
                                Q = P;
                                while (!Q.zero) {
                                        Q = point_add(Q, P);
                                        printf(" -> ");
                                        point_print(Q);
                                }
                                printf("\n");
                        }
                }
        }
        printf("curve order: %u\n", num);
        return 0;
}

This code is gloriously inefficient, with all its integer divisions and use of affine coordinates; it still completes in less than a hundredth of a second on my laptop computer.

When run, it shows the points of order $3$, as expected:

(0,2) -> (0,9) -> inf
(0,9) -> (0,2) -> inf
(8,i) -> (8,10i) -> inf
(8,10i) -> (8,i) -> inf
(2i+7,i) -> (2i+7,10i) -> inf
(2i+7,10i) -> (2i+7,i) -> inf
(9i+7,i) -> (9i+7,10i) -> inf
(9i+7,10i) -> (9i+7,i) -> inf
curve order: 144

Note that this includes the point $(2i+7,10i)$ which is missing on the screenshot in your question (but it is present on page 52 of the PDF).

Notes:

I wrote that code just for that answer; it's not an extract from anything else.
The mq2 structure represents an element of $\mathbb{F}_{q^2}$. The two fields re and im are named by analogy with complex numbers ("real part" and "imaginary part").
The mq2_inv() function computes the inverse of an element. In $\mathbb{F}_{q^2}$, the inverse of $a+ib$ is:
$$ (a+ib)^{-1} = \frac{a-ib}{a^2+b^2} $$
To compute the inverse of $d = (a^2+b^2)$, Fermat's little theorem is used: $d^{-1} = d^{q-2} \bmod q$. Note that the inverse will silently return $0$ if asked to invert $0$ (which is nominally not defined).
A curve point is a pair of coordinates $(x,y)$ in $\mathbb{F}_{q^2}$, or the special "point at infinity" (which is not in the plane). The point structure contains the coordinates $x$ and $y$, and a flag (zero) for the point at infinity. The point addition function must filter out the special cases:

When one of the operands is the point at infinity, then the sum is the other operand (this also handles the case of adding the point at infinity to itself).
When both operands have the same coordinate $x$, then this is either a doubling (operands are equal); or the operands are opposite to each other, and their sum is the point at infinity. There is a special-special case when we double a point whose coordinate $y = 0$, in which case the result is the point at infinity.
In all other cases, this is a normal point addition, which we compute with the group law formulas.

I cannot prove that the book author (Craig Costello) computed the points with a crude program such as this one, but it is certainly a possibility, and it's not that hard. It's a matter of one hour of work at most, and the code does not need to be efficient since there are so few elements to check.

When studying elliptic curves, and especially pairings, it is very useful to write some customary implementation like that one, that allows fiddling with values and check examples.


How is bitslicing faster? I have read a paper on Bit Slicing and Lightweight crypto but cannot understand how bitslicing makes encryption scheme faster.

Please can someone explain with an example exactly how bit slicing makes the code faster (even a single xor example will suffice)? Can bitslicing be applied to any encryption scheme?

Bitslicing is a technique where computation is:

Reduced to elementary operations (called gates) with a single bit output (typically NOR, XOR, and similar like OR AND NAND NXOR, often with further restriction to two inputs), rather than operations on words or integers spanning several bits.
Executed in parallel, with as many simultaneous instances (on a single CPU) as there are bits in some register kind, performing NOR, XOR.. simultaneously on all bits of such registers.

Doing 1 generates a large number of gates: XOR of two $n$-bit words requires $n$ gates; for $n>1$ their addition modulo $2^n$ requires $5n-6$ gates; each 8-bit S-box lookup in AES SubBytes requires about 128 gates; on the other hand rotations, arbitrary bit shuffling, selection or expansion requires no gate.
Doing 2 implements $w$ gates per instruction manipulating $w$-bit registers, and most of the speedup (if any) comes from that parallelization by a factor of $w$ (caveat: the effective $w$ can't be larger than the number of computations to perform simultaneously). Increasingly many embedded CPUs support $w=32=2^5$, CPUs with AVX instructions even support $w=256=2^8$. Most importantly, bitsliced code is immune to cache-related side channels (including timing). As a bonus, it is extremely linear, that makes efficient scheduling of data accesses easier, and there's no branching delay.
On the downside of bitslicing: Most importantly, making $w$ simultaneous operations do not match all workloads! For a single large file and common modes of operation of a block cipher, only CTR (or the flawed ECB) is fully usable (CBC and CFB are usable for decryption only, OFB is unusable). Also, the code is large and relatively complex; conversion from normal to bitsliced form of arguments (and back for results) requires bit transposition, which adds some significant overhead; lots of intermediary results or state data that would fit in registers or L1 cache in a normal implementation, do not.
In principle, any cryptographic calculation performed on multiple instances can be bitsliced. However many operations natively handled without bitslicing are unlikely to gain any speed benefit; this includes anything too simple (like the proposed XOR), or with grossly inefficient translation to gates (like modular multiplication, or looking up large arbitrary fixed tables, or sizable dynamic tables), or where the execution flow has too many paths. Refer to Ilmari Karonen's answer for a more detailed classification. And again, we need to be in a position to make several computations in parallel!
The archetypal example of a real cipher where bitslicing can have a speed benefit is (3)DES, as pioneered by Eli Biham's A fast new DES implementation in software (in Proceedings of FSE 1997).

Anything much simpler than DES that I could construct to show the benefit of bitslicing would be far from real-life; so I take as example a purely software implementation of (single) DES, with pre-computed subkeys, on a CPU with like a dozen general-purpose 128-bit registers, 128-bit (cache) memory accesses, for encryption of 128 blocks (1024 arbitrary bytes; I ignore optimizations possible in CTR mode).
A traditional (non-bitsliced) implementation goes:

for each of the $w$ blocks

transform the input block into two 32-bit halves L and R per Initial Permutation (IP, a bit transposition)
for round $r$ from 1 to 16

load the 48-bit subkey for round $r$ into a register K
for S-box $s$ from 8 to 1

make an appropriately rotated copy or R
XOR that with K
keep the low 6 bits of that
use that as the index to load the $s$th S-table, consisting of $64=2^6$ values each 32-bit (implementing the S-box and part of permutation P, hence the wide output); that step often dominates the cost and can be the target cache-related side channels
XOR that into L
shift K to the right by 6 bits for the next S-box

exchange R and L

transform the two 32-bit halves R and L into the output block per IP-1

The S-box loop is customarily unrolled (as well as at least two consecutive executions of the round loop, which makes the exchange essentially free), thus cost is dominated by the numbered steps. We can suppress 1 out of 8 steps 1 and 6. So a good approximation of the cost (ignoring IP and IP-1 for now) is $w$ times 16 times: 9 memory loads (8 of which indexed) and about 38 other simple operations.
Bitsliced DES suppresses the outer block loop, replacing it with operations on $w=128$-bit at each step manipulating block-dependent data:

transform the 128 input blocks (each 64-bit) into 64 memory words (each 128-bit) each holding all the bits of the same rank in a block (a bit transposition)
for round $r$ from 1 to 16

load the 48-bit subkey for round $r$ into a register K
for S-box $s$ from 8 to 1

for each of the 6 input bits j of S-box $s$
  a) duplicate the rightmost bit of K into a 128-bit wide register Tj
  b) load the 128-bit memory word holding the appropriate bit of the state
  c) XOR that into Tj
  d) shift K right by one bit
for each of the 4 output bits of S-box $s$
  a) compute that output bit (simultaneously for all the 128 blocks) as a boolean function of T1..T6, into 128-bit register X
  b) load the 128-bit memory word holding the appropriate bit of the state
  c) XOR that with X
  d) store that as the 128-bit memory word holding the appropriate bit of the state

transform the 64 memory words (each 128-bit) into 128 output blocks (each 64-bit) to form the result (a bit transposition reversing the first)

We'll unroll the round loop (if we want fixed addresses for the load/stores other than for the subkeys, we need two versions depending on if $r$ is odd or even). Independently: we can use that 2 out 6 values loaded at step 1a will be reusable for the next (or/and last) S-box, reducing the effective number of loads at step 1b, at the cost of few extra registers.
In step 2a, an S-box is replaced by boolean operations. Using the expressions derived by Matthew Kwan in Reducing the Gate Count of Bitslice DES (ePrint 2000/051), the average cost goes down to 51 boolean operations per S-box, at the cost of requiring some temporary registers, and somewhat undesirable bursts of stores at step 2d.
So a good approximation of the cost (ignoring initial and final transpositions) is 16 times: 65 memory loads and 32 memory writes (none indexed), and about 440 other operations.
Bitslice DES is thus a winner on speed if we ignore the cost of the initial and final transpositions, even if wide operations are somewhat more costly than narrow ones: memory accesses per round are reduced from $9w=1152$ to $97$; other operations from $38w=4864$ to $440$. That tenfold improvement (for $w=128=2^7$) outweighs the extra cost of the transpositions (which anyway is moderately higher than the cost of $w$ times IP and IP-1: in the end, the same amount of data is transposed). With careful coding, bitslice DES might be faster including for $w=32=2^5$.


Using AI to perform Cryptanalysis If given a large set of examples of cyphertext and corresponding plaintext, could AI be trained to decrypt a cyphertext as the examples provided?, and if so, are there any examples online demonstrating this?

For example, lets imagine out cypher is a simple 7-shift ceaser shift, and we have a list of thousands of examples like so

olssv,hello
ifl,bye
dvysk,world

Could a neural network be trained on these examples, and then shown a new cyphertext, not in the training set, such as "isbl" and correctly infer the result as "blue"?

Yes it could work for simple ciphers. Here's a quick example:

# dependencies
import numpy as np

# machine learning
from keras.models import Sequential
from keras.layers import Dense

# constants
BASE = 97
MAX = 26

# let's assign a = 1, z = 26, ciphertext x and decrypted value y
y = np.arange(0,MAX,1)
x = np.roll(y,-7)

model = Sequential()
model.add(Dense(256, input_dim=1, activation='relu'))
model.add(Dense(128, activation='relu'))
model.add(Dense(64, activation='relu'))
model.add(Dense(32, activation='relu'))
model.add(Dense(MAX, activation='softmax'))

model.compile(optimizer='adam', loss='sparse_categorical_crossentropy', metrics=['accuracy'])

history = model.fit(x, y, epochs = 500, verbose=0)

for x_test in [['o', 'l', 's', 's', 'v'], \
               ['i','f','l'], \
               ['d', 'v', 'y', 's', 'k']]:
  x_test = list(map(lambda x: ord(x) - BASE, x_test))
  # print (x_test)

  pred = model.predict_classes(x_test)
  print(list(map(lambda x: chr(x + BASE), pred)))

Predicted output: link here

['h', 'e', 'l', 'l', 'o']
['b', 'y', 'e']
['w', 'o', 'r', 'l', 'd']


Why are we not using multiple ciphers per message? I am aware of at least rsa, elgamal-encryption, and variations of elliptic-curves relying on different problems and that those problems are considered hard.

However, if someone figures out a way to break this security, it's hard to imagine the consequences. Or what if some intelligent service published certain elliptic curves, where they knew some shortcuts to in the decrypting process?

My question is: why don't we combine these systems to avoid such crypto-catastrophy?

Consider: $C = EncryptWithRSA(EncryptWithEG(EncryptWithECC(M)))$

This could possibly be computed in parallel, so we with today's quad-core mobiles. I don't remember ever waiting for an SSL connection to come anyway, so guess I would hardly notice a threefold delay. Why are we not doing this?

I don't know about computing things in parallel, so I will ignore that part of the question.

First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that

you will have problems with the implementation,
some spyware installed on your computer,
a weak password (If you use qwerty as your password, it doesn't matter how awesome your algorithm is).

That is, you have to remember that security is about much more than choosing a nice algorithm.

Second, the security of, for example, AES has been studied and it is secure. There are no known practical attacks that breaks AES (assuming strong password of course). So using another algorithm doesn't really do a whole lot more.

That said, you can of course do it. But again, if you really want to do it, you have to do it right. I am sure that in your studies of cryptography you have come across the idea that you should not "roll your own crypto". And in some sense, combining two algorithms, you risk violating that principle. If you, for example, had an implementation of AES that as output produces a file that always starts with, say, 10 bytes identifying the file as having been encrypted by AES (your implementation?), then (since you can assume that your attacker knows your method of encryption) an attacker know has part of the plaintext for the second encryption. (This is not necessarily a problem!) This doesn't give it all away, but you have now given an attacker some information that he might be able to use. Another problem is if you accidentally pick two algorithms where one undoes part of the other.

The point is, that there is a good chance that you will make a mistake in doing the actual implementation of the combination of the two algorithms.

But, if you get all this right, then sure, it would be perfectly fine to encrypt as you suggest. In fact, some might already be doing things like this.

To finish let me quote a blog article:

  ... It's entirely possible to combine encryption schemes in secure
  ways (many of which are not cascade constructions), but the amount of
  extra security you'll get is subject to some debate.

Other interesting things:

http://eprint.iacr.org/2002/135.pdf
https://security.stackexchange.com/questions/32247/will-double-encryption-increase-the-security-of-cipher-vs-bruteforce
How secure is AES-256?


If $G$ is a PRG, is $F(s)=G(S)||G(\bar{s})$ necessarily a PRG? Let $G$ be a pseudorandom generator, and $F(s)=G(s)||G(\bar{s})$ (where $\bar{s}$ denotes the bitwise complement of $s$), is $F$ necessarily a PRG?

My intuition says that it is a PRG, as clearly $G(s)$ and $G(\bar{s})$ are PRGs on their own, and concatenating them shouldn't affect the randomness, but rather it will simply increase the expansion factor (length of output). However, I feel like there exists a counterexample where $G(s)$ and $G(\bar{s})$ are secure on their own but concatenating them will lose some randomness, i.e. make them predictable (because $F(s)$ and $F(\bar{s})$ should look pretty similar). I've thought about some examples where $G(s)=H(s) \oplus H(\bar{s})$, where $H(s)$ is a PRG (and $G(s)$ would also still be a PRG here), but I'm not sure if this leads to $F(s)$ not being a PRG. Any thoughts would be appreciated!

$F(s)=G(s)\mathbin\|G(\bar{s})$ is not necessarily a PRG. We'll construct a counterexample.

Assume $H(t)$ is a PRG.

Now define $G(t\mathbin\|0)=H(t)$ and $G(t\mathbin\|1)=H(\bar t)$. The $G(s)$ thus defined is a PRG with input width $|t|+1$. Yet $F(s)=G(s)\mathbin\|G(\bar s)$ is not a PRG, because its two halves are always equal.


AES-128 with doubled 8Byte key Assuming I encrypt data with AES-128 and a random 8-byte key x in the following way:

ciphertext = AES_128_ECB_ENC(plaintext, x||x)

So basically taking the 8 byte key twice to form the 128-bit AES key. Would it make it easier to guess x than the naive (max) $2^{64}$ tries, assuming you know a single plaintext-ciphertext pair?

Would it somehow be possible to reduce the key expansion steps of AES, due to the symmetry in the key?

In AES key schedule, firstly a round key x-ored with the plaintext before the first round. The used keys are $k_0, k_1, k_2, \text{ and},k_3$ where each has 32-bit. The next key used in the round key is calculated as follows;

\begin{align}
k_4 &= k_0 \oplus f_1(k_3) \\
k_5 &= k_4 \oplus k_1 \\
k_6 &= k_5 \oplus k_2 \\
k_7 &= k_6 \oplus k_3 \\
\end{align}

As you can see, with the first non-linear $f_1$, we have an avalanche effect that will affect the rest. There can be some cases that this kind of key produces bad keys that causes attack less than 64-bit security, but;

What is 64-bit security in today standards. Many super machines can reach $2^{64}$ very easily; Titan, summit. Also, the collaborative power of bitcoin miners reached $2^{92}$ SHA-256 hashes per year in 06 August 2019.

Also, if you look at some recent specially designed DES attack machines they reached to find DES key in 25 seconds in 2017, i.e. 56-bit reached 25 seconds.

In, short, even there can be attacks needs to be searched better than the brute force, that is only for enthusiastically as long as there is a hidden aim in your question. The luck of having such a key from good key gen is negligible.


HMAC based Key exchange Alice and Bob need to share public keys to sign/verify ephemeral keys. They have a secret key $K$.

Alice generates a 32 bytes random number $A$, computes $\operatorname{HMAC-SHA256}(K, M||A)$ and sends Bob the hash and plain $M$, $A$
Bob computes $\operatorname{HMAC-SHA256}(K, M||A)$ to check the hashes
If hashes match, Bob computes $N=\operatorname{HKDF}(A||K)$
Bob encrypts his public key $E_N(\mathit{PubKeyBob})$ using AES 256 GCM, and sends the cipher to Alice
Alice computes $N$ and decrypts the cipher, encrypts her public key $E_N(\mathit{PubKeyAlice})$, and sends Bob the cipher
Bob decrypts the cipher and they both have each other's public key

Is this a safe way to share public keys?

If they have a pre-shared key $K$ and want to authenticate public keys, the simplest way would be for Alice to compute $T = HMAC(K, PubKeyAlice)$ and send $(PubKeyAlice,T)$ to Bob.
This authenticates the public key of Alice. There is no need to encrypt it, since it is a  public value anyway.


Large text file encryption per line Some background:

I receive data in text files of over 16 million records (lines). I need to be able to encrypt the first column in that file so that it cannot be deciphered. This process will be carried out on two data sets with the same first column. The encryption on both these separate files will allow the two sets of data to be joined together on the encrypted column. One of these files is from our company and the other is a different company. When the join process is complete the column can be deleted. My boss wants a standalone application that can do this as it cannot be guaranteed that when we go offsite the company will have that software. He wants the encryption to be able to be carried out on the companies pc so that before we receive the data that column is encrypted.

Any help is appreciated.

EDIT

It's hard for me to describe this idea to you so bare with me.

Basically it will be one application that accepts a text file as input (this is because different sources will have different software and text files are the standard that everyone knows). The user then inputs a password and/or padding string for the encryption and then the application will encrypt the specified number of charters on each line of the text file and output that to another text file.

Example of input data:

|    ID    |    FName    |    SName    |    Number    |    Pcode    |
---------------------------------------------------------------------
|5364gfyue8|    Jason    |    Young    |   65782947   |   BT753HY   |
---------------------------------------------------------------------
|8472hgiek5|     Ben     |    Tops     |   87385942   |   BT439ES   |
---------------------------------------------------------------------
|0243hgqwl4|    Philip   |   Moore     |   73894769   |   BT641II   |

Example of output data:

|    ID          |    FName    |    SName    |    Number    |    Pcode    |
---------------------------------------------------------------------------
|85hftFHDYTE*=jcg|    Jason    |    Young    |   65782947   |   BT753HY   |
---------------------------------------------------------------------------
|5jgj59GUF55=hf4!|     Ben     |    Tops     |   87385942   |   BT439ES   |
---------------------------------------------------------------------------
|jhIOPfd5GF^83=3c|    Philip   |   Moore     |   73894769   |   BT641II   |

Here is the deal. You can do this pretty easily in SQL. Exactly how is off-topic on this site. I'd suggest one of the other SE sites. Maybe StackOverflow or DBA.

That said, I am writing this as an answer for a reason. My reason is to persuade you to not do it. Here is why, it gives your customers a false sense of security. Your approach to doing the join is to use deterministic crypto, AES in ECB mode or a SHA2 hash of the values in the column. The problem is, there is a one-to-one mapping from original plaintext to ciphertext. So, anyone who knows that mapping will be able to reverse the mapping.

So then the question is, who knows the mapping. Well, you do (and by you I mean your company). So it isn't really doing much to anonymize the data from your prospective. Also,
if you are giving your encryption software to your customers so they can run it on their machines, they can easily figure out the one-to-one mapping by reverse engineering your code (this is especially true if you use something like AES with a fixed key).

So, in short, I would suggest you don't do what you are planning on doing. As to what a better solution to the problem is, I'd suggest asking that as a separate question on here. Start by defining the problem with some examples and make sure you specify exactly what you want to protect and from whom you are protecting it.