Attacks on AES-128 (ECB) based on some knowledge of plaintext I'm working with a third party protocol which employs AES-128 in ECB mode of operation to encrypt a packet composed of 16-byte blocks (it encrypts each block independently). I'm trying to determine if there are any reasonable attacks against the encryption.

One of the plaintext blocks it encrypts has a 4-octet nonce followed by 12-octets that are always the same (part of the device's unique ID). It is also known that those 12 constant octets are one of 16 different values (ASCII hex digits). Not knowing anything else about those 12 constant digits or how the nonce is generated (assume truly random), is there a practical attack against the encryption?

Further, there is a single key shared by all devices which use the protocol, so in theory I could collect these blocks from lots of different devices, all are encrypted with the same key. All of the devices having different IDs, but all packets from a given device having the same ID.

Another plaintext block (this one is actually encrypted with a different key, specific to the device) has a 4-octet nonce, an 8-octet millisecond timestamp, one octet that is always zero, one octet of arbitrary non-constant data, and two octets that give the length of the unpadded message in octets, and can therefore be narrowed down to one of 12 values by counting the number of blocks in the entire packet (each block cannot hold more than 12 octets of message). I don't know if maybe having the timestamp (i.e., a 64-bit value that increases monotonically and by a more-or-less knowable amount between any pair of packets) is useful in breaking the encryption, but I guess if CTR mode isn't a problem, than this wouldn't be either.

I'm looking for basically anything that could compromise the security of the protocol, so anything that significantly narrows down the keyspace, or even the possible values for those 12 constant octets.

If the protocol doesn't provide authentication, an attacker can probably mount replay attacks or make deterministic changes to messages.

If the nonces in different blocks are not compared in any way, they can just take the ID block of a previous message and use it with a new one, to forge it being from that device. If nonces are required e.g. to be equal in all the blocks of a message, the attacker can still reorder them freely, which reorders the message in the same way. If there are any blocks without nonce, those can be freely moved within and between messages.

  One of the plaintext blocks it encrypts has a 4-octet nonce followed by 12-octets that are always the same (part of the device's unique ID).

A 32-bit nonce means you need to see on average $2^{16}$ such blocks from the same ID + key to see a collision. Even seeing just a few hundred gives an attacker a larger chance to see one than is usually considered secure. Such a collision shows the attacker the two messages came from the same device/ID.

  I'm looking for basically anything that could compromise the security of the protocol, so anything that significantly narrows down the keyspace, or even the possible values for those 12 constant octets.

You cannot find the key even with known plain/ciphertext pairs (unless it's been chosen in a non-random way that allows an attack). If the attacker ever sees two blocks with equal ciphertext, they will know the plaintexts are equal and may be able to derive information about the ID, depending on which block matched which.


Scrypt KDF cipher (scrypt CLI) - known vulnerabilities and cryptanalysis? There is a scrypt cipher that is used for example by some cryptos like LItecoin for their mining algorithm.

I never heard of scrypt. I know eg SHA-256 which is well analyzed and considered as secure until now.

Any known cryptanalysis for scrypt / vulnerabilities?
is scrypt considered in the community as a secure (comparable to sha256) cipher?
How collision-resistant is it?
Is it easily breakable by quantum computing attacks?

scrypt
scrypt is actually a password-based key derivation function (PBKDF *) created by Colin Percival; Stronger Key Derivation via Sequential Memory-Hard Functions. We want slower PBKDF functions since it will slow the attack times. The below is from hashcat performance;
scrpyt                         1172.8 kH/s (16.61ms)
PBKDF2-HMAC-MD5               18059.2 kH/s (69.72ms)

It is slower and designed against large-scale custom hardware attacks (ASIC,FPGA, and GPU) by requiring a large amount of memory. Internally uses PBKDF2 and Salsa20/8.

Any known cryptanalysis for scrypt / vulnerabilities?

The attackers cannot reverse the scrypt to find a pre-image. The only meaningful way is the password cracking by trying all possible passwords up to some length, checking the common password list, and trying combinations, or various other methods. If you want to mitigate this, you need to use a password with good entropy. You can generate one using diceware ( also EFF has a nice diceware page) or Bip39 or some other system that generates password with good entropy.

is scrypt considered in the community as a secure (comparable to sha256) cipher?

SHA256 is not a cipher, it is a hash function. You can also use SHA256 for KDF however not advised. The KDFs are designed for these purposes. For hash functions, we consider the pre-image, secondary pre-image, and collision resistance. For KDF functions the collision resistance or the collision attacks are not related.
There are no attacks on scrypt except for the first item.

How collision-resistant is it?

Collisions are not related to password hashing, the pre-image is requried

Is it easily breakable by quantum computing attacks?

Hardly, since the number of q-bits will be much higher than AES. The main reason will be a large memory. If ever built, it will use Grover's algorithm.
scrypt CLI program.
In short, scrypt CLI program uses AES256-CTR for encryption and HMAC_SHA256 for integrity and authentication. Little details;

AES with the key size 128 bits resisted attacks even after nearly 22 years and practically still secure [1] [2] but vulnerable to multi-target attacks. From the code, as we can see, they use a 32-byte key, i.e AES256. That is even secure against Grover's quantum search [3].
CTR mode requires a nonce (number used once), and should not be repeated. Once reused, it will be vulnerable to the two-time pad.
HMAC is Hash-based Message Authentication Code here initiated with SHA256. It's security proven by Bellare, Mihir (June 2006). New Proofs for NMAC and HMAC: Security without Collision-Resistance under the assumption that the compression function is PRF.

* : don't confuse with PBKDF1 in rfc 8018


Example of cryptography random number I read that random numbers are being used in cryptography and security. I think I have idea how to truly generate true random, non-deterministic number. But before continuing further I'd like to ask few basic questions.

What kind of numbers are needed for cryptography/security? Are those integers?
How long should those numbers be? 10 digits, 100 digits?
I read few articles about random numbers, but did I get it right, they are used to create hashes to create stronger encryption?

What kind of numbers are needed for cryptography/security? Are those integers?

Bits. Simply have your TRNG generate random bits.

As mentioned in the other answer, the only difference between bits/hex/integers/etc is in the formatting and representation. It is almost certainly more appropriate and simpler to generate random bits than it is to rely on some process to generate a random integers in a given range.

How long should those numbers be? 10 digits, 100 digits?

256 bits is sufficient for any one user. You can take a 256-bits of uniformly random information and use it to generate an arbitrary amount of uniformly random information (for practical purposes) using a CSPRNG.

I read few articles about random numbers, but did I get it right, they are used to create hashes to create stronger encryption?

Random numbers are not required to create hashes

Typical hash functions are deterministic algorithms
Random numbers may be used as part of an input to a hash function, depending on context

Hashing is not related to encryption

The two are sometimes used in conjunction, but encryption is not (typically) built from hash functions

"stronger encryption"

Random numbers are required to securely use a cipher (e.g. for keys, IVs)
But the algorithms themselves such as AES and ChaCha are nigh unbreakable and so cannot be "stronger"


Using a LibSodium CryptoBox KeyPair with `crypto_sign` More of a theoretical question...

Taking a system where Lib Sodium has been used for asymmetric encryption, where a "crypto_box_keypair" has been generated, and the public key has been distributed to a number of different systems.

Would it be possible to sign a message using that keypair?

As in, the message remains in plain text, and a signature is generated with the secret key (possibly indirectly), and anyone in possession of (and trusts) the public key, can verify that the message hasn't been tampered with.

Considering that the "crypto_sign" function requires the use of "crypto_sign_keypair", not "crypto_box_keypair".

From a PHP implementation point of view, I was wondering if you could...

Take the keypair that has been previously generated by:

<?php
$key_pair = sodium_crypto_box_keypair();
$key_secret = sodium_crypto_box_secretkey($key_pair);
$key_public = sodium_crypto_box_publickey($key_pair);
?>

Then, for every message you want to sign, create a "crypto_sign_keypair", and use sodium_crypto_sign() as intended:

<?php

// $sign_seed = random_bytes(SODIUM_CRYPTO_SIGN_SEEDBYTES);
// $sign_pair = sodium_crypto_sign_seed_keypair($sign_seed);

$sign_pair = sodium_crypto_sign_keypair();
$sign_secret = sodium_crypto_sign_secretkey($sign_pair);
$sign_public = sodium_crypto_sign_publickey($sign_pair);

$message = 'Hello';

$message_signed = sodium_crypto_sign($message, $sign_secret);

?>

The $sign_secret and $sign_pair can be destroyed, because the recipient just needs to use $sign_public:

<?php
$message = sodium_crypto_sign_open($message_signed, $sign_public);
?>

The problem is that $sign_public needs to be sent to the recipient.

Where they need to verify it hasn't been tampered with, and that it came from the owner of the original $key_secret, by using their trusted copy of $key_public.

Noting that:

sodium_crypto_sign_detached is basically the same thing, but does not contain the message in its output.
sodium_crypto_box requires the recipient to have a keypair as well.
sodium_crypto_box_seal uses the public key to encrypt.
sodium_crypto_secretbox and sodium_crypto_aead_* use a shared key (symmetric).
sodium_crypto_auth uses a shared key.

It's possible to go the other way around (thanks Scott Arciszewski)

<?php

$sign_pair = sodium_crypto_sign_keypair();
$sign_secret = sodium_crypto_sign_secretkey($sign_pair);
$sign_public = sodium_crypto_sign_publickey($sign_pair);

$key_secret = sodium_crypto_sign_ed25519_sk_to_curve25519($sign_secret);
$key_public = sodium_crypto_sign_ed25519_pk_to_curve25519($sign_public);

$key_public = sodium_crypto_box_publickey_from_secretkey($key_secret);

?>


Emphemeral key creation from a long term shared secret (without DH) Assuming I cannot use DH scheme, and the long term key is known to both sides, is there a known algorithm / standard that defines how to derive a short term key from a long term key?

Let's create a simple scheme that includes authentication and the dependence of the session secret on both the long term secret $K$ as well as random generators of both sides:

generate and store random $R_A$ at A;
send random $R_A$ from A to B;
generate and store random $R_B$ at B;
send $(R_B, MAC(K, R_B \| R_A \| B \| A))$ to A;
let A validate that the MAC authentication tag is correct and that B, therefore, controls key $K$;
send $MAC(K, R_A \| R_B \| A \| B))$ to B;
let B validate that the MAC authentication tag is correct and that A, therefore, controls key $K$;
let both sides calculate $Info = R_A \| R_B$ and $K_S = KDF(K, Info)$

Here $A$ and $B$ are identity strings of the entities A and B respectively.

Currently only one session key is calculated, but it is easy to add e.g. a label and identity to the $Info$ structure to calculate specific keys (so to create a message authentication key for A, you could create $Info = R_A \| R_B \| \text{"Auth"} \| A$ where $\text{"Auth"}$ is the label and $A$ is the identity of A, for instance, a serial number. Using separate session keys for specific uses and entities is highly recommended.

The above mixes a challenge / response protocol with session key establishment. There are many variations for such schemes.

You can just swap randoms, calculate and create session keys as above, and use one of them to authenticate the parties, instead of relying on $K$ for authentication.

You can, of course, skip the authentication of the parties entirely. But then you would not know that you're communicating with a legit party. You would be sure of the authenticity of the entity when you'd receive the first authenticated message protected by the newly established session key. However, I would strongly advise against mixing entity and message authentication - if just for the error handling if the authentication does not succeed (but there are more issues than just that).

Yet another variation would be to rely on a random value generated by a single party. This is more efficient and could remove one handshake message from the protocol. However, the resulting session key now only depends on the correctness of one random number generator.

Note that these purely symmetric schemes do not provide forward security. That means that the security - especially the confidentiality - of the messages depends fully on the confidentiality of the key $K$. If it ever gets known then an adversary can simply decrypt stored sessions. Don't forget to destroy your keys when they are not needed anymore.

There are of course standards for these kind of schemes, but I'll quote Andrew S (Andy) Tanenbaum on standards: "The nice thing about standards is that you have so many to choose from..."

I noted ratchets as well in the comments; I didn't go into that as I think it is more targeting creating the next long term key rather than an ephemeral session key.


Are there simple, cryptographically safe one-way hashing functions? I'm trying to understand what is required to construct one-way hash functions. I know about many algorithms used in practice, such as SHA256, Blake2, MD5, which are of high quality, but they're complex and studying them doesn't really answer my question. I also know about "simpler" algorithms such as multiplication modulus - but those are often not one-way, so they also don't help with the question.

Are there one-way, cryptographically safe hashing algorithms that are very, very simple to describe? When I say simple, I mean really, really simple. As in, a cellular automata, or something that could be implemented in 4 or 5 lines of code.

Designing a conceptually simple one-way function is a very hard challenge in itself - and conceptual simplicity is not such a well defined concept, so the answers you will receive might be a bit opinion-based (and in particular, so will be my answer).

One of my favourite candidate OWF regarding conceptual simplicity is Goldreich's local one-way function. It is more a vast class of possible functions than a specific one, but here is the core idea:

You fix some simple predicate $P$ that acts on a small number of inputs $d$.
You fix $m$ random subsets $(S_1, \cdots, S_m)$ of $[1,n]$, such that each subset is of size exactly $d$. $n$ represents the input size of the function, and $m$ is the output size.

Now, the function simply does this: on input $x \in \{0,1\}^n$, output $y = y_1y_2\cdots y_m \in \{0,1\}^m$ where $y_i$ is computed by evaluating $P$ on the $d$ bits of $x$ indexed by the subset $S_i$.

As you can see, the high level idea of the function is extremely simple. The hard part is choosing a good predicate $P$, and studying the conditions that must be satisfied by the sets $S_i$ to be able to withstand existing attacks. And indeed, both problems have been intensively studied in the theoretical community in the past ten years. But this does not affect the extreme simplicity of an implementation: to implement it, fix once for all a list of subset $(S_1, \cdots, S_m)$ (if you want a compression function, take $m = n/2$), picked at random in some setup phase, and store it in some file. For $P$ and $d$, take something widely regarded as good in the theoretical community - e.g., you can take $d = 5$ and $$P : (x_1,x_2,x_3,x_4,x_5) \mapsto x_1+x_2+x_3+x_4\cdot x_5 \bmod 2$$ (see e.g. this article). The code for evaluating the function is extremely simple: to generate the $i$th bit of the output, it retrieves $S_i$ from the stored file (a random subset of $[1,n]$ of size $5$), and applies the above $P$ on the bits of $x$ whose index are in $S_i$. Moreover, all the output bits can be generated in parallel.

Now, if your sole purpose is understanding how OWF are built - well, looking at a very specific example will hardly help, as OWF functions can be constructed from a huge variety of designs. But if you only wanted to see a conceptually simple one, with some detailed explanations on why this family of functions can be conjectured to be one-way (see Goldreich's paper, which I find fairly easy and pleasant to read), this might satisfy your need.


Does decryption with a wrong key creates a new encryption? I'm wondering if decrypting with a wrong key is the same a encrypting in a different way.
For example if I encrypt the message "hello" with Caesar cipher with key = 3 it will give the message "khoor" but if I decrypt it with key = 2 the result will be "ifmmp". So we can say, decrypting a message encrypted with Cesar cypher will be the same as encrypting the encrypted message with -wrongKey.
But in a general way, if I decrypt a message with a wrong key, do I encrypt the encrypted message in a different way?

In general this is a moot point, as modern encryption schemes are designed so that the recipient knows if they have used the correct key or not. It is an interesting question to ask about encryption primitives, like a block cipher. Put more precisely, you are asking whether there is always a $k_3$ such that
$D_{k_2}(E_{k_1}) = E_{k_3}$
This is essentially asking if encryption forms a group, and in general the answer is no. See e.g. Is Triple-DES a group?. There are notable exceptions. You've seen that Caesar cipher is one, and Vigenere is another.


Slow encryption (or reverse time-lock) Are there cryptographic scheme where encryption is sequential and take a long time (in a way that it can be quantified) while instead decryption with a secret key takes very short time?

Some sort of reverse time-lock encryption where it takes a long time to decrypt rather than encrypt?

(Either with symmetric or asymmetric)

One obvious way (which is a variant of the normal time-lock encryption technique) is to do RSA encryption, with a truly huge $e$.

That is, to encrypt, you compute $M^{3^\lambda} \bmod N$; by making $\lambda$ sufficiently large, you can make this take a long time.

To decrypt, you would have precomputed the values $(3^\lambda)^{-1} \bmod p-1$ and $(3^\lambda)^{-1} \bmod q-1$, which can be done in $O(\log \lambda)$ time; you proceed with RSA decryption in the standard way.


Do I need to send the RSA public exponent with the public key? I used RSA to provide confidentiality for a protocol. As I know the public key of RSA has two values: $e$ and $n$. Of these two, $e$ usually has value 65537.

When the public key is sent, does the sender need to send $e$ and $n$ or just $n$?

RSA key pair generation can be performed with a static $e$ or with an $e$ that is calculated after the private key has been calculated. Generally software chooses to perform the calculation using a set public key, the fifth prime of Fermat (F4 where 4 is the index) with that value 65537 (0x010001 in hexadecimals).

For compatibility reasons it is generally preferred to allow more values than just F4,  even if your own software only uses F4 for key pair generation. However if you are writing your own closed protocol then setting a static value such as F4 for $e$ is perfectly fine. Note that you may however still preclude some (admittedly weird) libraries / hardware solutions that generate random 16 bit values of $e$.

The RSA public key format is specified in PKCS#1. Most libraries will able to handle this key format and/or the SubjectPublicKeyInfo format found in X.509 certificates (this format contains the PKCS#1 format, but additionally indicates the type of key). So one advantage of leaving it in there is direct software support. Furthermore, you are also freed from thinking about how to encode the modulus & length of the modulus (in case multiple key sizes need to be supported).

Here is the ASN.1 module from PKCS#1 Appendix C:

RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}

So even if you do only use one value, it is a question if you don't want to send the value of $e$. In the end you'll just save 3 bytes not calculating overhead and to 9 to 12 bytes if you include all the ASN.1 overhead that is required to split the modulus and the exponent. If space is at a premium you may want to switch to elliptic curve cryptography (ECDH or ECIES) because of the smaller key sizes.


What is the correct elliptic curve representation? I'm studing the basics of elliptic curve from various resource some more mathematical someone more practical.
I know that the equation where the elliptic curves come from is the Weistraß equation
$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$
After the trasformation
$y\rightarrow y-(a_1x+a_3)/2$ I get the isomorphic curve : $$y^2=x^3+\frac{b_2}{4}x^2+\frac{b_4}{2}x+\frac{b_6}{4}$$
(the coefficent $b_2,b_4,b_6$ are a combination of the previous one).
After defining the equation I've started reading the group law and proceeding further I found out other kind of curves with different group laws(the formulas for calculating the addition and the double of a point are different).
In the end now I know that there exists three kind of curves:

Supersingular curves
$y^2+cy=x^3+ax+b$

Non supersingular curves
$y^2+xy=x^3+ax+b$

Ordinary curves
$y^2=x^3+ax+b$

Questions

What are the difference between this curves?
Why are EC defined only on ordinary curves? What is their advantage?
What is the correct elliptic curve representation?

Reading online seems that supersingular curves require more bit (to avoid this) so that's why they are not used. Is this true? What about non supersingular curves?

In general case, each elliptic curve over field $K$ can be defined by the following equation:
$$y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6$$
If the characteristic of field be larger than $3$, then all elliptic curves over it are isomorphic to
$$y^2=x^3+ax+b$$
In the case that characteristic is $3$ or $2$, we have two form of isomorphic curves which are as follows respectively.
$$y^2=x^3+ax+b$$
$$y^2=x^3+ax^2+b$$
$$y^2+cy=x^3+ax+b$$
$$y^2+xy=x^3+ax^2+b$$
Edit: The representation of elliptic curve depends on your goal and the field.  Elliptic curves are not defined only on ordinary curves. As an example, we have Koblitz curves (which are non-supersingular) that are a class of computationally efficient elliptic curves. Several of these curves are recommended for cryptographic use by NIST. Supersingular curves are useful for cryptographic goal, too. In the 1,2,3,4 you can find several details.


Modes of Operations Exercise I am currently stuck at an exercise for my Cryptography Class in University which is:

Alice wants to send a message $M = (M_1,M_2) =$ "Pay Bob \$100 from bank accout $12345$" to her bank (encrypted). Therefore she picks a random Initial Value ($IV$) coded $(IV, M_1, M_2)$ in 8-bit-ASCII, encrypts this and gets the Chiffre $C = (IV,C_1,C_2)$ which she sends to her bank.

Eve intercepts $C$ from Alice and wants to change it to $C'=(IV',C_1',C_2')$ with $M' =$ "Pay Eve \$500 from bank account $12345$"

Give a valid $C'$ for $M'$ if Alice uses AES in Counter Mode
Give a valid $C'$ for $M'$ if Alice uses AES in CBC-Mode

The $IV$ is transferred with the messsage so Eve is able to change it anyway.

Maybe one of you can explain how to do this I don't have any Idea.

I think it is now valid to answer this question as this course is likely to be over.

First observer how CTR-mode works:
$C_1=E_K(IV)\oplus P_1$

As you can see, there's a linear relation between the plaintext and the ciphertext. You now use $C_1$ (observed) and $P_1$ (known). You want to make $C'_1$ decrypt to $P_1'$. To obtain this you first construct $\Delta P=P_1\oplus P_1'$. Now you induce $\Delta P$ into the $C_1$, yielding $C_1'=C_1 \oplus \Delta P=C_1\oplus P_1' \oplus P_1=E_K(IV)\oplus P'_1 \oplus P_1 \oplus P_1=E_K(IV)\oplus P'_1$, meaning the plaintext is as desired.

Now observe how CBC-decryption works. $P_1=D_K(C_1)\oplus IV$. By applying the same $\Delta P$ as above to the $IV$, you reach the desired effect: $IV'=IV\oplus \Delta P \Rightarrow P'_1=D_K(C_1)\oplus IV \oplus \Delta P=P_1\oplus \Delta P$. As $\Delta P$ is constructed such that the message body is changed in the desired way, the desired change is done upon decryption.


Risks of publishing multiple signatures Is there a risk when publishing multiple signatures for the same message? For instance, an ECDSA key (using an EC key) and a RSA-PSS signature (using a RSA key).

The context of my question is the use of Web Crypto Javascript library, where the only signature algo implemented by Edge is RSA-PKCS1 (which is not the latest recommended algo).

I was thinking of producing multiple signatures using different algo/keys and let the client check the one it wants.

Is there a risk when publishing multiple signature for the same message ?

As long as the keys are independently generated, there's no risk. This simply follows from the fact that every forgery on the composite scheme - the message signed with $n$ different keys / signature schemes - immediately implies a forgery against at least one of underlying signature schemes. But because we assume these underlying ones to all be secure, the composite scheme is secure as well. And yes, RSA-PKCSv1.5 is also secure.

  What risks are there if the signatures are made with the same key?

If you re-use keys with different signature schemes, e.g. use the same key for RSA-PKCS and RSA-PSS, all bets are off by default in standard cryptographic security models and careful analysis is required to regain security statements. Examples of this include the standalones-secure CBC-MAC (a PRF for inputs which are not prefixes of each other) and OCB2 which used two related primitives with the same key in an insecure way. Without naming concrete schemes to be paired, a general statement is impossible - if they can even reuse the keys which is e.g. impossible for ECDSA and RSA-PSS as one uses a point on a curve as the public key and the other a ring with an exponent.

  However, providing two signatures lets say PKCS1/[SHA]256 and another PKCS1/SHA512 using the same private key, that would not be advisable. Right ?

This would be fine if PKCS1v1.5 signatures were secure for plaintexts without hashing, so a plain signature of 0x05 instead of hashing first would be secure. But this is not the case for PKCS1v1.5. So by default it's indeed not advisable to do this. If you really have to do it though, it could be fine on the grounds that random functions (SHA256 / SHA512) are practically unrelated in their I/O behavior.


With composite $n_1$ = $p_1q_1$, and a separate $n_2 = p_1q_2$, can the primes be calculated more efficiently than factorization? Supposing that the (3 total) primes are kept secret? Does the reuse of $p_1$ allow an attacker to compromise $n_1$ and $n_2$ if the attacker guesses that both were generated with a shared prime between them (each having one unique prime)?

Yes, this trivially compromises them. Simply compute the gcd of $n_1$ and $n_2$, which will return $p_1$ (assuming $q_1 \neq q_2$). The gcd can be computed efficiently using Euclid's algorithm.


E0 encryption algorithm attack vector E0 is used for encrypting Bluetooth communication, and it is initialised with a key of at most 128 bits. How secure is E0, and what are the E0 encryption attack vectors?

E0, being based on LFSRs, is not a particularly secure stream cipher. The key can be recovered via a known-plaintext attack given enough plaintexts. Two-level E0, which uses the keystream of one E0 instance to initialize the state of a second instance which itself encrypts only one 2745-bit frame, is vulnerable to an attack requiring 238 simple operations given the initial 24 bits of 223.8 frames. This is practical against Bluetooth even using two-level E0 for confidentiality. Note that one-level E0, which simply uses E0 directly as a stream cipher, is even more vulnerable to known-plaintext attacks.

To answer your questions directly:

E0 is not secure, even when used in the so-called two-level E0 scheme.
Known-plaintext attacks can be used to recover the key in negligible time.

If you need an extremely lightweight stream cipher, consider using ChaCha8, which is capable of encryption at the rate of 1.88 cycles per byte on a Core2Duo. Heavy optimizations may improve the keystream generation rate even more. ChaCha is an ARX cipher, using only addition, rotation, and bitwise exclusive-OR. The most secure shift register-based stream cipher out there, which is even faster, is Trivium, which takes only 80-bit keys. I'd recommend against it, but it is still better than E0.


Simulator in Zero Knowledge Proofs I'm reading about Zero-Knowledge-Proofs, in particular the argument of building a Simulator in order to prove the zero-knowledge property.
As expected, there's something that doesn't click yet.

Since a simulator is using a transcript to 'fool' the verifier, I understand the idea that since the Simulator knows nothing but the transcript, then the verifier can't extract any knowledge besides the statement being challenged.

Now, this doesn't prove that the verifier is not extracting knowledge from the transcript. If the transcript per-se has the knowledge, woudn't be a problem?.

Thinking it differently, if a monkey randomly type a Calculus book... yes, the monkey knows nothing about calculus, but a reading verifier would get real knowledge by reading his work.

Am I missing something?

..then the verifier can't extract any knowledge besides the statement
  being challenged.

Please let me amend it to, since a proper transcript (an indistinguishable one) can be generated by a simulator having no secret input at all, then transcript value is questionable for any reasoning about secrets (an easy, non-formal wording). In particular, a Prover can claim did not run (was not a party to) a protocol.

  Now, this doesn't prove that the verifier is not extracting knowledge
  from the transcript.

Knowledge extractor algorithm is a requirement for another property, proof of knowledge.

  Thinking it differently, if a monkey randomly type a Calculus book...
  yes, the monkey knows nothing about calculus, but a reading verifier
  would get real knowledge by reading his work.

Simulator is required to be efficient (expected polynomial running time), and calculus book is too complex to fit that. I'd suggest a weather forecast instead, like yes/no for rain tomorrow.

Back to book, a fast (efficient) reader would get garbage most of the times, with no chance to distinguish the correct case (proper textbook) better than guess.


Security analysis of a "one-time pad" type hill cipher Suppose the Hill cipher were modified to something like a one-time pad cipher, where Alice wants to send a message to Bob, and she chooses a key matrix randomly everytime a new message is sent (and the inverse of the key matrix is sent to Bob by other means everytime - just as in the one-time pad). Would this yield perfect secrecy or at least $\mathsf{IND-CCA}$?

Any thoughts on how to proceed with the security analysis of this?

Expand the equation system corresponding to the matrix multiplication:

$c_j = \sum_{i=0}^{n-1}k_{i,j}p_i$

In other words, each element of the cipher text corresponds to the sum of the cipher text elements of an OTP encryption of the input plain text. If the matrix is never reused, it should be fairly easy to go from here. You are basically using $n$ one time pads to encrypt the message instead of a single one. - Almost, since the $k_{i,j}$ values of the matrix have to be selected in such way that the determinant is not zero (presuming a prime field is used for the arithmetic operations). The next step is therefore to observe what this constraint means: If the diagonal is selected at random, the other matrix elements might be selected in such way that the determinant is non-zero.


Secret sharing over reals - constructing a (k,n) threshold scheme After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz
The above paper describes a method for sharing a real number as a secret, I quote from Section 4 (note: this paper may be accessed freely)

  We first introduce a (k,k) secret-sharing scheme which distributes a
  secret a taken from the interval [0,1). We use the Lebesgue
  measure on [0,1)   Choose independently, with a uniform distribution,
  k-1 real numbers, {$s_1$,.., $s_{k-1}$} in the interval [0,1).   2)
  Choose $s_k$ $\in$ [0,1) which satisfies $s_1$ +...+ $s_{k-1}$
  +$s_{k}$ = a (mod 1).   The proof that this is indeed a secret-sharing scheme is similar to the proof of its analogue in the finite case.
  For introducing a (k ,n) secret-sharing scheme for every k $\leq$ n,
  we observe that the same technique described in [BL] works here as
  well.

I can see how this (k,k) threshold scheme works. However, I am having some issues with the (k,n) threshold scheme - I've tried to look at Generalized Secret Sharing and Monotone Functions which is referred to above as BL (note - this paper can also be accessed freely.) I don't see how this paper helps me construct a (k,n) threshold scheme.
Any help would be appreciated!

This $(k,n)$ scheme works, but isn't very interesting.

Effectively, it is:

For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.

For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $\binom{3}{2} = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 \bmod 1), (r_2, z-r_2 \bmod 1), (r_3, z-r_3 \bmod 1)$, and distribute to the three share holders the shares:

$$(r_1, z-r_2 \bmod 1)$$
$$(r_2, z-r_3 \bmod 1)$$
$$(r_3, z-r_1 \bmod 1)$$

It works, as:

For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares.  In the above example, the first two share holders jointly know both $z-r_2 \bmod 1$ and $r_2$, allowing them to reconstruct $z$.
For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.

It's quite straight-forward; the biggest issue is that this requires distributing $\binom{n-1}{k-1}$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.


Standard tools for deterministic RSA key generation using seed? I'd like to resuse the mnemonic I have from bip39 for crypto in other domains such as ssh and tls, etc.  Are there standard tools (ie, openssl) to deterministically generate rsa key/pairs given a seed value?  I know technically it is possible using PBKDF2 to create a PRNG etc, but I'm definitely not looking to roll my own crypto.
I'm just wondering if there is an easy way using openssl or gnu to reuse my bip39 mnemonic in other contexts besides crypto.  Or if there is a way of converting the derived key pairs from one algorithm into rsa using standard libraries.
Thanks.

For generating RSA keypairs from BIP39 mnemonics, a quick search give me three tools. but it is a bad method for deriving key pairs. A better method is using Key Derivation Functions with a standard tool like GnuPG.


Reusing encrypted message on MITM attack? I'm using RSA public key private key for sending AES key from each client to server application.
then i'm using this AES key and IV for communicating between client and server.
what should i do for this MITM attack scenario??
client[encrypted text]   ---> Server
the MITM can use this encrypted text again to send it to server. consider if this encrypted text is an operation on transfering money.
the solutions i have planned for this are these:
1- attach new IV(encrypted) on each sending to server , so the server knows what's the next message iv is
well , i just can think about this only for now

You didn't mention the mode of encryption used.
If you are using CBC, predictable IVs maybe an issue.
I would recommend not reusing IV to prevent message replay. You can add a counter inside the encrypted payload and ensure it is increasing.
Notice when you add protection against replay you need to think about out of order etc.
In many cases protocols add timestamps and allow only a limited discrepancy.


Benefits of functional programming languages So far I mostly saw Python (because of simplicity) and C (because of efficiency) for cryptographic programming. But there is a different kind of programming languages called functional programming languages. An example is Haskell. These languages have no side effects and can be proven correct. I was wondering if those programming languages would have any benefits over "normal" programming languages when used for cryptographic applications. Is that the case? If yes, why aren't they used more frequently?

These languages have no side effects

Well, yes, kind of. They also are higher level languages, where you don't have (as much) control over e.g. timing or the wiping of memory. Those are the side effects that cryptographers worry about - rather than the mathematical side effects that you are alluding to.

I was wondering if those programming languages would have any benefits over "normal" programming languages when used for cryptographic applications.

Personally I think that any higher level language that provides e.g. memory protection is really a requirement for a secure application. Those kind of memory protection is generally provided by functional languages. It is probably even better than higher languages where you may have mutable variable values.
However, for the cryptographic primitives it makes sense to use machine code and - of course - native instructions whenever they are available. I've seen that bit-ops are generally much slower on these kind of languages. And we're talking about huge numbers here. For instance, Java and C# are already much slower than C if cryptographic primitives are programmed correctly (think a change of 2 x in performance degradation). Most other interpreted languages are much slower than that.
The performance advantages that functional languages may bring - such as delayed execution by passing functions - are not helpful - if not outright dangerous - for cryptographic primitives.

I was wondering if those programming languages would have any benefits over "normal" programming languages when used for cryptographic applications. Is that the case? If yes, why aren't they used more frequently?

Here again we must make a distinction between "cryptographic applications" and "cryptographic primitives". I think that a well tested library of native functions is quite often used within higher level languages. There are e.g. many OpenSSL wrapper libraries in use within higher level languages such as Python. I think this makes sense, although more (array) boundary testing on the used native libraries would be useful.
As for functional languages: I don't see this "proven correctness" as much of a benefit. Unusually there some boundary checks etc. to be made. But otherwise, generally you can work with the test vectors to show enough correctness for the primitive.
I still see purely functional languages mainly useful for mathematical applications and such like. Personally I think that they are complex enough that most developers will not use them for generic applications. Those kind of mathematical applications are generally not the type of applications that require a lot of security.
Whatever you think of the last section (which is rather opinionated), generally we don't choose a language based on the cryptography we tend to use. Security should be an integral part of an application design, but usually it is not the main use case. A language is mainly chosen because it fits the main use case or - of course - simply because of developer familiarity (and purely functional languages still are not the most popular languages out there).


Is there any more information on this RSA backdoor? Someone posted an article on Reddit a few days ago, and I haven't found much about it except for links back to the same page.

And for a brief summary, essentially, it's possible to introduce a backdoor during RSA key generation. For example, to generate a backdoored RSA-1024 key. (Assuming $\text{getPrime}(x)$ will return a random $x$-bit prime number)

\begin{align}
A &= \text{genPrime}(384)\\
P^\prime &= \text{genPrime}(128)\\
Q^\prime &= \text{genPrime}(128)\\
P &= Ak_1 + P^\prime
\end{align}

Where $k_1$ is incremented until $P$ is prime, starting with $k_1 = P^\prime$.

\begin{align}
Q = Ak_2 + Q^\prime
\end{align}

$k_2$ is is calculated similarly for $Q^\prime$.
$P$ and $Q$ are then used as the prime numbers for the rest of the key generation algorithm, and $A$ is kept as the backdoor key. $A$ can be generated based off of a predictable per-user value, like a MAC address or user ID.

To use the backdoor, the attacker (or in this case, developer) recalculates $A$ in the same way it was originally calculated (or just looks it up in a database) and then calculates $N^\prime = N \mod A$ and then factors $N^\prime$ into $P^\prime$ and $Q^\prime$. This will take the complexity of factoring a 256-bit number, which is well within reach of most organisations concerned with implementing backdoors. $P^\prime$ and $Q^\prime$ can then be used to calculate $P$ and $Q$ in the same way as above, and thus generate the entire private key.

Is there any more information about this? Possible attacks? (besides the obvious one in the case that $A$ is leaked) It seems intuitive that this would lower the security of RSA, considering it's lowering the key space from 1024-bit to 256-bit, but I don't see how it can be broken without knowing $A$.

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key.

The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve):

The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good.  He keeps the EC private key secret; he'll install the EC public key into the program below.
To generate a key, the program selects a random 192 bit seed $R$.
It uses that seed to see a process that selects a random 512 bit prime $P$.
It encrypts the seed $R$ using the EC public value (perhaps using EC-ElGamal), resulting in a 384 bit value $E$.
It then selects a 512 bit prime $Q$ with the constraint that $Q \equiv P^{-1}(2E+1) \pmod{2^{385}}$
The product $PQ$ is the RSA modulus (and the rest of the RSA key pair is generated normally)

Then, the attacker can easily factor this RSA key (by extracting $E$ directly from the bit pattern of the RSA modulus, using the EC private key to decrypt it resulting in $R$, and then using R to recover $P$.  And, no one without the EC private key has any advantage to factor this, even if they know the exact procedure used to generate the RSA key; both $P$ and $Q$ were chosen fairly, and the additional constraints on $Q$ do not help the attacker at all.

The moral of this story: if the attacker can control your RSA key generation process, you may have no security.


What is the difference between regular and "twisted" ECC curves? When I do:

openssl ecparam -list_curves

I get, among other entries:

brainpoolP512r1: RFC 5639 curve over a 512 bit prime field
brainpoolP512t1: RFC 5639 curve over a 512 bit prime field

Apparently the "t" means it is a twisted ECC curve. Is this slightly more secure or slightly less secure? I'd rather give up a few milliseconds of performance than give up any security margin.

TL;DR: There is no difference.

Given an elliptic curve $E$ defined over $\mathbb{F}_p$ for some prime $p$, we say that a second curve $E_t$ defined over $\mathbb{F}_p$ is a twist of $E$ when $E_t\cong E$. That is, when there is an isomorphism between $E_t$ and $E$, defined over $\bar{\mathbb{F}}_p$ (the algebraic closure of $\mathbb{F}_p$).

From this we can conclude that every curve is a twisted curve, as every curve is isomorphic to itself. Thus the definition of a regular curve versus a twisted curve is nonsensical, there is no difference.

You may be left wondering why we care about twists in the first place. Well, it turns out that given some curve $E/\mathbb{F}_p$, in some cases one can force a user to work on some twist of $E$ instead (there could be many twists). This twist could have different security properties (notice the definition of twist with respect to $E$), which could in turn lead to an attack. This is an example of a so-called invalid-curve attack.

Edit: Note that ${\tt brainpoolPXXXr1}$ and ${\tt brainpoolPXXXt1}$ are trivial twists (see Definition 9.5.1). That means that the security properties are essentially the same. The reason why both these curves are specified, is because ${\tt brainpoolPXXXr1}$ is pseudo-randomly generated (and therefore supposedly leaving them unable to create backdoors), yet has large curve parameters. By specifying ${\tt brainpoolPXXXt1}$ which has $A=-3$, we can make some improvements in the curve arithmetic, making operations more efficient (see EFD).


Encryption on the cloud with versioning Can file-versioning, which is available for instance in Dropdox, weaken the security of encrypted files if someone is able to see two or more snapshots of the ciphertext at different times?

To be specific, the files are encrypted by PGP on the file level (each file, making extension: important.doc.pgp ) with asymmetric keys.

I'm assuming that you mean any time the file changes, it is re-encrypted with PGP. Here is a description of how PGP encryption works:

Whenever you change the file and re-encrypt with PGP, a new, independent session key is chosen. So what you end up with is a (potentially only slightly) modified file, being encrypted with a brand new session key.

All modern block ciphers, when used correctly, will protect against cryptanalysis, even when the analyst has access to multiple encryptions of the same (or slightly modified) plaintexts. Since PGP is generating a new, fresh, independent key, this would fall under the category of when used correctly. So, no, an attacker having access to all these encrypted versions gains no advantage in breaking the plaintext or the keys.


How to generate the APA SBox? I am trying to generate the S-Box provided in the Affine Power Affine paper (PDF) but I'm not sure I understand it fully.

The essence of the paper is this:

AES(i) = Affine(Power(i))

APA(i) = Affine(Power(Affine(i)))

Where Affine is the affine transform and Power is the inverse transform used in generating AES s-box.

Now to calculate the first value of the s-box, we take i = 0

APA(0) = Affine(Power(Affine(0)))

APA(0) = Affine(Power(63))     {Affine(0) = 63}

APA(0) = AES(63)

AES(63) = FB     {You can confirm this from wikipedia's page on Rijndael s-box}

So, APA(0) = FB

But the paper has a table which says that APA(0) is 8C.

There must be a mistake I made because I highly doubt that the paper has an error.

Actually, you are right and the paper is wrong.

They omitted the fact that they used a different generator and/or vector than the AES s-box. This is why you are not getting the same results.

I ran a brute force generation of all APA s-boxes, and none of them starting with $0x8C$ continued with the results of the paper. It is probable they used two different affine transformations, and it would take 65000 times longer to search that space, so I am not going to do it. There are other problems with the s-box; strict avalanche is inferior to the AES s-box, and there are 4 self inverse elements.

Here is the full report:

Iterative Periods: 2 (2)  12 (2)  26 (2)  176 (1)
Self Inverse error at index 135  0x87
Self Inverse error at index 152  0x98
Self Inverse error at index 171  0xAB
Self Inverse error at index 225  0xE1

SAC Min/Max: -16  +16  12.5%, DSAC: 452, DDSAC: 220, Avg/Dev: 128.2 8.35, Satisfied: 60.9% (39)
GA: 358.6, Dist: 0 62 242 456 544 442 222 68 12
Aval: 0.0312, Dist: 16 0 4 8 20 32 24 20, Totals 124 0.0605

HOSAC Min/Max: -16  +16  12.5%, HODSAC: 1464, HODDSAC: 724, Avg/Dev: 128.1 7.86, Satisfied: 61.2% (137)
HOGA: 1176.8, Dist: 0 242 776 1602 1940 1598 754 234 22

BIC Min/Max: -16  +16, DBIC: 1508, Avg/Dev: 127.9 7.88, Satisfied: 58% (130), BIC: 0.12856
HOBIC Min/Max: -16  +16, DBIC: 5244, Avg/Dev: 128.5 8.1, Satisfied: 57.4% (450), BIC: 0.13498

Differential Uniformity: 4 (255)
Non-linearity: 112  Delta: 16 (255)
AutoCorrelation: 32 (255)
SSI: 133120

There is a revised version of that paper from 2010 which uses $0x5B$ for the generator and $0x5D$ for the vector, and generates a different s-box.

The 2nd paper had reproducible results. It also had no self inverse elements and a full iterative period, although it still did not have fully superior statistical properties to the AES s-box.

It should be noted that APA using the Rijndael affine transformation is a complete mess of fixed points and is unsuitable for cryptographic applications. APA s-boxes within a different finite field than $0x11B$ used by Rijndael are more interesting, field reduced using $0x165$ has the best results.


How secure is Salsa20? I have been hearing about Salsa20 from quite some time. It is even the favorite cipher in the ransomware world. Some ransomware used this cipher, probably because of speed.

I want to know how secure  this cipher is when compared to AES. How much has it has been reviewed by cryptanalysts?

Pulling information from the wikipedia entry on Salsa20:

eSTREAM selection
Salsa20 has been selected as a Phase 3 design for Profile 1 (software) by the eSTREAM project, receiving the highest weighted voting score of any Profile 1 algorithm at the end of Phase 2.[6] Salsa20 had previously been selected as Phase 2 Focus design for Profile 1 (software) and as a Phase 2 design for Profile 2 (hardware) by the eSTREAM project,[7] but was not advanced to Phase 3 for Profile 2 because eSTREAM felt that it was probably not a good candidate for extremely resource constrained hardware environments.[8]
Cryptanalysis
As of 2015, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[3] breaks 8 of the 12 or 20 rounds.
In 2005, Paul Crowley reported an attack on Salsa20/5 with an estimated time complexity of 2165, and won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis".[9] This attack, and all subsequent attacks are based on truncated differential cryptanalysis. In 2006, Fischer, Meier, Berbain, Biasse, and Robshaw reported an attack on Salsa20/6 with estimated time complexity of 2177, and a related-key attack on Salsa20/7 with estimated time complexity of 2217.[10]
In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in 2255 operations, using 211.37 keystream pairs.[11] However, this attack does not seem to be comparative with the brute force attack.
In 2008, Aumasson, Fischer, Khazaei, Meier, and Rechberger reported a cryptanalytic attack against Salsa20/7 with a time complexity of 2153, and they reported the first attack against Salsa20/8 with an estimated time complexity of 2251. This attack makes use of the new concept of probabilistic neutral key bits for probabilistic detection of a truncated differential. The attack can be adapted to break Salsa20/7 with a 128-bit key.[3]
In 2012 the attack by Aumasson et al. was improved by Shi et al. aainst Salsa20/7 (128-bit key) to a time complexity of 2109 and Salsa20/8 (256-bit key) to 2250.[12]
In 2013, Mouha and Preneel published a proof[13] that 15 rounds of Salsa20 was 128-bit secure against differential cryptanalysis. (Specifically, it has no differential characteristic with higher probability than 2−130, so differential cryptanalysis would be more difficult than 128-bit key exhaustion.)

Salsa20 is about as secure and analyzed as one could reasonably ask for. It is one of the few alternatives to AES that a knowledgeable cryptographer could comfortably suggest for usage in the real world.


Efficient setup for a Montgomery multiplication Montgomery described an efficient method to compute a modular multiplication. This works by using a special constant $R$ and assumes the inputs $a$ and $b$ have been made into a special representation (residues $aR\mod N$ and $bR\mod N$) and produces the value $abR^{-1}\mod N$. Thus to pursue the computations, one needs the value $ab$ to be also in the special representation, which requires an additional (Montgomery) multiplication with the constant $R^2\mod N$.

This is especially useful to compute modular exponentiations with a large modulus $N$ and a big exponent such as in RSA.

Every step such as computing the special representation of $a$ and $b$ are costly, and so is the computation of $R^2\mod N$ (note that it has to be computed once, but still is costly).

What are the different ways to do the computation of $R^2 \mod N$ efficienty?

The usual way is to calculate $2^k R \bmod N$ for a small divisor $k$ of $l$ where $R = 2^l$ and use Montgomery multiplication in a Square-and-Multiply algorithm. This does require a division, but as $R$ is usually chosen to be just a little bit longer than $N$, the division doesn't have to be optimized much.

But you should also consider the fact that in some occasions (like RSA key generation) one can do also without knowing $R^2 \bmod N$. You neither have to Montgomery transform the random bases for a Fermat or Miller-Rabin test nor a number you want to invert using Fermat's little theorem (in the second case just Montgomery multiply with $1$ afterwards).


Security of a self-decrypting block-cipher? If I have a block-cipher like for example AES,
a plaintext $x$, we use different function to encrypt and decrypt
: $\text{encrypt}(x) = y$ , $\text{decrypt}(y)=x$.
Now, if we build a function with a permutation $P(x)$ with $P(P(x))=x:$
$F(x)=\text{decrypt}(P(\text{encrypt}(x))$ , we have $F(F(x))=x$, a function that encrypts and decrypts.

Does this reduce the security or allow new attack on the cipher?
I know stream cipher already encrypts and decrypts using the same function but what about a block-cipher ?

As I understand, your question is about using an involutive function $F$ as a block cipher. This function is constructed as $F(x) = D(P(E(x)))$, for some (let's assume secure) block cipher represented by $(E, D)$. I will assume the encryption and decryption keys are equal such that the same holds for $F$.
Below is a generic attack that only uses the involutive property of $F$, there might be additional problems (depending on $E$ and $D$).

It is typically required that block ciphers are secure against chosen-plaintext attacks.
In the example it is trivial to obtain $x$ given $y = F(x)$ and an encryption oracle. We just ask the oracle to encrypt $y$.
In other words, an encryption oracle is equivalent to a decryption oracle.
Practically speaking, the attacker just needs to get his victim to encrypt something that he already encrypted earlier. Do not underestimate this attack; it is often easier to trick the victim into encrypting something than you might suspect.

Note that many block ciphers do use involutions in their structure. This could be useful, for example, to reduce the size of the implementation.

What about stream ciphers?
In a stream cipher, the state of the cipher constantly changes. This effectively means that the function $F$ is variable, so you'd need a much stronger oracle (which can somehow rewind the state).


How can I (generally) calculate a stream cipher computation cost? With AES-CTR the computation time to encrypt a message of lengh $n$ blocks is $n$ computations of the block cipher.

What is the running time to encrypt a message of $n$ bits using a stream cipher, like Salsa, Snow, trivium or any other stream cipher? How can I (generally) calculate a stream cipher computation cost?

For any typical stream cipher (including block ciphers in streaming modes like CBC / CFB / OFB / CTR), the time needed to encrypt a message consists of two parts:

the time needed to set up the cipher, which is approximately constant, and
the time needed to encrypt a chunk of the message (also approximately constant), multiplied by the number of chunks in the message (rounded up).

Most ciphers will process the message (or at least generate the keystream) in chunks of more than one bit at a time.  For block ciphers in streaming modes, the chunk size will typically equal the block size of the underlying block cipher.  For dedicated stream ciphers, the chunk size may vary, even between different implementations of the same cipher.  For some examples, RC4 generates its keystream in chunks of 8 bits, whereas Trivium can generate anything from 1 to 64 bits at a time, depending on how strongly the implementation is parallelized.

In any case, the typical runtime will be of the form $a + b \lceil n / c \rceil$, where $a$ is the setup (+ teardown) time, $b$ is the time per chunk, $c$ is the chunk length and $n$ is the message length (in appropriate units, typically bits or bytes).  Asymptotically, this will be ${\rm O}(n)$.

One peculiar corner case is that, for ciphers that require the message to be unambiguously padded to a multiple of the chunk size (such as block ciphers in CBC mode), messages that already happen to be a whole number of chunks long will typically need to have an extra chunk appended, so that the time cost becomes of the form $a + b \lceil (n + 1) / c \rceil$.

Also, it should be noted that these are all theoretical timings.  In the real world, if you graph the time needed to encrypt messages of varying size on a real CPU, you're likely to see all sorts of weird jags, kinks and noise due to things like cache misses, branch prediction, microcode optimizations, interrupts, concurrent threads, etc.  On a large enough scale, though, the overall pattern will still generally look approximately linear in the message length.


Alter plaintext through IV in block cipher AES in CBC mode IV: 69bb375aa919c72aa561dd7b7ffacf66

Ciphertext: "c28ea025d10186510855d083747d6435c808d9857075abd9bfc54b094e60eaf3"

Plaintext: "SEND ENCRYPTED DATA"

I want to be able to change the resulting Plaintext to "SEND THE DATA", which if I understand correctly would involve altering the IV in this case.

I have read about the bit flipping and how this attack works, I am just having troubles implemeting it in this scenario, please help.

below the encryption (at the server side- we were given the code), includes the padding used,   def encrypt(plaintext):
            log.info("[%d] encrypt data command invoked" % (client_id))
            iv = Random.new().read(AES.block_size)

        # add padding
        if (len(plaintext) % 16 != 0):
            plaintext += b"_" * (16 - len(plaintext) % 16)

        cipher = AES.new(shared_key, AES.MODE_CBC, iv)
        ciphertext = cipher.encrypt(plaintext)

        return hexlify(iv) + b"," + hexlify(ciphertext) + b"\n"

   def no_tranform(plaintext):
        log.info("[%d] send data command invoked" % (client_id))
        return hexlify(plaintext) + b"\n"

    commands = {"SEND ENCRYPTED DATA": encrypt,
                "SEND THE DATA": no_tranform}

 Also you can see that the only allowed commands are "SEND ENCRYPTED DATA" and "SEND THE DATA" and I would like the latter.

Each bit you flipped in the IV changes the same bit in the decrypted plaintext. So if you want to change the first E character of ENCRYPTED into a T of THE then you need to XOR the binary representation of E and T (probably ASCII) and XOR that with the byte in the IV. This will of course only work for the first block of 16 bytes. Fortunately "SEND THE DATA" is small enough for that (13 bytes if I count correctly).

That leaves the problem of the padding. The original block contains the padding in the second block because of the size (19 bytes). However, you just have to adjust the padding of the first block by performing the XOR as displayed above. Instead of XOR'ing the final 16 - 3 = 3 plaintext bytes with a letter you XOR them with the value 03 in hex and XOR that with the IV. Now you've also generated the required padding.

Finally, you need to leave out the second block. And that's all me wrote, happy programming.


How does the security of Elliptic curve compare to normal discrete logarithm? Intro:
EC are often compared with RSA but how about a more safe version of the discrete logarithm?
All 3 can be reduced to the problem:
$$b = g^a \mod{P}$$
In RSA $P$ is a product of two primes. To solve the discrete logarithm 'just' a factorization of $P$ is required. Different to the two other cases $a,b$ is known and $g$ is searched.
But if $P$ is a prime the problem can get much harder. It depends at the factorization of $P-1$ because $P-1$ is also equal to the number of different elements.
As far as I know the best choice is a 'safe prime' with $P = 2 q +1$ with $q$ a prime as well.
This discrete logarithm can be solved in $\mathcal{O}(\sqrt{q}) $ with $q$ the biggest prime factor (with Pollard's algorithm).
At EC $P$ is a prime as well but the number of elements can be different (but still $\approx P$). It can e.g. be determined with Schoof's algorithm.
A number of safe elliptic curves can be found at safecurves.cr.yp.to .
Tested safe curves had all $2^3 \cdot q$ elemnts (with $q$ a big prime). Afak solving those will also take $\mathcal{O}(\sqrt{q}) $ time.

Question:
Given the discrete logarithm solving problem for normal numbers and elliptic curves (mod a prime $P_i, P_e$). Given a valid generator $g_i, g_e$ and a possible result $b_i, b_e$.
$$\text{normal: } b_i = g_i^{a_i} \mod P_i $$
$$\text{elliptic curve: } b_e = g_e^{a_e} \mod P_e $$
Let the elliptic curve have $N_e = 2^3 \cdot q$ different elements with $q$ a big prime (other variables chosen in that way).
Let $$P_i = 2 \cdot q +1$$
Do both problems have the same solving time of  $\mathcal{O}(\sqrt{q}) $ ?
(we ignore the linear factor of computation time for each single step due to different multiplication time)

Bonus questions:
Which other factor have impact into the solving speed?
BQ1.) The number of elements of some curves from safecurves.cr.yp.to had also the property: $N_e -1 = 3 \cdot r$ with $r$ a big prime. Does this have any impact?
BQ2.) Has the factorization of $P_e -1$ any impact at the security?
BQ3.) Has the factorization of $q-1$ any impact at the security? (for normal and EC)

Edit: Update

It looks like 'number filed sieve' can do better than Pollard's algorithm ($\mathcal{O}(\sqrt{q}) $). To use it on EC the embedding need to be small -> chose a big one
besides the safe prime property $P_i$ should als be not close to $p^n$ with $p$ a small prime like $2,3,..$

$\rightarrow$ assumption: so there is a difference?

As far as I know the best choice is a 'safe prime' with $P=2q+1$ with $q$ a prime as well.

This is the best choice for a given size of $P$, but not for a given size of $q$. See this.

This discrete logarithm can be solved in $\mathcal{O}(\sqrt{q})$ with q the biggest prime factor (with Pollard's (Rho) algorithm).

Essentially yes (minor caveat: $\mathcal{O}(\sqrt{q})$ is not effort, but the number of multiplications of integers of size $P$, with $P>q$, hence the effort grows faster by a factor at least $\ln P\,\ln\ln P$). That the DLP can be solved with such method and effort does not imply that such method or effort is needed. And if $P$ is a safe prime, there are methods (including the Number Field Sieve) requiring less effort. Again, see this.

Do (DLP in a subgroup of an appropriate Elliptic Curve on one hand, of $\mathbb Z_P^*$ on the other hand) have the same solving time of $\mathcal{O}(\sqrt{q})$ (group operations, where prime $q$ is the order of the subgroup)?

Yes, when using Pollard's Rho algorithm. That algorithm is believed optimum in the Elliptic Curve case, and for $P$ large enough in the $\mathbb Z_P^*$ case.
No, when $P$ is a safe prime (and large enough to make the DLP non-trivial), and using the Number Field Sieve to tackle the DLP in the subgroup of $\mathbb Z_P^*$.

Note: I don't know that the Number Field Sieve can be used to solve the DLP in an appropriate Elliptic Curve (sub)group; and it would come as a huge surprise if it was more efficient than Pollard's Rho algorithm.


Secure method for encrypting 32 byte private keys I am using 32 byte EC private keys on the client side of a web application. These keys should be securely stored on a server database. The keys should be encrypted (AES) before being sent to the server in javascript. The ciphertext will be given to the client when they have been authenticated with their login credentials. The client would then decrypt the ciphertext to obtain the private key.

Anyone with access to the database ciphertexts should not be able to derive the private keys.

On the face of it, it seems that ECB is actually fine because the private key data is pseudo-random, but ECB is generally not recommended for any purpose. What mode would be appropriate in this situation? CBC tends to be used often for similar purposes from what I can see.

If I used GCM, will the client always be able to authenticate the ciphertext? So if the client-side encrypted a private key with a particular encryption key and only retained the encryption key, the server cannot forge a combination of IV, authentication tag and ciphertext which would be decryptable using the same key?

I'm not sure if such authentication would be useful as already the client has to trust the downloaded client software, but I suppose it could be a matter of "why not?". In that case would there be downsides to using GCM? More data would need to be stored of-course but not a lot.

PBKDF2 is a reasonable method to derive the AES key for a password, am I right? Are there any weaknesses to PBKDF2 or advantages to any other algorithms?

Lastly I've read about the AES key wrapping algorithm, though I do not know much about it and there does not seem to be many open-source implementations.

SIV is a mode specially designed for this purpose. SIV-AES would be a good choice, but it has the same issues as AES-wrap; not many implementations. If you use a GCM you should make sure that the IV is unique (if your plaintext is ever not random you would otherwise be in problems).

As for the password based key derivation function: yes, PBKDF2 is good, with a high enough iteration count. For this kind of data though I would really make sure that the pass phrase has enough entropy. You could consider scrypt with a relatively high memory usage and possibly additional key access restrictions / authentication.


Value of $\varphi(n)$ and $\lambda(n)$ Is it true that $\varphi(n)$ is generally larger than $\lambda(n)$ for the same $n$? If so, can anyone give me a proof?

As $n$ is the product of primes $p$ and $q$, $\varphi(n) = (p - 1)(q - 1)$ and $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$. The former multiplies $p - 1$ and $q - 1$, whereas the latter finds the least common multiple of the two. Naturally, $\forall a,b:\operatorname{lcm}(a,b) \le a\cdot b$, so we can say that $\forall n:\lambda(n) \le \varphi(n)$. In the case that the LCM for $a,b$ is $a$ and $b$ themselves, then they will be equal. Otherwise, the LCM will always be smaller. As $p$ and $q$ are always primes and therefore odd, we have $2\mid\gcd(p - 1, q - 1)$, thus $\lambda(n) < \varphi(n)$.

So yes, it is true.


Inversive Congruential Generator The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$.
One can choose $a,b$ in $k$ such that the orbit length of the iteration is exactly $p$. My question is very simple:

Is the Inversive Congruential Generator actually used in Cryptography? Is there any known attack against it?

The inversive congruential generator is not commonly used in cryptography. Its basic description, in fact, makes it entirely unsuitable for it—once you know a single value of $x$, you can predict the remainder of the sequence, which is something a secure pseudorandom generator should not allow.

To avoid the above trivial attack, you could truncate the output to, say, half of the bits of $x$. But the truncated inversive generator is also predictable by more elaborate means, as long as you truncate fewer than half the bits.

To top it off, inversion modulo $p$ is a very slow operation, which makes this generator very inefficient. So even for non-cryptographic purposes this is not a good generator to use.


How can I calculate the avalanche effect in symmetric algorithms? I am working with symmetric algorithms in Java with javax.crypo and Bouncy Castle libraries and I need to calculate the avalanche effect of different symmetric algorithms such as DES, 3DES, Blowfish and AES.

I have read about the avalanche effect and means that when an input text is changed slightly (for example, flipping a single bit) the output changes significantly. To calculate this, I made some test by creating a new text changing the first word in the original text and later encrypting both texts. After this I compared the bits that had changed between the original text and the new text.

To this tests I used the four algorithms in CBC operation mode and with PKCS5PADDING. As I know, the change between the encrypted texts must to be high although the changed word is only in the first block of the text, because the input in CBC mode is the encrypted text generated by the previous block, so all blocks are used to generate the final text. So, I think that the change must be considerable.

I read that the 50% of change is a satisfactory value because it means that a change of a word or a single bit in the input changes the output with a 50% probability, and it is strong. The problem is that the results in my tests are about 50% for the four algorithms, and I think that it is no correct, because the difference will be higher and I suppose that AES that works with S-boxes as substitution for encryption must have more change. I have been searching a estimation of avalanche effect result values for these algorithms, to contrast with my results, but I haven't found a estimation. So, I don't know if I am calculating the avalanche effect correctly.

I calculated the avalanche effect in the resulting ciphertexts, not in each round during the encryption process.

I was looking for information and I have found few articles on this subject in which they show: the password used, the original ciphertext, and the encrypted text on it that has made one change. The comparison is performed by bitwise between the two ciphered texts, and so I understand, not in the ciphertext during rounds in the encryption process. It is not like this? Some of these articles are: link and link

Am I calculating the avalanche effect correctly in the symmetric algorithms?

Is there some estimated values about this effect in the algorithms?

You appear to be under the impression that AES should score better than DES, because AES is stronger than DES.

The issue is that your test is extremely crude; any decent block cipher will pass the test.

If I were to go to an analogy, it's as if you have devised a test for automobiles, which the sole check being 'is there an engine?'.  You run your test on a Yugo, and it passes, you run your test on a high-end Porsche, and it passes; and you ask, the Porsche is a much better car than the Yugo; why isn't it scoring better?

As for the differences between AES and DES, the important ones are:

AES has a much larger key than DES.  The DES key is small enough that it can be (and has been) brute forced (that is, checking each key individually) by adversaries with a reasonable amount of resources; the AES key space is so much larger that, even with the "small" setting of 128 bits, it's infeasible to do so.
The AES block size is larger than DES; with DES (and CBC mode), you'll start to leak contents of the plaintext after encrypting a few Gigabytes; the same will happen with AES, but only after a truly huge amount of data has been encrypted (e.g. the amount of data that travels over the entire internet in a week)
There's also some known ways to apply linear cryptanalysis to DES; however (again) only after a large amount of data has been encrypted.

Your tests won't pick up on any of these differences, and so (as far as your test is concerned), DES and AES look equally good.


Adaptive vs. Static security model in ABE From Lewko, I understand the difference between an adaptive and selective model:

Adaptive model: the attacker can adaptively query the challenger for private keys.
Selective model: the attacker has to declare the challenge message BEFORE he can see the public parameters setup.

Now comes to Rouselakis with static model:

  All queries done by the attacker are sent to the challenger immediately after seeing the public parameters.

This is what I understand: After seeing the public parameters, the attacker sends a batch of requests to the challenger, and the challenger replies a batch of responses.

Q1: The word "immediately" confuses me. Why immediately after seeing the public parameters?

Q2: How "weaker" is static model than the adaptive model? Can anyone give an example that the attacker can break this scheme by sending "adaptive" requests to the challenger (but not all requests in one patch)?

Towards Q1 -- immediately should just mean that the adversary has no more information as the public parameters (so it doesn't have to be "few seconds" but. "without any intermediate messages")

Towards Q2 -- assume you have some system with a weakness like the following: If you get to send an valid encryption to the challenger, the challenger responds with the master key. You won't be able to exploit that in the static model (with overwhelming probability) but in the adaptive case it's easy


How much can I assume hashes to be different for different contents? I know that some hashes, like MD5 or SHA-1, that were previously thought to be safe are now known to be vulnerable to collision attacks. But it is obvious that collisions exist for all hashes, given that the space of possible hashes is smaller than the space of possible contents. For example, if one considers all possible files whose size is smaller or equal to the hash size, there must be some collisions.

However, I wonder if I can be sure that hashes will be different for “small enough” differences in contents. For example, for a given hash, can I assume that:

All contents whose size is = the hash size will have different hashes (so that if $H(m_1) ≠ H(m_2)$ then $H(H(m_1)) ≠ H(H(m_2))$)?
All contents smaller that $m$ bits/bytes will have different hashes?
All contents that differ by less than $m$ bits/bytes will have different hashes?
All contents that differ by less than $m$ consecutive bits/bytes will have different values?
Inserting less that $m$ bits/bytes within a content will change its hash?
Inserting less that $m$ bits/bytes at the end/beginning of a content will change its hash?
Anything else?

If there are such assumptions that are true, do they survive the hash being truncated?

I guess answers to these questions are very dependent with the chosen hash functions. I’m very interested by answers about hashes of the SHA-2 and SHA-3 families, but answers about other hash functions (even MD5 and SHA-1) are welcome as well.

All contents whose size is = the hash size will have different hashes (so that if hash(file1) ≠ hash(file2) then hash(hash(file1)) ≠ hash(hash(file2)))?

No, but finding such a value should be impossible for a secure hash.

  All contents smaller that m bits/bytes will have different hashes?

That depends on the value of m. If m = 1 (bit or byte) then it will be true for any secure hash. If m is very large we get back into the situation that there must be identical hashes because of the pigeonhole principle.

  All contents that differ by less than m bits/bytes will have different hashes?

No, because of the pigeonhole principle again. No, but finding a pair of messages that collide should be impossible for a secure hash.

  All contents that differ by less than m consecutive bits/bytes will have different values?

See above.

  Inserting less than m bits/bytes within a content will change its hash?

See above.

  Inserting less than m bits/bytes at the end/beginning of a content will change its hash?

See above.

  Anything else?

Basically it all comes down on the basic properties of secure hash values.

  If there are such assumptions that are true, do they survive the hash being truncated?

In general truncating a secure hash of course limits the security, but it should only harm security by 1 bit for each 2 bits removed (for collision attacks - possibly more for other attacks, but those would have a higher security in to deal with in the first place).

  I guess answers to these questions are very dependent with the chosen hash functions. I’m very interested by answers about hashes of the SHA2 and SHA3 families, but answers about other hash functions (even MD5 and SHA1) are welcome as well.

The answers above are for generic secure hash functions. MD5 / SHA-1 are obviously not considered secure anymore.

Detailing each and every security property of each and every secure hash and testing if it is vulnerable to attacks is way too broad for any answer.


Severity of Cooking NIST P Curve Constants Bruce Schneier and Gregory Maxwell have both stated that they believe the constants chosen for NIST's P curves (i.e. P-256r) are cooked. DJB has put together a detailed list of red flags but, outside of the suspicious constant, everything else appears to be potential implementation issues.

What kind of a speedup could they gain from cooking the constant?

Note: I'm aware of related questions, I'm looking for more of a high-level takeaway.

These are "red flags".  No one knows of a specific exploit, only some possible reasons to be concerned that one might exist.  Since no one knows of a specific attack, we can't possibly know how much speedup such a hypothetical attack might allow.  Basically, you're asking for speculation where there is not enough information to allow meaningful speculation, so there's no useful answer to your question.  Of course, if the curves are cooked, the sky is the limit: it could be arbitrarily bad.  So at this point, there's not a lot of hard data to make a risk management decision.


Is it ever safe to use encryption with compression? In the wake of compression-based side-channel attacks like CRIME and BREACH, are there any safe ways to combine compression and encryption?

The JWE Specification was finalised almost 2 years after BREACH, but still includes DEFLATE compression as an option. Are there cases where that could be used safely?

In my use case (storing encrypted data in a user session token), experimentation has shown compression of around 42% on average, and every bit counts, so I would dearly love to be able to turn this on safely!

I think that the answer to this question is a bit more involved than it first seems. The reason is that the compression attacks work when different lengths after compression reveal information about the plaintext. This is of course a huge problem. However, you have to ask the question without compression as well: when does the plaintext size leak information.

In practice, the plaintext size leaks information in many settings, and it's very problematic. A very nice paper that deals with this is called Side-Channel Leaks in Web Applications: a Reality Today, a Challenge Tomorrow (it appears at IEEE S&P 2010).

So, this question arises when using compression and when not using compression in exactly the same way. If you have a lot of control over your application, then you can pad to a fixed length (if this is feasible regarding efficiency). This is indeed harder to do when using compression since you typically don't have a fixed useful upper-bound on the post-compression length. If you did have such an upper bound, then you could compress and then pad.

In many cases, the actual values being encrypted are not known ahead of time and the person designing that part of the application knows nothing about security. Then you are in trouble whether you are using compression or not.

In summary, length leakage is a real problem that is way too ignored. The use of compression in some cases makes it worse (like in the CRIME and BREACH scenario), and in some cases it's the same problem as without compression. It depends on the application and you have to do the analysis.

(Just to answer the specific question: if you are saving 42% by using compression, try to estimate the maximum foreseeable size after compression and pad to that; you may very well still save 25-35%.)


Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-QuantumWorld In this paper (Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World), author describe password authenticated key exchange scheme on page 9 and 10 (see Fig. 1 on page number 10).

I have following doubts in my mind

  How initially new user starts communication with the server. Whether there is any registration process for new user?
  How server gets the client password, as in the protocol client do not send any password. On the contrary, server verifies it as $\gamma$' = -H1(pwc) where pwc is client password. I think Server may ask for password from client during registration phase and then store it in its database but i am not sure.
  In Fig. 1 on page number 10, client send $<C,m>$ to server. Is 'C' is client's id or sid or something else. As author do not give any description of it.
  Similarly, S is in session key formation skc= H4(C,S,m,$\mu$,$\sigma$,$\gamma$') in Fig.1. Is S is server id or sid or something else?

Please Guide.

A password authenticated key exchange (PAKE) scheme assumes that the two parties have some shared secret (the password) with too little entropy. They now want to agree on a key and authenticate each other using this password.

The trick is to do this in such a way that an attacker cannot brute force the password with recorded data. This ensures the password remaining secure in spite of the low entropy because you always have to talk to one of the parties to try a guess.

So 1. and 2. are out of scope for PAKE schemes. The password is just assumed to be pre-shared. 3. and 4.: Yes, $\mathcal{C}, \mathcal{S}$ identify the client and the server. These must usually be included  in authentication protocols to avoid tricky relay attacks. I recommend Boyd's book for details.


Is this MAC scheme secure? Say we have a computationally secure Message Authentication Code scheme (Gen, Tag, Ver).

Let $Tag'_k(m):=$ first half bits of $Tag_k(m)$. Let's assume the range of tags is $n$bits.

Is (Gen, Tag', Ver) secure?

An efficient adversary that breaks (Gen, Tag, Ver) can't be constructed using an effecient adversary that breaks (Gen, Tag', Ver) because the former still would have to guess the last $\frac{n}{2}$ bits. So I want to say it's not secure.

Yet I want to say it is secure because I can't think of an algorithm that can efficiently break (Gen, Tag', Ver).

It is not secure in general, but not insecure in general either.

For example, you can get a MAC algorithm for which it would be secure by concatenating constant data to a secure MAC. $Tag_k(m) = M_k(m)||0^n$ is a secure MAC if $M$ is. And clearly taking the first half of that is a secure MAC if $n = |M_k(m)|$.

On the other hand, reverse the order of the constant and non-constant part above and you get a MAC scheme for which taking the first half is very insecure.

If your secure MAC algorithm is based on a PRF, you can take the first half and have a MAC that is secure, but easier to guess randomly. (Because a secure PRF is a secure MAC and a truncated PRF is still a PRF.) Many MAC algorithms like HMAC and CMAC, for example, can be truncated for this reason.


Requirement for the length of a HMAC tag? I've seen NIST requirements about key length. What about the output lengths ?

Is 112 bits enough for the HMAC output length ? Can we truncate the tag to keep only 112 bits ?

Short answer, no.

The 112-bit value is actually the security parameter, and not necessarily the key length. For all NIST hash functions, the security provided is half the output bit of the hash function, therefore SHA-224 or better is required for 112-bit security. The security parameter we are considering is collision resistance.

However, there are other considerations for a MAC, such as how long the attacker will have to forge the code, which in some applications can be shorter than a second, and you can get away with a shorter code, such as 96-bits, which provides only 48-bits of security. A threat analysis of your application can determine if this is acceptable. 96 and 128-bit MACs are common lengths for short lived messages, with 128-bits becoming standard for new algorithms. How MAC failures are handled is also very important.


"perfect" hash function Does there exist any hashing function that has a different output for all of the messages?

For example, let's say we have the function $H_{256}(x)$

Where $H$ is a 256 bit digest. Is it possible to construct $H$ so that it has a different output for every combination from $0$ to $(2^{256}-1)$?

EDIT: what I mean is, if you have a hash function which produces a fixed length 256 bit digest, is it possible to make such function so that every permutation of 1's and 0's of length 256 have a different output? I hope I'm clear now

What you are looking for is a permutation,  and not normally what we call a hash function.
The identity function is a permutation and so is modular addition. And many more.

You probably want some other properties of cryptographicly secure hash functions such as preimage resistance.

A pseudo random permutation will suffice any secure block cipher such as AES will meet the bill.

Note this in itself isn't a usefull hash function, for hash functions we want a compression function where the output is smaller than the input. From pigeon hole principal it is obvious that if the output domain of a function is smaller than it's input domain it must have collisions and can not be a permutation.

With cryptographically secure hash functions like SHA-3 we fully expect there to be many collisions even when the input domain is restricted to match the output domain we simply don't know how to find any such collisions which is a basic requirement for cryptographically secure hash functions.


Why is Diffie-Hellman considered in the context of public key cryptography? In all textbooks I used the Diffie-Hellman key exchange is under "public key cryptography".

As far as I can see it is a method to exchange a key to be used with a symmetric cryptographic algorithm, so it falls very naturally in the area of symmetric key cryptography.

So where does DH stand in the split between symmetric and public key algorithms?

The Diffie-Hellman key exchange is a public-key technology. It is (by itself) not an encryption algorithm (or signature algorithm), though.

Here is the basic function: (All calculations here happen in a discrete group of sufficient size, where the Diffie-Hellman problem is considered hard, usually the multiplicative group modulo a big prime (for classical DH) or an elliptic curve group (for ECDH).)

Each party choses a private key $x$ or $y$
Each party calculates the corresponding public key $g^x$ or $g^y$.
Each party sends the public key $g^x$ or $g^y$ to the other party.
Each party uses the received public key together with its own private key to calculate the new shared secret $(g^y)^x = (g^x)^y$.

The result of this key exchange is a shared secret, which is usually then used with a key derivation function (using other input known to both parties, such as a session ID) to derive a set of keys for a symmetric encryption scheme and MAC keys, if we aren't using an encryption scheme with integrated authentication. If we are building a bidirectional channel (like in TLS/SSL or SSH), we derive different keys for both communication directions.

This might be what causes confusion: it is an asymmetric technology used to negotiate symmetric keys. But the same is valid for most other asymmetric technologies, like signature or encryption algorithms: At the core there is something asymmetric, but then we use a symmetric algorithm to do the bulk of the work. For example, with most asymmetric encryption algorithms we usually encrypt just a symmetric key for the actual message, with most signature algorithms we first hash a message, then asymmetrically sign the hash.

The values $g^y$ or $g^x$ are named public keys, because they can be transmitted in plain, so anyone listening on the connection knows it.
The values $x$ and $y$ never leave the choosers computer, so they stay private. $(x, g^x)$ and $(y, g^y)$ are the private-public key pairs here. Incidentally, these are the same types of keys as in DSA or ElGamal.

One could have long-term key pairs (and then the public key could even already be in some address book, saving the transmission, or be signed with some certificate), but more usually these key pairs are created on the fly for each connection.

When combining the Diffie-Hellman key exchange (with a long term public key of the receiver) with a symmetric encryption scheme, we get a nice public-key encryption scheme – actually one of the first ones to be proposed at all. It works like this:

The receiver has a private key $x$ and a corresponding public key $g^x$.
The sender somehow securely obtains the public key $g^x$.
The sender choses a temporary private key $y$ and calculates the corresponding public key $g^y$.
The sender calculates $(g^x)^y$ and derives from this a symmetric key $K = f((g^x)^y)$.
The sender encrypts his message: $C = E_K(P)$.
The sender sends $(g^y, C)$ to the receiver.
The receiver gets $(g^y, C)$.
The receiver calculates $(g^y)^x$ and derives from this $K = f((g^y)^x)$. This is the same $K$ as before.
The receiver decrypts the message: $P = D_K(C)$.

This is an asymmetric encryption scheme – to encrypt, the sender needs to know only $g^x$, while for decryption $x$ itself is needed.


Size of encrypted AES CEK in CMS block When I run

openssl cms -encrypt -aes256 -in sample.der -out wrapped.der -outform DER -recip ecc.crt -keyopt ecdh_kdf_md:sha512

the part of the CMS output which is supposed to have the 256 bit CEK encrypted under the KEK shows to be 40 bytes:

316:d=7  hl=2 l=  40 prim:        OCTET STRING      [HEX DUMP]:FDC50AE5E72BC6D856D9682ACA5B4C2BD23F6B8A35F2E03417E0FE32062B810D3E4DF0048D1C0E2F

I was expecting this to be 48 bytes (32 byte encrypted output + 16 byte padding). It appears the KEK generated from the ECDH operation is not AES256.

What is the key type of the KEK and algorithm used to encrypt the CEK?

This is the complete CMS message:

0:d=0  hl=4 l= 724 cons: SEQUENCE
4:d=1  hl=2 l=   9 prim:  OBJECT            :pkcs7-envelopedData
15:d=1  hl=4 l= 709 cons:  cont [ 0 ]
19:d=2  hl=4 l= 705 cons:   SEQUENCE
23:d=3  hl=2 l=   1 prim:    INTEGER           :02
26:d=3  hl=4 l= 328 cons:    SET
30:d=4  hl=4 l= 324 cons:     cont [ 1 ]
34:d=5  hl=2 l=   1 prim:      INTEGER           :03
37:d=5  hl=3 l= 151 cons:      cont [ 0 ]
40:d=6  hl=3 l= 148 cons:       cont [ 1 ]
43:d=7  hl=2 l=   9 cons:        SEQUENCE
45:d=8  hl=2 l=   7 prim:         OBJECT            :id-ecPublicKey
54:d=7  hl=3 l= 134 prim:        BIT STRING
191:d=5  hl=2 l=  23 cons:      SEQUENCE
193:d=6  hl=2 l=   6 prim:       OBJECT            :dhSinglePass-stdDH-sha512kdf-scheme
201:d=6  hl=2 l=  13 cons:       SEQUENCE
203:d=7  hl=2 l=   9 prim:        OBJECT            :id-aes256-wrap
214:d=7  hl=2 l=   0 prim:        NULL
216:d=5  hl=3 l= 139 cons:      SEQUENCE
219:d=6  hl=3 l= 136 cons:       SEQUENCE
222:d=7  hl=2 l=  92 cons:        SEQUENCE
224:d=8  hl=2 l=  82 cons:         SEQUENCE
226:d=9  hl=2 l=  41 cons:          SET
228:d=10 hl=2 l=  16 cons:           SEQUENCE
230:d=11 hl=2 l=   3 prim:            OBJECT            :organizationName
235:d=11 hl=2 l=   9 prim:            PRINTABLESTRING   :Widgits Inc
246:d=10 hl=2 l=  21 cons:           SEQUENCE
248:d=11 hl=2 l=   3 prim:            OBJECT            :organizationalUnitName
253:d=11 hl=2 l=  14 prim:            PRINTABLESTRING   :SUB-CA ENC
269:d=9  hl=2 l=  37 cons:          SET
271:d=10 hl=2 l=  16 cons:           SEQUENCE
273:d=11 hl=2 l=   3 prim:            OBJECT            :x500UniqueIdentifier
278:d=11 hl=2 l=   9 prim:            BIT STRING
289:d=10 hl=2 l=  17 cons:           SEQUENCE
291:d=11 hl=2 l=   3 prim:            OBJECT            :commonName
296:d=11 hl=2 l=  10 prim:            PRINTABLESTRING   :ENC CA
308:d=8  hl=2 l=   6 prim:         INTEGER           :333230303032
316:d=7  hl=2 l=  40 prim:        OCTET STRING      [HEX DUMP]:FDC50AE5E72BC6D856D9682ACA5B4C2BD23F6B8A35F2E03417E0FE32062B810D3E4DF0048D1C0E2F
358:d=3  hl=4 l= 366 cons:    SEQUENCE
362:d=4  hl=2 l=   9 prim:     OBJECT            :pkcs7-data
373:d=4  hl=2 l=  29 cons:     SEQUENCE
375:d=5  hl=2 l=   9 prim:      OBJECT            :aes-256-cbc
386:d=5  hl=2 l=  16 prim:      OCTET STRING      [HEX DUMP]:1DD39A70A664EDA8B78EAE1A79D8ECDF

(moved from comment, expanded slightly)

(AES) Key Wrap is not the same as normal data encryption like CBC or GCM; it does quite a bit of remixing, and adds exactly 64 bits to any AES "plain key" (here 256 + 64 = 320 = 40 bytes) even though it uses the AES algorithm which has a 128-bit data block. See http://tools.ietf.org/html/rfc3394 and the relevant example in section 4.6.

The KEK is indeed 256 bits in this case, determined by the algorithm id-aes256-wrap, but that key doesn't appear in the message; it is derived from ECDH key agreement, using the originatorkey in the message (in the BITSTRING at offset 54) and the key in the recipient cert identified in the message.

The ECDH key(s) here appear to be on a 521-bit curve, presumably secp521p1, although on looking closer I notice it is not encoded in the AlgorithmIdentifier for originatorkey as is normally the case for encoded public keys. If the ECDH curve were substantially smaller, then the key-agreement strength would be less than 256, which would make the use of a 256-bit CEK in a sense wasted.


Recover plaintext in passive attack of RSA of coprime public key I have a situation in RSA like this.

Charles sends same message $m$ to Alice and Bob encrypted with $e_A$ and $e_B$ respectively. It happens that he they are under same modulus $n$ and $gcd(e_A, e_B)=1$. Now Eve intercepts two messages $c_A$ and $c_B$. The claim is that Eve can easily get $m$ in this situation.

My thought on this case is follows:

With $e_A$ and $e_B$ coprime, Eve can use the extended Euclidean algorithm to get solution to $1=a_1e_A+a_2e_B$. She then calculate $(c_A)^{a_1}(c_B)^{a_2} \bmod n = m \bmod n $
Now the problem is that one of $a_1$ and $a_2$ is actually negative (let's assume $a_1$). So the above $(c_A)^{a_1}$ involves calculation of an inverse modulo $n$. Yet I think $c_A$ is not necessarily be invertible.
An concrete example I can think of: $p=5$, $q=7$, $n=35$, $\phi(n)=24$, $e=11$, $m=21$, in this case, $c_A = 21$, not invetible.

I think somehow Eve must be able to recover the message. But I simply got stuck in above analysis.

Am I missing something? Please point out! Thanks so much!

Hint: if $c_A$ is not invertible, what does that say about $gcd(c_A, n)$?  How can you exploit that to obtain $m$ in another way?