How 'safe' is a 12-digit alphanumeric key? To Access my data over a Portal i got a 12-digit alphanumeric key like:

VGW8-U98T-TXLV

How safe is this key? I don't want to know the chance to win with brute force. I want to know there are several standards to calculate keys like this? It is the one and only way to get access / safe my really personal health data. The portal can easily reached by a website.

I can't tell more informations about how the key is generated or used.
Maybe I'm a bit paranoid, but to get access with just these key and nothing else (e.g. birthday as second check) seems a bit easy. Even if the key give a lot of combination for a brute force.

Well, you have $(26+10)^{12}$ choices if the characters are truly random and independent. That's how we commonly judge security in these situations.  So that's $4.7 \times 10^{18}$ alternatives, or 62 bits of security. Hmm, not bad but we commonly refer to at least 128 bits of security on this site. However...

The real security question here is what happens if the wrong key is entered? Consider that a hole-in-the-wall machine only uses 4 digit PINs, but it gets angry when the wrong PIN is entered three times. What does your portal do? It would be really really bad if it just accepted incorrect passwords ad infinitum. Some form of lock out would be in order, or   a  delay (exponential) after each failed attempt.

There are standards/libraries for token generation such as the secrets module in Python with ad hoc security parameters. It's difficult to progress this further in light of the above uncertainty and your minimal revelations about the portal.

And to the counter, any password like your's is almost certainly going to be written down.

And I'm assuming that your records are encrypted in some secure form, rather than directly  using this password without an intermediary key derivation function.


Is AES key length a size of the key or entropy? While educating my self I'm having hard time to understand what an 128 bit AES key actually means?
Is it a key length or entropy?
Please explain to me trough following example (assuming AES):

Password length in characters (L) = 20 (characters)
Symbols used (N) = 95 (ASCII set)
Entropy = log2 (N^L) = 128 (is this what is called 128bit AES key?)
OR
Key length = L * 8bits = 160 bit key length ? (is this supposed to
be 160bit AES key?)

When somebody says that he's using 128bit AES key, I want to know to what is he referring to, a key length or entropy?

When they say they are using a 128 bit AES key, they mean the length of the key is 128 bits. Technically a 128 bit AES key could have 0 bits of entropy, 128 bits of entropy, or anywhere in between.

To be secure, however, the 128 bit key should also have high entropy. Ideally, a 128 bit AES key would also have 128 bits of entropy.

A few side notes
Keep in mind that $\log_2N^L$ only computes the entropy in the key if the $L$ characters in the password were chosen randomly.

There is no such thing as a 160 bit AES key. AES supports key lengths of 128, 192, 256 bits.


What is Homomorphic encryption evaluation key In some homomorphic encryption schemes (e.g Multi-key fully homomorphic encryption report, Computing Blindfolded: New Developments in
Fully Homomorphic Encryption), it defines an encryption key, a decryption key, and an evaluation key to perform an evaluation f on the encrypted data. Could you please explain what is the difference between the evaluation key and the other keys?

In short

Public key is used to encrypt, private key is used to decrypt, and evaluation key is used to perform homomorphic operations (usually, homomorphic product or, the somehow equivalent operation, a logic AND gate).

In detail

Public and private keys in homomorphic encryption (HE) schemes are just the same as in other types of schemes.

The evaluation key ($evk$) is also public, it is typically generated using the private key, and it is used to control the noise growth or the ciphertext expansion during homomorphic evaluation.

Some schemes have a "Key-switching" key instead of the evaluation key, but they are more or less the same. For instance, in the description of FV and YASHE, you can see that to perform a homomorphic product, one first multiplies the ciphertexts, $\tilde{c}_{mult} := c_1 \otimes c_2$, then uses this "extra public key" to adjust $\tilde{c}_{mult}$, that is, to get a ciphertext $c_{mult}$ with the correct dimension and that can be decrypted using the original secret key.

So, in general, this is how you use $evk$: you perform a homomorphic operation that introduces a lot of noise or that generates a ciphertext in higher dimension, then you perform an extra operation using $evk$ to "correct" that ciphertext.

As an extra example, take a look to FHEW Library Interface and you will see that the NAND gate uses $evk$, but the NOT gate does not.

Further observations

If you bootstrap, then you typically need $evk$, since you need it to perform homomorphic evaluations in general and bootstrapping is the homomorphic evaluation of the decryption circuit.
In principle, there is no special relation between multi-key HE schemes and evaluation keys (FHEW is not multi-key and also has an $evk$).
Even if the scheme is symmetric (i.e., does not have a public encryption key), it may still have evaluation key.
Some schemes do not have evaluation key (e.g., GSW).


Sequential public key generation with secret private keys? So this is an idea that popped into my head the other day and I wonder if there are any known crytographic schemes with these properties?

Is there a way to construct a public / private key system in such a way that I can somehow compute some "seed" like 0x22EDEF67FFEED that can be used to derive an infinite number of public keys, while NOT being able to generate the corresponding private key?

To be able to generate the private keys you need to know a secret that was computed together with the above "seed".

Example usage:

Alice publish a public key seed with the above rules with the value 0x22EED...
Alice then makes the promise that she will make the private key for the Nth derived public key public every Nth day.
Bob can now encrypt some secret with the 100th derived public key and publish it, knowing that the data will be publicly available in exactly 100 days.
After 100 days Alice publishes the 100th private key and Bob's secret can be decrypted by anyone.

I have no idea if this would be useful in the real world, but it peaked my interest anyway.

Yes, this is indeed possible.

A scheme with such properties is e. g. used in Bitcoin's HD (hierarchical deterministic) wallets. The scheme was introduced in BIP32 (Bitcoin Improvement Protocol) and is explained in detail here: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

Regarding your example scenario: That is also possible with the system Bitcoin uses. However the key derivation path and the order in which the private keys are released is important in order to not leak future private keys in advance.


Are there attacks on AES with 16-bit keys? Are there known attacks on AES that uses a 16-bit key?
Assuming the data can be 95MB size, and that I can request the same data over and over.

For example, can someone explain to me how this code vulnerable? I know my around C, but can’t seems to find anything here. Usual CRIME attack won’t work.

#include <string.h>
#define MAX_SIZE 100000000
#define MAX_NAME_LENGTH 1000

unsigned char shared_key[16]={0x01,0x23,0x45,0x67,0x89,
0xab,0xcd,0xef,0x01,0x23,0x45,0x67,0x89,0xab,0xcd,0xef};

char directory_location[50]="../../server_directory/";
char *file_to_string (char *output_string,
FILE *input_file, int *length);

FILE *compress(char *input);

FILE *encrypt(unsigned char *key, FILE *input);

void application_send (FILE *output);

int get_file (char *name, unsigned int name_length)
{

FILE *input, *compressed_file, *encrypted_file;

int file_length;

char uncompressed[MAX_SIZE];

char file_string[MAX_SIZE];

char filename [MAX_NAME_LENGTH];

if (name_length >= MAX_NAME_LENGTH-50)

return -1;

strcpy(filename,directory_location);

strcat(filename,name);

input = fopen(filename,"r");

if (input == NULL)

return -1;

file_to_string (file_string, input, &file_length);

memcpy(uncompressed,name,name_length);

memcpy(uncompressed+name_length,file_string,file_length);

compressed_file = fopen("compressed","w");

if (compressed_file == NULL)

return -1;

encrypted_file = fopen("encrypted","w");

if (encrypted_file == NULL)

return -1;

compressed_file = compress (uncompressed);

encrypted_file = encrypt (shared_key, compressed_file);

application_send (encrypted_file);

return 0;
}

There is no such thing as a 16 bit AES key. AES is a block cipher with a block size of 128 bits and a key size of 128, 192 or 256 bits. As a block cipher, AES can only encrypt 16 bytes (128) bits at a time. AES in itsef is not (CPA) secure as repetition of the plaintext would lead to repetitions of the ciphertext.

To encrypt larger amounts of data, AES needs to be used as primitive in a block cipher mode of operation. Although block cipher mode of operations of course depend on the (high) security of AES, they have their own security boundaries. ECB is not secure at all, CBC needs a randomized IV, CTR needs a unique nonce and has limitations on the size of the input.

The practicalities of establishing the mode and parameters such as the IV depend on the protocol. You would have to examine the protocol, mode and cipher to establish if your use case is secure or not. This would also depend on the attacks you're willing to allow. For instance, just using AES in CBC mode of operation does not protect against man-in-the-middle attacks at all.


Intuition for SHA3 sponge construction I would like to get some intuition on the security of the sponge construction. I'm referring to this diagram and notation.

Let's consider the case where we have don't apply $f$ in the squeezing phase i.e. we simply take the bits in the r-space ($Z_0$ in the figure) at the end of absorption and call that the hash of our message.

The Wikipedia article says that one could replace the XOR function and simply choose to overwrite the $r$ bits with the message instead of using XOR. The security level is not compromised if this is done and makes it easier for me to understand.

Reading a few other answers, it seems to be the case that the core thing that keeps SHA3 safe is the lack of knowledge about the state of $c$ in the final step. But this seems problematic.

For instance, let's say I have the hash of a known message (and therefore the internal states $c$ corresponding to this message at all stages) and would like to modify the last part i.e the $P_{n-1}$ bits. It seems like I have a very localized problem i.e. I know $(r_1, c_1) \xrightarrow{f} (r_2, c_2)$ and must find $(r_1', c_1) \xrightarrow{f} (r_2, c_2')$ for arbitrary $c_2'$. If I want to do it for any intermediate block, $P_k$, then $(r_1', c_1) \xrightarrow{f} (r_2', c_2)$ is the constraint, where $r_2'$ is arbitrary. This is because the bitrate is overwritten in intermediate blocks so that part of the output can be arbitrary while for the last block the state of the capacity is not used so it can be arbitrary. Moreover $f$ is just a permutation and so this task seems... not too hard?

I want to add, I know that hundreds of very clever people have tried various attacks and failed so this has a good resolution. This isn't some crackpot "I broke SHA3" post - it's more of a "what aspect of SHA3 am I missing" post!

So if it's just a permutation of 0s and 1s as we've concluded, what is hard about finding an alternate message string that satisfies the constrains I've mentioned on the permutation outcome?

To be more precise, it is a pseudo-random permutation from $\mathbb{Z}_{2^{1600}}$ to $\mathbb{Z}_{2^{1600}}$. It is not just 0s and 1s changing positions.

Because of the size of $\mathbb{Z}_{2^{1600}}$ (which contains $2^{1600}$ elements!), the input and output are related in a somewhat random (but  deterministic way), and it cannot be predicted without actually evaluating the permutation (or its inverse) on a given input and checking the result.

There are tools such as linear and differential cryptanalysis that can be used to try and predict the output, but keccak-f was explicitly designed so that using these techniques would be computationally intractable.

  It seems like I have a very localized problem

You cannot isolate parts of the state and work on them independently. Changing one bit of the state and then applying the permutation diffuses those changes across the entire state in an unpredictable manner.


How can Alice enable Bob to look-up values in a private map I think this problem is similar to private set intersection, yet distinct in a way where:
Alice has an extensive Mapping of say id to name

id1 -> John Doe
id2 -> Jane Doe
id3 -> Edgar Poe

Bob has a short-list of id's say

id1 (Alice knows the name of this person)
id3 (Alice knows the name of this person)
id4 (Alice doesn't know the name of this person)

Neither Bob, nor Alice wants to share all their data assets with each other. However Alice has agreed to share the names of the people for whom Bob has knows the id.
Bob on the other hand, doesn't want Alice to know which id's he has.
Are there any known, secure protocols which only involve two parties? (no-trusted 3rd parties etc)

Many (most?) leading PSI protocols can be easily adapted to provide this functionality. It is sometimes called "PSI with associated data" or "PSI with data transfer". For example, you can see this variant of PSI described explicitly in:

Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear complexity. Financial Cryptography 2010.

Even many protocols which don't mention "associated data" explicitly can be easily modified to provide it. I know for sure that the following papers (which are the fastest 2-party semi-honest PSI) will support it:

Benny Pinkas, Thomas Schneider, Gil Segev, Michael Zohner: Phasing: Private Set Intersection using Permutation-based Hashing. Usenix 2015.
Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu: Efficient Batched Oblivious PRF with Applications to Private Set Intersection.
CCS 2016.

These protocols use an "oblivious PRF" paradigm for PSI, which works roughly like this:

Parties perform an Oblivious PRF where Alice learns (description of) a random function $F$ and Bob learns $F(y)$ for every $y$ in his set.

Alice can compute and send $F(x)$ for every $x$ in his set. Now Bob can compare against his set of $F$-values and identify the intersection. For values $x$ that Alice has but Bob doesn't have, the corresponding $F(x)$ value looks random to Bob, so leaks no information about that $x$.

There is a fair amount of other algorithmic/combinatorial stuff in these protocols, but eventually at some level the protocol is doing what I described above.
To add associated data to this protocol outline, you can just use the $F(x)$ values as keys to encrypt the associated data. Something like this:

For every $y$, Bob has $F(y)$ and (if it's not long enough) expands it with a PRG to get two values $tag_y$ and $k_y$.

For every $x$, Alice similarly expands $F(x)$ into $tag_x$ and $k_x$. She sends $(tag_x, \mathsf{Enc}(k_x, data[x]))$, where $data[x]$ is the record/data associated with key $x$.

Bob can look for tuples of the form $(\tau, c)$ where $\tau$ is a tag that he recognizes as $tag_y$. He can then decrypt $c$ with the corresponding key $k_y$ to obtain the data associated with $y$.


When using Client Certificates, is it usual to generate your own? We're building a webservice for a third party customer who wants us to use "two-way SSL". By which I understand them to mean they want us to host the site using https, and to require that include a Client Certificate in each http request.

I've been working through a number of examples on how to make all this work with the tooling we use, and I think I'm beginning to get a handle on it.

If I'm understanding correctly, we'll provide them with a certificate. They have their client include it in their requests, and we validate that the certificate we receive is what we expect.

What's not clear to me is whether it's usual for us to have the certificate created by a CA, or for us to do it ourselves. With SSL certificates, an unsigned cert is meaningless. But with client certs, we're expecting to receive a specific cert, so I'm not sure I see that validating that everything is signed back to a recognized root authority really matters.

Do people generally use CA-signed client certs, regardless?

In a typical business to business setting it may  be that the client is also a server for other use cases. In that case the server cert and corresponding private key of the other party could be reused. To be able to verify that it is correct you should probably pin (trust just that) certificate as you may not want to trust other certificates issued with a generic CA to connect - although you could also whitelist the particular server name.

Yes, it is perfectly valid to issue your own certs in this setting. For security reasons it is best if the other party creates a key pair with corresponding certificate request, which you then use to create a signed certificate that you can trust. For this you need a CA & CA software (and trust your own CA certificate). You could also simply  trust a self signed certificate from the other party.

I think it generally just makes sense to use a normally issued certificate by a third party CA iff:

either you want to reuse the cert / key material and/or
you have some reason to only trust a cert with a particular host name.

Key management is a complicated matter. To avoid awkward conversations I would definitely ensure that you create the protocol together with the other party. Time for coffee and cookies!


Which one is better using DSA, or MAC and encryption? I want to authenticate server messages to clients. The communication between clients and server is unicast. As I know I can use either used MAC or DSA.

by using MAC, I required a shared key between client and server which can be conducted by distributing public key to the client, and the client can generate share key, encrypts it by using public key and send to the server. So I require encryption and MAC algorithms.
by using a Digital signature, I required only distributed public key to clients.

So which one is better using DSA, or MAC and encryption?

Which is better depends on context.

Reasons to choose 1 (MAC with a key that was generated by client and sent encrypted under public key of server)

Shorter messages from server to client (a MAC is at least 4 times shorter than a DSA signature).
Much faster verification of messages by client (DSA signature verification is slow; that can be improved with ECDSA, and much improved with RSA signature instead of DSA; MAC is the speed king).
Much faster preparation of messages on server, after the initial key establishment (DSA signature generation is slow compared to a MAC; that can be improved with ECDSA, RSA tends to make that worse; again, MAC is the speed king).

Reasons to choose 2 (DSA signed messages)

No need for any communication from clients to server.
Conceptual simplicity.
No need for a CSPRNG on clients (these are hard to get secure).
No secret whatsoever in the clients (keeping a secret secret and unaltered is harder than keeping a public information unaltered).
No need for encryption at all (which is harder to get secure than signature verification).
Less secrets on server (option 1 requires the server to keep the client-unique MAC key secret).
The same signed message can be sent to all clients (most useful for multicast, but not much of an argument for unicast).


Are quantum computers a sign that we should phase out RSA? Shor's algorithm has already been implemented to factor 15 into 3*5 on a simple quantum computer. Is technology to the point that we should consider RSA deprecated?

I don't think so. We are still an incredibly long way away from quantum computers being built that can deal with RSA (if they ever happen). It's certainly a good idea to get ready and have alternatives in hand. If you are really paranoid then you can start encrypting things today that still need to be secret in 10-20 years using a combination of RSA and lattice-based encryption. Otherwise, I would just wait.


What is a universal hash function? Short and to the point. I'm assuming that it is not a kind of hash function that can be used universally. After having read about universal hash functions used with the one-time pad to form an authentication scheme, these things have bugged me out.

From Wikipedia:

  In mathematics and computing universal hashing (in a randomized
  algorithm or data structure) refers to selecting a hash function at
  random from a family of hash functions with a certain mathematical
  property. This guarantees a low number of collisions in expectation,
  even if the data is chosen by an adversary. Many universal families
  are known (for hashing integers, vectors, strings), and their
  evaluation is often very efficient. Universal hashing has numerous
  uses in computer science, for example in implementations of hash
  tables, randomized algorithms, and cryptography.

Definition:
A randomized algorithm $H$ for constructing hash functions $h\colon U \to \{1,\ldots,M\}$
is universal if for all $x \neq y$ in $U$, we have
$\Pr_{h\gets H} [h(x) = h(y)] \leq 1/M$

From this answer:

  Let $\Phi$ be a finite collection of hash functions that map a given
  universe $U$ of keys into the range $\{0, 1, 2,\ldots, m - 1\}.$

  $\Phi$ is called universal if for each pair of distinct keys
  $x, y \in U$, the number of hash functions $h \in\Phi$ for which
  $h(x) = h(y)$ is precisely equal to $$\frac{\lvert\Phi\rvert}{m}.$$

  With a function randomly chosen from $\Phi$, the chance of a
  collision between $x$ and $y$ where $x \neq y$ is exactly
  $\frac{1}{m}$.


Most efficient way to perform secure bitwise multiplication Suppose there are two parties with binary strings of equal length. What would be the most efficient way to securely calculate the bitwise multiplication of these strings (i.e if one party has 0101 and the other party has 0011 then the product would be 0001)?

My current thinking is that some sort of single-bit multiplicatively homomorphic cryptosystem would work best, but I have been unable to think of any (ElGamal, for example, does not support encryption of 0).

The most natural method for this task would be to use oblivious transfer: on input a bit $x$ for Alice and a bit $y$ for Bob, Alice plays the role of the sender in an oblivious transfer with input $(x_0,x_1) = (0,x)$, and Bob plays the role of the receiver with input $y$, and learns $x_y = x\cdot y$. By repeating this method in parallel for all the bits of their input, Alice and Bob get the bitwise multiplication.

This is probably the most natural and efficient method to perform this task. An alternative is to use ElGamal over a group $\mathbb{G}$ with generator $g$ and public key $h$ for which Alice knows the corresponding secret key.

Alice sends an encryption $(c_0,c_1) = (g^r, h^rg^{x})$ of $g^x$. Bob computes $(c'_0,c'_1) = (c_0g^{r'},c_1^y)h^{r'})$, that is, a rerandomized encryption of $g^{xy}$, and sends it back to Alice, who decrypts and get $g^{xy}$. As $xy \in \{0,1\}$, she easily recover $xy$ from that. Again, by repeating this method in parallel for all the bits of their input, Alice and Bob get the bitwise multiplication.


Why is h(m||k) insecure? Here is the post that explains the failure for doing h(k||m) and I understand it.

But I don't understand how h(m||k) is subjected to collison attack, or birthday attack. Please explain?

The birthday attack can be used with every hash function. It's a simple matter of probability (see: birthday problem). However, that only means that a hash function has to generate $2n$ of output to achieve $n$ bits of security.

It's fairly obvious that $H(m||k)$ is collision-resistant provided that $H$ itself is collision-resistant, since $H(m_1||k)=H(m_2||k)$ would imply that $H(x)=H(y)$ for $x=m_1||k$ and $y=m_2||k$.

However, the big advantage of HMAC over $H(m||k)$ is that collision-resistance of the underlying hashing function is not needed. Bellare proves in New Proofs for NMAC and HMAC: Security without Collision-Resistance that HMAC is secure as long as $H$ is a pseudorandom function, which is considerably weaker than collision-resistance.

Thus, even though the once popular hashing functions $MD5$ and $SHA$ are already broken, $HMAC_{MD5}$ and $HMAC_{SHA}$ are stil considered secure.


Which assumption is stronger (p-BDHI) and DL? (p-BDHI): p-Bilinear Diffie-Hellman inversion problem

Given $P,sP,s^2P,...,s^pP$. Find $e(P,P)^{\frac{1}{s}}$.

(DL): discrete logarithm problem

Given $P,sP$. Find $s$.

To break (p-BDHI), attacker needs to break DL.

I think the two assumptions have same-level hard problem.

No one is stronger than another. Is it right?

p-BDHI is clearly at least stronger than DL: if you can break the DL problem, you can recover $s$, and then compute $e(P,P)^{1/s}$ (if you are in a group where inversion can be computed efficiently, which I think is always the case in known pairing groups).

On the other end, it is not clear that breaking p-BDHI could allow breaking the discrete logarithm problem, as, intuitively, breaking it only involve computing a group element and does not directly give a way to recover an exponent (this is informal as it could still be that p-BDHI allows too break the discrete logarithm problem, it does just seem far from obvious).


Encryption and HMAC key derivation I'm deriving keys from a user-supplied passphrase for symmetric encryption using AES-256 in CBC mode with a HMAC for authenticity/integrity.

My key derivation function currently looks like this:

Please note that scrypt could just as easily be subbed out for PBKDF2 or bcrypt, that remains to be seen.

I have a couple questions:

Does input truncation using SHA-256 expose any potential weaknesses?

My reasoning for doing it in the first place is because many algorithms like bcrypt only accept a limited password input size. (bcrypt seems to accept up to 55 or 72 characters, not sure on the source of this)
Would it be better to prefer a hash method with a longer output, ie SHA-512?

When generating the HMAC authentication and encryption keys, would I benefit at all from using SHA-512?

AES-256 IIRC needs 256-bit keys, so if I either used AES-192 or used SHA-512, how would I go about fixing the discrepancy in required size?

Does input truncation using SHA-256 expose any potential weaknesses?

No, hashing the passphrase with SHA-256 will be no stronger or weaker than feeding it in directly.  If you go with Scrypt (which I would recommend you do), there are no restrictions on the size of the passphrase... and Scrypt consumes it internally with one round of PBKDF2-HMAC-SHA256 anyway.

  When generating the HMAC authentication and encryption keys, would I benefit at all from using SHA-512?

No, you wouldn't. In fact, this step is unnecessary.  Just use the output of Scrypt directly... randomBytes = Scrypt(passphrase); encKey = randomBytes[0, 31];  authKey = randomBytes[32, 63]


Size of p in ElGamal cryptosystem? In the ElGamal cryptosystem, I was wondering whether the $m$ (message) should be less than $p$ (large prime). Because on decryption, we are getting $m \bmod p$. For $m \bmod p$ to be equal to $m$, shouldn't $m$ be less than $p$? So what should be the size of $p$? Should it be a very very large prime number if I need to encrypt a file of 5 GB or something?

As your message treated as one element in the finite field defined by $p$, it must be smaller than this $p$.

There are other reasons, but you mention one about why to use hybrid systems. When you encrypt using public key, the process starts by generate a random symmetric key used to encrypt your data. What is encrypted using the public key is this symmetric key.

Another reason is to encrypt to more than one recipient. The data itself is encrypted once for all, and is this symmetric key the one encrypted for each target.

Note that the size of a symmetric key is much smaller than the size of its equivalent in security in public key.


Is the use of AES in LoRaWAN correct? I'm reading about LoRaWAN (specification). This network protocol has a particular way to encrypt data, detailed in the part 4.3.3.1. Here is a recap of how the encryption work, as I understood it.

First, a sequence A with blocks with a size of 16 bytes each A1..An is created. The length of A depends of the length of the payload  so that len(payload) <= 16*n = len(A) < len(payload) + 16. Here are the values used for the block Ai:

0x01 | 0x00 | 0x00 | 0x00 | 0x00 | Dir | DevAddr | Counter | 0x00 | i

One block is 16-bytes long. The Counter is incremented for each payload; i is incremented for each block created (1 <= i <= n). Dir is 0 or 1 depending if it's upward or downward, and the DevAddr is fixed with the address of the end-device.

Now that the blocks are created, they are encrypted to get a sequence S of blocks Si:

Si = aes128_encrypt(K, Ai) for i = 1..n
S = S1 | S2 | .. | Sn

And finally the payload is encrypted:

(pld | pad16) xor S
truncation of the first len(payload) bytes

The message sent is created by concatenating a header (containing among other things the values of DevAddr and Counter), the encrypted payload and a MIC (Message Integrity Check) generated with another AES key. The receiving device knows the key, so it can:

check the MIC
create the blocks A1..An by using the values indicated in the header
encrypt them to get the sequence S
decipher the payload

Here are my questions

I find this implementation basic. More specifically, I'm under the impression that a specific bit of the payload is in the same position after the encryption. But I don't know if an attacker can use that to gain information?

Also, an attacker can know pretty much everything by intercepting messages, so he can probably know the sequence A. Is there a way he can decrypt the payload or gain information about the key?

This is identical with CTR mode encryption with a MAC. That's known to be secure.

It doesn't say in your question if:

the Ai blocks are completely unique;
the header is included in the MIC calculation.

If those preconditions are met then I don't see any issue with the protocol.

The first one I cannot verify but seems likely, the second one is certainly true (when I look at the linked document).

Note that the MIC is somewhat short, only 32 bits. For this protocol it could be enough. On the other hand, the AES-128 based CMAC calculation is fine for a MIC.

Disclaimer: this should not be seen as a full review of the protocol, just a direct answer to the question.


Establishing encryption key using shared secret I need to establish some security on a network of 8 bit microcontrollers. very limited RAM, CPU and packet sizes.

I have zeroed in on a shared secret based scheme. Setting up shared secret is out of scope. Encryption is AES128.

To securely create and share an encryption key between two nodes, A and B, I cooked up this:

A creates an encryption key Ks = H(Ns, R0)
A sends R0 to  B
B calculates key K's = H(Ns, R0)

K's and Ks will be same if and only if B has Ns

Where H = Hash(R0|Ns|R0), or Hash(R0|Ns|H(Ns)) or maybe HMAC (still undecided)
R0 = random number
Ns = Shared network secret.

Ns is 16 byte. R0 is 4 byte. Both come directly from a RNG.

Primary Objectives are: Tamper proofing, Forward secrecy.

Not concerned about resistance to Side channel or replay attacks for now.

R0 (and hence Ks) will be updated periodically, perhaps every 100-10K independent packet transfers.

Is the scheme ok? Do the Ns or R0 need to be increased in size? Most importantly, will this scheme be able to keep Ns safe, and for how long?

===============
Edit:

Reg Forward secrecy:

I wanted to ensure that as long as network secret is safe, if a future session key (Ks) is compromised, past session keys and data should not also be compromised. Also, a renegotiation of session key should re-establish security.

That may not be exact definition of forward secrecy, but that's what I meant. I don't have sessions but I will expire keys periodically and after time or some count of packets is crossed etc, and call that a session.

===============

Reg H()

Based on answers, I have added AES(k=Ns, d=R0) to list of functions for H(). Will decide based on time/clock requirements.

===============

For now, based on the answers, I infer that all current options for H() will create good enough keys that will protect both encrypted data and Network Secret Ns.

If you are reading this text and feel that any of them might not be safe, please leave a comment or answer. Thanks.

You don't need a hash function for this.  Given that you're already using AES-128, and that your master key $N_s$ is 128 bits long, a perfectly good method for deriving the session keys $K_s$ would be to encrypt the random number $R_0$ (padded to a full AES block) using AES-128 (in ECB mode, i.e. using the raw block cipher) with $N_s$ as the key.

Even if the attacker can choose the random numbers $R_0$, and could obtain all the corresponding session keys, recovering $N_s$ would still require a practical chosen-plaintext key recovery attack on AES.  No such attack is currently known, and if one was found, AES would be considered totally broken.

However, it's also worth noting that this key derivation scheme (either as above, or as proposed in your question) does not provide forward secrecy; an attacker who has captured a past session, including $R_0$, can easily decrypt it if they later somehow learn $N_s$.

It is, however, possible to achieve something similar to forward secrecy using key renewal.  That is, instead of deriving temporary session keys from a fixed master key, you regularly derive a new master key from the old one, and then erase the old key.  This erasure will protect old messages from decryption even if the new key is compromised; it will not, however, protect future messages from compromise of an old key in any way.

One way to do this would be to compute the new master key $K_n$ from the old key $K_{n-1}$ as $$K_n = \text{AES}_{K_{n-1}}(A),$$ and the corresponding session key as $$S_n = \text{AES}_{K_n}(B),$$ where $A$ and $B$ are any two distinct constant cipher blocks (e.g. all zeros and all ones).  You would then use $S_n$ to encrypt your messages using an authenticated encryption mode.

Maintaining key synchronization between the two communicating sides can be a bit tricky.  One method would be to store the key renewal counter $n$ explicitly, and to transmit it in plain with each message.  Upon receiving a message tagged with a new counter value $n' > n$ (and $n' < n+2^b$ for some reasonable constant $b$, to prevent denial-of-service attacks), you'd compute $K_{n'}$ and $S_{n'}$ and try to use them to decrypt and authenticate the message; if the authentication succeeds, you increment your own counter to $n'$ and start using $K_{n'}$ and $S_{n'}$ as the new keys; otherwise, you assume the message was bogus and ignore it.

Note that it's enough to use a $b$-bit counter and let it wrap around.  For most applications, $b$ can be fairly small; say, $b = 8$, or even $b = 1$.  It's also possible to implement key synchronization without transmitting a counter at all, but this gets slightly more complicated.  (Basically, whenever you receive a message you can't authenticate with $S_n$, you need to retry authentication with $S_{n+1}$.)


Is secure communication without public-key crytography feasible? We all know about public-key cryptosystems, and we know some of these are computationally secure (for the time being, of course).

Are there any algorithms out there which allow safe communication between peers in a non “public/private” key fashion? If so, I would like to know some of these. If not, does any kind of formal demonstration of the infeasibility of such algorithms exist?

The obvious answer is symmetric keys.  You'll find that this is actually what asymmetric keys end up used for, exchanging symmetric keys.  If you trust someone who gives you a key, and you can trust that no one else has it, that's about as secure as it gets.  The difficult of satisfying those requirements is why we have asymmetric keys.


Collision attack on hash Let us define the hash function $h\colon \{0,1\}^{2n}\to\{0,1\}^n$ as
$$h(x||y)=E(x,y),$$
where $E$ is a block cipher and $x,y\in\{0,1\}^n$. Any ideas on how to easily find collisions on this hash?

It's straightforward to find a large set of preimages for any hash value!

For arbitrary $x,z \in \{0,1\}^n$, you can construct $Y(x,z)$ such that $h(x||Y(x,y))=z$. Let $D$ be the decryption function for the block cipher, i.e. $D(x,\cdot)$ is the inverse permutation from $E(x,\cdot)$. The goal $h(x||Y(x,z))=z$, i.e. $E(x,Y(x,z))=z$, is equivalent to $Y(x,z)=D(x,z)$.

Thus for any $x$, all of the inputs $x||D(x,z)$ for $z \in \{0,1\}^n$ are collisions for $h$.


I think I'm trying to find the C in an RSA cipher to find the key for an aes_128_ecb cipher, can anyone tell me if I'm on the right track? And if I am on the right track, how do I reach the solution from here?

I'm doing a CS game and I've hit a wall (I'm a rank beginner when it comes to encryption) on the encryption portion. I've been given the encrypted output and what I think (from my research) is an encoded version of the key using this:

For me, C is what I'm looking for, d = 7, N = 98286183916580532129117891164396375520832348985166654489180704043300879122347 and P = 89511674269883781051088511817946305647658886680759682801944853433540569894936.

p and q for N are 294156383975755063828794349953398256143 and 334129018681034197306379539716603659429

C was created randomly and is known to be 16 bytes. P is known because it was the first 32 bytes of the encrypted file (that I ripped out using a hex editor and turned into base 10) and d and N were both hardcoded.

I tried reversing it manually (using modular arithmetic, since a = b mod n then b = a mod n so C = root7(PmodN) ) but I got a 37 byte number that I know must be incorrect. Can someone please tell me where I'm going wrong?

I can post the source if it's necessary.

I think you should review how RSA encryption and decryption work.

You are given all the elements you need:

$P = C^d \mod N$

You know $d$, you know $p$, $q$, and thus $pq = N$. Usually people use $e$ to the encryption exponent and $d$ for the decryption exponent, but from what you said, $d$ is being used to encrypt.

You can recover $C$ with $P^u \mod N$, where $u$ solves:

$ud = 1 \mod (p-1)(q-1)$

Can you figure it out from there? (Hint: The Extended Euclidean algorithm will help.)


Why is 2048-bit RSA always paired with 320-bit ECC? You may already have noticed that most smart cards ship with 2048-bit RSA support and 320-bit ECC over GF(p) support. You may have already asked yourself "why exactly 320-bit?". Now I remember having read a while ago (I can't find the reference sorry), that you can use the 2048-bit RSA to somehow hack together 320-bit ECC.

Now my question is:
Is there actually any relation between maximal RSA and ECC key length and if so how can you get 320-bit ECC from 2048-bit RSA and why is it limited to 320-bits when the RSA engine can do 2048-bit?

Please note: I'm pretty sure they are not paired because of equivalent security, because they provide vastly different security.
320-bit ECC provides roughly 160-bit security and RSA-2048 provides roughly 112-bit security, so this can't be the reason.
I'm suspecting this to be related to the functional large (RSA) integer units of the smart cards which are somehow used to do 320-bit ECC, however the interesting part here would be "why not 512-bit or 1024-bit ECC?" and it should be some technical limitation because it's shared across many different smart card manufacturers.

As far as I know, there is no mathematical trick to put hardware doing a full modexp engine (with modulus register meaningfully sized for RSA) to good use for ECC; an hypothetical such engine is bound to get very much under-utilized with the typically much smaller modulus used for ECC.

However, in Smart Cards, hardware support for RSA does not use such engine; rather it is used a dedicated a co-processor with some moderately wide wordsize $w$ bits, matching multiplier, and a small RAM with wide databus. Arguments are split into $w$-bit chunks just as is done on regular CPUs. RSA and ECC are built on top of that using microcode for that coprocessor, and software in the main CPU. Up to some limit for $w$, processing time decreases as $2^{-2w}$. Public details are scant, but consistently $w$ is many times below the width of an RSA secret prime (typically 512-bit at the very least), and at least often below the width of the public modulus for the group on which the ECC curve is built (typically 160-bit at the very least).

So my guess on what limits the RSA and ECC key size supported by Smart Card RSA and ECC accelerators are:

The size of the RAM accessible by the coprocessor, which at least sometime is dedicated and uses a sizable portion of the silicon. That might sometime answer the question. The RAM size accessible by the coprocessor is closely tied to the upper bound for RSA; it also defines a different bound for ECC; and that later bound is much lower because point multiplication requires a much larger number of intermediate values the size of the base group.
What's achievable at decent speed given word width $w$ of the coprocessor. Going to the next number of chunks might be impractical even if there is enough RAM, as time is proportional to roughly the cube of the number of chunks (for ECC: to the square of the number of chunks times hash width, but since the number of chunks is lower, going to the next number of chunks creates an even wider gap).
Market demand: standard key sizes are few, which combines with 2 to make the upper size commercially supported rather arbitrary.

Note: I'm not confirming the numbers in 2048-bit RSA always paired with 320-bit ECC. In fact, most modern Smart Card ICs I see around support higher limits, substantially so for RSA.


Proving the existence of a pseudorandom function I've been reading the Introduction to Modern Cryptography book by Katz and Lindell as part of my own learning and have come across this exercise which I am not sure how to approach. The exercise is: (exercise 3.8)

Prove unconditionally the existence of an efficient pseudorandom function
$F:\{0,1\}^* \times \{0,1\}^* \mapsto \{0,1\}^*$ where the input-length is logarithmic
in the key-length (i.e., $F(k,x)$ is defined only when $|x| = log |k|$, in which
case $|F(k,x)| = |k|$).

There is also a hint which states that you should use the fact that any random function is also pseudorandom.

This is my initial train of thought:

We require the pseudorandom function to be indistinguishable from a function chosen uniformly at random from the set of functions that map $log|k|$ bit strings to $|k|$ bit strings (let's say this set is called $Func_{log\,|k|\, \mapsto |k|}$). I'm guessing that we need to work how many functions in this set in order to work out the probability of picking a random function, $f$, from this set.

I know that the set of functions $Func_{n \mapsto n}$ mapping $n$ bit strings to $n$ bit strings contains $2^{n*2^n}$ functions. However my first obstacle is calculating how many functions are in $Func_{log\,|k|\, \mapsto |k|}$ since the functions in this set are not bijective as they are in $Func_{n \mapsto n}$.

If I could calculate this value then I would approach the rest of the problem by calculating the amount of possible pseudorandom functions (clearly given by $|k|$ since $k$ is chosen uniformly at random). I was then hoping, if there was a similar number of functions in $Func_{log\,|k|\, \mapsto |k|}$ (although I speculate there is way more than $|k|$ functions in this set), then eventually try to show that it would be hard for any ppt distinguisher to tell between the pseudorandom function and the randomly chosen one.

I have no idea if this is along the right line and I also don't really know how to bring the hint in to play. All I can think is that it may turn out to be easier to prove that $F$ is indistinguishable from another pseudorandom function which also happens to have been chosen at random.

If anyone could provide a hint as to how to calculate the amount of functions in $Func_{log\,|k|\, \mapsto |k|}$ or pointers for how to approach this then that would be great. As I said, I am doing the exercises for my own good so I'm not massively keen on being given a full solution straight away.

Though this is an 4-year old topic, it seems the following should work:

We can construct a function $F_k(x)$ with output length $l_{out}(n)=l_{key}(n)/2^{l_{in}(n)}=n/2^{O(\log n)}$.

Didivde the key $k$ into $2^{O(\log n)}$ blocks with equal length, denoted by $k_i$ with $i=1,2,\dots, 2^{O(\log n)}$. Because $k$ is uniformly distributed in $\{0,1\}^n$, so is $k_i$.

$F_k(x)= k_x$ is the pseudorandom function.


Bitcoin mining nonce and birthday attack Having read the basics of mining and this about SHA256 (probabilistic?) partial preimage possible? and SAT solving - An alternative to brute force bitcoin mining, I have the following question:

Wouldn't it be better to select a random nonce instead of incrementing the first by one? This way, the miner would make use of the birthday attack, which would make the probabilities of finding it higher (for a given number of trials).

I'm not sure that my understanding is correct.

Wouldn't it be better to select a random nonce instead of incrementing the first by one?

This is often thought of by people who read (or understand) only a garbled version of the original Satoshi paper/design. I'm surprised it seems not to be a dupe here, although it is crossdupe in bitcoin.SX where it is more ontopic:
https://bitcoin.stackexchange.com/questions/80752/why-is-the-nonce-bruteforced-from-0-to-n-while-mining
https://bitcoin.stackexchange.com/questions/78214/how-are-nonces-decided-in-mining
and nearly https://bitcoin.stackexchange.com/questions/41949/what-is-the-precise-nonce-finding-protocol

Put more technically, if miners are racing to find a nonce which makes a particular block header hash to below the target, doesn't it duplicate work to have them all try the same sequence and/or wouldn't at least some do better using different starting points (or sequences)? On that premise, yes it would be better, but that premise is wrong in several ways.

First, even in the original design, independent miners (the only kind Satoshi imagined) don't try to find a nonce for the same block. Miners are incented by receiving a reward for 'solving' a block, and that reward is encoded as a 'coinbase' transaction, which is the first transaction in the block, and thus contributes to the Merkle hash tree root in the block header. Different miners thus use different block headers and even if they all search the same nonce space from 0 to 232-1 they are searching different hash inputs.

Second, since mining became competitive, and especially since it moved to GPUs and then ASICs, mining doesn't really consist of "find a (or the) nonce for a block making it satisfy the difficulty/target". At difficulty significantly more than 1 (and it's currently in the trillions), most possible and attempted blocks are not satisfied by any nonce value. Instead mining consists of "find a block, and particularly an extranonce in coinbase, for which any nonce satisifies the current difficulty/target, and use that nonce". Over 99.999999% of atttempted blocks are losers, and to determine a block is a loser the miner must try all 232 nonces, which takes the same work regardless of the sequence tried.

For pool mining, which has now become popular, there are multiple miners seeking the same reward (i.e. one paid to the pool), and in that case the pool manager does allocate different extranonce ranges to members to avoid duplication and increase the probability that the pool as a whole (though not any specific miner) wins.  Since members must communicate with the manager anyway in order to earn rewards for partial solutions, there is no need or benefit of distributed random choice over centralized deterministic choice.

  This way, the miner would make use of the birthday attack, which would make the probabilities of finding it higher (for a given number of trials).

Bitcoin mining is not a birthday problem at all. Starting at different points or using different sequences of trials is not a birthday attack, and does not on average improve a birthday attack. It can improve competitive performance in some cases, but as described above none of those cases apply to Bitcoin mining.


worst-case OWF from weak OWF A function $f$ is a worst-case OWF if there is no adversary $\mathcal{A}$ such that $$\forall x,Pr[y=f(x): f(\mathcal{A}(y))=y]=1$$

A weak OWF is a function that the probability of inverting it is bounded by some $1-\frac{1}{q(n)}$ for some polynomial function $q(n)$. The question is suppose $f$ is a weak OWF, can we define a function $g$ that is a worst-case OWF but not a weak OWF?

My idea is to make $g$ easy to invert for (exponentially) most inputs. This make $g$ "weaker than" any weak OWF. For example, consider $$g(x) = \left\{\begin{array}{ll}0 & x < 2^{|x|}-1 \\ f(x) & \text{otherwise} \end{array}\right.$$

Clearly $g$ is weaker than any weak OWF. But how can I show that no adversary can always invert $g$ then?

In order to answer this question, you first really need to define what a worst-case OWF is. In particular, is it possible to efficiently sample a hard instance? I assume not, because this would be very hard to formalize and I'm not sure it makes sense. If not, then there is an easy answer:

If there exists a weak OWF then $P \neq NP$
If $P \neq NP$ then let $L\in NP\setminus P$ and let $R_L$ be its associated polynomial-time verifiable relation (i.e., $(x,y)\in R_L$ if and only if $x\in L$).
By the definition of a "worst-case" OWF, take a machine that samples $(x,y)\in R_L$ and outputs $x$.
The function would be defined to be $f(y)=x$.


2DES Meet in the middle attack complexity In the meet-in-the-middle attack, if we built the tables first and then looked for matches, we would have another high complexity problem. For each of the table 1 entries, compare with all the table 2 entries; this algorithm has complexity of O(2^2k). How the matching could be done while building the tables, resulting in the total complexity remaining at O(2k+1)?

Let $(K,K')$ be the key and let $C=E_{K'}(E_K(P))$.

Generate $$L=[(E_K(P),K):K \in \{0,1\}^k]$$ sorted in a hash table on first coordinate with time complexity $O(2^k).$ You can take a hash table of size a few times $2^k$ to avoid long chains by avoiding too many collisions in the table. Or sort the list at cost $O(k2^k)=\tilde{O}(2^k).$

Now try all $K'\in \{0,1\}^k$ and compute $D_{K'}(C)$ and lookup in the table at constant time, until you get a match. Check a few other plaintext ciphertext pairs to ensure the match is not spurious since the permutation $$u\rightarrow E_{K'}(E_K(u))$$ will typically have some fixed points, which may include $u=P.$ This gives overall time complexity $O(2^k)$ if you choose hash sorting.


How are state wiretaps obtaining plaintext from encrypted transmissions? According to the US 2011 Wiretap Report, encryption — on the off chance that it is encountered — has been no hurdle to retrieving the content of a conversation.

  Public Law 106-197 amended 18 U.S.C. § 2519(2)(b) in 2001 to require
  that reporting should reflect the number of wiretap applications
  granted in which encryption was encountered and whether such
  encryption prevented law enforcement officials from obtaining the
  plain text of the communications intercepted pursuant to the court
  orders. In 2011, encryption was reported during 12 state wiretaps, but
  did not prevent officials from obtaining the plain text of the
  communications.

— US 2011 Wiretap Report, page 8–9 (emphasis added)

Why was this encryption not successful?

Unfortunately the report includes very little detail about what kind of transmission and encryption was involved in any of the 12 cases.

Many reasons, including:

federal law requiring companies (e.g. telephone) to surrender encryption keys
interception before encryption (it's pretty easy to eavesdrop on keyboard input purely via electromagnetic radiation even several meters away)
MITM on an insecure channel (quite effective)
outright broken encryption algorithms
social engineering to recover key
Van Eck phreaking
weak keys
if all else fails, save the ciphertext for until you can subpoena the suspect and retrieve the key (but I guess this doesn't count)

etc... when you are being heavily monitored, purely cryptographic measures become too intangible and no longer suffice. You need to employ physical means to remain in a secure position.


SHA-256 for unique token I need to create an unique token for a web service. I'm doing that in the following in the following way:

var element_id  // auto increment number, every time different
var secret_key  // an secret key
var random_key  // a random generated string of 8 chars, every time different
var timestamp   // the timestamp at the moment of generation

var token = element_id + secret_key + random_key + timestamp;

This will produce a string consisting of 15 to 20 characters. In my system every string generated in this way is unique.

Then I create the SHA-256 version of that string

var sha256_token=sha256(token);

Will the sha256_token be unique in my system as it was the "clear" token?

Yes, the hash will be unique every time - if the input string is unique every time.

This follows trivially from SHA-256's collision resistance: If your input strings are different but the outputs are the same it's a collision in SHA-256 which would be a huge surprise to find for everyone and a publication-worthy result.

Now the more interesting question is whether your input string will be unique every time. If everything is fixed length - except perhaps the counter - then yes, it will be unique. If the secret key is variable length there may be "unlucky" situations where the last byte of the counter matches the first byte of the secret key and the allocations which belongs where are different (i.e. whether the byte belongs to the counter or the secret key). The "safest" choice here would be to pad everything (except one of the values) to a fixed upper bound length.


Are LRC (Longitudinal Redundancy Check) or CRC (Cyclic Redundancy Check) of any use in modern day computing? I am currently learning about the history of Data integrity / Error detection.

In the old days of tape drives, LRC was used for error detection. They were also used (at certain point in time) for ensuring data integrity. But nowadays, the work that CRC or LRC did, has been mostly replaced by Hashes (MD5, SHA1 etc).

My questions are:

What were some of the reasons, why CRC or LRC was replaced by Message Digests?
Are these methods (LRC & CRC) still applicable/safe in modern day computing?

P.S.: I am asking this question from a cryptographic/Computer Security standpoint.

I still see some uses of CRC in the case of encrypted protocols.
The secure parts are embedding hashes and/or MACs in a data field, then it checks the integrity of the whole message a second time with an extremely lighter algorithm (CRC).

This way in embedded cryptography with high speed, you avoid yourself cryptographical computation if the transmission failed and the CRC/LRC is wrong.

Anyway, if you don't look at performances and don't work with microcontrollers, you're right it should desappear behind modern hash and MACs.


What does this notation stand for when describing a code? This code has appeared in some online course material.

I understand the $(5, 4, 3)$ refers to (length, num codewords, distance) but no explanation of the $Z_2^5$ notation is given:

  One $(5,4,3)$ code in $Z_2^5$ is given as below:

  $C_3 = \pmatrix{0, 0,  0,  0,  0\\0,1,1,0,1\\1,0,1,1,0\\1,1,0,1,1}$

$Z_2^5$ means that you are working in $GF(2)^5$.

$GF(2)$ is the Finite Field with two elements: 0 and 1 with the addition and multiplications defined:

$0 + 0 = 0\\
0 + 1 = 1\\
1 + 0 = 1\\
1 + 1 = 0$
It is equivalent to XOR.

$0 \times 0 = 0\\
0 \times 1 = 0\\
1 \times 0 = 0\\
1 \times 1 = 1$
It is equivalent to AND.

the $ ^5$ is the dimension of the space (or the size of the vectors). Here you are using a space of dimension 5, hence 5 coordinates.

$(0,1) \in Z_2^2\\
(0,1,0) \in Z_2^3\\
(0,1,0,1,1) \in Z_2^5$

The exponent notation represent the Cartesian product of the spaces:

$Z_2 \times Z_2 = Z_2^2\\
Z_2 \times Z_2 \times Z_2 \times Z_2 \times Z_2 = Z_2^5$


simple algorithm to encrypt/decrypt a text file I need to write a first program in one language that saves data in a text file, and write a second program in a second language to decrypt that file. The two languages in question don't include any crypto libraries, so I'm on my own.

Could someone recommend, point me to, or summarize a simple algorithm (pseudo code) that provides some level of basic encryption?

I don't have much experience in this area, but if you can summarize clearly in pseudo-code, I can implement it (don't assume prior knowledge).

It doesn't have to be bullet-proof, but just something that deters the user from understanding the text file. Something more secure than just a simple character-substitution (1 for 1), like perhaps a key that generates a random string used to XOR or similar complexity. I have no idea where to start.

My advice would be to use a stream cipher.

First of all, it is easy to implement, because you won't have to think about dividing into blocks, padding, etc..

Secondly, the idea of stream ciphers is very easy: you generate a  pseudorandom sequence of bits out of the private key. Then you XOR this sequence with a plaintext. You will only have to code the generation, the rest is elementary.

Finally, there are very easy stream ciphers, e.g.  RC4 http://en.wikipedia.org/wiki/RC4;  another example is Salsa20 http://en.wikipedia.org/wiki/Salsa20

And when I say "simple" I mean not only the amount of lines of code, but also the ease of debugging/ flaws search.


What is the use of key iterations? I read about PBKDF2 on Wikipedia and seen few apps. having option to manually enter number of iterations. I am still not clear on this.

(1) With what I understood, key iterations can be used only with symmetric encryption. If a file/text is encrypted using passphrase, HASH is calculated and encrypted with AES for 'n' number of times. If iterations selected is 100 then this is done 100 times. This is done to defend against brute-force attack.

(2) Key iterations have no use with public-key encryption.

(3) Some apps. by default take 100 iterations. Few apps by default takes 2000 iterations when using AES. How many iterations are considered secure with AES-128 and AES-256?

With what I understood, key iterations can be used only with symmetric encryption. If a file/text is encrypted using passphrase, HASH is calculated and encrypted with AES for 'n' number of times. If iterations selected is 100 then this is done 100 times. This is done to defend against brute-force attack.

First things first: PBKDF2 (and comparable schemes) are called password hashing schemes (PHSs) (or more popularly password-based key derivation functions). All they do is take a password, preferably some randomness (aka a salt) and return a uniformly random-looking bitstring which can only be derived using the previously mentioned inputs and is suitable as a symmetric key. The special thing about PHSs compared to normal key derivation functions (KDFs) is that they also take one or more cost parameters. Usually at least one of them allows you to linearly scale execution time which is the case with the iteration count in PBKDF2.
Now the usual flow for using PHS is the following:

Gather password and salt
Run both through the PHS with some specified iteration count - AES is usually not involved in this step
Use the derived key to key some symmetric operation
Use the keyed symmetric operation for whatever it is that you need to do, e.g. encrypt / decrypt data

Indeed the key idea of the above is the observation that if you invest effort $E$ into deriving your password an attacker not knowing your password will have to invest $2^{H(P)}\cdot E$ effort where $H(P)$ is the (min-)entropy of your password. This then allows you to derive your password in say 1 second and an adversary to spend a lot of ressources to brute-force it - even if it is only moderately complex.

(2) Key iterations have no use with public-key encryption.

Well, you could feed the output of your PHS into a private key generator allowing you to immediately recover it from the password. In fact this is what BIP-39 does. Alternatively you could use a PHS to generate a symmetric key to encrypt / decrypt you private keys - which is what GPG does.

(3) Some apps. by default take 100 iterations. Few apps by default takes 2000 iterations when using AES. How many iterations are considered secure with AES-128 and AES-256?

The usual advice is "use as many as you can afford" where "afford" is a time(-memory) budget that you specify and then measure out the relevant parameter set. However if you prefer cold, hard standards, NIST SP800-63B is the relevant one and recommends at least 10,000.


Usage of different size chunks during AES encryption/decryption I want to encrypt user's files on our server. For this purpose I decided to use the PHP Mcrypt library. I chose to use the Rijandel-128 algorithm and CBC mode for encryption. Since files are quite large, I decided to encrypt/decrypt files by chunks.

Everything works well when I use one chunk size for encryption and decryption processes. But when I encrypt a file with 8 KB chunk size and try to decrypt it with 4 KB chunk size, file is corrupted.

My question is – is it possible to encrypt and decrypt a file with different chunk sizes? If yes, what are the pitfalls of this process? Right now, I don't understand if there are any bugs in my code or there are some encryption restrictions I'm not aware of.

To see the problem, let's see how I would chain up a single function (call it $AES\,CBC_k(iv, m)$) which only encrypts a single block at a time into something that can encrypt "chunks" of any size.

Let $m=m_1||m_2||m_3||m_4$ be the message I want to encrypt. Each $m_i$ is a single block (in AES it is 128 bits). I want to use $AES\,CBC_k$ to encrypt $m$. The proper way to do this would be to compute:

$$c_1=AES\,CBC_k(iv, m_1)$$
$$c_2=AES\,CBC_k(c_1, m_2)$$
$$c_3=AES\,CBC_k(c_2, m_3)$$
$$c_4=AES\,CBC_k(c_3, m_4)$$

Then let $c=c_1||c_2||c_3||c_4$ be the ciphertext. Using this process (note how the iv changes from block to block), we could build another function, say $E_k$ which encrypts messages of any length (actually a multiple of the block size).

To illustrate your problem, let's split $m$ into two chunks: $m_1||m_2$ and $m_3||m_4$ and see what it sounds like you are doing. It sounds like you are calling $E_k(iv, m_1||m_2)$ then $E_k(iv, m_3||m_4)$. This is like doing the following.

$$c_1=AES\,CBC_k(iv, m_1)$$
$$c_2=AES\,CBC_k(c_1, m_2)$$
$$c_3=AES\,CBC_k(iv, m_3)$$
$$c_4=AES\,CBC_k(c_3, m_4)$$

Notice the iv for $c_3$ and compare it with the iv for $c_3$ in the correct operation above.

So, if you really want to encrypt the way you are talking about doing, you would need to use the last block of the previous chunk as the iv for the next chunk. Managing this yourself in code, while do able, is somewhat of a pain. I'm willing to bet there is an encryption library for PHP that can so this for you (on file streams or something so the whole file doesn't have to be in memory).

The real question
So it sounds like your real question is how to encrypt large files in php without having to read the whole thing in to memory. I don't use PHP much, so I can't really comment. I will say don't use the solution here as it was obviously not designed by anyone who knows anything about cryptography. I know in other languages (Java, c#) you can pass in a file stream to be encrypted in most libraries, which probably solves the problem of having to read in all the memory. Not sure if PHP has something like that though.

Update
It looks like php has encryption filters that you could use with stream_filter_append to encrypt streams so that the file doesn't have to be loaded into memory. Then you would have a stream to read from and a stream to write to. Simply read from the input stream and write to the output stream. The encryption happens automatically thanks to the filter.


"Security" of SHA functions (Wikipedia), what does it mean? Wikepedia's table Comparison of SHA functions mentions "Security(bits)" for some SHA functions. From the ratio (Output size (bits): Security(bits)), I feel it is something like "collision resistance". So,

Should we only consider collision resistance as the Security of a hash function?

what does the Security in the table mean?

Security in the table refers to collision resistance. By the birthday problem, there's a generic attack that finds collisions in any compressing function by choosing $\sqrt{2^m}$ random inputs ($m/2$ security bits), where $m$ is the output length.

Depending on the application, weaker requirements might be sufficient, such as second pre-image resistance or even one-wayness. A generic attack against the two weaker notions requires about $2^m$ work ($m$ security bits).


Why is AES-128 considered secure while RSA needs a 1024-bit size to be considered secure I got asked this question today and I didn't know the answer,
AES-128 is considered secure, the key size is 2^128, so you would need in average 2^127 tries to break the key.
Why does RSA need at least a 1024-bit modulus to be considered secure, If we consider a bruteforce attack on the private exponent, it would take 2^1019 tries (lets consider the private exponent is 1020-bit in length). Is the difference because of a much less complex attack that exists on RSA but doesn't exist in AES?

It's because with the key to determining the secret private key in RSA is to factor the public modulus into its two prime factors p and q and need a very large number (2^1024, 2^2048) to make this is computationally difficult.


Is using a smart card and password two-factor authentication? I use a smart card - as read only device - for user identity as well as a password:

The smart card (holds the user ID) is something I have;
The password is something I know.

Is this still two-factor authentication?

Is this still a two-factor authentication?

Yes, it can be but it depends on how the smartcard is used.

For example your OS could just use the password for authentication and ignore the fact that a smartcard is present in which case there would be no 2FA.

Or your smart card / OS could be configured to use a key on the card that doesn't actually require a correct user input to allow operation (though I'm not sure how many cards support that) and in this case it is imaginable that only the card matters for authentication which is also no 2FA.

However it is most likely that the OS will e.g. decrypt a per-user secret using a private key stored on the card or perform public-key based authentication against a remote server and your card will allow usage of the relevant key if you authenticate first to the card, which indeed is a form of two-factor authentication, as you need the card which holds the key and you need the password to operate the card.


Is there an existing AEAD scheme with minimal IV requirements? Is there an existing AEAD scheme such that, for inputs with the same AD and IV

ciphertexts are allowed to leak whether or not their plaintexts are equal,
if the scheme can process the plaintext in a streaming manner, then it is allowed to leak where different plaintexts have their first difference, and
is otherwise secure against an adversary that can choose the IVs used for encryption?

Sounds like you might be after deterministic authenticated encryption. Check out SIV mode. This mode doesn't use an IV at all (though it does generate one internally, outside of the attacker's control). Being deterministic, it leaks equality of (header, plaintext) pairs.

The basic idea is to put the (header, plaintext) pair through a PRF, such as HMAC, and use the result as an IV for, e.g., CTR mode. After decryption, you check authenticity by checking to see if you can reproduce the IV's value.

If you want to be able to stream plaintexts, look into "Online ciphers from Tweakable Blockciphers". As you anticipate, these schemes leak shared prefixes but are otherwise secure. But note that this latter paper does not consider authentication, and generic techniques that assume standard IND-CPA security may not work. See "On-Line Ciphers and the Hash-CBC Constructions" for how to get AE in this context.


Are common (secure) stream ciphers CCA1-secure? My latest question and especially Ricky Demer's comment on the answer got me thinking: This homomorphic tranformation of RSA is most likely IND-CPA and maybe even IND-CCA1, but if it could be IND-CCA1, so could be a stream cipher in theory. This is especially interesting if you consider RSA-KEM paired with an unauthenticated stream cipher. Practically this would most likely also imply a simple standard construction for an XOR-homomorphic IND-CCA1 cryptosystem. This would also imply a post-quantum secure IND-CCA1 scheme with a partial homomorphism: McEliece as a KEM paired with a stream cipher (which is basically McBits minus the authentication).

So the question naturally follows:
Are common (unbroken) stream ciphers CCA1-secure?
Or formulated differently if CCA1-security isn't a thing: Are stream ciphers secure against non-adaptive chosen ciphertext attacks?

With "common" stream ciphers I mainly mean secure block ciphers in CTR mode and cipher such as ChaCha20 and Salsa20/20.

For stream ciphers, IND-CCA1 and IND-CPA security differ precisely in that an attacker can choose the IV in the CCA1 game (because that's part of the ciphertext that can be submitted to the decryption oracle); but in the CPA game is constrained to whatever choice of IV the cryptosystem makes.

We can artificially construct a stream cipher vulnerable under CCA1, but not under CPA: consider AES-128 in CTR mode with random IV, except that the AES encryption block is modified so that for all-zero input block, the output block is the key. Decryption no longer works for the block cipher, but it still works for the stream cipher (albeit differently when the counter is initialized to all-zero, or reaches that). Under the CCA1 game, an adversary recovers the key by submitting to the decryption oracle a ciphertext with all-zero IV and first block of ciphertext; while there's no way to take advantage of the modified block cipher under the CPA game, and the stream cipher remains secure (the adversary has negligible odds to get the IV to reach zero, thus the stream cipher is indistinguishable from true CTR mode, which is IND-CCA1).

For a less artificial example, we can hypothesize a block cipher vulnerable to key recovery under CPA, but not under random Known Plaintext Attack. That weakness directly makes the derived CTR or OFB stream cipher vulnerable under CCA1, but not under CPA.

Thus if there was a block cipher vulnerable to key recovery under CPA but not random KPA, with the corresponding CTR or OFB stream cipher common, that would be a common stream cipher not IND-CCA1, answering the question in the negative.

However I know no common stream cipher that's vulnerable under CCA1. Much to the contrary, modern native stream ciphers like ChaCha20 and Salsa20/20 aspire and appear to be IND-CCA1. And modern block ciphers are believed secure under CPA, and their corresponding CTR stream cipher is accordingly believed IND-CCA1 (just as claimed in that other answer, even if I fail to follow it's proof sketch).


Authorities on password hashing best practice I am trying to understand how best practices on password hashing come about. With password hashing, I mean specifically for the case of storing user passwords in a database in a hashed representation, in order to compromise user passwords if an adversary gets access to the database. I understand that recommendations (especially algorithm, number of rounds, etc.) continue to change.

My question is, who would be authoritative sources on what is currently best practice, and where and how can I keep up to date?

Right now my process is that I notice someone saying something about best practice in a StackOverflow answer that does not fit my understanding, and then I start digging for more information. This seems backwards, and I'd like to get ahead on this thing.

The best place to start is the password hashing competition. It was run by and had many entries by competent researchers. You don't make a mistake going with their recommendation.

If you are interested in ongoing discussion I suggest their mailing list.


In a hybrid cryptosystem is safe to send the encrypted key together with the encrypted message? I am encrypting a message using an hybrid cryptosystem:
I encrypt my message using AES-256 and I encrypt the symmetric cipher key using RSA.
The following questions come to my mind:

I want to know if it safe to send the encrypted message with the encrypted key together ?
What does it imply for an attacker to get the RSA encrypted key with the encrypted message ?
What is the correct way to send the message and the encrypted key ?

Yes it is safe.
Assuming you get everything else right(Proper encryption mode), proper padding, secure random key, proper key management and avoid problematic other usages of same key, etc...
You have to provide the encrypted key to the legitimate user, if you have two different transfer systems with independent weaknesses you could transfer separately but that is probably rare and RSA applied properly (e.g OAEP) is sufficient so the encrypted key will reveal nothing about the key to that without the RSA private key.


Frequency analysis of transposition ciphers Can we do frequency analysis of transposition ciphers?

If yes, please tell me the procedure and I would be happy if you provide me with some links related to it.

I heard that it can be done using bi-gram frequency.

I did it for substitution ciphers but am unable to do it for transposition ciphers.

I did it for substitution ciphers but am unable to do it for transposition ciphers.

When it comes to transposition ciphers, it’s not really surprising frequency analysis doesn’t turn out to be as useful as it is when looking at substitution ciphers.

See, one important strength of transposition ciphers is that they are not susceptible to frequency analysis, since transposition ciphers do not change the symbols for each letter.

Instead of replacing characters with other characters, transposition ciphers just change the order of the characters. Typically, the text to be encrypted is arranged in a number of columns. These columns are then reordered, resulting in encrypted text. This means that, to decrypt/break a ciphertext created using a transposition cipher, you need to find the number of columns (which is usually based on a common factor of the total number of characters in the text) and then rearrange the columns accordingly.

Now, don’t get me wrong – frequency distribution is interesting to look at during a transposition cipher analysis, but for other reasons… frequency analysis on a transposition cipher shows that the constituent letters are what would be expected in a standard text (example: “e” is the most common English letter).

As you’re obviously just starting out to learn how to analyze and potentially decrypt/break transposition ciphers, you could check stuff like the “Analysis of columnar transposition ciphers” section of "Introduction to Cryptology and Cryptosystems" by Prof. H. Williams, which provides a first, rather simple insight.

UPDATE: Since the original PDF of Prof. Williams went offline, here’s an excerpt containing the 3 related pages. Please note that the excerpt I am making available here is provided for reference purposes only and does not represent a complete copy of "Introduction to Cryptology and Cryptosystems".

Also (in contrast to Wikipedia’s related article), there are ample pages online which provide nice examples of the cryptanalysis and deciphering… randomly picking one of them: “Transposition Cipher : nrich.maths.org”.


Side-channel resistant discrete uniform sampling on $d\neq 2^t$ values? Assume you have some source of $\mathsf{Bern}(1/2)$'s (probably some CSPRNG in practice). What is generally done to sample from $\mathsf{Unif}([d])$ in a side-channel resistant way (assuming $d$ isn't a power of 2)?

For the power of 2 case, it seems clear that you can generate $t = \log_2(d)$ random bits and interpret them as an integer. While I'm sure the implementation must be more careful than this, this seems algorithmicly rather straighforward.

For the non-power of 2 case, you could simply set $t = \lceil \log_2(d)\rceil$, then rejection-sample from $\mathsf{Unif}([2^t])$. This seems like it should be side-channel resistant as well (when you reject you leak information, but you also throw away the randomness the adversary knows information about).
The downside of this is that (in expectation) it requires (up to) twice as many random bits used, if $d = 2^t + 1$ for some $t$.
This will still be $O(\log_2(d))$ random bits, so asymptotically it's optimal, but it definitely feels like it could be improved.

So my question is essentially if anything better is known/used (either in the literature, or in practice).

Off the top of my head, here's a somewhat more efficient rejection sampling algorithm.  It involves maintaining a (possibly non-secret) bit counter $k$ and a secret $k$-bit value $0 ≤ s < 2^k$.

Initially, let $k = 0$ and $s = 0$.
To sample a uniform integer $x$ from $\{0, \dots, d-1\}$ for a given upper bound $d$:

Let $t = \lceil \log_2 d \rceil$ and $g = 2^t - d$.
If $t > k$, generate a uniformly distributed random $t - k$ bit number $z$ and let $r = s + 2^kz$; else let $r = s \bmod 2^t$.  (That is, we take $r$ to be the lowest $t$ bits of $s$, adding extra random bits at the top if needed.)  Now $r$ is uniformly distributed on $\{0, \dots, 2^t-1\}$.
If $r ≥ g$, update $k \leftarrow \max(0, k - t)$ and $s \leftarrow \lfloor s \mathbin/ 2^t \rfloor$ and return $x = r - g$.
Else let $h = \lfloor \log_2 g \rfloor$.  If $r ≥ 2^h$, subtract $2^h$ from both $r$ and $g$ and repeat this step.  (In other words, while $g$ and $r$ have the same highest set bit, clear that bit and repeat.  This process will eventually stop, since we know that $0 \le r < g$; it's not hard to show that clearing the highest bit preserved this invariant, and that $r$ is always uniformly distributed on $\{0, \dots, g-1\}$.)
(Now $r$ is uniformly distributed on $\{0, \dots, 2^h-1\}$.) Update $k \leftarrow h + \max(0, k-t)$ and $s \leftarrow r + 2^h \lfloor s \mathbin/ 2^t \rfloor$ and repeat from step 1.

Note that I'm assuming that we can do comparisons and basic arithmetic (i.e. addition, subtraction and bit shifts) on secret values without leaking any information about them (other than the result of the comparison).

Basically, the idea is to split the interval $\{0, \dots, g\}$ of rejected values into a sum of intervals of power-of-two sizes (which can be conveniently obtained from the binary expansion of $g$), find out into which of these intervals the rejected sample belongs to, and add that many bits of randomness from the rejected sample back into the entropy pool $s$.

(In particular, note that the number of bits in the entropy pool $s$ is always strictly less than the length of the longest requested value.  In particular, if $d$ is constrained to be at most $2^n$, then an $n$-bit integer variable can be safely used to store $s$.)


Point halving on elliptic curves of even order I am trying to understand how point halving on elliptic curves of even order works. Specifically: suppose $g$ is an elliptic curve, and $G$ is a generator point on this curve. The order of group generated by $G$ is even and equal to $q$. Suppose also that $A = x \cdot G$. I know $A$ but I don't know $x$.

My questions are:

What algorithm(s) could I use to calculate $A' = \frac{A}{2}$ such that $2 \cdot A' = A$?
When $x$ is odd, is the division undefined? Would the halving algorithm detect odd points?
When $x$ is even, my understanding is that there are two solutions $A' =\frac{x}{2} \cdot G =\frac{x + q}{2} \cdot G$. Is there an algorithm that would consistently differentiate between the first and second solutions?

Supposed $Q = (q_x,q_y)$ is a point on elliptic curve $E$ defined by $y^{2} = x^{3} + ax^{2} + bx + c$. To  find the half point $P$ of  $Q$, we need to do the following:

Write down the equation for the derivative of $E$ at $P$. letting $\lambda$ be the derivative, we have
$\lambda = \dfrac{3x^{2} + 2ax +  b}
    {2(x^{3}  + ax^{2} + bx + c)^{1/2}} \tag{1} \label{1}$
Write down the equation for  the tangent line to $E$ at $P$:
$y-p_y = \lambda(x-p_1) => y = \lambda(x - p_x) + p_y \tag{2}$.
Write the equation for the intersection of the tangent line with E:
$y^{2} = (\lambda(x - p_x) + p_y)^{2} = x^{3} + ax^{2} + bx +
    c \tag{3}$.
Write down $\lambda$ in terms of $p_x$:
The equation from (3) comes out
to a monic cubic polynomial. Since it is monic,
    the sum of the roots add up to minus the coefficient of $x^{2}$. The
    roots are the intersection points. Hence $p_x$ will be a double root, and $q_x$ will be the third root. If you simplify this equation, you will see that the coefficient of the $x^{2}$ term is $a - \lambda^{2}$. Therefore $2p_x + q_x = \lambda^{2} - a $ and so $\lambda^{2} = 2p_x + q_x + a  \tag{4} \label{4}$
Set equation from (4) and equation from (1) equal to  eachother.
Combining equation $\eqref{4}$ with the equation for $\eqref{1}$ and replacing $x$ with $p_x$, we get
$\lambda^{2} = 2p_x + q_x + a
    =  \dfrac{(3p_x^{2} + 2ap_x +  b)^{2}}{2(p_x^{3}  + ap_x^{2} + bp_x + c)} \tag{5} \label{5}$.
Simplifying this equation and moving everything over to
    the left hand side will yield a quartic polynomial in $p_x$. The roots of this polynomial are the x-coordinates of the half points of Q..

The relationship  between  the half points of $Q$ is the  same as  the relationship between  the roots of $\eqref{5}$. It will change depending on the nature of $E$. Here are a few things we can say for certain.

Since neither $q_y$ nor $p_y$ make an appearance in this quartic polynomial, each quartic polynomial will actually give the  halves for two separate points. The quartic from $\eqref{5}$ gives us the half points of $Q = (q_x,q_y)$ as  well as the half points of $-Q=(q_x,-q_y)$.
To find out if a half point exists for a point $Q$, there is a value you can calculate based on $a,b,c$ of $E$ and $q_x$. This procedure can be found on page 5 of Quartic Equations and 2-division on Elliptic Curves (Most of the results from this answer are directly from this paper).
If the points on E make up an odd ordered group, then each point $Q$
only has one point $P$, and hence the quartic equation will only
have one root. This follows from the fact that
elements in odd groups have unique square roots.In this case, the factors of the quartic polynomial will be a linear equation and an irreducible resolvent cubic.
Equation (5) is equal to $(x-s)^{2}(x-t)^{2} <=> Q$ is a 2-torsion point. In this
case, $Q$ will have two distinct halves, one where $x=s$ and another
where $x=t$. $-Q$ will also have halves with these x-coordinates.
Equation (5) is equal to $(x-s)^{4} <=> Q$ is a singularity.


DSA: How to calculate 224-bit $q$ for 2048-bit $p$ $p$ is a 2048 bit prime number

$q$ is a 224 bit prime number

I know that $q$ is a prime divisor of $p-1$, thus $p=1 \bmod q$ but I couldn't write efficient code to calculate this.

I can calculate 2048 bit prime $p$, but how to find $q$ efficiently?

Currently what I am doing is generating 224-bit primes and checking whether they are dividing $p-1$ or not but it takes forever...

I can calculate 2048 bit prime $p$, but how to find $q$ efficiently?

You're doing things in the wrong order.

Instead, you pick a 224 bit $q$, and then such for a 2048 bit prime of the form $p = kq + 1$ (for some integer $k$).

This can be done with essentially the same amount of effort as finding a 2048 bit prime (without constraints), and directly answers the problem, as such a $p, q$ pair guarantees that $p \equiv kq + 1 \equiv 1 \pmod q$


Shamir's Secret Sharing on non-prime GF I am implementing Shamir's secret sharing scheme on arbitrary binary files.  I don't intend to use this; this is a project to help me explore cryptography.  In setting up the finite field arithmetic, I chose my field to be GF(257).

My understanding is that a prime GF is needed to ensure that a single modular inverse exists for each value in the field (this conflicts with the answer to How can Shamir's method for secret sharing work in the GF(256)?).

Can someone explain this discrepancy?

You appear to be confused by the sentence in the answer:

  If you use simple modular reduction they won't work (e.g. you can't just compute the operations mod 256).

This sentence is true, but doesn't mean what you think it does.

It doesn't mean that you can't compute inverses in $GF(256)$; instead, what it means is that you can't compute the addition and multiplication as $A + B \bmod 256$ and $A \times B \bmod 256$; other algorithms need to be used.

It happens that addition is easy; you can do it by doing a bitwise exclusive or; in C, that's A ^ B

Multiplication and inverses are a bit trickier; however, I can point you to the answer here that addresses how to do with with a few table lookups


Tamarin-prover issue on a basic Diffie-Hellman Exchange I am starting Tamarin-Prover and I have a little issue of understanding.
Here is a basic exemple of my issue :
First Code :
theory test
begin

builtins : asymmetric-crypto, diffie-hellman

rule Register_pk:
    [Fr(~ltkA)]-->[!Ltk($A, ~ltkA), !Pk($A, pk(~ltkA)), Out(pk(~ltkA))]

rule C1:
    [Fr(~x)]
    -->[C1($C, ~x), Out(<$C, 'g'^~x)>]

rule S1:
    let pubkeyC = 'g'^x in
    [Fr(~y), In(<C, pubkeyC)>]
    --[ Secret($S, C, pubkeyC^~y)]->
    [S1($S, ~y, pubkeyC)]

lemma Secret_dh:
"
    All S C dh_secret #i. Secret(S, C, dh_secret)@#i ==> not( Ex #k. K(dh_secret)@#k)
"
end

after a : tamarin-prover --prove test.spthy the lemma is verified
Then I only change the lemma into :
Second Code :
lemma Secret_dh:
exists-trace
"
    All S C dh_secret #i. Secret(S, C, dh_secret)@#i ==> Ex #k. K(dh_secret)@#k
"

And after a : tamarin-prover --prove test.spthy the lemma is verified too. And I find this completly abnormal ..
Thanks for your help .. And have a good day.

Did you try asking this on the Tamarin google group? I'm guessing that's the right place to ask such a question and get a good answer.
Though from a first glance, I would guess that the empty trace (or any trace in which no Secret fact occurs) satisfies your second lemma, and this is thus entirely expected behavior.
Intuitively, your second lemma states: there exists a trace, such that (if a Secret fact occurs in it, then the adversary knows the secret). This trivially holds for any trace without a Secret fact, and thus the lemma indeed holds.
Or, put differently, your second lemma is not the negation of the first lemma.


How big does M need to be in Blum Blum Shub? I've read that Blum Blum Shub is a CSPRNG, defined by x_n+1 = x_n^2 mod M. I didn't understand that, and couldn't find any sources on how big should M be.
Are 32 bits enough? 64 bits? Or are even more bits required?

The usual definition for the Blum-Blum-Shub (BBS) generator goes as follows:
Let $N$ be a Blum-Integer of unknown factorization. Let $j$ be the "extraction rate". Let $x_0$ be a uniformly random non-negative integer smaller than $N$. Define $x_{i+1}=x_{i}^2\bmod N$. For a request of $M=jk$ random bits, compute all $x_i$ up until at least $x_k$ and concatenate the $j$ least significant bits of each of those values as the random output.
The classic, original BBS construction used an extraction rate of 1. Later analysis (PDF) suggested that $j$ can safely be of order $O(\log\log N)$. Follow-up concrete analysis (PDF) suggests the following bound (Theorem 3):

The BBS Generator is $(T_A,\varepsilon)$-secure if $$T_A\leq \frac{L(n)}{35\delta^{-2}n\log_2 n}-2^{2j+9}n\delta^{-4}$$ where $\delta=(2^j-1)^{-1}M^{-1}\varepsilon$, n being the bitlength of $N$, $L(n)$ being the effort to factor $N$, and $(T_A,\varepsilon)$-secure meaning that an adversary can distinguish the output from random with effort $T_A$ and success probability $\varepsilon$.

Now let's pick $n=3072$ for fun for which the standard estimate is $L(n)\approx 2^{128}$ work effort. Let's also pick $j=4$ and $k=32$ extracting 4 bit from each squaring and wanting 128 bit. Let's also suppose we want $\varepsilon=2^{-1}$ success probability for the adversary. This gives us $\delta=(2^{1}\cdot 31\cdot 128)^{-1}\approx 2^{-13}$. This in turn gives us $2^{2\cdot 4+9}\cdot n\cdot 2^{52}\approx 2^{79}$ and $\frac{2^{128}}{35\cdot 2^{26}\cdot n\cdot \log_2 n}\approx 2^{81}$. Therefore an adversary in this scenario requires about $2^{81}$ work to break this BBS generator with success probability $1/2$.
Using the above, you can also try and estimate other parameter values, but I guess you already noticed that for BBS to be secure you either need rather large moduli or extract at a very slow rate and / or only extract a few bits from a seed. In general, you're better off using a generator like AES-CTR DRBG.


o(1) in time complexity of number field sieve It is well known that the time complexity of the number field sieve can be calculated by the formula
$$\exp\big((C+o(1)) (\log n)^{1/3}(\log \log n)^{2/3}\big)$$

The constant C is known for the special and general number field sieve variants.
My question is, how can the value $o(1)$ be approximated for cryptographic reasonable values of n (e.g. $2^{1024} \le n \le 2^{4096}$)?
Do there exist known upper and lower bounds?

The reason for this question is as follows. By the definition of o(1) one can only conclude that asymptotically this value vanishes. But for any bounded value of n, the value can be anything. Therefore, in a strong mathematical sense, this formula is useless to conclude anything about real-size factorization problems.

Summary: it is common, and arguably safe, to assume that the $o(1)$ term is positive, and take it at zero, in circumstances where the formula is then used to estimate a lower bound of the ratio of work for larger value of $n$ to that for smaller values of $n$.

The formula given, with $o(1)$ term, gives the complexity of NFS. If modified by assigning a real value (say, zero) to the $o(1)$ term, it yields a function of $n$ without unit, thus insufficient to calculate the time (or effort, or cost) needed to run the algorithm for a given $n$. The $o(1)$ term happens to encompass the very order of magnitude of the cost (as a consequence of the outer exponential and the positive exponent to the $\log n$ term).

However, a common and legitimate use of that formula is to evaluate how the effort to run the NFS scales with $n$, by computing the ratio of what the formula gives for different values of $n$ (and taking the base-2 log for a security variation in bits). In that sense, it makes sense to ask which value of $o(1)$ should be used for a given $n$.

I don't know, and likely that depends on the variant of NFS (which also has a huge influence on $C$), and the hardware at hand.

However, a common approach is to hypothesize that this $o(1)$ term is positive, and take it as zero when extrapolating how larger $n$ needs to be, thus (if the hypothesis is correct) erring on the safe side from a key-holder's point of view.

Addition commenting the self-answer: an example of the practice in the previous paragraph is the formula given by the NIST in Implementation Guidance for FIPS PUB 140-2 and the Cryptographic Module Validation Program (updated August 1, 2016), computing the conventional bit strength $x$ of an RSA public modulus of $L$ bits as
$$x\;=\;{1.923\times\sqrt[3]{L\log(2)}\times\sqrt[3]{(\log(L\log (2)))^2}-4.69\over\log(2)}$$
which is obtained by

straightforward transformation of the GNFS complexity formula using $C=\sqrt[3]{64\over9}$ rounded to 4 significant digits;
ignoring the $o(1)$ term, thus obtaining an $x$ such that $2^x$ is an estimation of work in unknown unit;
solving the above issue by introducing the additive constant $-4.69$ (which really is a multiplicative constant of $2^{-4.69/\log(2)}$ on the involved work $2^x$), determined so that when $L=1024=2^{10}$, the result obtained is $x=80.000\dots$, because that fits the FIPS 140-2 normative context, and anecdotal evidence suggests that the cost of breaking common 80-bit symmetric cryptography would be smaller than the cost of factoring a properly generated 1024-bit RSA modulus.

That formula thus arguably errs on the safe side from the key-holder's point of view if used to estimate the security given by an RSA modulus of $L\ge1024$ bits properly generated from true randomness, under the assumption that GNFS roughly as practiced now remains the best factoring algorithm.