In AES Keyschedule : Infer all round keys and cipher key from last round key I am given the last round key in AES and I want to infer all round keys and the first round key which is the cipherkey.

Can anyone provide an algorithm to do that?

For AES-128, it's easy (that is, so easy that there are hardware AES implementations that, in decrypt mode, just store the last round key, and derive all the other subkeys, including the first one, on the fly).

Let us treat the expanded key as a series of 32 bit words $w[0], w[1], w[2], w[3], ..., w[40], w[41], w[42], w[43]$, there $w[0], w[1], w[2], w[3]$ are the 128 bit AES key, and $w[40], w[41], w[42], w[43]$ is the last round key.

Then, the key expansion process is defined as $w[i] = w[i-4] \oplus F_i(w[i-1])$, where $F_i$ is a simple function that involves possibly sending the inputs through the sbox, and xoring in the round constant.  Starting with $w[0], w[1], w[2], w[3]$, this allows us to efficiently compute the rest of the $w$ array.

So, if we rewrite this as $w[j] = w[j+4] \oplus F_{j+4}(w[j+3])$ (which we get by setting $j = i-4$ and rearranging), then, starting with $w[40], w[41], w[42], w[43]$, we can compute $w[39]$ using this formula, and then work our way backwards through the key schedule, ending with the initial values.

For AES-192 and AES-256, it's actually pretty similar, except that you need more information than the last round key (which makes sense; there are only 128 last round key bits; not enough information to recover the full 192 or 256 bit key).  However, if you have the last 6 $w$ elements (for AES-192), or last 8 elements (for AES-256), the same logic works.


Does a hash function necessarily need to allow arbitrary length input? I always assumed that a hash function allows input of arbitrary length, since that's what all the hash functions I was aware of did. Wikipedia's definition of a hash function is as follows:

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

However, some functions like bcrypt, which label themselves as password hash functions, define a maximum size input length (in the case of bcrypt, 72 bytes). This seems like a contradiction, and has lead me to come up with two possible explanations:

Password hash functions, although similar in name, are not hash functions.
Arbitrary length inputs is not a strict requirement for hash functions, merely a common feature.

As such, I would like to know how to resolve this apparent contradiction. Is it necessary for a hash function to allow arbitrary length inputs or not?

Is it necessary for a hash function to allow arbitrary length inputs or not?

Of course not.  SHA-256 is limited to inputs of 18,446,744,073,709,551,615 bits or less; it is not defined for larger inputs; SHA-256 is not disqualified from being considered a hash function because of this limitation.


Is script execution time a decent source of pseudorandom number generation? This is for a PHP script for password generation.
Naturally there are other things being calculated before the password is generated.
But I figure the time it takes for the script to initialize and queue would make it decently pseudorandom.
Has there been studies on script execution time as a source of pseurandom number generation?

If not, any tips on how to conduct cryptanalysis on this?

AFAIK, there are papers that show, for example, that process times are not so random as they may seem. This is in the context of operating systems gathering entropy for devices like /dev/random. I've read this in many places but I can't provide any reference (if someone could it would be great ;-)).

Having said that, if you have other sources of entropy, script time could be an additional input, of course. Some considerations that come to my mind are:

Take care with the resolution of your time source: if the maximum resolution is minutes, it will probably return always 0.
Run some tests to see what results you get and how they are distributed. A usual distribution could be that 1 is returned 20% of the time, 2 30%, 3 30%, 4 20%, for example.

Depending on how you plan to use these "random values" these considerations may alter the results one way or another.

My advice is that you use a decent entropy generation algorithm instead of trying to invent your own. You can start your quest, for instance, here:

https://en.wikipedia.org/wiki/Fortuna_(PRNG)

See the reference links for more algorithms.


What is a SHA1_Compress() function? I'm trying to implement the scrypt key derivation function using JavaScript. When implementing the algorithm, I found that there was a function called SHA1_Compress listed in the specification. Is the function identical to a normal SHA-1 hash function? Or it is a totally different thing? I tried to search the term with Google but found nothing.

The function SHA-1 is defined on a message $m$ that is a sequence of bits.  It works as follows—this form is named Merkle–Damgård after the people who suggested it in days of yore:

Let $m' = m \mathbin\| 1 \mathbin\| 0^p \mathbin\| \operatorname{length}(m)$ be the result of padding $m$ with a one bit, $p$ zero bits, and a 64-bit message length, so that the length of $m'$ is an integral multiple of 512 bits.
Break $m'$ into 512-bit blocks $m_1, m_2, \dots, m_n$.
Compute $f(\cdots f(f(\mathit{iv}, m_1), m_2)\cdots, m_n)$.

Here $f\colon \{0,1\}^{160} \times \{0,1\}^{512} \to \{0,1\}^{160}$ is the compression function which compresses a 160-bit starting state and a 512-bit block into a 160-bit subsequent state, and $\mathit{iv}$ is the standard initialization vector.

In the case of SHA-1, the compression function is $f(h, m) := E_m(h) + h$ where $E_k$ is the SHACAL-1 block cipher—building $f$ out of a block cipher this way is called the Davies–Meyer construction.

The procedure SHA1_Compress computes $f$, the compression function that SHA-1 is built out of.  Since the $w_i$ are initialized as an output of SHA-1 itself, another way to look at the procedure described here is as an incremental computation of SHA-1—you might use a typical init/update/finalize style of API for this—which periodically treats the current state as a hash itself, which works because SHA-1 has no output filter.


Is every block padded with AES? I am looking at a tutorial on the Oracle Padding Attack, and I wondered, how do you find the rest of the blocks(not the last one), if there's only padding on 1 block?

Am I not understanding padding correctly?

Am I not understanding padding correctly?

You're not understanding the padding attack correctly.

Yes, only the last block is (typically) padded in CBC mode, however that doesn't mean that we can only attack the last block; what that means is that we can only use the last block.

In CBC-mode, the decryption of the block $i$ is computed as $P_i = D_k( C_i ) \oplus C_{i-1}$, where $D_k$ is the decryption using the unknown (to the attacker) key $k$.  Now, the attacker can see $C_i, C_{i-1}$, and so if he can deduce the value $D_k( C_i )$, he then has found the value of the plaintext block $P_i$.

So, what the attacker does is construct ciphertexts where the $C_i$ appears as the last ciphertext block $C'_n$, and he tries various values for the next-to-last block [1] $C'_{n-1}$; he submits those ciphertexts, and sees if, after decryption, the had valid padding.

Whether they do (mostly) depends on the last decrypted plaintext block, which is $P'_n = D_k( C'_n ) \oplus C'_{n-1}$; by trying various values of $C'_{n-1}$, he can deduce the value $D_k( C'_n )$.

Hence, this padding oracle attack can be used to decrypt any block, not only the last.

[1] The penultimate block, if you (like me) prefer to use the term 'penultimate' correctly...


How is an epsilon of 1/1000 non-negligible? Lately I've been studying cryptography and in the current course I'm taking we're reviewing statistical tests and how they can be used to determine if a pseudo-random generator is secure or not.

Essentially, one of the requirements for a Pseudo-random generator to be secure is that the probability of guessing the next bit in the string is less than 1/2 + a non-negligible epsilon (epsilon being any statistical advantage the computer has of guessing the next bit of the string due to insecurity in the PRG).

In an example the professor uses, he states that the probability of guessing the next bit of output from the PRG is 1/2 + 1/1000 (the non negligible epsilon).

How is 1/1000 non-negligible? I understand we're using computers with thousands of times faster processing power than a normal human brain, but that still means that a computer only has a 50.1% chance of guessing the correct bit. How can a computer leverage that tiny extra probability to crack a secret key?

How can a computer leverage that tiny extra probability to crack a secret key?

The answer to that depends on what type of key it is, how it's being used, etc. Certainly, the bias would make a brute-force attack easier, but you probably wouldn't need to worry about that, regardless.

Your professor, though, is trying to answer a different question. He wants to know, and wants you to think about:

  How small does the bias have to be in order to ensure that no one can leverage it to crack a secret key?

Note that this question is general: it makes absolutely no reference to what kind of key is being generated, or how it's being used. And this is how it should be: we're designing a general-purpose PRNG, so we shouldn't make assumptions about those things.

Suppose we used this PRNG to generate a 128-bit AES key. Well, assuming the bits are independent (but have the 1/1000 bias), then some math shows that the statistical distance between the result and a truly random 128-bit value is about 0.018. It follows if you used this PRNG in place of some mathematically perfect one, an attacker might be able to increase the chances of a successful attack by as much as 1.8% (but by no more than that).

Is this something you should be worried about? Well, if it's a 1.8% increased chance of someone decrypting a harmless IM conversation you had with a friend... probably not. On the other hand, if you're encrypting your bank password or a set of nuclear launch codes, a 1.8% increased chance of being compromised is probably an intolerable risk.

The 1.8% is an upperbound. We might not be able to find an attack that obtains that advantage. But by limiting the bias to something like 2^{-80}, we can safely stop worrying about the matter entirely.

The theorists would define a bias as "negligible" if it decreases "really fast" with respect to some adjustable parameter of the PRNG. This definition aims to ensure that we can always choose a value for the PRNG parameter such that (1) it's bias is quantitatively really small, e.g. 2^{-80}, but (2) the PRNG is still efficient.

Ultimately, however, you have to fix the parameter when you go and actually start  using the PRNG. At this point, you have to decide what concrete value of "negligible" you're comfortable with. This is a judgement call, but any reasonable PRNG will let you put it safely in the "we don't even have to worry about this" territory and still produce outputs as quickly as you could ask for.


Why does the CBC-MAC require PRFs? I'm stuck on exercise 4.19 from Introduction to Modern Cryptography.

  Let $F$ be a keyed function that is a secure (deterministic) MAC for
  messages of length $n$. (Note that $F$ need not be a pseudorandom
  permutation.) Show that basic CBC-MAC is not necessarily a secure MAC
  (even for fixed-length messages) when instantiated with $F$.

My idea was to construct the secure MAC $F'_k = m \| F_k(m)$, which would leak information on $F_k(m_1)$.
However, that would double the size of the MAC with every step.

Is there another/better/working solution?

Why are PRFs required for the CBC-MAC domain extension?

Edit: basic CBC-MAC refers to the following construction:

The book states that basic CBC-MAC is secure for fixed length messages when instantiated with a PRF.

The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be.
But ignoring this fact for a moment, one of your observations was indeed crucial.
A MAC does in general not hide it's input message.
As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure.
However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values.
And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle.
The CBC-MAC for our query will be computed as follows:
\begin{align*}
  t_1 :=& F_k(0^n)\\
  t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1)
\end{align*}
and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery.
We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$:
\begin{align*}
  t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\
  t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1
\end{align*}
And, given that $F$ is a secure MAC and it's output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$?
The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preseving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC.
Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$.
I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack.
For this, observe the values of $t_1,t_2$ in this instantiation.
\begin{align*}
  t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\
  t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1)
\end{align*}
I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$.
Therefore the attack sketched above works with this instantiation.


Tricking the Schnorr's protocol From the lecture notes I have learned the following:

$P \rightarrow V$: $T=g^t$ ($t$, randomly chosen from $Z_q$)
$P \leftarrow V$: $c$ (randomly chosen from $Z_q$)
$P \rightarrow V$: $s=xc+t \mod q$
$V$ accepts if $g^s=A^cT$, (where $A=g^x$)

Question: Can $P$ instead of sending $g^s$ send directly $A^cT$?

In other words, $P$ has all it need to generate $A^cT$ which is the same as $g^s$. Can someone explain what I am seeing wrong?

Well yes, $P$ can generate $A^cT$ and send it over, but why would it help?

The point of this protocol is that $P$ proofs to $V$ that it knows $x$, without revealing anything about $x$. The way that $P$ does this is that given some randomly chosen $t$ and a challenge $c$, it can compute an $s$ such that $g^s=A^cT$. The fact that $P$ can compute this $s$ proves knowledge of $x$ (note that $s=xc+t$). Anyone that does not know $x$, cannot compute $s$ (assuming some hard problem).

On the other hand, anyone can compute $A^cT$ given $A,c,T$, so this does not prove anything about knowledge of $x$.


Combining cascaded encryption keys into one key Is there an encryption algorithm where it's possible to combine multiple encryption keys into one, so that:

$E_{AB}(Data) = E_A(E_B(Data))$

KeyAB should be computable from KeyA and KeyB, but it must not be possible to compute or guess KeyA or KeyB from KeyAB and/or Data.

The algorithm should be as secure as possible, ideally asymmetrical (but if that's not possible, a good symmetrical one will also do).

XOR meets the above criteria, like so:
$KeyAB = KeyA \oplus KeyB$
$Data \oplus KeyAB = (Data \oplus KeyA) \oplus KeyB$

But XOR is obviously not a good crypto scheme, let alone asymmetrical. Are there any good alternatives for this particular use case?

For a crypto algorithm that acts like a group, the first thing that comes to mind is Pohlig-Hellman.  In this method, we have a large prime $p$, and define:

$$E_A(Data) = Data^A \bmod p$$

(with $A$ relatively prime to $p-1$)

This has the property that $E_B(E_A(Data)) = E_{A \times B \bmod p-1}(Data)$; however it has the security properties you're looking for; for example, given lots of $X, E_A(X)$ pairs, you can't recover $A$.

Now, this is a symmetric system (given $A$ and $E_A(Data)$, you can recover $Data$).  If you insist on an asymmetrical system, you might want to do this modulo a composite of secret factorization; only some who knows the factorization can then decrypt.  That version might be somewhat related to a better known asymmetric scheme...


Relying on a private public key for authentication I'm Alice, and I generate a public/private key pair. I securely & confidentially share my public key with Bob and Carol, who securely & confidentially share it with various other benevolent users – all of whom can now send me encrypted messages that only I can decrypt.

I'd like to authenticate that the encrypted messages I'm receiving are from users that have been legitimately sent my public key. Malicious Mallory has not been sent my public key, but has access to the network and can see the encrypted messages that I'm being sent. I need to ensure she cannot deduce my public key to send me malicious encrypted messages.

What do I need to look for in a crypto library to achieve this?

What do I need to look for in a crypto library to achieve this?

There are multiple options for this (from most to least desirable):

You want any public-key encryption scheme and any MAC algorithm and distribute as your public key, the encryption scheme's public key and the MAC key. Then you enforce that every message either has the MAC applied on the ciphertext correctly (proving possession of the key) or on the entire message and the MAC is then also encrypted.
You could also use static-authentication and a CCA2-secure public key encryption sheme (like DHIES, ECIES, RSA-KEM, or RSA-OAEP) and prepend a static secret to each message encrypting it as well. This heavily relies on the fact that an attacker cannot change encrypted messages meaningfully with CCA2-security and is "less clean" than using a MAC.
You can use a scheme that naturally hides the public key, e.g. DHIES or ECIES where one may only learn the group but no the public element from ciphertexts without breaking the encryption. Of course this is a much less common security notion, so one has to be careful whether a given scheme naturally satisfies it.


How was AES Encryption cracked on my app? I built an app that used AES encryption with 16 characters Key and IV.  It seems it could easily be hacked, as someone did it in a day.
I feel that I made a few mistakes

Used key & IV which was only plain text length of 16
Key not hashed with SHA-256
It was an Android app ( Xamarin Forms) and I did not obfuscate the app

Can anyone guide me on what went wrong?
[Updates]

The app needs to operate in offline mode. That's why I hardcode keys in the application.
This app is reading information from QR Code encrypted content. An attacker able to create a QR Code with fake information that becomes a valid QR code

If the characters are from $[A..Z]$ and $[0..9]$ then that makes 39 possibilities per character (byte). Then the keyspace will be $39^{16}$ and that is approximately 83-bit. This is space is achievable with supercomputers but not for ordinary people. Therefore, there must be something else around that cracks your system.

Used key & IV which was only plain text length of 16

That is not a good way.

The IV must random, though, your mode of operation is not clear therefore we cannot recommend the exact usage. In short, we can say that a (key,IV) pair must be used only once. You can use Android's secure random to generate the random IV.

For the key, one should go for the diceware or Bip39 to have good strength on the password. The user can still have a longer character than 16 so that at least 128-bit strength is achieved. With the password, the memory-hard password hashing algorithms like Argon2 to reduce the attack capability of the attackers.

Key not hashed with SHA-256

SHA-256 is not a password hashing algorithm we have Scrypt, PBKDF2, and Argon2 for those kinds of problems.

It was an Android app ( Xamarin Forms) and I did not obfuscate the app

This sentence indicates that probably you hardcoded the key into your application. And the attacker resolved the key by getting the package and analyzed the reversed byte code. This is not the correct way to store a cryptographic key.
If you want to communicate with your server use DHKE with your server to create the session key and possibly the IV by using the full exchanged key with HKDF. Then apply AES-GCM or ChaCha20-Poly1305 to achieve the authenticated encryption. In this way, you don't need to store secret keys. You only need the public key of your server. With this, you can achieve, forward secrecy, confidentiality, integrity, and authentication.
If you want to use app-in encryption, then get the password with a good strength from the user and derive the encryption key by using Argon2id.
You may also have the benefit of using the Android-KeyStore if that fits your needs.

updates

[Update] This app is reading information from QR Code encrypted content. An attacker able to create a QR Code with fake information that becomes a valid QR code

As Fgrieu mentioned that you can use a signed QR. To check the signature one only needs a public key.

If the content doesn't need to be encrypted, then there is no need for an encryption key.

If encryption is required, one can either install the key later and store it in the key-store or use a server-client approach so that the device doesn't use the key at all. The client either gets the key temporality from the server, or it can use the server as a decryption oracle while using a secure channel as told above.

[Update] The app needs to operate in offline mode. That's why I hardcode keys in the application

Installing the key later is the solution. You can install the key either manually in Android activity or use a specially designed QR code to read in then store it in the Android Key-Store.


Is the HMAC construction really neccessary for a fixed length message? The HMAC Construction is defined as:

Hash( (Key XOR opad) || Hash((Key XOR ipad) || Message) )

This was designed because a simpler construction such as:

Hash(Key || Message)

Is vulnerable to a length extension attack (but not for all hashes, a notable exception is SHA-3).

The questions are, what about cases where the message:

Is of a known, fixed length, and would be rejected if having any other length than the expected one (CBC-MAC, for instance, is secure for a fixed length message, but not for a variable-length one).
Is prepended with fixed-sized length indicator at very the beginning of the message (i.e. the extended message would be Fixed-Sized Length indicator||Message and the hash would be: Hash(Key||Fixed-Sized Length indicator||Message)).
The same scheme as the previous one but where the length indicator is only included within the hash.

(these may be completely different cases so consider them separately).

Note that for (3) an alternative configuration Hash(Fixed-Sized Length indicator||Key||Message) would guarantee that the length indicator is included in the first block of the hash - I mean, even for a huge key that is larger than the hash function block length. The length indicator would probably not need to be any more than 64bits of size (as most [older] hashes are limited to a maximum message size of 2^64 - 1 bits anyway). This makes it very hard to imagine how can it be insecure? But I'm not a cryptographer, I guess.

In summary: Yes, HMAC is the way to go for construction of a MAC from an arbitrary concrete iterated hash. We have no constructive argument of security of the MAC constructs in the question; we even have a concrete attack when using some otherwise apparently fine hashes.

I consider a hash constructed by iterating a compression function $F$ as $s_{i+1}=F(s_i,m_i)$ with $s_i$ of $h$ bits (also the size of the MAC), message blocks $m_i$ of size $b$, perhaps with Merkle-Dåmgard strengthening (this matches MD5, SHA-1, SHA-2, but not Keccak/SHA-3); I also assume Key is of fixed size, enters $m_0$, and the third construct is Hash(Fixed-Sized Length indicator||Key||Message).

Under the assumption that $F$ is an ideal PRF, the three constructs in the question appear to be secure, but perhaps to some sub-optimal degree. The best general attack (that is, valid irrespective of the details of the iterated function) that I see is to obtain the hash of messages of equal size (at least $\max(2b,h)+b$), with the beginning of the message random and the last message block fixed, until a collision is found between distinct $m_0$ and $m_1$ (which requires $\mathcal O(2^{h/2})$ MACs); then obtain the MAC of $\widetilde{m_0}$ with the last bit toggled; that MAC will stands a good chance to also be valid for the similarly modified $\widetilde{m_1}$. That's a valid attack against the MAC. It works because the collision between the MACs for $m_0$ and $m_1$ stands a good chance to have occurred before the last block, and in that case $\widetilde{m_0}$ and $\widetilde{m_1}$ will necessarily collide too.

The above generic attack does apply to HMAC (and CBC-MAC, and any iterated MAC with a single pass). However, HMAC (contrary to the other constructs) comes with security arguments that there is no asymptotically better attack, and even arguments valid with relatively weak assumptions on the iterated function; see Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, with extended abstract in proceeding of Crypto 2006.

The security arguments of HMAC, and the fact that the key enters both at the start and the end of the computation (which in turn insures, in the above attack, that the attacker does not get to know the colliding value), gives us a security margin. I'm reasonably confident that HMAC-MD5 won't be practically broken (excluding attacks on implementations such as DPA or injected faults) for some years, but I'm not so confident for MACs constructed from MD5 as in the question. Addition: there's a lot of truth in the saying: better safe than sorry.

As an illustration of the superiority of HMAC, we can make an iterated hash such that the three constructs are weak, but HMAC remains strong. An example is SHA-256 modified by removing the 8 additions modulo $2^{32}$ in the 4th (last) step of a round (making that $H_0^{(i)}=a$, .., $H_7^{(i)}=h$). If there's an attack against the collision-resistance, or (first or second) preimage resistance of that modified SHA-256, I fail to see it (update: on second thought, the best I see is a preimage attack similar to this, with cost about $2^{128}$ rather than $2^{256}$ for full SHA-256). However, in the constructs of the question, from a single message/MAC pair, it becomes easy to compute the MAC for any message of the same length differing in blocks after the first (notice that for known blocks and output, it is possible to walk back the hash states). [Addition following strongly critical comment: A key point of my reasoning is that the security argument of HMAC seems to apply when using that modified SHA-256; I'll concede a gap if it irreparably does not; or if since there's a widely accepted definition of security of a hash that this modified SHA-256 fails (quantitatively  at least), but SHA-256 pass (notice that SHA-256, contrary to Keccak/SHA-3, trivialy fails widely accepted definitions of security due to the length-extension property)].


What is the difference between synchronous stream ciphers and asynchronous stream ciphers? What are the benefits and drawbacks of each?

With synchronous stream ciphers, the bits of the key stream do not depend on the ciphertext bits. With asynchronous stream ciphers the key stream can be inferred (provided one knows the secret key) from previous bits of the cipher stream. If you're familiar with block cipher modes CTR would be an example of a synchronous streaming mode and CFB would be an example of an asynchronous mode.
Synchronous ciphers have the advantage that key stream can be pre-computed before plaintext or ciphertext is provided, often with parallelism. They have the disadvantage of ciphertext malleability (a known change in ciphertext produces a known change in plaintext) and so will need to be combined with some form of message authentication. If a transmission is only received in part, in can be difficult to recover the fragment as the exact position in the key stream needs to be identified (synchronisation). Synchronous ciphers are also deterministic constructions with a finite number of possible states and so will eventually cycle. Care must be taken in their construction/initialisation to make sure that short cycles are unlikely. For most stream ciphers (e.g. those combining key and plaintext by XOR) chosen ciphertext is equivalent to chosen plaintext in the information provided about the cipher which simplifies the security modelling. With no ciphertext dependency two different plaintexts encrypted with the same key are added to the same keystream which leads to significant weakness.
Asynchronous ciphers are largely serial in the encryption process (though not necessarily the decryption process) and the key stream can only be computed once the plaintext/ciphertext is provided. However, changing the ciphertext changes subsequent key stream and so there is considerably less malleability and a degree of message authentication. They also allow easy synchronisation at any point in transmission as the receiver can infer key stream after an initial run up of cipher bits (self-synchronisation). Asynchronous ciphers can always be provided with plaintext that prevents cycling and so no special cycle analysis is required. However chosen ciphertext has an effect on keystream and so CPA and CCA must be considered separately. Distinct plaintexts will lead to distinct keystreams, reducing the danger of repeated keys.


Rotor that divides binary number by mod 3 Let's say we have transformer(?) A = $\{0;1 \}$, B = $\{0;1\}$, $Q = \{q_0,q_1,q_2\}$, where A - plaintext alphabet, B - encryption alphabet, Q - the set of states. The functions of the rotor are described as:
$$q0 ◦ 0 → q0 \ \ \ q0 ∗ 0 → 0 \\
q0 ◦ 1 → q1 \ \ \  q0 ∗ 1 → 1 \\
q1 ◦ 0 → q2  \ \ \ q1 ∗ 0 → 2 \\
q1 ◦ 1 → q0  \ \ \ q1 ∗ 1 → 0 \\
q2 ◦ 0 → q1  \ \ \ q2 ∗ 0 → 1 \\
q2 ◦ 1 → q2  \ \ \ q2 ∗ 1 → 2$$
And the function which it executes is mod 3. Does it only work for determined length of plaintext? What algorithm is behind this scheme?

This is not really a cryptographical question, but rather a (rather simple) question about a finite automata.
This is a state machine; you feed in the bits of the number $n$ you're modding, starting at the msbit (and starting at the state $q0$).  After processing the number, if the state you end up in is $q0$, then $n \equiv 0 \pmod 3$, if you end up in $q1$, then $n \equiv 1 \pmod 3$, and if you end up n $q2$, then $n \equiv 2 \pmod 3$.

Does it only work for determined length of plaintext?

No, it'll work for any size integer.

What algorithm is behind this scheme?

Well, I suspect it's too simple to have a formal name.  The property that always holds is that, after processing an intermediate integer $\hat{n}$ (which has the binary representation of the bits you're processed so far), if $\hat{n} \bmod 3 = i$, then you'll be in state $qi$.
Here's how that property is preserved: assume that property holds at some point.  Then, when you process the next bit $j$ (which means that you will have processed the intermediate integer $2\hat{n} + j$, it will transition to state $q(2i+j \bmod 3)$ (you can verify this by manually going through the state transitions).  And, since $2\hat{n} + j \equiv 2i+j \pmod 3$, this preserves the above invariance.  Since we start with the property holding (that's why it's important we start at state $q0$), it holds no matter how many bits you process.


Using plain Diffe-Hellman for server authentication with known public key Other considerations aside, is it possible to use DH with an established public key (together with fixed g, p, q) to safely authenticate a server instead of using some signing algorithm?

In other words, we will replace $SIG_S(Data)$ in some protocol with this scheme. The steps described below can be merged with whatever protocol is used, so it doesn't need to add more steps.

Client $C$ knows $g$, $p$, $q$ and $g^s$.

$C \rightarrow S : \{ g^c \} $
Server generates a random value $N_S$.
$K \leftarrow KDF(N_S, g^{cs})$
$S \rightarrow C : \{ N_S, HMAC_K(Data) \}$ where $Data$ is the relevant data signed in the protocol we're modifying.
$C$ constructs $K$ and verifies that the HMAC calculation matches.

Assume that none of $K$, $N_S$, $g^s$ or $g^c$ is ever recycled for any other use (such as key generation).

What I wonder is if this would be an acceptable replacement for signing with DSA/RSA/etc to prove identity in this particular setup.

Examples:

Plain STS with server authentication only

$C \rightarrow S: \{ g^x$ }
$S \rightarrow C: \{ g^y, S, \{ SIG_S(g^x, g^y) \}_{K_s} \}$

Plain STS modified

$C \rightarrow S: \{ g^x, g^c \}$
$S \rightarrow C: \{ g^y, S, \{ N_S, HMAC_K(g^x, g^y) \}_{K_s} \}$

Plain SIGMA with server authentication only

$C \rightarrow S: \{ g^x$ }
$S \rightarrow C: \{ g^y, S, SIG_S(g^x, g^y), MAC_{K_m}(S) \}$

Plain SIGMA modified

$C \rightarrow S: \{ g^x, g^c \}$
$S \rightarrow C: \{ g^y, S, N_S, HMAC_K(g^x, g^y), MAC_{K_m}(S) \}$

An adversary can (repeatedly) submit $h$ as $g^c$ to get a random $N_s$ such that the adversary will

be able to test, with heuristically overwhelming accuracy, whether or not $\: \operatorname{KDF}(N_s,h^s) = x \;$.

An adversary could also attempt to learn something more about what session key the

server obtained, by sending an alleged ciphertext to the server after the key agreement.

(In particular, an adversary could do those things after seeing the client's actual value of $g^c$.)

It would be tricky to show security against such an attack without also showing

security against the case where, for each $h$ value, the adversary will learn

$\langle N_s,\operatorname{KDF}(N_s,h^s)\rangle\:$ for a random $N_s$ (chosen after the adversary chose $h$).

Such a security result would be somewhat analogous to CCA2 security; the analogy would be better

if $N_s$ was the same each time. $\;\;$ Unlike when I previously addressed a similar construction, I am now convinced that this will hold under $\:$KEA1 + KDF-is-a-random-oracle + computational-diffie-hellman$\:$ .

Under those three assumptions, the key agreement will be secure against an adversary

that can choose the server nonces $N_s$, including the ability to cause them to repeat.

The four signing algorithms that you might prefer over the above are BLS,BB,ECDSA.

(That's four because the middle one gives a variant that does use a random oracle.)

However, there are potential efficiency improvements that can be

obtained for only a known and very minor decrease in security.

In particular, in three of your four examples, it will only decrease security against an

active adversary that nonetheless does not have reliable communications with both honest parties.

For the first example and the last two examples, the encryption or MAC with $K_s$ or $K_m$ respectively

will defend against an adversary that [can modify a message in transit but will later

be unable to communicate with either $C$ or $S\hspace{.02 in}$] carrying out a "weak misbinding".

(I use the term "weak" because that is something an adversary with full control over

the communiations channel can necessarily do, no matter what protocol is used.)

Furthermore, for the first example, the encryption won't necessarily

succeed at that goal, although I suspect that it heuristically should.

For STSsao, encrypting the signature will (also) stop a passive eavesdropper

from being able to show that the server carried out a key agreement.

Those are the only reasons to use $K_s$ and $K_m$.

If one declines to use the relevant key, then one obviously should also not derive that key.


Symmetric cipher key size vs number of rounds. Longer key = more secure cipher? I would have questions related to discussion under this article.
Bruce Schneier answered questions regarding key size vs number or rounds:

  Why do you need more rounds with longer keys? And how did you come up with these seemingly arbitrary numbers for more rounds?

  When block ciphers get broken, they're invariably broken due to
  diffusion failures. What more rounds give you is more diffusions ...
  the key is twice as long, so it takes more rounds to get complete
  diffusion of the key.

  As to your second question, choosing the number of rounds for a cipher
  is a combination of experience and guesswork.

For example Threefish 512 has 72 rounds and Threefish 1024 has 80 rounds.

I would like to know your opinion on theses questions:

If Threefish 1024 would have only 72 rounds (as Threefish 512), could it be in some way less secure than Threefish 512?
If the number of rounds is a "guesswork", could Threefish 1024 (full 80 rounds) be still less secure than Threefish 512 (72 rounds), because of "incorrect guesswork" (8 additional rounds wouldn't be enough to provide more diffusion to maintain the longer key)?

With enough plaintext/ciphertext available (sizably more plaintext than keysize), any cipher can be attacked by trying all the keys; that's brute force. Therefore, for any cipher, too short key ⟹ insecure cipher.

A common symmetric cipher design goal is that the best attack is brute force as limited by key size, within a small factor. Therefore, for a symmetric cipher meeting that design goal, longer key ⟺ more secure cipher.

A common block cipher design goal is that it is as fast as possible while meeting its security level (matching its keysize per the previous goal). Increasing the number of rounds can make a cipher more secure, but does make it slower. Hence, for a cipher design meeting its security and speed design goals, more secure cipher ⟺ more rounds.

There is no definitive method to find the adequate number of rounds. A typical approach is to examine known attacks; try to make conservative estimate of how many rounds they can break for some security level and extrapolate to the desired security level (perhaps much higher); then take the largest number of rounds found for all attacks, and then some as a design margin.

I pass at the Threefish aspect of the question.


Name of the hash algorithms and create an unhash function Below is a function to hash a string into a number. I'm curious what would be the name of the below hash function and what would be best approach to create an unhash function to turn the number into a string (ex. 61752 to abc)?
function hash(str){
    const letters = "abcdefghijklmnopqrstuvwxyz"

    let h = 9

    for (let i = 0; i < str.length; i++) {
        let v = letters.indexOf(str[i])
        h = h * 19 + v
    }

    return h
}

console.log(hash("abc")) // will return 61752

EDIT - Per the helpful comments, this question involves a sort of broken base19 conversion with redundant characters from t through z.  As such the below does not reverse for any letters after 's'.  It could be fixed but I presume the question is just an intellectual exercise of some kind anyway.  It obviously is NOT a hash, nor is it an efficient coding system, snugly fitting 8 characters in a less than handy 34 bits.
From my rather layman point-of-view, it was difficult to initially spot as a base19 conversion due to the fact it's backwards (we treat the initial string as base19) and because of the way it multiplies 19 in a loop rather than explicitly $19^i$ (yeah I know...).

To reverse up to 's':
$61752 \mod 19 = 2$
We then take the rounded down result of 61752/19
Were left with $3250 \mod 19 = 1$
We then take the rounded down result of 3250/19
Were left with $171 \mod 19 = 0$
Here it is in Javascript
function rehash(str){
const letters = "abcdefghijklmnopqrstuvwxyz";var out="";

while (str>9) {
  out = letters.charAt(str%19) + out;
  str=Math.floor(str/19)
}
return out}


For discrete elliptic curves, can you find G, if you are given b and B? I know you cannot find $b$ if you are given $B$ and $G$, where $B = [b]G$,

but can you find $G$ given $b$ and $B$?

$G = [b^{-1} \bmod q]B$ where $q$ is the order of the group generated by $G$, assuming $\gcd(b, q) = 1$.


Diffie-Hellman, random number size During the key exchange, Alice and Bob both select a random natural number.

The question is how big this integer is? How many digits/bits it must have at least/most?

I'll assume the question asks: in the Diffie-Hellman key exchange protocol, how large does the secret random natural number that Alice and Bob each select needs to be.

It can be used a newly generated cryptographically secure random integer $x$ of 256 bits. This is conjectured safe for sound parameters (detailed below) and protocols used in practice. That's possibly good for a few decades, not accounting for mathematical breakthrough, nor hypothetical quantum computers usable for cryptanalysis.

PKCS#3 v1.4:1993 (official home) allows this, with an optional parameter $l$ length of private value in bits. When this option is used, $2^{l-1}\le x<2^l\;$ (with this option, PKCS#3 uses $x$ of fixed bit length, perhaps to reduce leakage by timing analysis). The modern Java CryptoAPI also has an $l$ parameter.

This practice is used in the Internet Key Exchange protocol of RFC 2409 with parameters of RFC 3526. It limits the cryptographic resistance to at most $O(2^{l/2})$, but, conjecturally, not significantly further down if the order of the generator used is a prime $q$ of at least about $l$ bits (or twice such a prime), which to my knowledge is met by all recommended DH parameters. See Paul C. van Oorschot and Michael J. Wiener, On Diffie-Hellman Key Agreement with Short Exponents, in proceedings of Eurocrypt 1996, which gives justification and a narrower criteria.

Choosing a larger bound for $x$ does not harm (demonstrably: by more than one bit of security), except for speed (execution time is roughly proportional to the bit length of $x$, all other things being equal). The absolute maximal security is obtained when $x$ is uniform on an interval of width equal to the order of the generator, but for some recommended DH parameters this comes at significant performance cost.

Note: This answer has been considerably expanded, following constructive criticism of an earlier version. I now stress that the above statement is relying on a stronger (thus mathematically less certain) assumption than a pure Diffie-Hellman assumption, and detail the conditions conjectured sufficient to ensure that a short exponent is secure.

The simplest form of Diffie-Hellman key exchange protocol works in the multiplicative group modulo some suitable public prime $p\;$ (the group $\mathbb Z_p^*\;$), using some suitable public member $g$ of that group. Alice (resp. Bob):

selects a random integer $x_a\;$ (resp. $x_b\;$) less than the bound $m$ discussed; the lower bound for $x$ can be $0\;$, $1\;$ (Handbook of Applied Cryptography Protocol 12.47), or $m/2\;$ (PKCS#3 with optional parameters $l$ and $m=2^l\;$);
computes and sends $y_a\;=\;g^{x_a}\bmod p\;$ (resp. $y_b\;=\;g^{x_b}\bmod p\;$);
receives $y_b\;$ (resp. $y_a\;$);
computes $z_a\;=\;{y_b}^{x_a}\bmod p\;$ (resp. $z_b\;=\;{y_a}^{x_b}\bmod p\;$).

Assuming that the messages have not been altered during the exchange, $z_a=z_b\;$. Both are $z\;=\;g^{x_a\cdot x_b}\bmod p\;$. For proper choice of $p$, $g$ and $m$ it is believed computationally infeasible to determine that common $z\;$ from knowledge of $y_a$, $y_b$, $p$ and $g\;$. That $z$ can then be used to establish a common symmetric secret key using a Key Derivation Function (beware that this protocol is vulnerable to a Man-in-the-Middle).

An $l/2$-bit security level requires choosing an upper bound $m$ at least $O(2^l)\;$. That's because regardless of parameters $p$ and $g$, there are generic attacks recovering $z$ in full with cost $O(2^{l/2})$ modular multiplications. One such attack finds $x_b$ from $y_b$, by precomputing $y_b\cdot g^u\bmod p$ for $u<2^{l/2}$, then searching $(g^{2^{l/2}})^v\bmod p$ for $v\le2^{l/2}$ among that; once a match is found, it comes $x_b\;=\;v\cdot2^{l/2}-u\;$; and $z$ is then computed as ${y_a}^{x_b}\bmod p\;$. There are better methods requiring much less memory, but we know no method requiring much less time and still generic (that is working for any $p$ and $g$, and more generally any group used for a generalized Diffie-Hellman key exchange protocol).

Common wisdom is that baring mathematical breakthrough or quantum computers usable for cryptanalysis, and with otherwise sound parameters, random-enough primes $p$ of 3072 bits can give about 128 bits of security. Beyond that, various practices exist for the choice of $p$, $g$, and $m\;$.

It can be used a safe prime $p\;$ (that is, such that $p=2q+1$ with $q$ a prime), and $g$ a generator of $\mathbb Z_p^*\;$ (a positive integer such that $g^q\bmod p\ne1\;$); and bound $m=p-1\;$. This works in the group $\mathbb Z_p^*\;$, which has even order $p-1\;$. Noticeably, a passive adversary can find whether the common $z$ is a quadratic residue modulo $p$ or not, which leaks ≈0.81 bit of entropy. This is a non-issue when $z$ is post-processed by a proper KDF.
As a variant it can be used $g$ of order $q\;$ (that is with $g^x\bmod p$ taking $q$ distinct values for unbounded $x\;$, which can is insured if $g^q\bmod p=1\;$ and $g\bmod p\ne1\;$), and bound $m=q\;$; or equivalently it can be used $g$ and $m$ as in [1.] above, but with restriction to even $x\;$. This is relying on a pure Diffie-Hellman assumption in the group of quadratic residues modulo $p\;$, which has prime order $q=(p-1)/2\;$. It is demonstrably as secure as [1.] is.
It can be used a prime $p$ such that $p=q\cdot r+1$ where $q$ is a prime of about $l$ bits; and $g$ of order $q\;$, which is equivalent to $g^r\bmod p\ne1\;$; and $m=q\;$. This is relying on a pure Diffie-Hellman assumption in a Schnorr Group of prime order $q$ of about $l$ bits. Common wisdom is that it offers about $l/2$ bits of security for small $l$; thus with a $p$ of 3072 bits, using $q$ of about 256 bits is believed not to harm security compared to $q$ of 3071 bits in [1.] or [2.] above. There's a speedup by a factor of nearly 12, which the applied cryptographer loves (even though Schnorr groups create complications for authenticated variants of the Diffie-Hellman key exchange protocol, where an active adversary could try to sneak in $y$ not member of the Schnorr group).
As a variant of any of the above three practices, and as suggested in the first part of the present answer, it can be chosen $m=2^l$ (and $m/2\le x<m$ in a PKCS#3 context).

When [4.] is combined with [1.] or [2.], we have the speedup of [3.] with $p$ still a safe prime. With $l$ large enough, there is no known reduction in security compared to [1.] or [2.]; but we do not know for sure how large $l$ should be. I see no argument to assert if at equivalent $l$, the security is more or less than the security of [3.] alone, which is commonly used.

When [4.] is combined with [3.], there demonstrably can't be a significant reduction in security compared to [3.] alone: no more than $\max(\log_2(q)-l,0)+1$ bits worth could be lost.

When using one or both of [3.] or [4.], the upper bound $m$ for $x$ is typically 160 to 512 bits, further with $m=q$ when not using [4.]. Otherwise (when using [1.] or [2.] without [4.]) the bound is typically per $p-1$ or $q$, thus 1023 to 4096 bits (though $p$ of 512 bits has been used, including as intentionally weakened cryptography).


Proof of correctness of Exponential ElGamal I have an assignment for proving the correctness of both ElGamal and exponential ElGamal homomorphic features (multiplicative and additive respectively). I have managed to prove the former but am struggling on proving the latter. I have reached the point where adding two ciphertexts $c_1$ and $c_2$ to obtain $c_3$, where:

$$c_3 = (a^{r_1} + a^{r_2}, m_1+m_2(b^{r_1} + b^{r_2}))$$

Have I gone completely wrong?

Yes,you got it wrong on this one. Most importantly, ElGamal is defined on a group in general, but you kind of mixed the additive notation with the multiplicative notation.

First, when writing ElGamal over a multiplicative group $(\mathbb{G},\times)$ as you did, we do not generally assume any additional structure on top of the group structure - hence writing $a^{r_1} + a^{r_2}$ does not make sense in general.

Second, in multiplicative notations, a ciphertext looks as follow: $c_1 = (a^{r_1},b^{r_1}\cdot a^m)$. You can write it $(r_1\cdot a, (r_1\cdot b)+(m \cdot a))$ if you want to use additive notations instead, but none of these notations will lead to the $c_3$ you obtained.

Hint for the solution: use the group operation to "merge" group elements, do not try to add up objects of the form $a^{r_1}$ and $a^{r_2}$, this will not lead you anywhere. Using multiplicative notation, you should make use of the following observation: $a^{m}\cdot a^{m'} = a^{m+m'}$.


How is the usual way of using PKCS5/7 when a weird data is given? PKCS5/7 pads the remaining data elements with a binary representation of how many space requires padding. This is useful and compact but what should I do in the following sample scenario below ?

Example:
Use case scenario is to use AES or any fixed length 128 bit block cipher to encrypt user supplied data where the user can have control over the bytes sent and not limited to any sort of language format (i.e. UTF-8).

The user send the following bytes 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 (16 pieces of 0x05 bytes) to be PKCS5/7 encoded before AES encrypted. The PKCS 5/7 encoder would not do anything since it has all 16 bytes (1 block size required by AES cipher).

When the user wants to decrypt the data, the AES decryption succeed but the PKCS5/7 padding engine see 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 (16 pieces of 0x05 bytes).

If 5 pieces of 0x05 bytes are removed and simply returns 11 pieces of 0x05 bytes, this will mean the original data which is 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 would be corrupted at the PKCS decoder level.

What is the best way to handle data arrays that have all the same elements in a PKCS5/7 padding scheme when decoding data ?

The PKCS 5/7 encoder would not do anything since it has all 16 bytes (1 block size required by AES cipher).

That's where you're wrong.

Padding should be always applied. If the user is encrypting a plaintext that is already a multiple of the block size, then the PKCS#5/#7 padding schemes will add an additional full block of padding, so that there is no ambiguity when decrypting.

In your example, that would mean this is the padded plaintext that is encrypted:

05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

There are of course padding schemes that don't add an additional block (for example PHP's zero padding), but that's not how PKCS#5 or PKCS#7 works.


Discrete logarithm problem - Pohlig Hellman $GF(2^p)$ I would like to ask how to modify Pohlig Hellman algorithm if I need to work with polynomials $GF(2^{60})$ I know how this algorithm works with numbers, but I am not able to imagine how to do some operations with polynomials. E.g. if I need to do $g^{\frac{p-1}{q^e}}$. How can I do this with polynomial?

A field like $GF(2^n)$ is represented by the residue classes of polynomials modulo $f(x)$ where $f \in GF(2)[x]$ is an irreducible polynomial of degree $n$ with binary coefficients. There are $2^n$ such polynomials $$a(x)=a_0+a_1 x+ \cdots+ a_{n-1} x^{n-1}.$$

Addition is by mod 2 addition of coefficients. When you multiply two polynomials, you take the remainder of the product modulo $f(x)$.

You can use square and multiply (see here) to compute the power
$$a(x)^k=a(x)^{k_0+2 k_1+ 2^2 k_2+ \cdots+ 2^t k_t},$$
taking care to reduce modulo $f(x)$ from time to time, so the degrees of the squares don't get too large.


Password hashing in /etc/shadow Passwords hashed under Unix/Linux systems can use several hashing algorithms.

      ID  | Method
      -------------------------------------------------
      1   | MD5
      2a  | Blowfish (on some Linux distributions)
      5   | SHA-256 (since glibc 2.7)
      6   | SHA-512 (since glibc 2.7)

I'm interested in how UNIX uses blowfish to encrypt the password. Is it bcrypt like (and in fact hashing and not encrypting) where the key is derived from the password, expanded and then used to encrypt the password itself several times, finally yielding a hash?

This "Blowfish" is actually bcrypt itself. Bcrypt was defined by reusing elements of the Blowfish block cipher, but modified. In particular, the key schedule part of the algorithm is expanded into a huge (and configurable) number of rounds.

The password (combined with the salt) is used as key for this modified Blowfish. Once the key schedule has been completed, the modified Blowfish is used to encrypt three blocks, normally the ASCII encoding of the constant string "OrpheanBeholderScryDoubt" (Blowfish, and the modified variant used in bcrypt, work on 64-bit blocks; ECB mode is used; so this yields 192 bits of output).

The man page is misleading, in that it both says that it uses Blowfish (it doesn't, it is a Blowfish variant which is distinct), and that it is encryption (it isn't; it is hashing, as you state).


Multi Factor Encryption? I got an alert last night to the keywords above and was curious, so took a look at the tor site flagged which is the following one:
http://nsrz5iogimqwgeax3clpp6hvfy6viom2woy7dghgxes4sqk63r7svoqd.onion. Obviously you need TOR to access it or a service like Tor2Web though reachability is spotty.
I'm asking SE because these guys are claiming to offer a cipher strength I've never heard of. I'd like to ask if you think it's even possible.
This question is about the encryption scheme "Blobby" presented on their site and the security claims surrounding it.
The first notation they use is $10^{yM}$ which I didn't get, but just below is an example $10^{41485806}$, which seems obscene with the unit to of the previous number being "operations", which can be inferred from them stating a relative strength of $10^{38}$ for AES-128 which is roughly $2^{128}$.
Now that I've have longer to look at it, it feels less impossible (though still a stretch), I think the key size and password length are important, but I suspect they're using a third mutagen.
The key claim of novelty for this encryption scheme is that both a nearly-arbitrary sized password (20-$2^{12}$ chars) and an arbitrary sized key ($2^{16}$-$\infty$ bit) are necessary for symmetric operation yielding "multi-factor security" with their custom encryption scheme. The precise quote is

Blobby is fundamentally different, the password is used in conjunction with the key, meaning that each is useless without the other, and attacking the key's password won't get you any closer to the message password.

If their claim is solid, would this be quantum resistant?
I have now downloaded the 3 sample files and looked at them, they are clearly encrypted. I've been trying the first sample for over 24hours now with not a whisper of joy.

Oh boy. Snakeoil at its finest.

This question is about the encryption scheme "Blobby" presented on their site and the security claims surrounding it.

Inventing and selling completely new symmetric encryption? One of the best indicators for snakeoil.

The first notation they use is $10^{yM}$ which I didn't get, but just below is an example $10^{41485806}$, which seems obscene with the unit to of the previous number being "operations", which can be inferred from them stating a relative strength of $10^{38}$ for AES-128 which is roughly $2^{128}$.

It seems they use big numbers for the sake of using big numbers and impressing people. For all practical purposes nothing beyond 256-bit security matters unless you want to invest the entire energy of the sun for most of its lifespan into breaking it. Double that number if you want to go "sure" against quantum computers thanks to Grovers provenly optimal search algorithm.

If their claim is solid, would this be quantum resistant?

It could be that their scheme is quantum-resistant. Symmetric crypto is rather easy to get quantum-resistant. But we don't know until they actually publish a description and even then we might not know because people won't care enough to analyze this scheme.

I'd like to ask if you think it's even possible.

Yes, you can build multi-factor encryption and you can build it nicely out of standard cryptographic primitives.
Now for the actual question you are probably having: "Ok, this is all snakeoil they're trying to sell me and you're saying that we don't need this, so how would you do it in practice?"
Well turns out people already did look at this problem, i.e. how to combine something that you know (like a password) with something that you have (i.e. a pre-generated key, a key-file or a security token).
My favourite three examples for this are the softwares VeraCrypt, BestCrypt and KeePass, which all handle this in a different way.

VeraCrypt will essentially mix your keyfile(s) with your password using their funky custom hash function and then run this through standard password-based key derivation. A random salt from the ciphertext will still be used.
BestCrypt will hash each of your keyfiles individually and then sort the hashes and prepend the hashes to the salt before key derivation.
KeePass will hash your keyfile and concatenate it with your password before feeding that into the password-based key derivation. A random salt from the ciphertext will still be used.

Obviously you need both inputs in all three cases to mount a brute-force / dictionary attack. Also note that any attack that would allow you to recover the password-based key derivation input without actually doing the forward iteration would be considered a major publication-worthy break. And yes there are publications that show that for standard password-based encryptions the optimal strategy is to search the password space or guess a secret symmetric key, the best one of which is probably by Bellare, Ristenpart and Tessaro (Theorem 3.4).


Can ECDSA key pairs be added up or multiplied? I have been given a public key ($y_1=x_1G$), but I don't yet know the private key ($x_1$). At a later time, I will get $x_1$ if some conditions are met.

Question:

Let's say I generate a new key pair $( y_2, x_2)$, both of which I will know.

Is it possible to add up these key pairs?

$ y =  y_1 + x_2G$
$ x = x_1+x_2 $

Let's say (before I have $ x_1 $) I encrypt a text with $y$. And let's say I get $x_1$ at a later date. Can I decrypt my text using $x$ (by adding up the private keys)?

Let's use ECDSA key pairs. Sorry if my question is somehow deficient, but I just started to study cryptography. You would help me a lot by clarifying this question. Best, Stan

Is it possible to add up these key pairs?

Yes. If $y_1=x_1\times G$ and $y_2=x_2\times G$, then
$$y_1+y_2=y_1+(x_2\times G)=(x_1+x_2)\times G$$
and that's a public key matching private key $x=x_1+x_2$.

  Let's say (before i have $ x_1 $) I encrypt a text with $y$. And let's say I get $x_1$ at a later date. Can I decrypt my text using $x$ (means by adding up the private keys)?

Yes, that follows from the above.

Note: there's no multiplication of key pairs as in the title, in the sense of an operation on keys yielding a new key (unless we note the group operation on the Elliptic Curve multiplicatively, which the question does not). With a group operation noted additively (as the question does), the only well-defined operation between public keys / group elements is addition, and we can only multiply these by a scalar (integer).


SPDZ- How to do secure less-than comparison The SPDZ paper explains how the SPDZ protocol can be used to find the sum/product of secret values and find the sum/product of a secret and a non-secret value (page 6).

The paper seems to say that from this you can do any other operation. How would you use this to do secure less-than comparison?

The Bristol SPDZ implementation tutorial program (line 19) shows that their implementation has a way of securely comparing two secret values to get a secret result. How did they implement this? It doesn't seem to be in the paper.

The way this is currently done within SPDZ is using a primitive which allows to truncate a secret shared value $[s]$ by a publicly known power of $2$.

You can see the code here.

In SPDZ, $k$ bit integers are in range $(-2^{k-1},2^{k-1})$. They are represented as $x \mapsto x$ mod $p$. So every number $x \in [2^{k-1},2^{k})$ is considered a negative number.

From a high level overview if we have the truncation, we can compute $[a] < [b]$ as a secret value:

Assign $s \leftarrow ([a - b])$ locally to see $[s < 0]$.
Denote $k$ as the bit length of $s$. Take $r \leftarrow [s/2^{k-1}]$ which has output either $[0]$ or $[1]$ depending on
the sign of $s$. Due to some technicalities of sign preserving, the output is in practice $[0]$ or $[-1]$.
To normalize the result, output $0 - [r]$. This is done locally again.

The expensive part here is step $2$ since parties have to communicate to achieve the truncation.

If you want to check the details you can find the specific protocols ($3.2$, $3.3$) on page $7$ here.


CRS generation for NIZK proof I am interested in learning more about NIZK proofs in the CRS model.

The CRS must be random but 'trusted' by all parties.

How does these data get generated both in theory and in practice?

The CRS must be generated in some trusted manner. One could use a secure coin tossing protocol involving a number of parties, and this would be fine as long as a majority of the parties are honest.

One could also apply a hash function to the New York Times of January 1st 2000 (or any other date) and use the result, although this would need a random oracle assumption.


Can you derive a 128 bit AES encryption key using PBKDF2 with SHA-256 I got confused about key derivation functions. For my project, I need to derive a 128 bits AES encryption key in CTR mode. To do so, I'm using a PBKDF2 to derive this encryption key using an initial information like a password.

PBKDF2 allows me to set its parameters before deriving a key, such as hashing function and iteration number. So, my question is if i set the PBKDF2's hashing function as SHA-256, and specificy the derived key's length as 128 bits, would that be okey? As SHA-256 will hash the input multiple times and produce a hash of 256 bits, how can I get a 128 bits encryption key while having 256 bits output of the SHA-256?

Truncate the output to 128 bits.

(Or, consider using AES-256 instead.)


Is ShiftRows(SubtBytes(x)) = SubtBytes(ShiftRows(x)) the same for the same entry : in AES Is ShiftRows(SubtBytes(x)) = SubtBytes(ShiftRows(x)) the same for the same entry : in AES
It seems like these two are equal, can someone explain in theoretically?

There is no theoretically required here.
ShiftRows changes the position of bytes, regardless of their value
SubBytes changes the value of bytes, regardless of their position
Therefore the order of these operations does not matter


What is the best and fastest algorithm to generate a hash collision? I want to find any two strings with same hash in any hash algorithm ( at least try to find depends on its collision resistance). What kind of algorithm should I follow? Should I constantly produce two random strings and compare them until I find a collision? Or I also think to produce a large rainbow table and check if there is duplicate element. How can I find the collusion as fast as possible?

The currently best algorithm to finding collisions of generic hash functions is the parallel pollard-rho algorithm due to van Oorschot and Wiener (1994, PDF). A nice summary with an updated communications cost model can be found in Bernstein's "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?" (2009, PDF). For an in-depth discussion, please refer to these two papers.

I shall now sketch the parallel pollard-rho algorithm. Let $b$ be the the length of the hash function $H$'s output in bits, let $c$ be a positive constant and let $\pi:\{0,1\}^b\to\{0,1\}^{b+c}$ be an injective padding function (in practice appending $c$ zero bits works). Furthermore let $M$ be the number of parallel processing units you have. Define the sequence $x_{n+1}:=\pi(H(x_n))$ with $x_0$ being arbitrary (but different for each processor).

Compute $x_i$ until the first $b/2-\lceil\lg M\rceil$ bits of $x_i$ are $0$ and call this a "distinguished point". We expect to have found a distinguished point after $2^{b/2}/M$ after time $2^{b/2}/M$ on all $M$ processors. Note that we have considered $2^{b/2}$ inputs for $H$ at this point across all processors.

Now we only need to look through our list of $M$ distinguished points and find two which are equal, this can be done using e.g. distributed sorting algorithms in time aboutt $O(\sqrt M)$. As the starting values for the sequences were different, but the end values are the same, there must must be a collision in them.

Let's call the matching distinguished points $y_j$ and $z_k$, now compute $|j-k|$, i.e. the difference in the sequence lengths. Go back to their respective starting values and apply the iteration $|j-k|$ times on the starting value which had the larger index for the distinguished point. Now iterate the sequences in parallel until you find the collision.

All in all this algorithm will take about $O(2^{b/2}/M)$ time and a negligible amount of memory per processor.

  Should I constantly produce two random strings and compare them until
  I find a collision?

No, this will likely take time $2^b$, because you only consider two strings at a time and not all strings you have evaluated so far.


Post Quantum Symmetric Cryptography So I am looking for the most secure method of symmetric key cryptography for long term messaging use between two users. I have heard that most symmetric key algorithms are not absolutely compromised by quantum computers, but rather weakened.

I have read that AES 256 is in fact the weakest, followed by AES 128, and AES 192 being the strongest.

Let us imagine that today quantum computers exist with "good" capacity to break cryptography.

Is AES still the best symmetric key solution as of right now? If not which is? If so then which AES key space is the strongest?

These are many questions which remain unanswered or lack good discussion as there isn't much in regards to post quantum security concerns.

AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers.

Related key attacks could happen when AES is used within a construction such as a hash function, where the output of one round is used as a key for the next round.

As far as we know now, quantum computing won't have as much as an impact on most symmetric algorithms as it does on asymmetric cryptography (that usually relies on specific mathematical problems that can be solved using quantum computers).

As mentioned, the best generic attack on symmetric ciphers, Grover's attack, about halves the key strength. But you need a lot of qbits to create the attack. Of course, there may be new attacks found that are particular to a specific block cipher, but as far as we can see now, most constructs seems pretty secure against quantum computers. That means that a 256 bit key will still deliver 128 bits of security against analysis using quantum crypt-analysis.

That means that there seems little reason to double the 256 bit key strength, as 128 bits of security are considered plenty against any attack that require such kind of order of operations.

If you require 256 bits security with quantum computers (why?) you could consider Threefish-512 - an algorithm actually designed to deliver that kind of security.


How does DH work when combined with ECC or RSA? I know that Diffie-Hellman is used to create keys in a secure way over an insecure channel. But there is one thing which I cannot understand: I see that a lot of sites use ECC or RSA alongside DH.

But why would you need to implement ECC or RSA if you already have a shared secret or key with each other? Can't you already use to strong symmetrical encryption?

What's missing is the authentication of the entities. If you don't authenticate the entity then you don't know who you've established the master secret with. This means an attacker can pose as a man in the middle or the attacker can simply act as one of the entities.

You can use static DH key pairs, but in that case the DH public keys must be trusted and the scheme loses the forward secrecy property.

In TLS 1.3 only DHE and ECDHE will be used for key agreement, which means that the key pairs are fully ephemeral and the forward secrecy property is indeed in effect.


Reductionist proofs of decisional problems to computational Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to break a decisional problem $\mathsf{Γ}$ (i.e: semantic security->guess if $b=1$ or $b=0$) in order $\mathcal{I}$ to break $\mathsf{Π}$ and if so to conclude that $\mathsf{Γ}$ is as secure as $\mathsf{Π}$, meaning that if there exists $\mathcal{A}$, we can build $\mathcal{I}$?

Further explanation:

Typically when there is a reduction to a decisional hard problem then in your construction either you model your security with an adversary that  breaking the system means that the attacker should compute something or it has to distinguish something (indistinguishability games in order $\mathcal{A}$ to guess $b$ from an encryption of $x_b$). And this attacker is used as a subroutine by the well established problem attacker in order to break his scheme.

Let’s say that the attacker in our model is able to distinguish encryption $x_0$ from encryption $x_1$. This doesn't mean that the attacker is revealing the underlying key, nor that it has to compute something. It means that it can only distinguish. I have hard understandings how such attackers can be used as subroutines for well-established computational problems where an attacker $\mathcal{B}$ has to compute something instead of distinguish (or decide). And I would like to know if such reductions exist or if – from theory – you can never reduct from decisional to computational. I.e: CDH cannot use a DDH attacker to compute $g^{ab}$ but it is the other way around.

Such reductions I know are

the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions,
the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and
the reductions in LPN/LWE.

Re:

  Can you be more specific? I.e: with CDH ? How CDH can be broken using a decisional problem attacker? ?  curious yesterday

Very recently, Fazio, Gennaro, Milinda Perera, and E. Skeith III (CRYPTO 2013) proved that

If the CDH problem over elliptic curves (EC) is hard, every bit of the secret DH value is unpredictable, and
If the partial CDH problem over the finite field $\mathbb{F}_{p^2}$ is hard, every bit of the secret DH value is unpredictable.

Their slides are avilable at Milinda Perera's website.

Overview.

Let $P:\mathbb{G} \to \{0,1\}$ is a predicate that is a candidate of hard core of the CDH function, $f(xg,g^a,g^b) = g^{ab}$.

We want to construct $\mathcal{I}$ that, given $g,g^a,g^b$, computes $g^{ab}$ by using a predictor $\mathcal{A}$ that predicts $P$ with non-negligible advantage.

Fazio et al. adopted a general framework proposed by Akavia, Goldwasser, and Safra (FOCS 2003), which can be considered as an extension of the proof strategy for the Goldreich-Levin general hardcore predicate.

The framework of Akavia et al. is summarized as follows:

We define a multiplication code that $\mathcal{C} = \{C_x:\mathbb{Z}_N \to \{0,1\} \mid x \in \mathbb{Z}_N\}$, where $$C_x(k) = P(k \cdot x).$$
Imagine a very long codeword of length $N$ whose $k$-th value is $P(k \cdot x)$.
(Since they will consider the Fourier transformation, $\{0,1\}$ will be replaced with $\{-1,+1\}$.)
We can treat the predictor as a received word whose values are corrupted at most half minus non-negligible portion.
The reduction algorithm now uses a list-decoding algorithm to find out candidates of $x$.
If the candidates are few, the reduction algorithm outputs one of them.
(In the CDH case, we cannot verify whether the guess is correct or not.)

Akavia et al. constructed the list-decoding algorithm for "good" multiplication codes and showed several candidates of one-way functions are "good."
Fazio et al. defined multiplication codes for EC-CDH and PartCDH and showed their "good" properties.


Is a PRF always collision resistant? Context:
We usually assume that the hash functions we use in practice are both: collision resistant and pseudorandom. I wonder what's the relation between those properties.

Question:
Is a pseudo random function always collision resistant?

First, a PRF is a keyed function, meanwhile a hash function is usually keyless.  So, a hash function cannot be a PRF.

Second, a secure PRF can be swapped with a uniform random function without detection, and the best way to find a collision of a uniform random function is the birthday attack.  So, if the PRF has superpolynomially large codomain, then it would be collision-resistant, since the birthday attack would take more than polynomial-time.


The "openssl genrsa" command only generates a private key? The command :

openssl genrsa -out RootCA.key 4096

generates a single file named RootCA.key. When I open the file, it only contains the private key.

Then the next command:

openssl req -new -x509 -days 1000 -key RootCA.key -out RootCA.crt

Generates a certificate , named RootCA.crt containing the Root's public key.

How can the second command generate a public key, given ONLY the private key?
 Isn't the whole value of cryptography depends on the impossibility of generating one key from another in a key pair ??

How can the second command generate a public key, given ONLY the
  private key?

It will probably use the public key encoded in the private key datastructure. As per RFC 3447 / PKCS1 (v2.1) the RSAPrivateKey should contain:

RSAPrivateKey ::= SEQUENCE {
          version           Version,
          modulus           INTEGER,  -- n
          publicExponent    INTEGER,  -- e
          privateExponent   INTEGER,  -- d
          prime1            INTEGER,  -- p
          prime2            INTEGER,  -- q
          exponent1         INTEGER,  -- d mod (p-1)
          exponent2         INTEGER,  -- d mod (q-1)
          coefficient       INTEGER,  -- (inverse of q) mod p
          otherPrimeInfos   OtherPrimeInfos OPTIONAL
      }

which contains a public key $(n,e)$ as well as the private key $(n,d)$ and some other useful information.

  Isn't the whole value of cryptography depends on the impossibility of
  generating one key from another in a key pair?

No. Generating the public key from the private key is fine. Generating the private key from the public key is not. And in fact with RSA, it can be hard to recover the public key from the private key, if you only store the private exponent $d$ and the public modulus $n$ (which is the bare minimum needed for private-key operations) and if you pick the public exponent $e$ not to be the standard $65537=2^{16}+1$ but some random large integer.

On the other hand, for DSA and ECDSA, the private key is only an integer $d$ and the public key is $g^d$ for some fixed $g$ which is needed for private key operations. So recovering the public key from the private key is always and inevitably possible with (EC)DSA.


How does AWS Secret key and access key work Those keys are too short to be public/private RSA keys. What are they? How does it use them to authenticate the client?

My guess is:

AWS access key ID is a form of unique user/account identifier
AWS secret key is like private key
When AWS CLI sends a API request, the payload is signed by generating an HMAC with the secret key as the key
The HMAC, AccessKeyID and the payload is sent to AWS service
AWS service verifies the identity of the sender and integrity of the message by recomputing the HMAC code.
If it's verified the request is accepted and processed.

Is this accurate? Why does AWS do this instead of asking user to upload a RSA public key? Why is this safer?

EDIT: I think this is how it works -- https://docs.aws.amazon.com/AmazonS3/latest/dev/RESTAuthentication.html#ConstructingTheAuthenticationHeader

AWS has designed their own custom authentication algorithm. You are referencing the older signature version (v2), a newer one (v4) was released in 2014. Details are outlined here: Authenticating Requests (AWS Signature Version 4) . A major difference is that the request is not signed with the secret itself, but with a signing key which is generated using the secret. It also uses HMAC-SHA256 for signing.

  Why does AWS do this instead of asking user to upload a RSA public
  key? Why is this safer?

Using asymmetric keys would be safer since AWS would only store a public key instead of the secret, which is stored by both the user and AWS.


Is it possible to sign OpenPGP key without consent of a key owner? If yes, can unsolicited signatures be removed from a key? For example, I have my key listed on a key server. On one day a key issued on the name of Julius Caesar signs my key. Obviously this key is a fake key and I want to remove its signature from my key can it be done?
Can I block unsolicited signing of my key? Can I make signatures appear on my key only when I have validated them?

As each certification is an independent OpenPGP packet, of course it can be deleted -- OpenPGP allows so by opening the gpg --edit-key <key-id> menu and running delsig in there. An alternative would be to use gpgsplit to split up an OpenPGP key file into its individual packets, removing the offending signature and concatenating the files again.

You cannot remove anything from the key server network, though. Most key servers synchronize with each other, and this is done by just merging all unknown packets with no exceptions. Using the common key server software, it is not easily possible to delete a single packet (you'd have to dump everything, find the offending certification, delete it and import the data again). But even if removed, the offending certification will be merged back as soon as the server syncs up to the others again.

You will hardly be able to convince a key server operator to remove a certification for the given reason; and for technical reasons, you'd have to convince all key server operators to do so at the same time (and hope, no other user has a copy of that certification and uploads it at some point in future again).

One of the design principles of the OpenPGP key server network is preventing deletion: by just always collecting all information the servers can get hold of, it is very hard for even powerful attackers being able to control relevant parts of the servers to apply any kind of censorship. The fact that wrong information might be contained is accepted, no content in the key server network is validated at all (apart from some basic, technical verification on the protocol level).


Is this a good PHP encryption Strategy? I'm writing a multi-tenant application that interacts with a couple of different APIs on behalf of each customer. Obviously, we need to store private keys for these various different APIs in the database so that we can connect to them. Goes without saying, I need to encrypt those.

I wanted to use a separate encryption key for each tenant on the system (I'm using openssl_encrypt with AES-256-CBC). To accomplish this, I have a separate "crypto" database. The tenant_keys table contains the following columns:

A tenant_hash, which is a has of a random value stored in the tenant's settings table, used for lookup
A tenant_key, which is the tenant's unique encryption key.
A key_timestamp that I'll use in the future to periodically rekey tenants

The obvious weakness is that if the database were stolen, the attacker would have all of the keys. To combat this, I've generated a "master key" that is stored as a text file on the server. This master key is then used to encrypt all of the various tenant keys. So, when a session is first initiated and the tenant is looked up, the tenant's key is decrypted and stored in the session. So, here are my questions:

Is there a better way to secure each tenant key (perhaps some sort of key server, but building an entire CA  hierarchy and such seems like overkill vs protecting the master_key file with good chmod settings)?
Is there a safer way to store the tenant's key ephemerally without needing to do a round of decryption (costs CPU time) each time we need to use it, besides in the PHP session? The PHP sessions will ultimately be stored in some sort of shared storage (probably redis) as the environment will be clustered.

Protection Against Rainbow tables

First of all, design a log-in system so that users cannot set bad passwords and have protection against rainbow tables. One nice solution is using salt as in bcrypt.

Protection of Public Keys

Generate public-private pair for each user. Then, encrypt users private keys with their passwords and prefer Password Key Derivation Functions PKDF, so that you can prevent the guess and brute-force attacks on the user's passwords. You can use their password to encrypt and decrypt the key-encryption key.

Session Keys

When you want to send a message to a user, generate a session key and encrypt the message with AES crypto algorithm with an appropriate scheme, CBC, CTR or GCM, and secure the session key by the user public key with appropriate padding scheme.

Later on, when a user log-in the system, you can use their passwords to decrypt their private key and open the messages, if any, by extracting the session keys for each message. Hope this clear.


How are data science and cryptography related? Are there any interesting connections between the fields of data science and cryptography?

Data science involves the use of statistical analysis to analyze data while cryptography also involves statistics in crypt-analysis in order to protect data. And of course both fields require a lot of math.

So I wonder if there are any interesting links between these two fields.

If by data science, you mean "machine learning and cie", there is some recent works that made the link between these two hot topics :

For example, some people are trying to do data analysis on encrypted data : https://eprint.iacr.org/2017/1114


How does Google's “authenticator number generator” work? I have two-factor authentication enabled on my Google account, and I have this app on my phone which generates a number I have to type when I'm logging in to Google-Mail.

But I don't understand how this number is validated on Google's side. My bank has a similar approach: they gave me this little gadget which also generates numbers.

How do such “authenticator number generators” work?

I found the accepted answer above a bit unhelpful -- it basically just says: "read these two RFCs".  So, on the theory that the quickest way to get the right answer to a question on the Internet is to provide a wrong one, and wait a few New York Minutes until someone corrects you, here's my attempt at a summary overview answer, based on a laughably cursory examination of the Wikipedia entry and the two RFCs.

basically your phone and the server app start by agreeing on a secret key, which they both know.  that happens just once, when you set up the app on authenticator.

From there on in, the number that's generated every 30 seconds is based on SHA-1 hashing the secret key with the current time (in the form of a unix timestamp, rounded down to 30 seconds).

So, tl;dr: it's a hash of a shared secret with the current unix timestamp.

Or is it? Corrections welcomed...


Is the garbled circuit adaptive? Alice sends the garbled circuit for a function to Bob in the offline stage. In the online stage, Alice sends affine transformations for the circuit to Bob. Then, Bob employs the garbled circuit and the affine transformations to re-randomize the circuit, and evaluates the re-randomized circuit on his input (using OT). The adversary chooses the input after seeing the garbled circuit. Is the garbled circuit adaptive?

Adaptivity essentially refers to giving the adversary the power to choose an input which potentially depends on the garbled circuit, i.e., the input is adaptiveley chosen after seeing the circuit.

So if a GC scheme is proven secure in the model where the adversary outputs $x$ after seeing the garbled circuit, yes. Otherwise, no.

For formal definitions see, e.g., [1]

References

[1] https://eprint.iacr.org/2015/1250.pdf


How to protect from Silver–Pohlig–Hellman algorithm I read that Silver–Pohlig–Hellman algorithm solves the discrete logarithm with prime module $p$ in $O(\log^2(p))$ if $p-1$ is a smooth number. This seems pretty fatal for cryptography, since it is a polynomial over the key length, right?

So my questions are:

How probable is this to happen?
(How) can it be prevented?

Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently.

However, the solution is pretty simple: Choose a safe prime as modulus: $p=2q+1$ (with $q$ prime), or a prime $p$ where $p-1$ contains at least one large factor, so that the BS-GS algorithm for this factor is too large (It has $\mathcal{O}(\sqrt{q})$  memory and time complexity for prime $q$).

For example this is done in DSA: Choose prime $q$ first, then calculate a prime $p$, where $p-1$ is a multiple of $q$. Examples for suggested key lengths $(|q|,|p|)$: (160,1024), (224,2048), (256,2048),...

edit:

To answer your first question: If you choose $p$ randomly, chances are high that your security is MUCH lower than you would expect:

For random $p$ , the chance of $p-1$ being divisible by a low prime $a$ is $\frac{1}{a-1}$. A random $p$ means that $(p-1)$ mod $a$ is uniform distributed in $[0,a-2]$.

Now, if $a$ is small, we can ignore the costs of the BS-GS algorithm for $a$, and you "loose" $\log_2{a}$ bits of security: The remaining problem doesn't have to be solved for group order $(p-1)$ but for $(p-1)/a$.

Since there are quite a lot of small prime numbers, you have a problem. Best to avoid this problem by choosing $p$ not totally random, but with $q$ large enough. (Choose q, calculate some $p$ and test them for primality).


Using a non-secure random generator for IV or salt generation I was just looking at a post on Code Review when I noticed the other answer to the post. While I would agree mostly with the answer, I do however doubt if having a Cryptographically Secure PRNG is really an issue for generating IV's and salt values (where the salt is used for password based key derivation).

What would be the requirements on the random number generator to be used for IV and salt generation? Would a uniquely seeded, well distributed, non-secure RNG suffice?

Let's take AES-CBC for example—a typical cryptosystem that requires a randomized IV.  Suppose I can predict the IV in advance.  Then I can start by asking for the encryption of $\mathit{iv}_0$, which is $\operatorname{AES}_k(\mathit{iv}_0 \oplus \mathit{iv}_0) = \operatorname{AES}_k(0)$, and proceed by asking to be challenged on the messages $m_0 = \mathit{iv}_1$ and $m_1 = \mathit{iv}_1 \oplus 1$ (or any message distinct from $\mathit{iv}_1$).  If I get back $\operatorname{AES}_k(0)$ as the ciphertext for $m_b$ for unknown $b$, then $b$ must have been 0; otherwise 1.  Hence if the IV is predictable in advance, AES-CBC is an insecure cipher—specifically, it fails the standard of IND-CPA.

On the other hand, most things called ‘salts’, like what you sprinkle on password hashes, need only be distinct between users to thwart multi-target attacks in the multi-user setting.  It's convenient to choose them at random from a large space so there is negligible chance of collision and no need for state, but that's not necessary in principle—a unique per-application identifier and a counter of hashes within that application would suffice.  (Without the per-application identifier, a multi-target attack could save effort attacking (say) the 7th user in each of a set of many applications.)

Similarly, if we take a nonce-based cryptosystem, like AES-GCM or crypto_secretbox_xsalsa20poly1305, and turn it into a randomized cryptosystem by choosing the nonce at random, the danger is, again, not in predictability of the nonces but in collisions of nonces—though in contrast to AES-CBC and password hashes, the consequences may be more catastrophic than merely revealing ciphertext equality or admitting multi-target attacks.


Finding collisions for the DES F-function It's known that for a given subkey, the F-function of the DES is not injective (see Is the DES F-function injective for a given subkey?). I am interested in efficiently finding collisions for this function, i.e. for a given subkey $k$, I want to find two different inputs $x$ and $y$ such that $F(x,k)=F(y,k)$.

I am wondering if there are shortcuts that make finding such key values easier than plain brute-force?

If S is a DES S-box, for a given "output", S(input) = output has exctly 4 solutions for "input", or "collisions". You can then find collisions for F by concatenating collisions for each S-box.
You can start with setting an output for F and then look for all possible "inputs" for each of the 8 S-boxes on the 4 relevant bits of the output of F.


Primitive root in a finite field Wen-Her Yang and Shiuh-Pyng Shieh proposed two password authentication schemes by employing smart cards, one is timestamp-based and the other one is nonce-based. Their scheme consists of 3 phases: Registration, login and authentication phase.

Considering timestamp-based scheme, step 3 of registration phase says:

  Find an integer $g$ which is a primitive element in both $\operatorname{GF}(p)$ and
  $\operatorname{GF}(q)$, where $g$ is the system's public information.

What happens if we use a $g$ that is not a primitive element of those two fields? How can this affect scheme security?

I myself think that by selecting a $g$ that is not a primitive element, we end up using a smaller group which probably can make things easier for an attacker to solve discrete logarithm problem $h_i=g^{\mathit{pw}_i\cdot d}$ and obtain $\mathit{pw}_i\cdot d$.

You're right. In general if a $g$ is not a primitive element of $\operatorname{GF}(p)$ it generates a smaller subgroup of $\operatorname{GF}(p)^{\ast}.$ Since $|\operatorname{GF}(p)^{\ast}|=p-1$ is divisible by 2, this subgroup can be as small as 2 in size, and its size can take on any value $w,$ where $w \mid (p-1).$


Is $g(x)$, the first $(n -\log(n))$ bit of $f(x)$, a (strong) one-way function? Given a (strong) n-bit-by-n-bit one-way function $f$, is $g(x)$, the first $(n - \log(n))$ bit of $f(x)$, a (strong) one-way function, too?

When reading Prof. Sanjam Garg's Graduate Cryptography lecture notes, I came across this problem. I am trying to construct an adv. cracking $f$ based on an adv. cracking $g$, but unable to bound the ratio of $|\{x|g(x) = v$ and $f(x) = v||u\}|$ to $|\{x|g(x) = v\}|$ for arbitrary eligible $v$ and $u$ from the fact that $f$ is a one-way function.

Is there another way to prove/disprove this statement? Thanks.

Without knowing the details, note that any algorithm can utilize the $n-\log n$ bits of $g$ to invert it, can then brute force the remaining $\log n$ bits in time complexity $O(2^{\log n})=O(n),$ thus inverting $f.$

This will at most multiply the overall complexity by a linear factor, thus cannot achieve more than a polynomial gain between inverting $f$ and inverting $g$.


Could a 6502 CPU safely compute a SHA-1 hash in a reasonable length of time? The 6502 is the CPU in a Tamagotchi (which can be hacked to run custom code). SHA-1 is the default hash used for TOTP (the algorithm used by two-factor authentication tokens and apps). Hopefully you now understand why I'm asking this.

(given this context, this would be a couple dozen bytes of input, and less than a second or so of time)

Yes, a 6502 can compute SHA-1 in a reasonable time: less than $\lceil(k+9)/64\rceil/5$ second for a $k$-byte message on a 1 MHz 6502 as on the 1977 Apple ][. E.g. 0.2s for up to 55 bytes. We need like 128 bytes of RAM excluding the hashed message. Code likely fits 1 kbyte of code including constants.

Note: I do not know clock speed, RAM and code size resources on a Tamagoshi.

I'm basing this on a commercial implementation I wrote for the 8031/8051, another 8-bit CPU (from an old post). My 660-byte code (including tables and C interface) is well below 50,000 CPU cycles per 64-byte block (where many instructions on registers are 1 cycle, and external memory access is 2 cycles; one cycle lasts 12 external clock periods of the original 8051, common variants reduce that to 6 or less). That code is not optimized quite to the max for speed, because the customer was short on easily addressable internal RAM, and code size was a consideration too. On the 6502, I estimate the number of CPU cycles would be less than 4 times that with unrolled code using zero-page addressing, that is less than 200,000 cycles. I would not be surprised if things could be brought down to 120,000 cycles or so. I second Poncho's comment that 83,700 cycles seems rather optimistic.

The most natural code is constant-time, thus at least a side-channel by timing is easy to avoid. Probing, and power/electromagnetic emission analysis are credible security threats, if an adversary can approach the hardware.

Note: I know no security CPU that used the 6502, but many have used the 6805 or derivatives, which are very comparable 8-bit CPUs. Some are still in active use.


Memory during crypto computation I'm implementing a cryptographic primitive and I have a question about the memory model. The function (simplified) looks something like this:

void encrypt(unsigned char *out,
             const unsigned char *in,
             const unsigned char *pub_key)
{
  unsigned char buf[OUTPUT_SIZE];
  size_t i, j;

  memcpy(out, in, OUTPUT_SIZE);
  for (i = OUTPUT_SIZE; i < INPUT_SIZE; i += OUTPUT_SIZE) {
     compute(buf, in[i], pub_key);
     for (j = 0; j < OUTPUT_SIZE; ++j) {
        out[j] ^= buf[j];
     }
  }
}

To summarize: the input (plaintext) is chopped in blocks of size OUTPUT_SIZE and a computation is done on each block (except the first). Each iteration, the result of a computation on the input block and the public key gets stored in the buffer. The output (ciphertext) is the result of the binary sum (xor) of all processed blocks. The caller of the function has to provide an allocated memory block for the output. This memory may reside on the stack or the heap.

My question is: is this construction secure? I am afraid that because the memory is provided by the caller, there are scenario's in which an adversary can inspect intermediate values of this memory through sidechannels and learn about the secret plaintext. On the other hand I'm thinking: if the attacker has access to the out buffer, then why not also to the in buffer?

If the computation is performed via an ordinary function call, then the caller and the callee live in the same address space. In this case, there is no concern about secrecy: the callee is not protected from the caller in any way. A malicious caller has access to the same memory as the callee and so they can access the key, they can inspect and modify the execution of the function, etc.

You should worry about accidental leaks, due to a buggy caller. It is standard good practice to wipe all memory that has been used for cryptographic computations after use. This way, even if the program later leaks memory, that's one secret that won't leak. For example, in this case, you should wipe the temporary variable on the stack. The basic idea is to call memset(buf, 0, sizeof(buf)) at the end of encrypt, but this actually doesn't work in practice, because the compiler is likely to optimize it away (what sense is there to write to an object that goes out of scope immediately afterwards?). CERT recommendation MSC06-C discusses this problem and some solutions (use memset_s if you have it, but it was only standardized in C11).

If the call is a cross-context call of some kind, for example a system call from a user program to a cryptographic service running in a more privileged CPU mode, or a call to a different process using shared memory, then the situation is different. In such cases, you need to be careful inside the cryptographic service to use the service's own memory for all key material and intermediate results that the client must not be able to access. Furthermore, in the service, you need to be careful when reading data in memory that is shared with the client, because the client might change the content of that memory: never read the same memory twice, or read back what you wrote. And you need to be careful when writing data to memory that is shared with the client, as the timing of these writes might convey information. The general rule for a data processing service running in a different context but communicating via shared memory (e.g. an operating system kernel) is: first copy the input parameters; then process the data in the service's memory; then copy the final output into shared memory. It sometimes makes sense to do this in several stages, but keep the data flow in mind and be aware of what the client might observe and perturb.