Why not authenticate full-disk encryption? Common FDE software (TrueCrypt, BitLocker, dm-crypt) doesn't authenticate ciphertext stored on the disk. The commonly cited reason is "it would take too much space", reasoning that you would need an authentication tag for every sector and that would eat significant percentage of available space.

With 512-byte sectors and HMAC-SHA256 for authentication, you would consume roughly 6 % of disk space if each sector was fully authenticated. I could understand that someone would consider this amount to be too much, but if that's the case, you could simply truncate the HMAC tags, for instance to 64 bits (still better than nothing, right?), and use less than 2 % of total space.

With 4096-byte sectors, space is a complete non-issue, less than 1 % is spent on per-sector HMAC tags. Especially for AES-CBC-ESSIV where malleability is a significant risk, this seems like a price well worth paying.

Given that with CBC you need to re-encrypt the whole sector every time anyway, I don't see how authentication would matter even in terms of performance.

So, are there reasons for not using authentication that I'm missing?

Authentication and probabilistic encryption are two desirable features which each take up a small amount of extra space. And you are absolutely right that the percentage of space consumed is of no concern in most scenarios.

But as the other answers also point out that means you can no longer fit a logical sector inside a physical sector of the same size. That is a significant practical problem.

In terms of reading it is not a major issue. For example if every 512 byte logical sector requires 592 bytes to be physically stored on disk, you could simply store every group of 32 contiguous logical sectors in 37 contiguous physical sectors.

In such a layout you have the small percentage of slowdown for sequential reads which is to be expected. And each seek is also slightly more expensive because you would need to read one extra physical sector each time you have done a seek.

The real problem is writing. Most of the time when writing a range of logical sectors the first and last sector will only need to be partially written. That means the encryption layer has to read the original, update it, and write it back. That costs expensive additional seeks. Moreover the encryption layer might not know beforehand which is the last sector to be written, so it might end up doing the read-modify-write cycle for sectors in the middle of the range to be updated.

But it gets worse. If the operation is for some reason interrupted (for example kernel freeze or power failure), the cycle may not have been completed, which can corrupt your data.

If the physical disk guarantees atomic updates, the logical layer would not guarantee atomic updates. Instead the logical layer would potentially leave you with a logical sector which produce read errors on every attempt to read.

If the physical disk does not guarantee atomic updates, it gets even worse. The last physical sector written could contain data related to two or more logical sectors. If it got corrupted because of a power failure during write, the logical layer would not only lose the logical sector being written but also other nearby logical sectors which were not even being written to at the time of the power failure.

Very similar problems exist at the file system layer, where one common solution is a journal. But introducing another journal at the block layer means more slowdown and extra disk space usage.

This overhead could be mitigated by moving the encryption to the file system layer. But storage encryption is difficult enough to get right as it is, integrating it with the file system layer makes it a lot more complicated and thus more error prone.

There is another layer of complexity once you realize that protecting the integrity of individual sectors is not even sufficient. If each sector is individually protected by a MAC (or similar) an adversary could selectively revert individual sectors to an earlier point in time.

By selectively reverting a subset of sectors the adversary can construct contents which does not match any earlier point in time.

To see why this is bad imagine a file was deleted and the sectors it covered were reused for a different file. The adversary could combine the metadata from when one file existed with the data sectors from when the other file existed. This means the adversary has successfully moved the protected data from one file to another. If one of the files was highly confidential and the other was one that you would happily share with anybody, the adversary would be able to trigger a leak of confidential data.

You could protect against this by computing a hash-tree over the disk and storing a MAC of the root of this tree. This makes updates even more complicated, and updating a sector is now going to take logarithmic time rather than the constant time we were used to.

The worst problem however is that you still need to protect the integrity of the crypto code. If the code to do all the cryptography is not protected, an adversary could simply modify that code to bypass all the security measurements. And not only the crypto code itself, but also all the code used to bootstrap the system to the point where it can start reading the encrypted disk needs to be protected.


AES with small and large string keys byte *key;
String skey = "abcde"

If I convert skey to bytes and uses it to encrypt AES 128 bit, 192, and 256 bits. How AES would work with small key sizes or large key sizes? Is it key expansion or key round that would make it work or it would break? What actually happens behind?

TL;DR: it depends on the API implementation of the AES encryption function you are using.

AES is a block cipher with specific key sizes, 128, 192, 256 bits. To use it as an actual encryption mechanism it is required to use it in a specific mode of operation. Otherwise it is only useful to permute a single 128 bit block. These mode of operations (usually) do not affect the key size.
You can broadly distinguish the following possibilities:

If you use a programming API with a badly sized key then it usually will generate an error (special return value or exception);
Some API's actually implement the full Rijndael instead of AES; AES is a subset of Rijndael. Rijndael accepts all key sizes between 128 and 256 bits with a step of 32 bits (AES is based on 32 bit operations) but it will not accept just any key size such as a key size smaller than 128 bits as in your example;
Yet other API's do not perform input validation at all, for instance the horribly crappy C/PHP mcrypt library simply right-pads with zero bytes and may even use a partial key if it is too big (nowadays it additionally outputs a message to the warning log);
If you're using a lower level programming language and API (your code kind of hints at C) then it may be that you first need to select AES-128, -192 or -256 and then provide a key. As the key size is now known this could be simply a pointer in memory. In that case the short key will be used together with any byte value that comes after the key. If you would not be able to re-generate (guess, brute force or simply get lucky because the program always behaves similarly) then the message you've just encrypted may get lost forever (!). If the key is too large then part of the key may be simply ignored (just like it would for possibility #3).
Sometimes API's are also programmed on a higher level where instead of a key a password is accepted. This should be apparent from the API, if the API was designed well. In that case a Password Based Key Derivation Function (PBKDF) should be used to convert a password to a 128, 192 or 256 bit key. This function should be documented as well. The result is called Password Based Encryption or PBE. One standard for this is PKCS#5: Password-Based Cryptography Specification (Version 2.1) in RFC 8018.

Note that the bits in an AES key should be indistinguishable from random. A string such as a password doesn't have this property, even if it is encoded to bytes. ASCII for instance only uses 95 printable characters per byte. Even though other encodings (Windows-1252 or UTF-8) may contain more possible values per byte, they won't match the requirement of having 256 random values per byte.
PBKDF's (see reason #5) such as PBKDF2, bcrypt, scrypt or Argon2 strengthen the password and output the requested number of bytes, all of which depend on the password. The output of the PBKDF can then be used as key (and other pseudo random data such as the IV).


Encrypting data with HMAC-SHA1 challenge response as the key I came across a piece of software that uses the following algorithm to generate a symmetric encryption key to encrypt data.

Generate a non-secret 64 byte random string $M$ (fixed challenge)
Generate a secret 20 byte random string $K$ (HMAC key)
Compute $E = \operatorname{HMAC-SHA1}(K, M)$

$E$ is a 20-byte encryption key that is used to encrypt some data (with some well-known cryptographically secure algorithm). $M$ is kept alongside the data, while $K$ is separated from it and kept secret. Whenever data has to be accessed, $K$ is retrieved and the HMAC computation is repeated to re-generate $E$ and decrypt the data.
Is this algorithm secure, assuming that $E$ and $K$ are kept secret?

Yes, it is secure to generate the key as long as the $K$ is kept secret.  Although the collision of SHA-1 is broken, HMAC is a PRF under the sole assumption that the compression function is a PRF. It is not affected by the collision of the has function.
The security strength of the HMAC is relay on the size of the key. The usual attack is to search for the key $K$.
Keep in mind that, the attacker will go to search for $E$ if $E<K$. In your case, since both are 20 bytes, so brute-forcing $K$ can be faster, though not possible.


Signal Sender Keys: Why it works and which is the common key at the end? As I has read upon "WhatsUp Encryption Overview" when a client receives a sender message then it performs the following actions:

Decomposes Sender Message to Chain Key and Signature Key.
Generates a Message Key from a Chain Key and update the Chain Key.
The sender encrypts the message using AES256 in CBC mode and signs it with Signature key.
The sender transmits the single ciphertext message to the server,
which does server-side fan-out to all group participants.

So I wonder at the end which is the final group key each participant, as far as I understand has a single key so how others on a group chat are able to decrypt the message?

Also I cannot understand at step 2 which key is used in order to encrypt the message in AES CBC Mode?

Also how Chain Key is updated? As some sort of a DKF function is used to concat all single keys into one master key?

There is no single or final group key. Each group participant has its own Sender key. Whenever a new member joins a group, it generates its own Chain key and Signature key pair. It combines the Chain key and public Signature key into a Sender key and distribute it to all the group participants using the pairwise direct messaging.

All the other group participants already have their own Sender key and they share it with the new participant through pairwise messaging. In this way, everyone keeps the Sender key of each other. Sender key is decomposed to Chain key and public Signature key once it is exchanged.

Now if a sender wants to send a group message:

It derives a Message key from Chain key as:

HMAC-SHA256 = (Chain key, 0x01)

And updates the Chain key as:

HMAC-SHA256 = (Chain key, 0x02)

It encrypts the group message with the Message key using AES256 in CBC mode.

It signs the message with its private Signature key.

Then it sends the message to the server. The server creates copies of the cipher text and sends it to every member. This is called server-side fan-out.

Upon receiving the message, group members use sender's public Signature key to verify the message, derive the Message key, update the Chain key the same way as the sender did, decrypt the message and delete the Message key.

Now if the sender wants to send another message, he will derive a new Message key from the updated Chain key. The earlier Message key is deleted.

The problem with this design is that it doesn't offer perfect future secrecy. If a Chain key of a specific group member is compromised any future message which is sent by that particular member will also get compromised. It is only using symmetric ratchet instead of using double ratchet as in pairwise direct messaging.

Computerphile has also made a good video on this - What's Up With Group Messaging?


What can be learned from an encrypted text? I assume nowadays crypto algorithms are well-built, so one can't make a difference between a ciphertext and random bit stream. This way the method used for encryption can't be figured out either.

I am curious, if there is perhaps something else that can be derived from a ciphertext, some meta data for example.

First lets have a look at your attack model: attacker is eave dropping only. This means no modification, just listening.

You also assume that the encryption system is perfect and you can't differentiate it from a random oracle (if I'm not mistaken we call this indistinguishability).

Due to all these restriction, if the system is well devised (no meta data). The only pieces of informations that you would be able to catch are the length of the data or the existence of the transmission (when are they communicating etc...)

Nowadays in order to avoid giving such data, (military grade) communications just send random noise when not used. That way, you won't be able to tell whether or not they are communicating. So no you cannot retrieve informations in this context.

Considering the use of meta-data, then you can retrieve some kind of "context-sensitive" pieces of informations by doing traffic analysis.
E.g. you can track communications between the hospital and your employees ... You don't know what they are about, but you know that your employee might be having some health problems...

More to read here : TRAFFIC ANALYSIS: or... encryption is not enough by Carmela Troncoso, IMDEA Software Institute.


What's the difference between DH and DHE? The DH equation is:

$$ K = g^{xy} \bmod p$$

Does using DHE mean even the $g$ and $p$ parameters are randomly generated (instead of being fixed)? Is this the difference?

Using DHE means even the $g$ and $p$ parameters are randomly generated

No, that's not what DHE means.
They may be randomly generated, but as this is a very expensive process (because you need to find a safe prime), computationally seen, you usually don't do this.
What you do in DHE is that both parties pick random values for $x$ and $y$ at run-time (e.g. protocol execution).

However, when you're doing a DH (without the "E") key exchange, the server has a certificate, which embeds a static, public Diffie-Hellman key, i.e. $g^x\bmod p$ as well as $g$ and $p$ allowing you to save an additional signature (e.g. using RSA or ECDSA) to verify the authenticity of the DH parameter. So while the server's DH value is static, the client still usually chooses a random value for security and storage-reduction reasons. Obviously fixing the parameters in the certificate implies they can't be changed at run-time.

Please note: Static-Ephemeral DH is very rarely used these days (especially with TLS).

Please note: this answer uses the TLS terminology for DH and DHE, in many other applications static DH isn't a thing and DHE is always used and just labeled as "DH".


PBKDF vs HKDF for pretty long key I'm developing a messenger application with encrypted chats.

In the first version of the app I've used PBKDF2 (10000 iterations, SHA1, random salt) to extend a short user password and generate keys to encrypt (AES256) and sign message (HMAC).

In the current version of the app I generate a random 130-bit key and use it instead of a user password. I think that using PBKDF2 with such a key has some overhead.

I see 2 possible ways to improve the current approach:

Keep using PBKDF2 and decrease iterations to 1 or 10.
Don't use PBKDF2 and use HKDF instead.

What are the advantages and disadvantages of each approach? Are there any other options?

You're right: there is no need for key stretching if your key already has enough entropy to resist brute force attacks without it.  A 128-bit keyspace should be plenty for that.

AFAIK, there is no significant difference between HKDF and single-iteration PBKDF2 in practice.  Both effectively achieve the goal of expanding the input key to a potentially longer sequence of derived keys, in a way that does not allow the original input key to be efficiently recovered from the derived keys.

Arguably, using HKDF for this purpose is somewhat "tidier", in the sense that it has been explicitly designed for non-password-based key derivation, whereas using PBKDF2 with an iteration count of 1 is formally outside its original design parameters.  However, there are several existing schemes, such as scrypt, that do use PBKDF2 in such a way, and there is no apparent structural reason why PBKDF2, used in such a way, would not be a secure non-key-stretching KDF.  Also, if you are already using PBKDF2 for password-based key derivation anyway, implementing a second KDF might be seen as needless complexity (however minor).

Personally, my favorite approach, in situations that do call for both key stretching and the generation of more than one hash output block of derived key material, is to use hybrid PBKDF2/HKDF — that is, to use PBKDF2 (or another key-stretching KDF) to generate an intermediate pseudorandom key (of one hash output block size), and then use the HKDF-Expand function to generate the derived keys from the intermediate PRK.  This combines the best features of both PBKDF2 and HKDF, and is implicitly permitted by RFC 5869 section 3.3 (which says one may skip the HKDF extract stage if one already has a uniformly distributed pseudorandom key string).

Using this approach could allow you to support both password-based and random-key-based key derivation within a unified framework:

For password inputs, derive an intermediate PRK using PBKDF2 with a suitably high iteration count.
For random key inputs, derive the PRK using HKDF-Extract (or PBKDF2 with a single iteration), or just use the input key directly as the PRK.
In either case, derive the actual encryption and MAC keys from the PRK using HKDF-Expand.

Ps. Just out of curiosity, I searched for earlier answers I'd written mentioning HKDF and PBKDF2.  I don't think any of these questions are exact duplicates of yours, but the answers may be somewhat relevant:

Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it?
Should I salt an AES password at each encryption?
Does it make sense to stretch non-keys?
Securing content and login with "same" password


formulas for adding points on curve25519 Curve25519 is a Montgomery curve. https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#diffadd-dadd-1987-m-3 gives a set of formulas for adding two points (well, more specifically, the X coordinate in XZ form):

  A = X2+Z2
  B = X2-Z2
  C = X3+Z3
  D = X3-Z3
  DA = D*A
  CB = C*B
  X5 = Z1*(DA+CB)2
  Z5 = X1*(DA-CB)2

This series of formulas gives 3x XZ coordinates - not 2x. (X2, Z2), (X3, Z3) and (Z1, X1). If I'm trying to add two points I'd expect two sets of XZ coordinates - not 3x.

Are the formulas wrong or am I missing something?

Classically, if you want to add two points $P = (x_2,y_2)$ and $Q = (x_3, y_3)$, you need all coordinates to compute $R = P+Q = (x_5, y_5)$.

The geometric relation between those points are that $P$, $Q$ and $-R = (x_5, -y_5)$ are aligned. Now, suppose you know only the $x$-coordinates of $P$ and $Q$, meaning you cannot differentiate between $P$ and $-P$ on one hand, and $Q$ and $-Q$ on the other hand. So there are four possible outputs: $P + Q$, $P - Q$, $-P + Q$ and $-P - Q$. We can remark here that $P + Q$ and $-P -Q$ share the same $x$-coordinate $x_5$ according to the previous notation, and $P - Q$ and $- P + Q$ the same $x$-coordinate. Let's call it $x_5'$.

This means by knowning only $x_2$ and $x_3$ we can get the two possible resulting $x$-coordinates of $P+Q$ or $P-Q$. So if you know the $x$-coordinate of $P - Q$, you can compute $P + Q$. That's what happens in the formula you quoted: the coordinates $X_1$ and $Z_1$ correspond to the point $P - Q$.

This is useful for the Montgomery scalar multiplication. It takes on input a point $P$ and compute $nP$ where $n$ is a scalar. At each step of the algorithm, the addition always involve two points $R_0$ and $R_1$ such that $R_1 - R_0 = P$ is a constant. So, since this is known, the addition can always be performed using only the $x$-coordinate (well, $XZ$ projective coordinates).

This can work for other model of curves, but in the case of Montgomery curves, it gives pretty fast formulas for addition and doubling!


Is there any way to find out two numbers such that the XOR between them is a given number? I have the following operation I took from a cryptanalysis I'm performing for a specific CBC encryption where the challenger has provided the key:

C1 = Encryption (K, IV⊕P1) ⇒ P1 = IV ⊕ Decryption (K, C1)

I know the value of Decryption (K, C1) and I also know it is equal to IV⊕P1.

Can I compute the value of IV or P1 without brute force?

Is there any way to find out two numbers such that the XOR between them is a given number?

No. When $(G,\odot)$ is a group, if one knows the value $z=x\odot y$, and nothing else about $x$ or $y$, then $x$ individually can be any element of the group; same for $y$. This applies here, for the group $(\{0,1\}^b,\oplus)$, where $b$ is the block size in bits.

  Can I compute the value of IV or P1 without brute force?

Perhaps. In CBC encryption, the IV is usually public (that, or the receiver has some mean to find it that is not part of CBC encryption per se). It often is the first block of the ciphertext message.


Byte size of Diffie-Hellman public values I have a scenario that uses RFC-3526's Diffie-Hellman Group 14 for 2048 bit key exchanges. From the document, it specifies the P (prime) value in hexadecimal value as:

  FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
  29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
  EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
  E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
  EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
  C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
  83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
  670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
  E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
  DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
  15728E5A 8AACAA68 FFFFFFFF FFFFFFFF

It also specifies G (generator) as 2 which I assume in hexadecimal as:

  0x02

Assuming Alice's private key is a and Bob's private key is b. My question is when Alice and Bob exchanges their A and B where:

A = G^a mod P
B = G^b mod P

How big should I expect A and B to be in bytes?

$A$ and $B$ have values between 1 and $P-1$, and can in fact take on half the values in that range.  As $P$ is 256 bytes long, so will $A$ and $B$.  As there are approximately $2^{2047} > 256^{255}$ potential values that they can take on, we can't express them in 255 bytes.


HMAC-SHA1-128 parameters I have a question regarding what parameters should be used when generating HMAC-SHA1-128. I have fairly limited knowledge in this field.

HMAC parameters:

H = Hash = SHA1

K = Key size = 128 bits (16 bytes)

B = Data block byte length = 64 bytes

L = Output size of SHA-1 Hash = 160 bits (20 bytes)

Ipad = inner padding = 0x36 repeated B times

Opad = outer padding = 0x5C repeated B times

Charset = UTF-8

Does this make sense? Anything else I should consider? I want to make it similar to the following RSA example:

Format = x.509

Charset = UTF-8

Encoding = Base-64

Endianness = Little Endian

Key size = 2048 bits

Is encoding, endianness or anything else other than the things I mentioned under HMAC parameters relevant and should be paid specific attention to?

Thank you!

Edit since last comment:

Regarding the data;

I would like to take data from 4 different columns in a database table and create a HMAC based on those - one HMAC for each row in the database table.

The data are the following:

Date(YYYY-MM-DD), Time (hh:mm:ss), String(xxxxx), Number (1000.00).

The data shall be separated by semicolon - so the full string will for example be: 2000-01-31;23:59:59;"hello";1000.00

There's not a word about the data to authenticate! Update: we are told that's data from a row in database with 4 different columns: Date(YYYY-MM-DD), Time (hh:mm:ss), String(xxxxx), Number (1000.00). It is of paramount importance to specify how this data is transformed into byte before entering HMAC. Concatenation would be dangerous for the last two fields, because in digitsfollow12 34.56 and digitsfollow123 4.56 would give the same MAC.

The hash you want to specify is usually designated SHA-1, not SHA1.

SHA-1 is obsolete, even though when combined with HMAC it remains safe and thus tolerated. A modern replacement would be SHA-256 or SHA-512, followed by truncation of the final HMAC result if a 160-bit output is desired.

The data block size B is redundant with specifying SHA-1, and will need to be kept in sync with the hash. I would suppress that.

Ipad and Opad, and their repetition count, are redundant with the specification of HMAC. I would suppress that.

"Charset = UTF-8" does not make sense to me, unless you want some encoding (like Base-64), or it applies to the data to authenticate, in which case that should be told.

It is not specified how various parameters are passed: array of chars, string, and nature of that; and if the length (e.g. of data to authenticate) is separate or some attribute of an object, and in what unit (bytes, bits), and the maximum. It is not told wether data to authenticate is passed in one block or iteratively.

Giving an example in a spec helps immensely.


ECDSA signing vs generating public key I'm trying to understand the process of ECDSA signing. I already figured out the process of generating a public key out of a private key by multiplying the private key with G.

The equation for ECDSA signing is as follows: $S = k^{-1} (\text{hash} + dA * R) \pmod p$. What I'm trying to understand is the process of multiplying $dA$ (my private key) by $R$ ($x$ of public key generated from random private key). Is it a "simple" multiplication (such as 5*5 = 25) or the same way we multiply $k$ by $G$ to generate a public key?

Is it a "simple" multiplication (such as 5*5 = 10) or the same way we multiply k by G to generate a public key?

It's multiplication modulo the curve order.  For example, if dA = 9, R = 7 and p = 13, then dA * R = 9 * 7 mod 13 = 63 mod 13 = 11.


Bcrypt input length vs collisions I am currently implementing oauth2 bearer token authentication and am storing the tokens bcrypt encrypted. My question is how long should the tokens be to achieve maximum security. E.g. at what length would longer tokens be useless since a bcrypt collision is as likely as guessing the token.

The bcrypt algorithm generates a 192-bit password hash by encrypting three 64-bit blocks using a password-derived blowfish key. The common format for storing bcrypt hashes, however, only includes 184 of the output bits.

If bcrypt was a "perfect" 184-bit hash, finding a some preimage would take the same amount of work as a brute force attack on a 184-bit key. So if you had random binary tokens, a token longer than 184 bits would be useless. Similarly, with a random hex token, length over 46 characters would be useless, etc.

Many bcrypt implementations also have a limit on input length. This is usually at least 51 bytes, so if your input format is hex, base 64 or binary, the above limit would be reached first. If you were hashing some less dense encoding, like decimal numbers (or indeed passphrases...), it might not be.

However, if your tokens are high entropy (e.g. 128+ bits) there is no need to use bcrypt. Bcrypt is useful for slowing down a brute force or dictionary attack, but 128 bits is enough that such an attack would be infeasible. A key derivation function such as HKDF, or even a simple salted hash, would be sufficient.


Should signature verification work using two different RSA libraries? I am new to the forum, so forgive me if this question is out of place or lacks adequate detail.

I am working on a project that involves allowing discreet clients to upload content to a central host. The host is expected to verify ownership and data integrity by testing the signature of the content against a user's supplied public RSA key. For some reason, signatures provided by a test client I have written can not be verified by the host. Signatures created by the host for the sake of testing pass with no problem. (That is the host uses the client's private key to create a signature based on the same content, and test's that signature against the client's public key).

The host is written in Go and uses Go's native rsa package to verify a PKCS1v15 signature of a SHA256 sum. The client is written in Node.JS and uses a third party package, forge, to sign the data, also using PKCS1v15 and a SHA256 sum. I have also tried PSS in place of PKCS1v15 on both sides. The results appear to be the same. Can this sort of pattern (create signature on platform-A and verify it on platform-B) be implemented practically, or is RSA public key encryption open to the interpretation of the stack implementer?

NodeJS Implementation

The following is the client written in NodeJS. Here, the user's private key is read from the file "test-client-rsa." The variable "hex" is the hex-encoded SHA256 sum of the test file being used, hard-coded here for simplicity.

var fs = require('fs');
var forge = require('node-forge')

fs.readFile('test-client-rsa', (err, data) => {
   if (err) throw err;

    var key = forge.pki.privateKeyFromPem(data);
    var hex = 'dac1f3853c1e4c6579692f59af0a30aacb86820d5ad331c792987c4dae047595';
    var md = forge.md.sha256.create();
    md.update(hex, 'utf8');

    var signature = key.sign(md);
    var buf = new Buffer(signature);

    console.log(buf.toString('base64'));
});

The client's output (encoded to Base64) resembles the following:

  JShQKsKAVcKow4HCnMKMw7MXwp3DhhAPXGhGPsOow4U9DQg3acOmIEjDoFR6eCUCwpZ4wq7CmBB7dsOrSMKOw6fDlDfCs8OKwonCm8KVLjMrIsKSwqTDkmnCgcKlRsO4QQrCiWDDjBbClcOTwqfDn8KDw57DgG0Qw7gcHsKSwr57w4rClyrDqkgrwo5owoAHBMOGwq/DpMKDwoVhw5bDtD9zw4NYCxwLwrLCoTp7wo3CtsOqPjFKwrdWw63CpMKQFcOcwpnCpMKhwrDCisOkBCZrw4wkwoYVwotWw7/DrBYSIsKjbXF9wqfDnRTCk0kTE8KTVMOSw6wicElvw45rwolbwpNgS8O+bSwhwqFHw5ICTcKRZcO0w7YOwoTCncOow4pBwo1ow7bCisKYwrRRMiTDpTLDnsKjQcOBwpgPw7rCokRtOcKTP8KiwppLwp3Dn2QYwqZvDEsRw4LCuiYbM8K5w6fClF98EW/CmUTCjcOjMcOHwqLDqsKpwqfDvcKgNA==

Go Lang Implementation

The following is the server implementation, written in Go. The code has been simplified to keep the example focused, and so lacks proper error handling and logging routines. In the method, the object "u" represents the user's identity, or RSA credentials in this example. The variable "u.pkey" is the user's RSA public key represented as bytes, while the input parameters "sig" and "data" represent the signature provided by the test client for the test file, and the content's of the test file itself respectively.

func (u User) VerifySignature(sig []byte, data []byte) bool {
    if !u.IsValid() {
        return false
    }

    hash := sha256.Sum256(data)

    if err := rsa.VerifyPKCS1v15(u.pkey, crypto.SHA256, hash[:], sig); err == nil {
        return true
    }

    return false
}

The server's output is consistently false with the call to "rsa.VerifyPKCS1v15" returning the error "crypto/rsa: verification error."

I've run through both layers of code several times now, and I am not able to spot the problem in the logic. Is there something incorrect in this pattern? Any help that can be provided would be greatly appreciated.

Yes, RSA signature generation and verification should work identically on different libraries. PKCS#1 - the dominant standard for signature generation and verification - has a complete and formal description of how the configuration / input is transformed into the output.

This includes:

the key specifications (and possible encoding);
the hashing;
the padding and hash indicators;
the modular exponentiation;
the transformation into octets of the result.

There are test vectors available from NIST as well, so it is possible to (partially) verify the correctness of an implementation against well known test vectors.

That doesn't mean that there may not be differences in implementation between libraries, so some libraries:

require a key in a specific format (and error handling if the format is incorrect is not always up to par);
require CRT (Chinese Remainder Theorem) parameters for a key;
require a pre-calculated hash value, some libraries an initialized hash function and some libraries just need an indication of the hash function (and some just assume a specific hash function, often SHA-1);
offer implicit character encoding for when the input is a text string (this may also be implicit for the programming language / runtime);
allow for online calculation of the hash / signature by offering update / final functionality  or streaming;
implicitly or explicitly perform the choice of the padding mode (PKCS#1, PSS, ISO 9797, RAW, etc.);
offer to encode or even implicitly encode the result into a text string.

Less common, but still possible is the way bytes are ordered for lower level functions. You may also have to configure implementation specific parameters, such as a random number generator for protecting the implementation or performing PSS signature generation. PSS may also require parameters - a second hash function for instance - for Mask Generation Function (MGF-1).

These are all design choices that may influence the outcome of the signature generation or verification. So a developer still needs to study the API to known what to expect, despite the well written PKCS#1 standard.

Fortunately, once the algorithm works it is unlikely to fail unless you manage to bugger up the character encoding of the message or the encoding / decoding of the signature.

It seems you got stuck on (3). Double calculation of the hash is a common mistake. Note that PKCS#1 signature describes the signing of messages and includes the hashing within the signature generation description, so having the signature also generate the hash is common among cryptographic APIs.


How do I explain zero knowledge proof to my 7 year old cousin? How do I explain zero knowledge proof to my 7 year old cousin?

I will use Bertie Bott's Every Flavour Beans from Harry Potter in my explanation. If your cousin has not read Harry Potter, you can refer to Jelly Beans instead.

So let's assume there are two beans which look same but one of them tastes like chocolate and the other one tastes like spinach. Your cousin claims that he can distinguish them just by looking at the beans. You don't believe him, but he doesn't want to tell you which one is which, so there is still a chance that you eat the spinach one.

Instead you hide them both behind your back and randomly choose one of them and show it to your cousin. You then put it back and choose randomly again in a way that allows you to know whether you picked the same bean or not (like swapping the beans x times). You then again show it to your cousin who will have to tell you whether it's the same bean as the one you showed before. Repeat this process until you are sure that he is indeed able to distinguish the beans (or that he's not).

You now know that your cousin is able to tell the beans apart while you still do not know which bean is the tasty one.

Finally, there are two side-channel attacks in this scenario:

He may be able to count how often you swapped the beans, so don't make it too obvious.
You could offer him one of the beans and when he refuses, it's probably the spinach one.


Signal/TextSecure multiparty Chat. Does the protocol transmits a symmetric key? As I look over the TexSecures specifications for multi-party chat I have noticed this. Also as far as I understood in TextSecure (now known as Signal) the minimal steps required to do a secure multiparty chat using

Generate ephemeral symmetric key K
Encrypt the message.
Hash the message's plaintext and encrypt the hashes with the key K.
Send cyphertext,hashes and the key K.

Also by improving it, if client generated an ephemeral signing key as well it can rachet the key and send few messages as well. But whilst I read that and have looked the schema a few questions have been rised to me:

Is assumed the communication channel to be previously secured when the key K is being sent. I mean transmitting private keys is like you are asking for your security to be compromised.
What if the ephemeral key K actually has been compromised?

Can you help me to answer these questions?

Yes, the channel is assumed to be secure. "When sending a message to a group, we simply deliver a pairwise encrypted message to each member of the group."
It's ephemeral. The double ratchet system ensures that ephemeral keys get changed out, so the compromise will be recovered from.


Why does gnupg create 4 separate keys and what does sub and ssb mean? When using gpg to create a single key, I get:

$  gpg --list-keys
-------------------------------
pub   2048R/0C0EA301 2018-01-01
uid       [ultimate]
sub   2048R/023A0509 2018-01-01

$ gpg --list-secret-keys
-------------------------------
sec   2048R/0C0EA301 2018-01-01
uid
ssb   2048R/023A0509 2018-01-01

When using bouncycastle to view the keys (in ~/.gnupg/pubring.gpg and ~/.gnupg/secring.gpg), I find that there are four keys created:

(#gpg.public[9AB238A08EF3EAB0A7D01E1284AB64C10C0EA301]
 #gpg.public[A841D2BA6635154081F3A5176DE7FF9B023A0509])

(#gpg.secret[9AB238A08EF3EAB0A7D01E1284AB64C10C0EA301]
 #gpg.secret[A841D2BA6635154081F3A5176DE7FF9B023A0509])

Why does gpg create four keys (public/private/sub/ssb) and what are they for?

The abbreviations stand for the following:

pub -- public primary key
sub -- public sub-key
sec -- secret primary key
ssb -- secret sub-key

In asymmetric cryptography you always have key pairs: A public key to encrypt, a private (secret) key to decrypt. Here we have two key pairs: (1, 3) and (2, 4). They can be identified by their identical fingerprints.

But why are there two key-pairs? When generating an OpenPGP key with GnuPG, per default a primary key (pair), also called master-key, and a sub-key (pair) are created. The primary key, also called master-key, contains one or more user-IDs (name, email-address) and is used for for signing. The sub-key, signed by the primary key and thus confirmed to belong to its user-IDs, is used for encryption/decryption.

The idea for having a master-key with sub-keys is very well described here. If you want to deviate from the default behaviour and gain more control about the key generation, e.g. create only a single key-pair or select a certain cryptographic algorithm, you should try gpg --full-gen-key (introduced in GnuPG 2.1.17).


Good pre-image resistance value for hash visualization I want to do "hash visualization", i.e. derive a human-meaningful information from a hash, like a phrase or an avatar. But the current techniques usually don't use many bits, for example tripphrases by Bret Victor only use roughly 43 bits. This is a problem because all the hash isn't used, so using a "big" hash function with many bits wouldn't help.

What is the minimum number of bits in the output of an "ideal" hash function that would guarantee preimage resistance by modern standards (i.e. with the biggest computing power that we can gather today)? This doesn't need collision resistance.

I disregard the perfect hash requirement.

In the application asking for preimage-resistance with a narrow hash, one should use a purposely-slow memory-hard hash (as used for passwords, also known as key-streching or password-based hash). This greatly reduces the number of bits needed for preimage resistance.

More precisely, we want to build a hash that starts with a fast hash of the payload (e.g. with SHA-512), then performs a slow hash of the result and (if the application allows) salt¹ and/or pepper² (e.g. per Argon2id), with the largest parametrization (iterations, threads, memory size) that the application allows.

If in the application one spends 1 second slow-hashing, and the adversary can spend $2^{25}$ more time (over a year) with $2^{20}$ (over a million) more×better computing resources, and we want residual probability $2^{-10}$ (less that one in a thousand) that the adversary succeeds, we need $25+20+10=55$ bits of hash.

This hash size is date-independent, but does not account for how much time the system must remain secure without adjustment of parametrization of the slow hash. Add like 1 or 2 bits per year to account for progress in technologies.

Caution: the need for collision-resistance is easily overlooked³, and much more bits of hash are needed for that. With the same hypothesis, we'd need $2\times(25+20)+10-1=99$ bits of hash (see this), and twice more extra bit per year for progress in technologies.

¹ Salt could be an email or/and a random number. The idea is to make it impossible for an adversary to amortize the cost of the slow hash across multiple targets with different salt, and make it impossible to start a meaningful attack before knowing the salt.

² Pepper could be a server-unique string, tentatively kept secret, but considered public in a conservative security analysis.

³ For example, collision resistance is required for integrity if an adversary can influence the hashed content after the last unpredictable step in its generation. With preimage-resistance only, a maintainer of a Unix distribution that uses an automated nightly build is vulnerable to a contributor maliciously changing a text in release note and becoming capable of producing something unrelated to the original but with the same hash.


How can I tell how many bits of security a secure hash function has? How can I tell how many bits of security a secure hash function has?

For example, how would I calculate or tell how many bits of security a secure hash function with 160 bits output would have? Assuming there are no known weaknesses…

Well, how resistant to attack would depend on what security properties you would need from it.

There are three standard assumptions we can make about a hash function:

Given a hash value, it is difficult to find an image that hashes to that value; this is known as preimage resistance
Given a image that hashes to a specific value, it is difficult to find another image that hashes to that same value; this is known as second preimage resistance.  This is considered a stronger assumption than preimage resistance, because it may be possible to modify the image and not change the output value.
It is difficult to find two different images that hash to the same value; this is known as collision resistance.

Sometimes we're interested in collision resistance, sometimes, we're not.  One example where we may be interested in it is if we're using the hash as a part of a signature scheme.  For example, suppose we find two images that hash to the same value; one says "I like icecream" and the other says "I agree to give Bob a million dollars".  We then get Alice to sign the message that denotes that she likes icecream; because what the public key system signs is actually the hash, Bob now hashes a signed message from Alice giving him a million dollars.

Now, there are other times where we don't really care about collision resistance.

So, what's the big deal about collision resistance vs. preimage resistance?  Well, it turns out that, if we don't assume any cryptographical weaknesses within the hash function, it is much easier to break collision resistance than it is to break preimage (or second preimage) resistance.

To break collision resistance, one way would be for the attacker to hash a huge number of variants of the message "I like icecream", and hash a huge number of variants of the message "I agree to give Bob a million dollars", and go through the lists and see if there's a value in common.  For a 160 bit hash, we need about $2^{80}$ messages in both of the lists (because of the Birthday paradox, that's likely to be sufficient); it turns out that this is about the best we can do (assuming no crypptographical weaknesses within the hash), and hence we have about 80 bits of security against this attack.

On the other hand, to break preimage (or second preimage) resistance, we can't use the Birthday paradox.  Instead, about the best we can do (barring a weakness within the hash function) is to hash lots of messages, and hope we get one that hashes to the target value.  For a 160 bit hash, we expect to go through about $2^{160}$ messages before we stumble across one, and hence we have about 160 bits of security against these.


On the fly signatures and zero-knowledge I am reading some articles which explain on the fly signatures (also called online/offine signatures).

The principle is that a few operations do not depend of the message we want to sign, so these values can be precomputed and use in the future to sign the message.

Let's see an example with the Schnorr signature:

  $p$ and $q$ two primes such as $ q|(p-1)$
  $\alpha$ an element of order $q \bmod p$
  $\mathcal{H}$ a hash function
  $s \in [1,q]$ the private key
  $\alpha^{-s} \bmod p$ the public key

  Signature of a message $m$:

  Choose randomly $k \in [2, q-1]$
  Compute $r=\alpha^{r} \mod p$
  Compute $x = \mathcal{H}(m || r)$.
  Compute $y = k - sx$
  Send the couple $(x,y)$.

As said before, we remark that steps 1. and 2. are independant of the message $m$ and can be precomputed.

It is explained that signature algorithms derived from zero-knowledge identification schemes are the best suited to implement this kind of signature.

Why is the consideration of zero-knowledge so important to apply this method?

Actually, it has not really to do with zero-knowledge.

From any public-coin three move identification scheme you can derive a secure signature scheme (in the random oracle model) using what is called the Fiat-Shamir heuristic. Many of these protocols represent honest-verifier zero-knowledge proofs (like the Schnorr, GQ etc. protocols). Now, every such scheme has basically the same structure (choose randomness, compute commitment, compute hash, etc.) and thus is a candidate for the precomputation of the first two steps as you describe it for the Schnorr signature.


Would a OTP No-Key Protocol work? Consider Shamir's No-Key protocol. What if you substitute the asymmetric operations with XOR, each party using an ephemeral OTP.

It's symmetric, so you could apply the protocol scheme as if it were homomorphic
It's much faster than Shamir's solution using public key crypto

Would this still be a valid and comparably secure protocol as Shamir's No-Key protocol?

Would this still be a valid and comparably secure protocol as Shamir's No-Key protocol?

No, it would not be secure at all.

In this revised protocol, Alice sends a message $M$ to Bob, to do that, she picks a random string $A$, and sends:

$$A \oplus M$$

Bob receives this, picks a random string $B$, and sends:

$$B \oplus (A \oplus M) = A \oplus B \oplus M$$

Alice then xors in her original string $A$, and sends

$$A \oplus (A \oplus B \oplus M) = B \oplus M$$

Now, someone in the middle hearing these three exchanges, if they exclusive or all three, they get:

$$(A \oplus M) \oplus (A \oplus B \oplus M) \oplus (B \oplus M) = M$$


Rolling Hash function over untrusted data: how to preserve statistical splitting properties? I would like to know if there is a construction for a Rolling Hash function to be used to split the received untrusted data in chunks.
The data is split whenever the hash function drops below a certain threshold and the splitted data is then used to build trees for efficient indexing of such data.
In my case the input data is however untrusted and I need a rolling hash construction that preserves the mean splitting size even under adversarial attacks on the data (which would otherwise make the trees highly unbalanced).
From what I have seen rolling hashes are mainly used in backup applications for deduplication purposes but they operate under the setting of non-adversary data.
Thank you in advance.

There are absolutely functions like this but no such function, regardless of its properties, can solve your problem. They depend on the adversary not knowing the secret value used for deciding where to mark the stream. For efficient rolling HMACs, the attacker has almost full control of the output if they know the key.
how to build a secure rolling HMAC
Performance is 1/16th that of AES encryption because one full block is encrypted for every input byte. The universal hash is trivial in comparison and not a bottleneck.
An attacker with the key can produce streams with arbitrary function outputs limited by the number of bits they are putting into the window. Putting in 16 bytes gives them (almost) full control of the output of the universal function and resulting AES encrypted output value.
This is true regardless of the function you use. If the attacker has the keys they can set the splitting properties of the stream arbitrarily. It's only a question of computing cost.
That's why most systems for chunking or otherwise marking locations in streams as interesting just use buzhash and friends with a secret tweak. The moment the attacker learns that F(x)<threshold they can construct a stream x|x|x|x full of marked locations. Constructing a stream that contains no marks is similarly trivial. It becomes possible to construct streams with arbitrary marks from a library of strings with known mark properties.
There's no point in paying the computing cost to prevent key recovery if the adversary can break the system anyway which is why secure rolling hashes aren't in wider use.


Steganography -unhide methods I'm trying to unhide information in a .bmp image using the tools on https://incoherency.co.uk/image-steganography/#unhide
However all I can see when using the tools are at best a black image with a few colored squares at the bottom and at worst a slightly blurry version of the image I'm using.
I've tried to use other tools but they don't appear to like .bmp files.
Are there any other methods to detect this? (that would be as easy as this site is supposed to be)

If you want to unhide a random message you need your own proper tools.
If you want to unhide a message sent to you then you need to use the tools that the sender used.
Expecting random tools to work on a random message is nonsense even if you might get lucky once.


Difference between a secure PRG and semantically secure encryption I am taking cryptography course in Coursera from Stanford University. I have following question

I have a question why append 0 in G(k) i.e., G'(k) = G(k) || 0 is
considered as not secure PRG as 0 in message is copied with out
encryption. Whereas in semantically secure E'(k,m) = 0 || E(k,m) i.e.,
prepend 0 is considered as semantically secure. Here why appending 0
does not break semantically secure [sic]?

I consider the SU Cryptography course on Coursera really good, up to certain level is very comprehensive. You should discuss these topics on the Coursera forum, IMHO you will be guided more precisely.

You have two questions here and you should know the DEFINITIONS of the secure PRNG and semantically secure encryption. Security of the message differs between two with what needs to be secure. For PRNG it's the output, for encryption it's the plaintext message.

  I have a question why append 0 in G(k) i.e., G'(k) = G(k) || 0 is
  considered as not secure PRG as 0 in message is copied with out
  encryption.

The expression ( G'(k) = G(k) || 0 ) effectively means you're appending zeros to the generated message. It means you can predict there will be 0 at the end of the (otherwise random) message. It is pretty unsecure PRNG.

  Whereas in semantically secure E'(k,m) = 0 || E(k,m) i.e.,
  prepend 0 is considered as semantically secure. Here why appending 0
  does not break semantically secure?

Even you have prepend anything to the ciphertext, it still doesn't reveal anything about the plaintext message.


Are there any symptoms of a side channel attack on the target chip? I would like to know if there are some symptoms that let me detect if  my integrated circuit is actually subject to a side channel attack.

For example, are the following potential indicators?

Energy consumption becomes too high
Temperature becomes too high

Side channel attacks are variably understood as excluding or including fault attacks. Let's start with the excluding definition, where side channel attacks monitor a device running some security-critical process, without deliberately attempting to alter its normal operation.

The most straightforward and perhaps earliest form of side channel attack is probing the internals of the circuit using contacts on the physical traces (e.g. of a PCB); that's called micro-probing when done directly on an IC. The archetypal goal of probing is capturing the data bus of a microprocessor system, letting one examine all that it manipulates. Some devices have dedicated sensors to detect probing; see e.g. figures 2 and 3 in Ross Anderson, Mike Bond, Jolyon Clulow, Sergei Skorobogatov Cryptographic Processors - A Survey, in proceedings or IEEE, 2006. On occasion, micro-probing indirectly cause misbehavior and can be detected as some fault attacks are in software, see last 5 bullets.

Many side channel attacks (including most with the keyword Differential) require many cryptographic computations to be performed. Counting the number of computations (with a carefully implemented power-loss-resistant counter in EEPROM or Flash) and limiting that number is a from of detection, and is effective if a small enough limit is functionally acceptable. Alternatively, the key can change regularly (e.g. every 100 uses), but typically that must be integrated in the specifications, and recovery in case of protocol errors can be an issue; and that's prevention rather than detection as asked.

In the special case of Power Analysis, it conceivably could be detected that a test setup inserts a resistor on Vcc or Gnd (the simplest option for a Power Analysis setup), and thus that the power supply voltage (which the device can measure) changes with DC power consumption (that the device can change by turning on or off some circuits, or changing a frequency divider). The effective series resistance of the power supply could thus be estimated to some degree, and attack suspected above some threshold. However, doing this has a risk of false positive (e.g. if the power contacts are dirty); and it could be circumvented by a better attack setup. I do not know that this line of defense is used.

Other forms of side-channel attacks seem basically undetectable to me. One can not hope to test if something is timing execution, monitoring EMI emission..

Fault attacks are detectable, high-security ICs (like those in many Smart Cards) have sensors for that, and high-security software has countermeasures trying to block these attacks by performing redundant checks. There are things like:

Vcc out-of-range or/and rapid change sensor.
Light sensor, to detect optical flash or laser pulses, as well as careless use  of the IC in lighted environment after epoxy removal or de-passivation.
Clk frequency out-of-bounds detector (glitching Clk used to be an effective fault attack in early Smart Cards; but the trend is internally generated clock).
Temperature-out-of-bound sensor.
Mesh(es) and associated sensors: one ore more mesh(es) (a long wired forming a regular pattern) is/are added on top of the IC or circuit, and it is hopped that probing will interfere with the mesh, activating some sensor: mesh-has-been-opened, meshes-have-been-shorted, capacitance-between-meshes surveillance (which has a chance to detect de-passivation). See this archived FlyLogic blog, read after Mesh Comparison.
Internal self-test: like stuck TRNG detector, parity check on bus or memory, or even dual CPUs performing the same operations concurrently with their result matched.
Checking results of cryptographic computations; the archetypal one is checking that $x\equiv y^e\pmod N$ after having computed $y=x^d\bmod N$ in RSA (especially if the computation of $y$ was using the CRT).
Redundant implementation and testing of critical states, like are the access rights granted by a proper PIN presentation.
Checksums on critical variables or code.
I imagine, much more..

Note: I have not much touched prevention (rather than detection) of Side Channel and Fault attack, which is a much wider subject.


Are MACs vulnerable to birthday attacks? Às the title already indicates, I would like to know: Are MACs vulnerable to birthday attacks?

Are Message Authentication Codes (MAC) are vulnerable to birthday attacks...

Like most things in life, it depends.

Certainly, if you have an $n$-bit MAC, then after about $O(2^{n/2})$ MAC'ed messages, there's a decent probability that you see two different messages $M_1, M_2$ for which $\text{MAC}_k( M_1 ) = \text{MAC}_k( M_2 )$

However, that begs the question: is this observation actually an attack?  After all, the security property of a MAC is "it's hard to generate the MAC of a message you haven't seen"; in the above attack scenario, you've seen the MAC's for both $M_1$ and $M_2$, and so neither would qualify under the "you haven't seen" part.

The pertinent question is "does having two message evaluating to the same MAC actually allow us to deduce the MAC of a message we haven't seen".  For most MACs, it doesn't; there's no obvious way to do this for HMAC, and for nonce-based MACs, the fact that each message was MAC'ed with a different nonce would appear to block any such obvious approach.

However, there is a common MAC where it would appear to be an issue: CMAC.  That is, if we can find two messages $M_1, M_2$ (both a multiple of 16 bytes in length; it is easy to extend this observation to non-multiples of 16 bytes) with $\text{CMAC}_k(M_1) = \text{CMAC}_k(M_2)$, then we know that, for any string $N$, we have $\text{CMAC}_k(M_1 | N) = \text{CMAC}_k(M_2 | N)$.  Hence, if we find such a collision, we can ask for the MAC of $M_1 | N$, and then we immediately know the MAC for $M_2 | N$; this counts as a valid attack.

However, CMAC is the only MAC I can think of with this potential vulnerability.


What is the history of recommended RSA key sizes? One can find up to date recommended key sizes for RSA at NIST sp800-131A for example. In short, it suggests a key size of at least 2048 bits.
Is it possible to find a history of recommended key sizes for RSA, going back to the invention of RSA?

512 bits (rounded down from the 664 bits or 200 digits in the patent) was recommended from its conception in 1974 and throughout the 1980s. Indeed, 463 bits was considered sufficient in the mid-1990s for the RSA-140 challenge. Whether key strengths as low as 100 digits (330 bits) were ever used in the early 1980s embedded systems is unclear; but probable given the RSA-100 challenge of 1991.
RSA's recommended key size increased to 768 (user) or 1024 (enterprise) at some point in the late 1990s1 due to academic successes in breaking bit strengths leading up to 512 bits.
Current recommendations (SP 800-572) are now 2048 or 3072 bits, depending on interoperability requirements.
In practice, these key strengths do not smoothly match Moore's Law as each new key size requires overhauling embedded systems and resolving interoperability requirements. So the trend has been to pick a key size much larger than necessary until the risk of breaching occurs, then pick another key size much larger than necessary.
A coarse stepwise increase governed by infrastructure costs and collective public perception of key strength.
 1. Inferred from this RSA article and this (irritatingly uncited) Wikipedia section.
 2. A sister document of the PDF cited in the question.


With Encrypt-then-MAC, and flexible protocols, do I need to authenticate the authentication? Sorry, the question is not easy to state (or wasn't for me, anyhow).

So I'm writing a very flexible format for security. It allows for full choice of cipher, key size, and so on, along with key confirmation and derivation. All of this is communicated in objects with Protocol Buffers serialisation. Now, I get that I need to authenticate the cipher configuration (using Encrypt-then-MAC), but in my protocol, the authentication method itself is highly configurable just like the rest. Is this a situation where I need to NOT provide flexibility, or can I actually NOT "authenticate the authentication"? I would prefer retaining the flexibility, but not at the cost of security.

The high level description of a PayloadItem (the format that defines how to write/read an item to/from the payload) is, with their types:

Type (string)
Name (string)
ExternalLength (long)
InternalLength (long)
Encryption (SymmetricCipherConfiguration)
KeyConfirmation (VerificationFunctionConfiguration)
KeyDerivation (VerificationFunctionConfiguration)

And I am thinking of adding EncryptionAuthentication (as a VerificationFunctionConfiguration) ... it seems to me that I cannot authenticate KeyConfirmation or KeyDerivation (I do not have the key at this point, yet, after all), too. Please help me through the security implications of this. I have already thought about the problem a good deal but would like some thoughts from others.

The key confirmation works by accepting a set of possible keys a receiver holds for a sender, and iterating through them, testing for equality with a verified output. The confirmation method is configured by its configuration object, which allows use of a MAC or KDF, with salt.

Similarly the key derivation is configured by its configuration object, allowing a selection of functions.

Is it okay if I just make sure that I do NOT use short-circuiting comparisons?

Though a full analysis would require some details and, presumably, a lot of work, guidance can be obtained from what is done in SSL: at the end of the handshake, a verification step occurs with the Finished messages. These messages are protected with the negotiated algorithms and keys (both encryption and MAC) and, crucially, the contents of a Finished message are a one-way hash of all the previously exchanged handshake messages, thus including the cipher negotiation, the server's public key, the key exchange messages... For instance, see this article for some discussion on the subject. The security of the SSL handshake against various types of active attacks relies heavily on the contents of these Finished messages, and (this must not be forgotten) on their mandatory aspect (client and server ought to refuse to send or receive application data until they have sent/received appropriate Finished messages).

With such a verification, a client (or server) implementing SSL will ensure some security level against active attacks on the handshake which should be at least as great as the weakest of the MAC algorithms that the client (or server) accepts to use. Getting beyond that level (i.e. showing a posteriori that a given connection was protected with the strength of the MAC algorithm which was apparently used, regardless of whether some system would have accepted a weaker MAC) can get tricky.


Worst case of Integer factorization From Fundamental theorem of arithmetic, every integer greater than 1 either is prime itself or is the product of prime numbers, and that this product is unique, up to the order of the factors.

$$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_r^{e_r}$$

Inorder to factorize, the worst case is if the composite number is a product of two large primes. (general statement)

In RSA key generation, it is stated as follows

For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but 'differ in length by a few digits'to make factoring harder.

In Paillier key generation, it is stated as follows

Choose two large prime numbers p and q randomly and independently of each other such that $\gcd(pq,(p-1)(q-1))=1$. This property is assured if both primes are of equal length.

My doubt is, what is the actual worst case for integer factorization problem?

1) $n=pq $ and $length(p) = length(q)$ $\ge$ k, for some $k \ge 1024,2048 \cdots $

2) $n=pq$ and $|length(p)-length(q)| \le k$, for some $k  \ge 1,2,3\cdots$

Provide reference stating the worst case for integer factorization with particular values of $k$

My doubt is, what is the actual worst case for integer factorization problem?
...
Provide reference stating the worst case for integer factorization with particular values of k

Such a statement can not be done for any class of algorithms at all, only a specific algorithm can have a worst case runtime.
In general, worst case estimations are barely used in cryptography at all, because the average case matters much more. Here's an example for that: Assume you had a new, hypothetical factorization algorithm, which has linear runtime for composite numbers on almost all inputs, but for values of the factorial function it has exponential runtime. Now the worst-case runtime is exponential, but the average is barely more than linear. And even worse: In the cases of $x!$ as input,the input is divisibly by $2$ when $x>1$, so just run the algorithm on $x!/2$ instead, with its linear runtime. This would make factorization entirely useless for cryptography - but the algorithm has exponential worst case runtime. Worst case assumptions are only useful if you can somehow reduce the average case to the worst case (possibly under randomized reductions, etc.) - for example in lattice-based cryptography these methods apply.
When looking at known factorization algorithms, there are some which scale with the size of the smallest prime factor, some scale with the total length of the numbers and some on "closeness of prime factors". In order to counter them all, suggestions like the ones you found are often made. However, those suggestions are made in reference to known algorithms not proven in any way whatsoever.
In order to get actual current state-of-the-art recommendations, keylength.com lists the recommendations of various sources with the publication date. The latest one references the BSI publication of Feb 2017 here: Publication in German, edit: found the English Verison
It has the following suggestion in the subsection RSA:
$\epsilon_1 < |\log_2(p) - \log_2(q)| < \epsilon_2$
And the suggested values for the boundaries are: $\epsilon_1 \approx 0.1, \epsilon_2 \approx 30$. The value $0.1$ for the metric would imply that $p/q$ differs from $1$ by at least a factor of $\approx 1.07177346$, which implies roughly if given the smaller prime $p$, that $q > (1+\frac{1}{14})p$, which in return means for length $b$ primes, the difference should be at least $b-4$ bits (which would mean the difference is $1/16$, but it should be $1/14$ or more).


VIC cipher author known? Does anybody know if the design of VIC cipher is attributed to anybody? I've tried Google and found nothing. There are quite a few sites describing the method in detail, a few implementing it programmatically, and ample stories of the code in the coin, but who actually came up with it? Who decided to put the ideas together in that way? Some Russian scientist I assume, but does anybody know who?

Russian spy Reino Häyhänen, code name VICTOR;
https://en.m.wikipedia.org/wiki/VIC_cipher


What is the meaning of probabilistic polynomial time adversary? I learned about probabilistic polynomial time adversary, but I have some doubt.

Is probabilistic polynomial time adversary referred to those who attack in polynomial time with the form of probabilistic?

Yes, but note as below, the probability is not biased.
From the Lindell, Katz book;

An algorithm $A$ is said to run in polynomial time if there exists a polynomial $p(\cdot)$  such that for every input $x \in \{0,1\}^*$, the computation of $A(x)$ terminates within at most $p(|x|)$ steps.
A probabilistic algorithm is one that has the capability of "tossing
coins", i.e. the algorithm has access to a random source of randomness
that yields unbiased random bits that are independently equal to 1
with $1/2$ probability and to 0 with $1/2$ probability.

Probabilistic Polynomial-time adversary means; An adversary runs in probabilistic polynomial time algorithm.

Different formulation (due to a comment of SEJPM):

A probabilistic polynomial-time algorithm is a probabilistic algorithm that may only perform a polynomial amount of operations including at most a polynomial number of coin-flips.
A probabilistic polynomial-time adversary is then any probabilistic polynomial-time algorithm.


AES-CBC streaming configuration IV usage I am interested in the implications of using AES-CBC in a streaming configuration.

Reading the specifications of a few protocols I notice that when using AES-CBC
they include IV + ciphertext + HMAC in every frame of data sent.

If a stream of data is being sent would it be safe to instead send an IV initially,
but then simply continue using the existing CBC context for the data sent later in the stream?

For example:

context = createAESCBC(mySecretKey, myUniqueIV)
cipherText1 = context.encrypt(pkcs.pad("hello world!"))
// write cipherText1 and HMAC to socket

cipherText2 = context.encrypt(pkcs.pad("foo bar"))
// write cipherText2 and HMAC to socket

instead of:

perFrameIV = generateIV()
context = createAESCBC(mySecretKey, perFrameIV)
cipherText1 = context.finalize(pkcs.pad("hello world!"))
// write perFrameIV and cipherText1 and MAC to socket

perFrameIV = generateIV()
context = createAESCBC(mySecretKey, perFrameIV)
cipherText2 = context.finalize(pkcs.pad("foo bar"))
// write perFrameIV and cipherText2 and MAC to socket

I am aware of AES-CTR, and AES-GCM. I am interested specificially in CBC.

This is broken.  If you send two packets with the same block twice, an eavesdropper on the network can tell that they are the same.  An adversary who can influence your traffic—for example, by causing your web browser to submit HTTP requests with some predictable formatting nearby a secret cookie—can exploit this to recover secrets from your conversation.

If you are having a sequential conversation, though, where each message has a unique number (maybe choose even numbers for one side of the conversation, and odd for the other side), then you don't need to transmit the IV each time: You could use $\operatorname{AES}_k(n)$ as the IV for the $n^{\mathit{th}}$ packet[1].  However, this only provides IND-CPA—that is, security against passive eavesdroppers on the network, not against forgers on the network.

Even better, you could use crypto_secretbox_xsalsa20poly1305 (or AES-GCM, if you insist on the notoriously side-channel-leaky AES) and use the message number as the nonce—then you have authenticated encryption which does defend against forgers, and you don't have to rely on a feathery pseudonymous carrion fowl on the internet for security analysis.


Double DES meet in the middle attack: probability that wrong key pair remains My Question is based on poncho's answer in this post.

If you're doing a meet-in-the-middle attack against 2DES with only on a plaintext-ciphertext pair $(P,C)$, I understand that the expected amount of remaining key candidates is $2^{48}$, assuming that DES encryption/decryption yields a random 64-bit block if done with a wrong key.

What makes me curious now is: if you have another plaintext-ciphertext pair $(P',C')$ to validate the candidates, what is the probability that a wrong key still remains?

So my approach is the following:
We just start a new attack, with the reduced key set.
Since there are only $2^{48}$ keys left, the possibility of a specific block is $\frac{2^{48}}{2^{64}}$ which is $2^{-16}$. Is this is already the possibility I'm looking for?
If yes, then this leads me to the conclusion that despite the probability of one specific block is very small, there are still $2^{48} * 2^{-16} = 2^{32}$ candidates in the set!

Yes your argument is correct, to an excellent approximation.

The reason I say approximation is that the second search in the sample space should really be conducted in the restricted set of DES permuataions that already map $P$ to $C$ (sampling without replacement) but for such a huge sample space the inaccuracy due to not doing this is likely much much less than the modelling step of assuming DES is a pseudorandom permutation.


Why do the elliptic curves recommended by NIST use 521 bits rather than 512? Wikipedia says in reference to the elliptic curves officially recommended by NIST in FIPS 186-3:

  Five prime fields for certain primes p of sizes 192, 224, 256, 384, and 521 bits. For each of the prime fields, one elliptic curve is recommended.

The first four bit sizes are immediately familiar from other cryptographic algorithms, but 521 seems to be the odd man out. Wikipedia even includes a footnote assuring readers that it is not a typo:

  The sequence may seem suggestive of a typographic error. Nevertheless, the last value is 521 and not 512 bits.

Is there a cryptographically-sound reason for 521 bits instead of a more conventional power-of-two? If so, what is it — or if not, why and how was 521 chosen?

I very much suspect it's to related to the fact that $2^{521}-1$ is prime. The previous similar prime is $2^{127}-1$ and the next such is $2^{607}-1$ so they're quite rare. Elliptic curve operations on such a field can be implemented somewhat faster than over another prime field with similar size but without this special form.

I very much doubt that serious thought went into this decision at all. If there are no breakthroughs in elliptic curve logarithm finding then 521-bit coordinate components are complete overkill. If there were a suitable breakthrough then there's no guarantee that 521 bits would be enough.
Elliptic curves tend to be used when the size becomes a factor in the design of a system. It's hard to imagine what sort of constraints would have to operate to make a 521 bit curve order make sense.


TLS Extension signature_algorithms values I hate asking for a reference, but I'm having a hard time finding this.

The iana page on tls extensions just links me back to rfc5246 where it only has the following values:

enum {
    none(0), md5(1), sha1(2), sha224(3), sha256(4), sha384(5),
    sha512(6), (255)
} HashAlgorithm;

enum { anonymous(0), rsa(1), dsa(2), ecdsa(3), (255) }
  SignatureAlgorithm;

I've got a client hello that I'm looking at here with the following signature and hash extension:

  000d 0014 0012 0403 0804 0401 0503 0805 0501 0806 0601 0201

Where can I find a reference for what these refer to?

Some of these values are sort-of defined in drafts that should become RFC at some point. For instance, the latest (as of today) draft of TLS 1.3 lists in section 4.2.3 the values 0x0804, 0x0805 and 0x0806 (these designate RSA signatures with the new-style "PSS" padding, used with SHA-256, SHA-384 and SHA-512, respectively).

The "000d 0014 0012" values are actually the header of the extension:

000d is the identifier for the "signature algorithm" extension.
0014 is the extension contents length (in bytes).
0012 is the length of the list of values in the extension (because the extension is defined as a list of values, and lists in TLS message encodings take an explicit header that gives the list length in bytes).

Note that while the 16-bit values were initially designed as two successive bytes (first for the hash algorithm, second for the signature algorithm), they now tend to be defined as full 16-bit values that cover the whole signature algorithm with no specific sub-structure.


Authentication and deniability I have the following problem: Alice wants to send Bob a message such that Bob knows it is from Alice but at the same time he cannot prove that Alice send him this message.

The solution I came up with, using RSA, is:

Alice picks a random key K, and encrypts the message M using this key K. M'= aes(K, M)
Alice hashes K and Bob's public key to get H. H = sha(K + Bob's Public Key)
Alice signes H using her private key. S = rsa_sign(Alice's private key, H)
Alice encrypts K and S using Bob's public key. P = rsa_encprypt(Bob's public key, K + S)
Alice sends P, M' to Bob

Bob receives P, M':

Uses his private key to get K, S.
Uses Alice's public key to verify S
Uses K to decrypt M'.

Do you see any holes in this?

Thanks!

In step 2 for Alice, what is the purpose of including Bob's public key in the hash? you can include a timestamp to prevent replay attacks instead.

In step 2 for Bob, there is a typo - should use Alice's public key instead of her private key.

Actually your protocol is similar to PGP, and I dont think it provides deniability because if Bob can prove that the public key belongs to Alice then the owner of the private key is most likely Alice.


Random Self-reducibility in Discrete Log I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is

how does it show that DL is hard in the average case.

The probability of success of an imperfect DL black box is $p(n)$ (for an $n$-bit string, and $p$ is a polynomial). So, in order to get a correct DL for an input $y$ is $1/p(n)$.

Does this mean that finding the DL of a single $y$ can be done in polynomial time? (just run the algorithm $n*poly(n)$ which is still a polynomial!)

Afterward, in a lecture the professor, went over describing that the probability of succeeding every time is $$\left(1-\frac{1}{p(n)}\right)^np(n)$$ and that this is less than $e^{-n}$.

How did they reach this conclusion?
If the conclusion is correct, does this mean that the machine is successful every time with negligible probability (so finding a DL of every is negligible?)

I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is how does it show that DL is hard in the average case.

Actually, Random Self-reducibility does not show that DL is hard in any case.  What it does show that if there exists a hard DL instance, then random DL instances are hard.

Remember, the "Random Self-reducibility" property is that we can take an arbitrary instance of the problem $g^x = h$, find $x$, and turn it into a random instance $r_1^y = r_2$, find $y$, and if we can solve the random instance, we can go back and solve our original problem.

How it shows that average instance is hard is by showing the converse; if the random instance had a nontrivial probability of being easy, then we can solve any arbitrary instance (by randomly transforming our arbitrary instance a number of times, and if we happen to hit an easy instance, which we have a good probability of doing, we get to solve the original problem).

All this formalism (which is what is tripping you up) is just expressing this concept in mathematical terms (as opposed to the verbal description I used).

Of course, if you try to do formalism, it is important to get the formulae right.

  The probability of success of an imperfect DL black box is $p(n)$ (for an $n$-bit string, and $p$ is a polynomial). So, in order to get a correct DL for an input $y$ is $1/p(n)$.

Actually, the probability would be $1/p(n)$; remember, probabilities are restricted to the range $[0,1]$

  Afterward, in a lecture the professor, went over describing that the probability of succeeding every time is

Actually, if the attacker is attempting to do this, he doesn't have a succeed every time; all he needs to do is succeed once.  A single success (that is, a random reduction into an instance that allows him to solve the DL problem) will tell time the answer to the DL problem he is actually interested in.

  $\left(1-\frac{1}{p(n)}\right)^np(n)$

That might be the probability that the attacker will need to perform precisely $n+1$ random reductions before hitting on an answer, but if so, I'm pretty sure you garbled that formula (as well as apparently using $n$ with two different meanings, the size of the DL problem, and the number of random reductions the attacker tries)


Why can you reverse a modulo function when knowing its primes We are dealing with cryptography in school right now and superficially went over the Rabin cryptosystem with the (apparently usual) example of p=7 and q=11 etc (we didn't do RSA).

I understand that there are many results when you try to reverse $15 = m^2 \pmod{77}$. E.g. $m^2 = 77+15, 77*2+15,77*3+15$ and so on.

What I don't understand is how it gets easier to reverse this function when you know the primes that you used to calculate the divisor (/the thing with which you did the modulo operation)?

Is this advanced mathematics or is it really quite easy, because for me whether I write $15 = m^2 \pmod{77}$ or $15 = m^2 \pmod{(7*11)}$ doesn't really matter, they're both the same equations.

Of course it apparently matters, so that is why I'm asking.

What i don't understand is how it gets easier to reverse this function when you know the primes that you used to calculate the divisor

Well, we know how to compute square roots modulo a prime; that is, how to solve the problem $a \equiv x^2 \pmod p$, for prime $p$ (assuming, of course, if there is a solution; there might not be one).

In addition, if we know the solution to $a \equiv x^2 \pmod p$ and we know the solution to $a \equiv x^2 \pmod q$, then we know the solution to $a \equiv x^2 \pmod{lcm(p,q)}$ (which is $a \equiv x^2 \pmod{pq}$ if $p$ and $q$ are relatively prime.

What this means that if we know the complete factorization of $n$, then we can solve $a \equiv x^2 \pmod n$ (by looking at each prime factor $p$ of $n$, solving $a \equiv x^2 \pmod p$, and then combining all the answers).  (Actually, I haven't gone into what you would do if $n$ had a factor $p^2$, however that isn't that much more difficult).

With that said, what if you don't know the factorization of $n$; how can you solve $a \equiv x^2 \pmod{n}$?  Well, if $n$ is large (that is, large enough to make factorization impractical), then that looks like a hard problem.  In fact, if you could solve that problem, it turns out you can factor $n$ (by selecting a random $r$, and then trying to solve $r^2 \equiv x^2 \pmod{n}$.  It turns out for composite (more specifically, has at least 2 prime factors) $n$ that there are (at least) four possible answers, and for at least half the answers $s$, $gcd(n, r-s)$ is a nontrivial factor, so that has a good probability of yielding a factor.  Hence, if we have a way to solve this equation modulo a composite, this gives us an efficient way to factor that composite.

So, if we assume factoring is a hard problem, so is computing square roots modulo a composite.


The relationship between the key length and encrypt time in Xor algorithm? I did work on the encryption algorithm and the decryption using the XOR method noticed that when more the key length, the less time spent on encryption and decryption.

I have two questions in particular:

Why the greater the key length less time?
in encryption algorithms using the XOR. Is the key should be a certain length or not?

For simple XOR-based encryption algorithms such as OTP, the key size must be the same as the message size. If you choose a smaller key and try to divide the message into chunks, you would not have a perfectly secure scheme anymore.

Now, since you tagged java, I'm assuming that this increase in time for smaller key sizes is due to the code trying to divide the message into chunks. In that case, this doesn't have much to do with the algorithm, but rather with how you are writing your code.


Why does TLS 1.3 support two CCM variants? One of the important improvements introduced in TLS 1.3 is the pruning of the many previously available cipher suites to only five secure options (for symmetric ciphers), that are each supposed to have distinct advantages. For four of these, the advantages seem to be clear:

TLS_AES_128_GCM_SHA256: faster on systems with hardware support for AES/GMCM.
TLS_AES_256_GCM_SHA384: bigger numbers for regulatory (or marketing) reasons; resistant to Grover's algorithm.
TLS_CHACHA20_POLY1305_SHA256: faster in software with no AES acceleration.
TLS_AES_128_CCM_8_SHA256: useful for embedded devices that just want to reuse an AES circuit for both encryption and authentication; shorter tag.

However, I am still puzzled about the rationale behind the inclusion of TLS_AES_128_CCM_SHA256.

If I understand correctly, CCM with 64-bit authentication tags should be resistant against $2^{64}$ forgery attempts, which is also the maximal amount of messages TLS allows to be encrypted with the same key. So what is the added benefit of also supporting a version with 128-bit tags?

Of course I could be mistaken about CCM_8, and maybe it is not suitable for authenticating $2^{64}$ messages after all. But in that case, why doesn't RFC 8446 mention this in the "Limits on Key Usage" section? What am I missing here?

The rationale goes this way:

On a "big" system like a PC or a smartphone, ChaCha20+Poly1305 or AES/GCM are very efficient; the latter is fast because the hardware provides dedicated opcodes that implement both AES itself (aesenc, aesenclast on x86 CPU) and the GHASH part of GCM, which is used for the integrity check (pclmulqdq opcode on x86 CPU).
On much smaller systems (embedded microcontrollers), things are not that easy. Pure software implementations of AES/GCM are quite slow; ChaCha20+Poly1305 may fare somewhat better, but not necessarily as fast as can be hoped for. Note that "speed" can mean "maximum bandwidth", but also battery life: when processing small messages, the cost for encrypting can be expressed in terms of a duration during which the CPU must be powered at its high frequency.

On that kind of system, you may have an hardware AES implementation, but usually not a an hardware helper for GHASH (because of size constraints on the CPU die, mostly). Thus, CCM works better than GCM on such microcontrollers. This explains the request for supporting some CCM-based cipher suites.
Constrained systems are usually constrained for everything; computing stuff drains the battery, but so does sending data. Reducing the amount of bytes to send can help, and every byte counts. The normal authentication tag of CCM is 16 bytes. The "CCM_8" cipher suites use tags reduced to 8 bytes, thus saving 8 bytes of overhead, at the expense of a higher probability of forgery.

This is how TLS 1.3 ends up with CCM_8 cipher suites. It's all about performance issues on small embedded systems. Note that MAC can tolerate a relatively high forgery probability because of their "online" nature: when an attacker tries to forge a MAC value, he still have to try it out on an honest receiver for every forgery attempt; if the attacker is talking with small embedded systems, he won't be able to do that many times per second (and each failed attempt implies an error on the receiving system). This contrasts with encryption, where a brute force attack is "offline" (the attacker tries potential decryption keys on his own computers, and can thus do that at a high rate, and quietly).

It is worth pointing out that AES/GCM has a bit of trouble with truncated tags. An authentication tag of $n$ bits cannot have a probability of forgery less than $2^{-n}$, but with GCM, when $n < 128$, it tends to be higher (specifically, successful forgeries leak extra information, making subsequent forgeries easier). As such, tag truncation on GCM is not recommended. CCM, for all its design issues, does not suffer in the same way.


Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox) I encountered this while solving a crypto puzzle. This is the puzzle.
You have a hash which gives a 11-bit output. How many minimum messages do we have to hash to have a 50% probability of getting a collision.
Normally we see kind of problem being solved by using an approximation $2^{n/2}$ or $\sqrt {2^n}$
So for a 11-bit hash, the number of messages to hash to have 50% chance of a collision would be
$\sqrt {2^{11}} = 45.255 \approx 46$ messages
However, the solution for this puzzle uses
$log_{\frac {2^{11} - 1} {2^{11}}}{(0.5)} = log_{\frac{2047}{2048}}{(0.5)} = 1419.22 \approx 1420$ messages
So you have to hash approximately 1420 messages to get a 50% probability of having a collision.
The solution doesn't explain how they arrive at this. So which is the correct solution?

You are approximately correct; they are wrong. Their answer calculates the chance of matching a particular value i.e. hash inversion. To see this $k$ tries have a $(2047/2048)^k$ of failing to find a match so you want $k>\log(0.5)/\log(2047/2048)$.
For small numbers we can calculate the exact value of the birthday bound by finding the smallest $k$ such that
$$\prod_{0\le i\le k}\frac{n-i}n=\frac {n!}{(n-k)!n^k}<0.5$$
which in this case is $k=54$.


How to determine the order of an elliptic curve group from its parameters? Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the order of $E(\mathbb F_q)$ is in the range $[q+1-2\sqrt{q}, q+1+2\sqrt{q}]$.

Is it possible to determine the order of $E(\mathbb F_q)$ given $a, b, q$ without enumerating the points?

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas:

The number of points is closely linked to a functional equation
$$ \varphi^2-t\varphi+q = 0 \qquad\in\operatorname{End}(E)$$
that the Frobenius endomorphism
$$ \varphi\colon\;E\to E,\;\begin{cases}\mathcal O&\mapsto \mathcal O\\(x,y)&\mapsto (x^q,y^q) \end{cases} $$
satisfies in the endomorphism ring of $E$. If $t\in\mathbb Z$ is chosen such that this equation holds, it is called the trace of Frobenius and one can show that
$$ \#E(\mathbb F_q)=q+1-t \text. $$
(The reason $\varphi$ has anything to do with point counting is that it leaves exactly the points with coordinates in $\mathbb F_q$ invariant.)
For odd $l$, there exist division polynomials $\psi_l\in\mathbb F_q[x]$ which vanish precisely on the $x$-coordinates of the finite $l$-torsion points of $E$. Therefore, one can compute $t\bmod l$ by checking for which $k\in\{0,\dots,l-1\}$ the functional equation $\varphi^2-t\varphi+q=0$ holds modulo $\psi_l$. Computing modulo $\psi_l$ greatly improves the complexity (compared to expanding the terms without any reduction). Having computed $t\bmod l$ for a sufficiently large (according to Hasse's theorem, $\prod_{l\in L}l>4\sqrt q$ is enough) set $L$ of odd primes, the Chinese remainder theorem can be used to reconstruct the trace of Frobenius $t$, thereby yielding the number of $\mathbb F_q$-rational points $\#E(\mathbb F_q)$ on $E$.

Of course, there are implementations of (the improved variants of) this algorithm in most computer algebra systems. Using sage, the number of $\mathbb F_{p^n}$-rational points of an elliptic curve
$$ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 $$
defined over $\mathbb F_p$ can be computed as:

EllipticCurve(GF(p), [a1, a2, a3, a4, a6]).cardinality(extension_degree = n)


How can C rand() be exploited if a secure seed is used? I've just started doing a research project on CSPRNGs and I would like to know what kind of vulnerabilities a regular PRNG has with a secure seed. For example, if I generate a random number using LavaRnd to seed srand(), then generate some big key with rand(), what can an attacker do to resolve that key, or otherwise find critical information?

I have seen a lot of people with similar questions, but the answer usually boils down to "the result will not have enough randomness", then there is a lot of hand-waving about the specifics. But what does that mean for a real world implementation? What actual vulnerabilities or attacks can be mounted on an insecure pseudorandom number generator using a secure seed?

The ISO/IEC 9899:1990 edition of the C standard contains:

  EXAMPLE     The following functions define a portable implementation of rand and srand.

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

The state of this generator is entirely characterized by the 31 low-order bits of variable next. If we "generate a random number using LavaRnd to seed srand(), then generate some big key with rand()" as in the question, then only $2^{31}=2147483648$ outcomes (at most) are possible for the "big key", determined entirely by the 31 low-order bits of input seed.

That then allows an attack that tries all these keys. If testing a key requires $2^{20}$ clock cycles (about a million) of a $2^3$-core CPU running at $2^{31}$ Hz, the attack is expected to last $2^{31+20-3-31-1}=2^{16}=65536$ seconds, that is less than a day.

Depending on what's done with the "big key", there might be much faster attacks. For example, that would be the case if rand() is also used to generate the Initialisation Vector, which customarily is at the start of enciphered messages. A simple attack can find the value of next from three consecutive values of rand(). That takes literally less than the blink of an eye, and allows finding effortlessly all past and future output of rand() not interrupted by srand().

On the other hand, perhaps the above $2^{20}$ cycles estimation is way too low (that could be the case for an RSA key). But by any measure, a 31-bit keyspace is farther waaaaay too low. Currently, the threshold of practical security is somewhere near 80-bit, give or take 20. 128 is considered fine till 2030, except if one believes in fairies or quantum computers becoming usable for cryptanalysis any time soon.


Which attacks are possible against raw/textbook NTRU encryption? In the same fashion that these questions about attacks to textbook RSA and ECC, I was wondering what are the immediate drawbacks of applying NTRU Encryption directly, without any padding scheme, such as NAEP or SVES.

Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the private key from the bits denoting the success/failures.

To review how raw NTRU encryption works: select a message $M$ (as a polynomial), select a random lightweight polynomial $R$ and then compute the ciphertext $C = RH + M$ (where $H$ is from the public key).

To decrypt it is required to compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$.  Because of how $F$ and $H$ are related, this is $pRG + FM$; the next step is to evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred). T his strips off the $pRG$ term, giving $FM \bmod p$; from that, it is possible to recover $M$. However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod p$; this will give the wrong $M$.

So, what can cause a wrap?  Well, wraps will occur if a coefficient of the polynomial $RG$ is too large. It is too large when it is outside the range $(-q/2, q/2)$ (not considering the implicit $\bmod q$ operation). $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is a value that can be used to calculate the private key from the public key. By artfully selecting $R$ values, an attacker could probe $G$ and - over time - recover it. Note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.

There are guidelines on how an honest encryption should select $R$ values so that decryption failures don't leak information. An attacker will however ignore these guidelines. NAEP prevents the key recovery attack by making the polynomial $R$ a deterministic function of $M$ (and some random bits that are included in the message). So after the decryptor recovers $M$ (and those random bits) we can recompute what $R$ should have been. We can then compares it to the $R$ that was actually used. If they're different then that also results in a decryption failure. An attacker can therefore not use a value of $R$ that is outside the guidelines.


Cryptographically secure shaming I was thinking of the problem of naming&shaming, victims don't want to reveal themselves. Yet the public wants to know, and have some confidence in the veracity of statements. Such confidence could arise for instance from multiple victims naming the same person. I was thinking cryptography could come to the rescue.

I'm having trouble even in the formal definition part. Initially I though multi party computation could allow a group of people to each name (or not) and only if a name passes a threshold is it revealed, and all members of the group could attest the name passed the threshold. But thinking of practice issues, we may want a async process, where after setup different people submit their testimony separately with minimal back and forth. We may not know in advance who will participate and want to be able to work with a subset members. The minimal number of people to ensure reasonable anonymity is rather small say 100, but we may want to increase the requirement significantly if we are thinking about minimum number of colluding members to reveal which specific member named someone.

I quickly run into impossibilities, If we allow ad-hoc groups to form and vote together then a not so large malicious group could break anonymity. I'm looking for a solvable variant of this problem.

There is a very recent paper that solves this problem at a large scale using secure computation techniques:

  How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior: Moni Naor, Benny Pinkas, Eyal Ronen

They motivate the problem from the point of view of passwords (they want to identify passwords that are too common), but it seems like the same problem you propose.