What is the best way to share a shared secret key over HTTPS to be used for HMAC authentication? I am writing an application in Java that will be using SHA-1 HMAC message authentication.  From what I understand, a connection over HTTPS is considered secure enough to share a secret key in plain text, and there is little added benefit to hashing the key before sending it from the client to the server.

So, my implementation would have to share a secret key when the first connection is made.  After that, the client would send an API key along with the message that would identify the client and allow the server to look up the correct secret key.

For more information on the approach that I want to use, I am following this guide (Gary Rowe's Multibit Merchant).

The goal is to authenticate the client on subsequent connections.

Is my assumption correct that I can safely send the secret key over HTTPS on the initial connection?

HTTPS itself does not do encryption, it simply relies on SSL/TLS in order to implement some level of security to your communications. The problem lies with the choice of underlying algorithm - SSL 2.0 is already considered insecure due to flaws. Similar (less critical) attacks have also been discovered for SSL 3.0/TLS 1.0 so you can only fully trust HTTPS if you know what the server AND client (browser) use behind the curtains.

Generally, the approach for communicating a secret key (read ANY secret key) assumes an effort of asymmetric cryptography (see RSA, for example). So your client would connect and send his (temporarily generated, if you must) public key and receive the secret key encrypted with this. The message can now only be decrypted by his private key which never appears in HTTPS traffic and is, mathematically, hard to figure out. This is, for the most part, the way HTTPS works.

Normally I would advise against reimplementing any sort of crypto but, if you have no control over the SSL/TLS versions the server advertises, I would go for an encrypted secret key exchange inside the session and leave the rest of the traffic as is. Just remember NOT to implement the primitives yourself - any language out there has a number of functions and libraries dedicated to this, including higher-level primitives for simply encrypting a message with little options.

It all depends on your skill and on the security you want to impose inside the system.


Crypto USB Devices - where is the PIN/Password stored? I am currently looking at the security of cryto USB drives for storing x509 certificates. I have one in possession currently. It can be read/written to using the Microsoft Crypto APIs. Anytime one reads/writes to/from the device it prompts for a PIN. The PIN can be changed using a UI which installs with the device.

I was wondering how exactly this PIN is stored/used?.
Does the device store the PIN on the device itself? Or is the PIN used to generate a symmetric encryption key which is then used to encrypt the contents of the device. Which will mean that only the right PIN will allow you to read from the device and also the PIN is not available on the device itself.

So I was wondering if there is a standard way in which device vendors do this. If so, what is it?

This is what the PKCS#11 standard says

  If a device does not have a tamper-proof environment or protected
  memory in which to store private and sensitive objects, the device may
  encrypt the objects with a master key which is perhaps derived from
  the user’s PIN. The particular mechanism for protecting private
  objects is left to the device implementation, however.

It's not clear what's a tamper-proof environment or protected memory in case of a USB crypto device.

It's impossible to say what the device really does; there are so many possible ways.

If you don't find any technical specification describing it, I would be wary of the actual security of the device.

If the device is FIPS 140 approved at any level, you can find back the FIPS certificate and the relevant security policy on this NIST web page.


What is the cost of encrypting of long message with public-key cryptography? Let m be a message of arbitrary size, potentially very large.
Is it necessary to use larger parameters in the public-key encryption scheme in order for the receiver to decrypt that message?

My guess is that, in the case of RSA, the size of the message cannot exceed the size of the modulus. I assume this holds for any public-key encryption scheme.

If so, what kind of algorithmic complexity are we talking about: is it linear in the input size (the message), or worse? [I assume it's worse]

EDIT: I don't want to use symmetric-key cryptography.

EDIT 2: You can assume that we possess a secure channel over which we'll send the encrypted message.

The real problem is not the encryption or even the decryption of an encryption scheme with huge values, it is the generation of the key:

For RSA, ElGamal, Paillier, etc. you need one or more large primes, which make up a modulus for your computations. In practice, you can find large primes by using the Miller-Rabin primality test. It has a run time of $O(t \log^3 n)$, and for large numbers it can be improved to $O(t \log^2 n)$ if using FFT-based multiplication. $t$ notes the number of test runs and you have an error rate of $1/4^k$, where the test says prime for a coposite number. While the runtime with multiplication optimazation has the smaller exponent, the Big-O notation does hide constant factors, and I don't know where the break-even is, but let's just assume the current crypto libraries already use the optimzation.

As a reference in this SO answer generating a $2048$ bit RSA key (which is generating two $1024$ bit primes and a tiny amount of its computation time to find $e$ coprime to $\phi(n)$ and calculating $d$) takes around $1$ sec. So $\approx 0.5s$ for a $1024$ bit prime.

If we want to increase the size by a factor $a$, then the Miller-Rabin test takes $a^2$ times longer. However, we also need to test $a$ times as many numbers on average to find an actual prime number. Example: A random $1000$ bit number is prime roughly with probability $1/ln(2^{1000}) = (\log 2)/ 1000$ and we need on average $1000/(\ln 2)$ tests to find a prime, a random $2000$ bit number is prime with probability $(\log 2)/2000$, and on average we need to test $2000/(\ln 2)$ numbers to find a prime. This means, we expect to run the algorithm on $a$ times as many numbers to find a prime.

For example, for a prime with $1 M$ bits for example and an estimate of $0.5$ sec for a $1024$ bit prime, we have a factor of $~976.5$ in size, so the runtime for Miller-Rabin itself is $0.5 \cdot 976.5^2$, and we need to test $976.5$ as many values, resulting in an overall runtime of $\approx 465 M$ seconds, which is around $14.76$ years.

In case you want to use RSA you need two of these primes, so after 30 years you have a RSA modulus with $2,000,000$ bit, which allows you to encrypt $0.25$ MByte of data in one piece. Of course using a large computing center will speed this up, but the real problem is the size, since I guess you didn't have $0.25$ MB of data in mind when you wrote "potentially very large".

Edit:
The encryption and decryption scale much less from the size increase. For RSA, you can still use a small exponent in the encryption, this doesn't have to be much larger than current ones. That means the number of steps in square-and-multiply are roughly the same, just each multiplication and modulo operation takes more time. Decryption then involves a number of length of the modulus, but overall it is still quadratic at worst, and much less than prime generation.


What are the randomness requirements for inputs to PBKDF2? I need to generate one 160-bit HMAC-SHA1 key for each user in my system. Can I use the username as the input to PBKDF2 function to generate the key?
Is it safe to use known values like username as inputs to PBKDF2? Or should the input to PBKDF2 function be random? If random, then how random?

As PBKDF2 is a key derivation function, its primary purpose is to turn a secret, low-entropy value into a higher entropy secret key.
In your use-case, if the key is expected to be secret (I assume it is), then using only publicly known data associated with the user will result in a key that anyone with access to the PBKDF2 parameters can generate.
That said, depending on how you intend to use the keys, if you intend to store them or generate them on the fly, etc. things could potentially change, but you would need to be careful of the fact that the output of PBKDF2 is effectively non-secret if you're solely using non-secret inputs.
The inputs don't necessarily have to be random (most passwords aren't, strictly speaking, random) but it should be secret.  Remember that in general with key derivation functions you are trying to trade off the time you spend generating the key with the time it would take for someone to brute-force all possible candidate inputs for that key.  So if the value is public, and even something directly associated like the username, they're not going to spend much more time figuring it out then you spent generating it.  But if they have to guess every allowable password, the time taken to guess the input (and therefore be able to recreate the key) should hopefully be increased to the point that the resources required of the attacker would make the attack cost-prohibitive for what you're protecting with these keys.
How that cost-benefit analysis works out for your case is up to your risk assessment which should lead into your choice of PBKDF2 parameters, or even decision to use that algorithm at all, and your requirements of what is used as an input (e.g. what types of passwords are allowed to be used).


What was the NSA's reasoning for making their bitwise combination functions in SHA-1 the way they did? I know that these functions are there to actually make the program work. What I want to know is why they made the functions one way but not another.
For example, why did they pick

  F1(B, C, D) = (B & C) | (~B & D)

as their first function instead of another function like

  F1(B, C, D) = (B & D) | (C ^ (D & ~B))

What choice did they have?

F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36.

However, those 36 are all basically equivalent. If you change the order of arguments for F1 and/or add some initial negations to any of the arguments, you will be able to construct them all. So they could have added some initial not-operations (making it more complex) or changed the argument order, but that's it.

The only other options they had were biased functions like the one in the question, ones where some input doesn't matter (so they are actually one or two input functions), and ones where the argument order doesn't matter, like B ^ C ^ D.


Access tree and Key geneation in KP-ABE I tried for about 1 month to understand ABE and know I am confusing about access tree. In paper "Attributed-based encryption for fine-grained access control of encrypted data" the author explained the generation of keys with access tree for KP-ABE which I attached the picture of it here.

I found an example for this but some parts in paper are not clear for me.

1) what is the meaning of "threshold value"? Based on the top example, how can I determine this for different nodes?

2) What is the meaning of the index (x)?

Thanks a lot. I appreciate your helps.

The threshold value for any node in the tree is the minimum amount of child nodes that is needed for derivation of the secret. For an OR node the threshold value is usually 1 while for an AND node the threshold value is equal to the number of child nodes. For instance from your diagram, the threshold value for the AND node numbered 1 is 2 and the threshold value for the other node is 2. The threshold value for the root node which in your diagram is r will also be 2 because it is an AND node and it has two sub nodes attached to it.
index (x) is simply a way to keep track of all the individual nodes that are part of the whole tree so you can evaluate them accordingly i.e according to their position in the overall tree which means being able to identify what child nodes are attached to any certain node and what parent node a particular node is attached to.

Hope this helps.


Security of secure two-party computation with a trusted dealer during offline phase? In the SecureML paper, one can assume that two non-colluding servers can run secure two-party computation protocol based on secret sharing with the help of a third party (client).
The client would send correlated randomness to the servers in offline phase, which can accelerate the computation in online phase, e.g. multiplication using Beaver's multiplication triplet.
I'm wondering how the security of this type of secure two-party computation is defined.
Is it secure if one of the servers and client collude?
Since the client knows the information about all the correlated randomness, does it incur some security flaw if that happens?

This is the so-called Common Reference String (CRS) model, or Correlated Randomness model. A good reference to it is the paper On the Power of Correlated Randomness in Secure Computation.

Secure multiparty computation (MPC) can be expensive (in terms of computational or communication complexity) when a trusted party (the one doing all the computation in secrecy) doesn't exist. Secure MPC is easy when a central trusted party can execute all in secrecy, but this is what everybody doesn't want.

With the CRS we have an interesting model: the creator of the randomness is usually a trusted party. But, this trusted party can be unaware of the computation the parties intend to execute. So the model separate who knows the joint randomness, and who execute the computation. And by supposing a CRS, we can reach secure MPC at a low price. Therefore, the belief that the CRS can't be compromised is a cornerstone of the model: it doesn't compute, but if it leaks the randomness, everything falls flat.


Encrypting Keys in a Firmware-Update I have a bootloader on a small device (Cortex-M0/M3). I want to publish encrypted firmware updates, that can be installed on the device, using the bootloader. The whole point of the encryption is to probit to make a copy of the firmware or to install unauthorized software. The device provides some means of readback protection.

I store a set of 256-bit keys in the bootloader (k1, k2, k3...). That set of keys can be different from device to device (licenses) and every key is associated with some kind of feature. Now I want to define, which keys a bootloader needs to decrypt the firmware. For example: k1 and k2 or k2 and k3.

I use a random key (kr) and a random IV to encrypt and authenticate the firmware using AES/GCM. For every key combination, that can be used to decrypt the firmware, I was going to store the encrypted random key kr, encrypted by a key that is built by xor'ing the required keys.

To take the example from above: If I want to have the firmware installable on all devices that know either k1 and k2 or k2 and k3, I would store E(k1 xor k2, kr) and E(k2 xor k3, kr) as plain text along the encrypted firmware.

Now, I have three questions: Does the approach above sounds reasonable? Can I use AES/ECB as E to encrypt the combined key? Could I use AES/CTR with the very same IV from the AES/GCM encryption of the firmware?

Your approach seems to have a lot of unneeded complexity and limitations. For example, you must decide the mapping between features and keys in advance. Here are some simpler approaches with more generality:

One key per bootloader: Let's call this the client key. Then to send firmware to a particular bootloader you encrypt/authenticate it using that bootloader's client key.

One key per bootloader, one key per release: You can save compute/bandwidth/storage by avoiding wastefully re-encrypting the same firmware with different client keys. With this approach you generate a release key for each firmware update, and encrypt/authenticate the firmware with the release key and then encrypt/authenticate only the release key using each bootloader's client key (of course, only for those bootloaders that you want to allow to install this update).

One master key: You can also use a single master key and give each bootloader a unique ID. Then, when releasing a firmware update, you can include metadata that lists the bootloader IDs that are allowed to install it. This metadata would be encrypted/authenticated with the master key along with the firmware itself. Then the trusted part of your bootloader checks that its ID is in the list before allowing the write. Note that with this approach if someone manages to read out the master key through a reverse engineering effort, they can easily mass-produce updates for all bootloaders, an un-feature that is not present in the approaches that have one key per bootloader.

To map your "features"-based approach to this, you can consider mapping the different feature sets in your bootloaders to different IDs. So the IDs need not be uniquely identifying each device but only each feature set if you want.

One master public key: Like the above approach, but using public-key cryptography to sign the firmware updates. A break of a single device will allow an attacker to read all future firmware updates, but at least they won't be able to generate homebrewed updates.


Is it possible to work out the hash algorithm from a list of known message-hash pairs? For example, in my situation I know hash(20) = 486e9638177faf1f34e49910491b77af.
I also know the hashes for all values from 0 to 20.

Is it possible to work out the algorithm used to hash these values?

In practice, maybe, if you got additional information, such as that the hash function is known to conform to some published standard (you just don't know which).

Theoretically, though, for any finite list of values, there is always more than one bounded algorithm that generates the list. You can never be absolutely sure you figured out the correct algorithm.


In BBC Sherlock's The Blind Banker, what type of cryptographic function is used by the Black Lotus? In BBC’s Sherlock, Season 1, Episode 2 “The Blind Banker”, the Black Lotus crime syndicate uses ancient Chinese number characters to refer to pages and words in a commonly known book (which was currently the A-Z London Guide).

What class of cryptographic functions would this most closely fall under? Is it symmetric/private key encryption? Or asymmetric/public key encryption? Or something else?

My understanding is that the key is the common book, and the Chinese characters are the ciphertext of the original words. Hence this would make it symmetric encryption? But at the same time, the book is publicly accessible so it's not strictly a secret/private key.

This sounds like a straight forward book cipher.

Symmetric encryption implies that the knowledge of the key is sufficient for both encryption/decryption.

Asymmetric encryption implies that the ability to perform the encryption/decryption operation is separated into two distinct keys.

  But at the same time, the book is publically accessible so it's not strictly a secret/private key.

Which book is used may be the secret key. Also, which book is used could be public knowledge, but certain subsections of it are the key.

Another way to look at it is that the set of possible bit strings of a given size is public knowledge. But if you select one particular bit string secretly from this publicly known set, it does not mean your secret key is then public information.


Low complexity implementation of a small blocksize cipher (< 64 bit) Searching for "small blocksize cipher" finds a number of discussions on the topic, mostly refering to FPE.

This one in particular suggests using AES as the round function of a Feistel network.

The problem is on some embedded devices, the use of AES is too complex, so a tradeoff between cipher strength and complexity is required.

In searching for a Feistel based cipher with low complexity, the TEA cipher seems a good choice, but uses 64 bit blocksize.

For a sub 64 bit block of data, say 44 bit, tweaking TEA by masking the output of each Feistel round with a 22 bit mask (0x3FFFFF) seems to work correctly.

The question is, does masking in this way break the TEA algorithm?
(other than weakening due to a smaller blocksize)

This will probably be OK.  It does have some non-trivial side effects/caveats:

The effective key length is reduced to 86 bits.  Only the low 22 bits of each of the 4 key words will matter, so only 88 bits of the key material are relevant.  Then, there are known equivalent-key properties of TEA that further reduce the effective key length to 86 bits.
A 44-bit block width is uncomfortably narrow.  Most modes of operation will have security weaknesses if you encipher more than about $2^{22}$ blocks of data.  Even if you encrypt a fraction of that much data, there's still a chance of problems: if you encipher $b$ blocks of data, there's about a $b^2/2^{45}$ chance of some sort of problem.
Due to the equivalent keys, TEA is not suitable for building hash functions.

Have you considered using something other than a block cipher?  Maybe a stream cipher?  What are your needs?


Is there any point to encrypting a file if it's transferred via ssh? Suppose I have two machines which can ssh into each other. Is there very little point in using gpg with a password protected symmetric cipher to transfer a sensitive file, and going to the effort of sharing the password - over, say, an encrypted call?

I realize that theoretically the ssh communication could be compromised without the password which protects the encrypted file being compromised, but what I'm asking is does the whole system need an overhaul if I'm leaning on ssh being secure for sensitive file transfer?

If you had a system like this:

\begin{equation}
  \text{you} \longleftrightarrow \text{your network} \longleftrightarrow \text{shared host} \longleftrightarrow \text{friend's network} \longleftrightarrow \text{friend}
\end{equation}

Your use of ssh defends against an eavesdropper or forger on your network.
Your friend's use of ssh—if your friend is using ssh instead of, oh, I dunno, rlogin or rcp—defends against an eavesdropper or forger on your friend's network.
The use of gpg with a password transmitted out-of-band to encrypt the file defends against an eavesdropper—but not a forger!—on the shared host.

Why no defense against a forger on the shared host?  Nobody bothered to teach OpenPGP about symmetric authenticated encryption.  You could use the scrypt(1) utility instead, which does use authenticated encryption.

How could there possibly be an eavesdropper on the shared host?  The eavesdropper might come in the form of the administrator of the VPS you're using for your shared host, who has access to the raw disk.  The eavesdropper might come in the form of an automatic backup system which persists the file much longer than you intended.

But, on a more careful reading of the first eleven words you actually wrote, I see that you actually have a system like this:

\begin{equation}
  \text{your machine} \longleftrightarrow \text{internet} \longleftrightarrow \text{friend's machine}
\end{equation}

Conceivably you might have different applications and daemons running with different privileges, and your user account on your friend's machine might be more vulnerable than your friend's user account.

But there's not much else that gpg adds beyond (a) a hedge against bugs in ssh or breakthroughs in breaking DH (like a network eavesdropper with a quantum computer) that don't apply to your out-of-band channel, and (b) a usability nightmare.


Can I use a deterministic NONCE for AES-GCM file encryption if I generate "fresh" keys for each encrypted file The NIST specification states that the deterministic NONCE(IV) should be 96 bits. It should consist of two fields: fixed field of 32 bits and a 64 bit counter. The use of a random 96 bit NONCE is discouraged (https://eprint.iacr.org/2016/475.pdf).

My use case is encrypting files on disk. Each file is encrypted with a new key generated by a KeyGenerator, initialized with the default SecureRandom() implementation. My question is this: do I really need a fixed field, or can I make the whole 96 bit NONCE initialized to 0. As in a 96 bit counter. This way the NONCE is effectively deterministic and I don’t have to store it as part of the file. Since a new key will be generated for each new encrypted file, then I shouldn’t ever reuse a key/NONCE pair which would be detrimental for AES-GCM.

I’ve seen some suggestions that the fixed field is actually a 32 bit random integer, but I think this is not necessary as I’d never re-use a key/IV in my construct (http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf).

My only concern then would be to ensure that I never generate 2 identical 256 bit keys out of SecureRandom, but that proof seems impossible to me and the probability of such event seems negligible. The only way to ensure I never generate duplicate keys is to keep the keys or their fingerprint in a database, but this is undesirable. But then even if I do employ a 32 bit random integer in my fixed field I also have no guarantee that a probabilistic event won’t happen and create a duplicate key/IV.

Update

I have summarized my research on how to use AES-GCM correctly in a blog post.

Yes, you can set the IV to zero if you use a different key each time. You speak about a random key, but is the key truly random, even in time? What happens if a file is changed, what attack vectors would surface in such a case?

Using a 32 bit random "fixed" integer is not a good idea. You'd quickly produce collisions even for a relatively small amount of files stored with the same key. So whatever you try to fix with that, it won't be fixed enough to be called secure in a cryptographic sense.

If you worry about the keys not being random, I'd add some startup tests for the random number generator instead. Because without a trusted random number generator a lot of operations are not going to be secure.


Difference between computationally and perfectly hiding (binding) properties I am new to Cryptography and has a trouble of understanding the difference between perfect and computationally hiding (binding) properties of a commitment scheme. I also would like to ask what does it mean to be a computationally bounded (unbounded) adversary? I tried to look at these through Google search but none provides a clear difference between these terminologies.

The words perfect and unbounded refer to basically the same concept*. If something has perfect security with respect to property X, then an adversary that is computationally unbounded can not violate property X. Computationally unbounded means that the adversary is allowed to run for an unspecified amount of time, in particular, $O(2^\kappa)$ for security parameter $\kappa$.

For example, we can ask if AES is a secure block cipher (permutation). What we could do is pick a random key $k\in\{0,1\}^\kappa$, encrypt the messages 1,2,3,4,... and give the results to the adversary.

If we bound the running time of the adversary to be $poly(\kappa)=O(\kappa^c)$ for some constant $c$, the answer is yes, we think AES is indistinguishable from a truly random permutation from $\{0,1\}^\kappa $ to $\{0,1\}^\kappa$.

However, if we allow the adversary to be computationally unbounded then there is a simple attack that can break AES. Say the adversary see $c_i=Enc(k,i)$ for $i=1,2,...,100$. Then with overwhelming probability, there is only one AES key $k$ that results in these $c_i$ values. As such, an unbounded adversary can simply try all $k'\in\{0,1\}^\kappa$ and check which results in the same ciphertexts $c_i$. Since there is likely only one such key the adversary will find it. This is a "brute force" type of adversary.

Note that if we instead used a one-time pad, then an unbounded adversary would not be able to break the encryption.

Now let us answer your question. Perfectly hiding means that an unbounded adversary can not learn any information about the value being committed to. One-time pad is perfectly hiding (but isn't a commitment scheme...). Hiding is a security property you care about when the adversary is the person who receives the committed values.

You can also have a computationally hiding commitment which means no adversary which has running time $poly(\kappa)$ can learn any information about the value by seeing the commitment (except with negligible probability).

Perfectly binding means that an unbounded adversary can not break a commitment and decommit it to more than one value. In other words, there must truly be only one value that the commitment can ever decommit to.

For computationally binding, then any adversary with running time $poly(\kappa)$ must have negligible probability of decommitting to more than one value.

Say our commitment scheme the classic "random oracle" approach where you commit to $x$ as $c=H(x || r)$ where $r\gets\{0,1\}^\kappa$ is a random value. Then this scheme is not perfectly binding. An unbounded adversary could pick some $x'$ and simply try $O(2^\kappa)$ other values of $r'$ until they get $c=H(x'||r')$. They could then "decommit" using either $(x||r)$ or $(x'||r')$. However, this scheme is computationally binding since finding such an $r'$ value requires $O(2^\kappa)$. Note, I'm ignoring some issues with the birthday bound.

There exist commitment schemes that have perfect bind or hiding but not both.

Edit*: as Maeher pointed out, there is a way for a commitment to be secure against an unbounded adversary while still not being perfectly secure. For this we introduce the statistical security parameter $\lambda$. A property X is said to have $\lambda$ bits of statistically security if when you run the (commitment) algorithm there is at most a $1/2^\lambda$ probability that property X does not hold (unconditionally).

For example, let us have some commitment scheme $C(x;r)$ which takes a value $x$ and a random tape $r$ as input. It just so happens that if $r=42$ the scheme completely falls apart. However, if we sample $r\gets \{0,1\}^\lambda$, then the probability that $r=42$ is $1/2^\lambda$ and this scheme can still be considered statistically secure. Importantly, the probability that the scheme fails to have the desired property is a function of the random tape $r$ and not of the running time of the adversary.


Do any non-US ciphers exist? Plenty of ciphers come out of the USA from government research or selection competitions. AES and DES are examples.

Are there any public ciphers produced by other states, China or Iran for example? Do you really think they trust AES?

EDIT: List of ciphers from different nations:

USA: Skipjack
Japan: Camellia
Russia: GHOST
Korea: SEED
China: SMS4

Plenty of ciphers come out of the USA from government research or selection competitions. AES and DES are examples.

Indeed, the US is known from some crypto-related competitions that were/are open to anyone and they surely will do ample of government research related to cryptology, but you need to be sure that you differ between “they selected it” and “they created it”. There is a big difference!
For example: what we now call AES was selected through an open competition by the USA, but the cipher design that became AES was not created by the USA.

  Are there any public ciphers produced by other states, China or Iran for example? Do you really think they trust AES?

Of course there are other countries and states that are known to be the origin of different ciphers, but listing them all would be a bit too broad. Instead, I’ll give you a quick heads-up:

Also, on page 3 of "The Design of Rijndael: AES – The Advanced Encryption Standard." by Joan Daemen and Vincent Rijmen (the creators of Rijndael – also known as AES), you can find a neat table that shows a list of the 15 AES candidates that were accepted for the first evaluation round, including their country of origin.

For your convenience, here are those 15 candidates:

CAST-256
submitted by Entrust (company), from Canada
Crypton
submitted by Future Systems (company), from Republic of Korea
DEAL
submitted by Outerbridge, Knudsen (researchers), from USA & Denmark
DFC
submitted by ENS-CNRS (researchers), from France
E2
submitted by NTT (company), from Japan
Frog
submitted by TecApro (company), from Costa Rica
HPC
submitted by Schroeppel (researcher), from USA
LOKI97
submitted by Brown et al. (researchers), from Australia
Magenta
submitted by Deutsche Telekom (company), from Germany
Mars
submitted by IBM (company), from USA
RC6
submitted by RSA (company), from USA
Rijndael
submitted by Daemen and Rijmen (researchers), from Belgium
SAFER+
submitted by Cylink (company), from USA
Serpent
submitted by Anderson, Biham, Knudsen (researchers), from United Kingdom & Israel & Denmark
TwoFish
submitted by Counterpane (company), from USA

From the 15 candidates that made it into the first evaluation round of the AES competition, only 5,5 originated in the USA. That’s a mere $36 \frac{2}{3}\%$ percent of US ciphers in their own cipher competition.

Wrapping it up:

AES is far from being a US government baby. Instead, cipher that won the AES competition (Rijndael) was born in the land of friendly people, “french” fries and tasty beer: Belgium!

Now, being a half-Belgian I may be a bit biased… but I honestly have a hard time trying to imagine why anyone would suspect a Belgian cipher design, just because it also happens to be used by the US government. Instead, that merely indicates that the cipher design is that good, that even the USA uses it to protect its valuable information and big parts of their national security.
A lot of ciphers were (and are) created outside of the USA. Yet, not all ciphers that are created are published; and if they are, they rarely gain attention due to missing publicity and/or popularity. That is one of many reasons why those competitions are interesting for cipher designers.

As said, listing all ciphers from all countries would be too broad, but the above list of “AES round 1 candidates” already shows Australia, Belgium, Canada, Costa Rica, Denmark, France, Germany, Israel, Japan, Republic of Korea, United Kingdom, and the USA.

That should be ample to understand ciphers are not a US-only thing and that the US is not as dominant in crypto as you think. In the end, even AES is non-US. They adopted a Belgian cipher to their standards, but they didn’t create it. If you really want to suspect someone for having whatever kind of dominance in the field of symmetric crypto, I can’t stop you. But if you take a good look at the origins of individual ciphers, you’ll notice they come from all over the world… and currently, your main suspect would be Belgium  due to AES (aka Rijndael) and SHA-3 (aka Keccak).


Can key-wrapping help to securely change passphrase used to generate encryption key? I am working on financial application where users' data are encrypted with symmetric cipher (AES-256), encryption keys is derived with KDF from user's password. I am looking for way how to give to my users some easy-to-store value (10-15 bytes long) that he stores in a safe and use it as "recovery key" when he forgot his password.

I am studying how key-wrapping works and how it can be used to change (forgotten) password in application where password / passphrase is used as input for encryption key generation (KDF). This article Encryption background: What is key wrapping? discuss how key wrapping works and how can be easy to change user password without need to re-encrypt user's data.

I understand there is no problem when I'm changing password that I know - I know my password, original encrypt key is unwrapped and re-wrapped with new key derived from new password; so far so good.

Question1: How can be key-wrapping mechanism used when I forgot my password? (password is used to create wrapping key). I think that in this situation it cannot done and user's data are lost because I cannot unwrap original encrypt key so I cannot re-wrap original encrypt key. Am I right or wrong?

Question2: Is there some way / mechanism / technique how can I decrypt encrypted symmetric cipher key (AES) with two secret values? One value is derived from password / passphrase and second is from something as Apple's recovery key. I am studying paper Infiltrate the Vault: Security Analysis and Decryption of Lion Full Disk Encryption but I'm not done yet.

Question1: How can be key-wrapping mechanism used when I forgot my password? (password is used to create wrapping key). I think that in this situation it cannot done and user's data are lost because I cannot unwrap original encrypt key so I cannot re-wrap original encrypt key. Am I right or wrong?

This is right of course, if you cannot recover the key required for unwrapping then you cannot unwrap.

  Question2: Is there some way / mechanism / technique how can I decrypt encrypted symmetric cipher key (AES) with two secret values? One value is derived from password / passphrase and second is from something as Apple's recovery key.

Yes, of course you can. This is quite often performed. It is even possible to require N out of M parts to form or decrypt the final key in certain protocols.

The recovery key size should of course be at least 32 bytes if you want to remain on the same security level as AES-256. Then again, using keys derived from a password will normally not provide 256 bit security either.


Why are the right halves kept unchanged in Feistel networks? As I'm going through the Feistel network in the DES algorithm.

While encryption uses a Feistel Network, the input block is divided into two halves left ($L$) and right half ($R$). In each round, the right half $R$ goes through unchanged. But the left part $L$ goes through an operation $F$.

I didn't understand why right halves is kept unchanged in a Feistel Network. Can anyone explain?

This structure allow us to make the process invertible. A Feistel structure creates a pseudo random permutation from a pseudo random function.
We want someone with the key to be able to calculate it in reverse and get the plain text from the cipher text.

Also recall that the after two rounds both sides get scrambled and after many rounds they are thoroughly scrambled to make deciphering without the secret key rather difficult. DES is no longer considered secure but the Feistel structure is still used in other block ciphers.


Why does FIPS 180-4 require the final padding block start with a 1? From FIPS 180-4 § 5.1.1, the padding used for the SHA family of hashes begins with a binary 1, followed by a number of 0s, and finally a 64-bit representation of the message length:

Suppose that the length of the message, M, is  bits. Append the bit "1" to the
end of the message, followed by k zero bits, where k is the smallest, non-
negative solution to the equation  + 1 + k ≡ 448 mod 512. Then append the 64-bit
block that is equal to the number  expressed using a binary representation.

A form of this question has already been asked before, and the answer seems to be that it's likely because MD5 did that, and MD4 before that. But while that explains why MD5, SHA-1, and SHA-2 do it, it leaves the initial question unanswered. What is the purpose of starting the padding with a 1? If the correct answer for the SHS is "because that's how MD4 did it", then why did MD4 do it?

For SHA-3 which does not use length encoding, the purpose is to eliminate ambiguity:

  The initial 1 bit is required so messages differing only in a few additional 0 bits at the end do not produce the same hash.

MD4, which has always employed length encoding, still seems to use this padding.

If you don't start the padding with a $1$ it is not completely obvious where the padding starts.

If the message ends in

$...011010$

and you pad it to

$...01101000000$

which zeros were part of the message and which part of the padding?

If the padding is $1000...$ you know it started at the last $1$ in the padded string.

$...011010$

$...01101010000$

Edit:
Considering Why does the padding in Merkle–Damgård hash functions like MD5 contain the message length?
This looks a bit like $10000...$ was used in the beginning and then the length was added for weaker assumptions on the compression function. In which case implementers probably complained that there are no real problems and that they didn't want to do any work, and that changes would require new certifications of products, etc. pp. and they ended up with this compromise which allows simply ignoring the last 64-bit block and using the old algorithms.


Is this a novel secret splitting method, or a different view of an existing one? I did try this on Information Security, but they were happier to see it moved here. The crypto content is quite low. It's more about secret storage and robust recovery of information, for instance allowing the sysadmin's password to be recovered by a quorum of other users, should he go under a bus.

I should am aware of a number of secret splitting methods, Shamir's polynomials and Blakely's hyperplanes for instance. I have not seen the following described anywhere in the literature, and AFICS, notwithstanding it operates over finite fields, it does not appear to be the same as Shamir's.

While I was playing about trying to understand the mathematics behind Raid6, it became apparent that the ability to reconstruct data in the face of missing portions could form the basis of a threshold secret splitting scheme.

The normal Raid6 operation employs what in forward error correction would be known as a systematic encoding. That is, the encoding operation is designed to render the input information 'in clear' at the output, as far as possible, to minimise computation. For example, in the case of a 6 drive with 2 redundancy Raid6, the encoding of data abcd by matrix multiplication is as follows

 | 1 0 0 0 |           | a |
 | 0 1 0 0 |   | a |   | b |
 | 0 0 1 0 | x | b | = | c |
 | 0 0 0 1 |   | c |   | d |
 | 1 1 1 1 |   | d |   | P |
 | v w x y |           | Q |

resulting in the plain data on the first 4 drives, simple parity on the 5th, and the more complicated sum on the 6th drive using the distinct non-unity multipliers vwxy from the appropriate Galois Field, GF(256) for byte based discs or messages.

The data can be recovered from any four of abcdPQ, in the general case by inverting the appropriate reduced matrix, though in practical drives, a more efficient method is used that takes advantage of the systematic encoding when possible. This is equivalent to a six share threshold 4 data split, with obviously no secrecy.

In the secret splitting mode, the multiplication would be replaced by

 | m00 m01 m02 m03 |            | e0 |
 | m04 m05 m06 m07 |   | d  |   | e1 |
 | m08 m09 m10 m11 | x | r0 | = | e2 |
 | m12 m13 m14 m15 |   | r1 |   | e3 |
 | m16 m17 m18 m19 |   | r2 |   | e4 |
 | m20 m21 m22 m23 |            | e5 |

where mxy are distinct multipliers from GF(256) [edit, thx poncho, obvious, but I failed to state it first time round] that form a matrix for which any reduced square matrix is non-singular (not guaranteed with a random selection)[/edit], d is the data message, rx are independent cryptographically secure random numbers, ideally from a one time pad, and ex are the encodings. The random data is used only in the encoding, and does not have to be stored or transmitted to the decoder.

As far as I can see, all six encoded channels have the input data combined with 3 random numbers, so without the full theshhold number of shares, the data is unrecoverable. I am sure that at least one, and possibly several of mxx can be replaced with unity, while retaining security. [edit]In fact, specifying a column of unity multipliers feels like being sufficient to enforce non-singularity for any reduced matrix.[/edit]

The scheme can be trivially modified to any number of shares and threshhold level, using a GF(p) where p>shares.threshhold.

I am not suggesting this might be in any way superior to the existing known methods, especially not Krawczyk's which is far more efficient for large secrets. But given the straightforward formulation, I'm surprised that I've not seen it described anywhere.

Is it novel? And does it work as well as I think it should?

I haven't seen this one before before, but keep on reading...

It would appear to work, but you need to be a bit careful, specifically with your $mxy$ multipliers; it should be apparent that not just any random set of values would work there.

I believe that a necessary and sufficient condition would be "if you logically add a $(1, 0, 0, ..., 0)$ row to the matrix, then all submatricies consisting of $N$ rows from this extended matrix must be nonsingular" (where $N$ is the threshold number of shares); if this condition does not hold, then either there is a group of $N$ valid shares that cannot reconstruct the secret, or there is a group of $N-1$ valid shares that can.  Proving it is sufficient is straightforward; proving that it is necessary would appear to require going through a number of subcases, depending on what subset of rows was linearly dependent, and whether that subset included the artifical $(1, 0, 0, 0, ..., 0)$ row.

Blom's key distribution scheme has exactly that same requirement to its internal matrix; his key distribution scheme isn't a secret sharing scheme; instead, it's a way to distribute key shares so that any two parties can agree on a key, and no set of $N-1$ other parties can recover it.

One suggestion to make Blom's scheme work was to use the matrix:

$$
\begin{matrix}
1^0 & 1^1 & 1^2 & 1^3\\
2^0 & 2^1 & 2^2 & 2^3\\
3^0 & 3^1 & 3^2 & 3^3\\
4^0 & 4^1 & 4^2 & 4^3\\
5^0 & 5^1 & 5^2 & 5^3\\
6^0 & 6^1 & 6^2 & 6^3\\
\end{matrix}
$$

(where $1, 2, 3, 4, 5, 6$ are distinct nonzero field elements)

This matrix meets the criteria I mentioned, and works great for you.  However, if you look at it closely, it you use it, well, you've just rediscovered Shamir's original method :-)


Name and security of these non-invertible functions? I would like to learn more about a specific set of non invertible functions:

The function should accept 2 inputs: one hidden and the other visible.
The output and the function should also be visible.
The hidden input will not change, the visible will.
The function should be deterministic. Collisions are acceptable given there are not too many.

An important requirement is that given a long enough hidden parameter 10-20 characters it will not be possible calculate the output of the function given another visible input (which includes not being able to calculate the hidden parameter…).
When I say possible to calculate I mean that one would have to basically brute force all the possible combinations for 10-20ish characters and that there is no simple mathematical shortcut.
This is my current algorithm:
x- hidden input string
v- visible input string

I first mix the inputs. Once one of them is finished append the rest of the other on the end, so for example :
if len(x)>len(v):
    s = [x[0],v[0],x[1],v[1], … ,x[len(v)],v[len(v)], … ,x[len(x)-1],x[len(x)]]

Now calculate the output by:
associating each character in s with a predefined number such as

a:1
b:2
…

and
output = 1
for each item in s:
    output += truncate(sin(output+item)) // truncate for similar behavior
                                         // on different sin implementation

The output should be a number between -1 and 1.
Questions:

Will this algorithm fulfill the requirements I mentioned above?
More specifically – for the same hidden input, given multiple visible inputs and their associated visible outputs – can an attacker easily find the output for an additional visible input?

How do I name these functions (So that I can read more about these constructs)?

If I understood your question correctly, you want a message authentication code (MAC). The "hidden input" is usually called key and the "visible input" is just the message. The output of the MAC is called tag (or also MAC).

The main security goal for MACs is resistance against forgery: It should be computationally infeasible for an attacker who does not possess the key to obtain a valid tag for any message whose tag they have not observed before.

Common variants of that primitive include HMAC, CMAC, or Poly1305-AES, just to name a few.

Now, about your algorithm: Usually, homebuilt ad-hoc constructions are a very bad idea. Unfortunately, I did not find a trivial way to completely break yours during the few minutes I thought about it, even though I'm sure the mathematical properties of the sine function are highly useful to attack it. However, if you look at the examples I just linked, you will see that these are quite a bit more complicated than your proposal — and there is a reason for that. Many simple constructions suffer from unforeseen vulnerabilities once examined a bit more carefully: My favourite example is the "keyed hash" $\mathit{msg}\mapsto H(\mathit{key}\Vert \mathit{msg})$, where $H$ is a Merkle-Damgård hash such as MD5, SHA1 or SHA2. This suffers from a length extension attack and is thus not a secure MAC even it may seem so at first.

The bottom line is: Crypto is hard. Please use one of the well-established primitives from a well-established implementation if you have to protect anything of importance.


Is $a b + e \mod P$ hard to invert? Given $a, p$, $c$ where $c = a b + e \mod p$, can $e$ be recovered?

Additional details:

$p$ is prime
$a, p$ are re-used across many instances of the problem
$b, e$ (and by extension $c$) are always unique for each instance of the problem
$a, p$ are about 783 bits, with $a$ being smaller then $p$ by a no more then a few bits
$b, e$ are uniformly random 256-bit integers

What I have tried:

If the problem was not done modulo $p$, but was over integers, then it would be a simple matter of performing $c \mod b$ to obtain $e$.
The modular inverse of $a$ is about the same size as $a$, otherwise we could do $a_i c \equiv b + a_i e \mod p$ followed by $\mod p_i$ to recover $b$.
I noticed that:

$a b \equiv p - b(p - a) \mod p$ which lead me to this little
algorithm:

$x = p - a\\
     b = c / x\\
     e = c \mod x\\
     y = x q + e \mod p\\
     y \equiv c\\
     y = c - e - 1\\
     b = (y * inverse(a, p)) \mod N\\
     output\ b, e$

but for whatever reason, this only seems to function when $p=65537$ and $a=256$.

Applying the above algorithm to a random instance of $a$ for the actual $p$ does not output $b, e$ correctly.
If $b, e$ were the same size as $a$, I'm pretty sure it would be information theoretically secure.
Since $b, e$ are smaller, it makes me think there is leakage somehow.
Since $a b \mod p$ is about 783 bits in size and $e$ is only about 256 bits in size, then much of the upper bits of $a b + e \mod p$ are equal to the upper bits of $p q \mod p$.

I don't know how to take exploit this information.

The answer might be obviously simple, but I just haven't been able to figure it out for a few weeks.

Here is a gist with python code for what I am attempting to break.

Background: $ab + e \bmod P$ is the public key operation for a trapdoor function I am researching. The same expression, usually with more terms/in a higher dimension, is quite prevalent in many lattice based cryptosystems.

My work is available on github, and consequently I happened to receive some analysis from another user there. The following is a transcription of the users comments.

  The "EPQ" key exchange program given here is vulnerable to a Lagarias-Odlyzko style lattice attack. The usual upper triangular lattice basis matrix is formed by taking an identity matrix and replacing the rightmost column with a vector made from the public key, system parameters, and ciphertext. This 3 dimensional lattice contains a short vector that exposes the plaintext, allowing us to recover it with an SVP oracle.

  I've experimentally verified the attack using fpLLL as the SVP oracle, and had successful key recovery in every trial. For concreteness and convenience, the lattice basis I've used is (where P is the system modulus, K is the public key, and C is the ciphertext):

  $\begin{pmatrix} 1 & 0 & P \\ 0 & 1 & K \\ 0 & 0 & C \end{pmatrix}$

  I actually used vanilla fpLLL on the command line, and manually typed in the numbers generated by the program. To demonstrate, I've generated this keypair just now:

  Public: 914984079037409997753646956896411367020716296641338957641608068567317657086975832590795630339277510788727851945111403187181412830140879040014025475367233381190196941804342169193880920240279264797993403702890997094738006766532630568999

  Private: 2502644320274784300686027905786577204651695824856428916800576785188468831099194056968432976701679611038222704877942453351051289674522482331865454722815092306

  And encrypted a random key to get this ciphertext: 31156599101993645275226400017248608173867507193910625562695392661378570296553738808446028840212848623662312900007512235634449530713883849145685393866636831069585880990434485646285032107701202733953935100342846543008476824530843873800801
  (The random key was: 101020355786439301914818388108389342468906297672328361246394394849844032365586)

  Then I entered this into the command line by hand (the flag -a svp tells fpLLL to act as an SVP oracle):

  ...:~\$ ~/codes/fplll/fplll/fplll -a svp

  $\begin{pmatrix} 1 & 0 & P_i  \\
0 & 1 & K_i  \\
0 & 0 & C_i
 \end{pmatrix}$

  [values taken out of the matrix for readibility and horizontal space saving] with
  $P_i=$90539821999601667010016498433538092350601848065509335050382778168697877622963864208930434463149476126948597274673237394102007067278620641565896411613073030816577188842779580374266789048335983054644275218968175557708746520394332802669663
  and
  $K_i=$914984079037409997753646956896411367020716296641338957641608068567317657086975832590795630339277510788727851945111403187181412830140879040014025475367233381190196941804342169193880920240279264797993403702890997094738006766532630568999
  and
  $C_i=$31156599101993645275226400017248608173867507193910625562695392661378570296553738808446028840212848623662312900007512235634449530713883849145685393866636831069585880990434485646285032107701202733953935100342846543008476824530843873800801

  fpLLL short vector output:

  [203453603089198469384658317783196545918051882397653184390372945748471804449, -20132211511540947010614907531449286044959891949349819581130241666199997596098,  101020355786439301914818388108389342468906297672328361246394394849844032365586 ]

  Which is of the form: [-modular_reduction_value, -s_value, plaintext] which correctly recovers the plaintext 101020355786439301914818388108389342468906297672328361246394394849844032365586 as well as the random s value used during encryption.

  As for parameters that foil this attack, I found that the lattice starts to contain many unrelated short vectors if either s or e are increased in size by around 16 bits, but this causes the lower 16 bits of the shared key to be corrupted, and these 16 bits can be searched by brute force...

Conclusion

So as you can see, it seems like the real question is "with what parameter sizes is $ab + e \bmod P$ hard to invert?", and we basically happen to have a question about that here.

However, it looks like in order to really quantify that, we have to know what problem the cryptosystem reduces to (if any); Then, we can find out what the most efficient algorithms for solving that problem are and how they scale, and use that information to select secure parameter sizes.


Fiat-Shamir transform: reliance on hash input by interactive proof Peggy would like to prove to Victor that she knows the discrete logarithm of $y$ based $g$; that is, she knows $x$ such that $y = g^x \bmod p$. One round of the interactive proof protocol consists of the following steps.

Peggy picks random $k \in \mathbb Z/(p−1)\mathbb Z$, computes $t = g^k \bmod p$, and sends $t$ to Victor.
Victor picks random $h \in \mathbb Z/(p−1)\mathbb Z$ and sends $h$ to Peggy.
Peggy computes $r = (k − hx) \bmod (p − 1)$ and sends $r$ to Victor.
Victor verifies that $t = g^r y^h \bmod p$.

The interactive protocol can be converted into a noninteractive zero-knowledge proof by choosing and making public a collision-resistant hash function $H$, and changing the second step of the interactive protocol to the following: Peggy computes $h = H(y, t)$. Then the noninteractive proof consists of $(t, h, r)$, which can be verified as follows: $$h = H(y, t), \qquad t \stackrel?= g^r y^h \bmod p.$$

What is the problem if in the non-interactive proof the hash $h$ depends only on $y$? That is, $h = H(y)$, and the proof consists of $(t, h, r)$, which can be verified as follows: $$h = H(y), \qquad t \stackrel?= g^r y^h \bmod p.$$
What is the problem if in the non-interactive proof the hash $h$ depends only on $t$? That is, $h = H(t)$, and the proof consists of $(t, h, r)$, which can be verified as follows: $$h = H(t), \qquad t \stackrel?= g^r y^h \bmod p.$$

I think you have the verification of Fiat Shamir wrong. The proof consists of $(h,r)$ and $y$ which is public anyway and only the relation $h = H(y,g^r y^h)$ is checked. As a result in your first case the proof is trivially valid. Your second case is interesting as it is not secure against an adaptive adversary. There is a paper by  David Bernhard, Olivier Pereira and Bogdan Warinschi on this issue which considers its applications to e-voting as well. Please take a look  at https://eprint.iacr.org/2016/771 page 6.


Can GCM be used in incremental mode? I want to sync blobs over the network and the most frequent change will be appending to blob. To minimize data amount sent I would prefer to encrypt appended data, send it over the network, append to encrypted blob and then decrypt whole blob at once when needed. Changes are very frequent and small, so storing each change independently possibly will have some performance issues.

Can I store counter along with blob and append to encryption using GCM with stored counter value (assuming it won't overflow/reset counter, which is obviously insecure)? Would GCM still provide authentication? Will this construction be secure (assuming correct implementation and key/IV selection)? What other options do I have?

P. S. I imagine this is easy done with CTR mode or any stream cipher, but they won't provide authentication.

I don't see any obvious way to do this without violating the security of GCM; at least, if you are at all concerned with an evesdropper (and if you're not, why are you encrypting at all?)

Here is a distallation of your requirements: you want to have the sender send the ciphertext (including nonce, ciphertext and tag).  Then, you want the sender to be able to send the edits to the ciphertext; the receiver applies these edits to its copy of the ciphyertext.  Then, the receiver decrypts this editted ciphertext, it gets an editted plaintext (and the editted tag authenticates if nothing was modified by a third party).  In your case, the edits to the plaintext are appending arbitrary texts; that's not important for this analysis.

However, one of the requirements for GCM is that you never allow an attacker access to two different ciphertexts generated with the same nonce/key pair.

So, if the modified ciphertext uses the same nonce (and key), then this is an obvious violation; someone listening into the exchange will gain the original ciphertext, and the editted version; that allows him to deduce the internal 'H' value (and thus allow him to generate his own ciphertexts).

On the other hand, if the modified ciphertext uses a different nonce (or key), the keystream used to encrypt the plaintext changes; the two keystreams are (one hopes) computationally indistinguishable from random, and so any edit will not be more efficient than just producing a new ciphertext to replace the old one.  Obviously, this would not meet the spirit of your requirements.

So, it appears that what you're trying to achieve would not be doable with GCM.

However, it turns out that, if you are not concerned with evesdropper, you could actually incrementally recompute the tag; I won't go into the details (in part because, as I said above, it generally is a bad idea).


Proof of RSA security dependent on public key exponent I am writing a (high-school) paper on the public key exponent's (in textbook RSA - no padding is discussed!) significance in terms of time and security. The time part is done; as for the security part, so far I have shown example of various attacks that can take place when the public key is low (e.g. $e$ root attack, Håstad Broadcast Attacks etc).

My question is: Is there a way to mathematically justify that there is no way to prove that the security of the system lies in the value of the public key exponent?

I have also done some readings on the integer factorization problem whose intractability cannot be proven - can I relate this to the link between security and the public key?

Loosely define the RSA problem as solving for $x$ the equation $c=x^e\bmod N$, with $x$ random in $\{0,1,\dots,N-1\}$ (or equivalently $c$ random in this set), and $(N,e)$ properly chosen. The best method we know for tackling that problem is factoring $N$, but we have no proof that there is no substantially better method.

We do not know if the RSA problem is more difficult when $e$ is small (e.g. $e=3$), or large or/and random, or even have expert consensus on that research topic or what should be done in practice (I'm in the league favoring good padding with $e=3$ at least when speed matters, and reluctantly bowing to $e=65537$ to avoid conflict with official advice); much less do we know if it is possible to make a proof in either direction.

We do not know an efficient integer factorization method (that is one with effort growing polynomially with the number of digits in the number to factor); and I doubt that there is a proof or even argument that such an algorithm can not be found, for integer factorization is not in Wikipedia's list of known NP-complete problems.


Zero Knowledge range proof I like the idea of a Zero Knowledge range proof. But I read that, to prove my age in a range, a commitment is required by a trusted party (TP) stating my age. How does that work? is the commitment a certificate from the TP?

Also, if I need a user “A” to prove to the verifier his current location (longitude, latitude) in a range without stating the exact location, can the zero knowledge range proof be helpful in that problem? Who should commit to that secret (in This case, user “A”'s current location) so it should be accurate? Can the TP be a trusted timestamped service or Google?

Yes, you need a commitment. The commitment comes from anyone who is trusted by the verifier to commit to genuine data. So to prove age, the date of birth, say seconds from epoch could come from a government issued ID. In case of lat-long, a location provider trusted by the verifier should be used so if verifier trusts Google.

There is vast literature and implementations and they provide varying guarantees like if you provide a proof to the same verifier twice but use the same commitment, the verifier will know that he has interacted with you before or not. Depends if you care about this or not. Regarding how they work, there are several techniques, a recent and popular is Bulletproofs. Another is this paper.


As fgrieu pointed out, the constants are defined in terms of a binary Linear Feedback Shift Register. Because LFSRs can be represented very efficiently using standard logic gates they have been used for pseudorandom number generation computers for decades. They have fallen out of favor for use directly as secure stream ciphers due to advances in cryptanalysis. But the round constants for Keccak are not being relied upon to provide all the properties of a cryptographically secure pseudorandom generator.

By defining them in this way, the designers of Keccak achieve a few things:

NIST specifically asked for functions for which the number of rounds could be extended. This definition of round constants provides an unlimited supply should more rounds need to be added later.
The constants are efficient to implement as an LFSR in hardware. You don't have to embed a table in ROM with 2304 bits of square and cube roots like SHA-2.
Because the constants work out to be mostly zeroes, an fully unrolled pipeline implementation could possibly be even a bit more efficient than a LFSR for every stage. Super-linear scaling FTW.
The designers show that they have not hidden any subtle weaknesses into the choice of round constants because there is not enough information content there to conceal one. NIST has had problems with this in the past: http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
The designers stake out the claim that the security of Keccak is not heavily dependent on having perfectly statistically unbiased round constants. This may sound petty, but saving your peer reviewers from needless unproductive discussions in advance seems to be a direct benefit to public cryptanalysis. It seems to have worked for Keccak anyway.

What's really fascinating is just how closely related all these reasons become under information theory. http://en.wikipedia.org/wiki/Algorithmic_information_theory


How does order-preserving encryption work? Order-preserving encryption (OPE) is, apparently, a method of encrypting data so that it's possible to make efficient inequality comparisons on the encrypted items without decrypting them.

I've been coming across this term in various places (including here) lately, but I have no idea how such encryption schemes are supposed to work.  Any obvious methods I can think of to allow such comparisons on encrypted data would result in catastrophic security failure.

Certainly, I assume that OPE must involve some kind of security tradeoff compared to traditional encryption, but given that it seems to be actively studied and used, it seems that it must be possible to implement in a way that retains at least some level of useful security.  I just don't see how.

Given that a quick Google search didn't turn up any convenient Wikipedia articles or other popular summaries of OPE, I figured I'd try asking for one here before diving into the academic literature.  (At worst, I may try to answer my own question later, if nobody else beats me to it.)

So, to summarize, my question is: How does order-preserving encryption work, and what security properties does it provide?

In the last couple weeks I've become pretty well-acquainted with the recent work in this area. I also built a prototype order-preserving encryption scheme following the algorithms presented in 'Order-preserving Symmetric Encryption' by Boldyreva et al. I'll take a stab at explaining the method I just implemented, which requires some understanding of discrete probability and the hypergeometric distribution.

Let $M$ and $N$ be two positive integers such that $M < N$. Start by considering a random order-preserving injective function from $[M]$ to $[N]$, where $[M] = \{1, 2, ... , M\}$ and $[N] = \{1, 2, ... , N\}$. Now, choose $M$ elements of $[N]$ randomly and put them in order. Our injective function $f:[M] \to [N]$ is simply this ordered set. To encrypt $i \in [M]$, just output the $i$-th element of this list. Obviously we can't use this as a real encryption scheme, we might need to randomly generate billions of numbers! So how do we proceed?

We proceed by noticing that we don't need the whole function in advance. If we could figure out a way to only generate an element of the ordered set when we need it as a ciphertext, we'd be hunky dory. This is called lazily sampling the function. To lazily sample our proposed function, we first need to look at the range space a bit differently.

Let's stick with our random order-preserving injective function $f$, which we're thinking of as an ordered list of elements of the range. Think of an element of the range as 'marked' if it's in the list and 'unmarked' if it's not. Now think of all the elements of the range, marked and unmarked, as being balls in a giant bin. If we draw balls without replacement, the number $x$ of 'marked' balls we've drawn after $y$ samples can be characterized by the hypergeometric distribution. The HGD has PMF $$\frac{\binom{y}{x} \binom{N-y}{M-x}}{\binom{N}{M}}$$
If you don't know what a PMF is, don't sweat it. All we really need to understand is the connection between OPFs and the HGD, which is that we can figure out how many points of our OPF lie below a given point of the range by treating the range point as the number of 'samples' in a hypergeometric experiment where the number of marked balls is $M$ and unmarked balls is $N-M$.

Also important to know is that we can efficiently and deterministically sample the HGD, i.e. given $y$, $M$, $N$, and some random coins $cc$ we can always generate an $x$ that describes the number of marked balls in our sample of size $y$.

We're close, I promise. We have the groundwork laid, we just need to figure out how to get an encryption scheme out of this.

Our encryption scheme follows fairly naturally from the above. Given a plaintext $m \in [M]$ and a key $k$ we can lazily sample our OPF and produce a ciphertext $n \in [N]$ by recursively searching the domain and range like so:

Start with the entire domain $[M]$ and range $[N]$. Call $y \leftarrow \frac{N}{2}$ our range gap. Now using our key $k$ we generate some pseudorandom coins and give them to our HGD sampling routine along with $y$, $M$, and $N$. This gives us an $x \le y$ that describes the number of points of our order-preserving function less than $y$. Call this $x$ our domain gap. Now because the $m$-th point of our OPF is the ciphertext of $m$, we know that if $m \lt x$ we need to recur on the points of the domain less than or equal to $x$ and less than or equal to $y$. If $x \lt m$, we recur on the points of the domain greater than $x$ and $y$. When our domain only has one point remaining, we'll have as our range a set of points in which our ciphertext can reside. Pick a point of this set and output it.

So after all that, it's just a fancy binary search??? Kinda, yeah. If you want to know all the messy details and how to actually make it secure, read the original OPE paper or look at the CryptDB implementation. My java implementation will also be open-sourced sometime soon, so you might check that out as well.

Order-preserving encryption has several caveats. To know all the details, read the follow-up of Alexandra Boldyreva, Nathan Chenette and Adam O'Neill's Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions (in proceedings of CRYPTO 2011, or full paper here). It analyzes the security of a random OPF and characterizes its leakages. Their most glaringly problematic result has to do with an adversary's ability to guess approximately where the underlying plaintext of a ciphertext lives in the plaintext space. Intuitively, it says that certain attackers can learn half the bits of a plaintext given its ciphertext. For certain applications this trade of security for functionality is acceptable, but in any case it's important to know what you're getting when you use these schemes.

Post a comment if you want something clarified in the above, I'll try to make a cogent edit.


How to design a practical and secure MAC scheme? I am sorry, but I need to introduce some concepts which are not directly related to cryptography to make myself clear, I hope I won't stun you with this ... (I'd rather explain  it here than redirect the reader to an even more stunning external link ;) )

UBI Properties

I am working on Flash memory devices. These devices are divided into blocks of a quite significant size (from a few kilobytes to a few megabytes). The blocks, called eraseblocks, have a major property : they wear out. Once data has been written to a specific location within an eraseblock, the whole block must be erased to overwrite this data.
This erasure operation can only be performed a finite number of times before the block becomes worn and unusable (this number varies between 103 and 105 on nowadays chips).

Multiple solutions handle this problem, by reserving some space at the beginning of each block to manage them. UBI (Unsorted Block Images) is one them and is the one I am currently using. UBI writes two header fields at the beginning of each block which contain some information about it and extra things that it needs to manage the blocks. Among these things, a few are worth to mention :

A 32-bit long logical eraseblock number
A 32-bit long volume ID
A 64-bit long sequence number

UBI can divide the Flash memory in partition-like entities called volumes. Each volume has an ID (volume ID) and a size expressed in eraseblocks. The blocks of a volume are numbered from 0 to this size limit (this is the logical eraseblock number). UBI makes a difference between a logical block (LEB) and a physical block (PEB). The former is a block of a volume and the latter is the physical block on the memory device itself on which is written the logical one. For instance, the block numbered 0 of the volume numbered 0, i.e. LEB(0,0), can be stored in any PEB at a given time, say PEB(10). UBI moves these logical blocks to various physical ones for an efficient wear-out management. Since some bad things can happen, any time UBI has to map a specific LEB to a PEB (by writing the block headers in the targeted PEB) it updates a global sequence number which is integrated in one of the headers.

Encryption concerns

I want to perform on-the-fly encryption when reading or writing to the memory. I already have the pure encryption pattern. It involves AES-128 encryption on a UBI volume basis.

Now, I want to combine it with a MAC scheme in order to authenticate that the data on the flash was not forged. The thing is : how can I cook up a reliable scheme for this purpose ?

Here are my thoughts on this subject : using HMAC-SHA1 (eventually truncated for memory space constraints), I can produce a tag that authenticates a given PEB(p) < - > LEB(v, l) mapping, using the encryption key K for the volume v. The tag should be produced in this way

  HMAC-SHA1(v | l | sqnum | p, K)

This pattern has some advantages :

It is easy to compute to perform checking operations
It prevents a malevolent user to corrupt the volume with any other method than the two following : erasing the physical block p or overwrite the physical block p (which involves erasure of the block), which can only be performed up to 105 times.

I came up with this design because I find it practical for the uses of UBI I am making, but I have no idea of the security flaws it might introduce or solve in the whole thing.

Actually, I have a few questions. First, is my design safe ?
And in any case, what would you suggest ?
I am aware that last one is quite an open question, but I think there might be existing patterns that could be customized to fit my use case.

There are many ways to authenticate the contents of the disk.  The way you have described is reasonable, if you have a way to store the global sequence number in an authentic way (so it cannot be tampered with).

Another general approach is to look at the data structure that is maintained by the UBI to map from logical block numbers LEV($v,l$) to physical block numbers PEB($p$).  Then, add a MAC on all entries of that data structure, and when you read the data structure, verify the MAC.

Also it might help to use tweakable encryption to encrypt each block, with the tweak set based upon the block numbers.

Broader comment: I think you should start by reading about full disk encryption (FDE) in general.  I don't see anything here that is terribly different from the issues facing FDE on magnetic hard disks.  Here are some good starting references:

Disk encryption theory, particularly its discussion of tweakable encryption.
IEEE P1619/D16 - Standard for Cryptographic Protection of Data on
Block-Oriented Storage Devices
And, these three research papers on disk encryption
Do Flash memory (SSD) architecture impacts encryption techniques?

Do note that many full disk encryption schemes provide only confidentiality, not authenticity, so you'll need to go beyond what those schemes offer.

P.S. One last comment: you are forming the input to your MAC by concatenation.  This is fine if all of the fields are fixed-length values, but if they are variable-length, you may be at risk of a concatenation attack.


HMAC with secret hash constants An HMAC depends on the Message, Key and the Hash function used such as SHA-256, SHA-512, etc.

Consider if the computation of the MAC used a different set of Initial hash values or initial array of round constants.  Instead of the "first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19", the first 8 primes 8675309 onward or similarly random non-trivial set of bits are used.

It appears that those values are not special, other than they should have little correlation.  The usual specified values are well tested, unlike the discussed different sets.

A similar post addresses some impact, yet I'd like to go one step further.

Suppose these different Initial hash values (IV) and initial array of round constants are kept secret, otherwise the MAC is computed as usual.

  What would be the negative authentication impact of exposing the secret cryptographic key of the HMAC in this case?
  Is the key still needed?

Here it helps to understand the history, internals and rationale for HMAC and Merkle-Damgård hash functions in a bit more depth.  In the M-D construction, the IV is used as the chaining argument to the compression function when processing the first block of the message.  What you are proposing to do is to put that IV value under user control, so that users may plug in a secret key instead.

The point of the HMAC construction is to achieve the functional equivalent of that indirectly, by prepending a block with the key (XOR'ed with a pad) before processing the message.  The hash function's fixed IV and the secret key block will be fed to the compression function, producing a new state that, from your point of view, you can think of as a derived secret key that then serves as the chaining value to hash the rest of the message.  When HMAC starts processing the actual message, the state of the hash function is the same as if you'd fed that derived secret key to the hash function as a user-selected IV.

In fact, if you look at the original HMAC papers, you'll notice that HMAC's security is analyzed in terms of something called NMAC, which is a construction using hash functions with user-controlled IVs.  HMAC is a practical improvement over NMAC with these advantages:

When HMAC was invented (and still today!), there were lots of legacy code bases and libraries that did not allow user control of the hash functions' IVs.  Therefore, HMAC can be implemented without modifying legacy libraries.
Allowing the user of the hash function to control the IV would, more likely than not, lead to people abusing it by supplying a secret key as IV and expecting it to behave like a secure MAC, leaving them vulnerable to even more length extension vulnerabilities.  A cryptographic API really should guard against misuse, and offer a secret-key MACs and public hash functions as different interfaces that accept different arguments.
NMAC requires two separate keys, one for the inner hash function and one for the outer.  HMAC uses just one user-supplied key to internally derive the two NMAC keys (that's what the ipad and opad values are used for).


Why not put MAC in fixed position and cover padding for MAC-then-encrypt? The biggest problem with using MtE with a mode where it's known to be secure (CBC) is with the padding, where you can't retrieve the authentication until you know where it is by looking at the padding bytes.

Instead, why not just place the MAC at the very end of the last block, and include the padding bytes in the calculation of the MAC?  Verify the MAC before even looking at the padding or anything else in the message (other than to calculate the MAC, of course).

The padding algorithm would simply have an argument telling it how much space to reserve after the padding for a MAC, either 0 if using EtM, or the space for the tag if using MtE.

Then process the MAC over the message plus added padding, and store it in the reserved area.  Are there any padding schemes which do this?

You scheme, let's call it pad-MAC-encrypt, would indeed fix any padding oracle attacks against MAC-pad-encrypt.

The reason it isn't used is probably that padding oracle attacks weren't known when CBC schemes were initially defined and now that they are known, there doesn't seem to be a convincing use case for CBC. Other modes have advantages over CBC anyway (no requirement for unpredictable IV, easier parallelizability). If you do need CBC for some reason (like backwards compatibility), you can just use encrypt-then-MAC which is simple and well understood.

I.e. rather than asking why it is not used, you should be asking what the advantage is over other safe schemes.


Create a field in PBC Edited (I removed the emphasize on Integers):

My question is partly cryptography and partly programming, I would appreciate any help on any aspect of it :)

I want to use PBC library to do the following operations:

Create a finite group, with "my custom" order ($Z_q$).
Choose a random value $g$ from this group.
Compute $g^r$, where $r$ is a random integer.

I tried to make the above work but I could not figure out to relate a finite group of my choice to this notion of pairing-based cryptography with no avail!

EDIT: Some more info on my problem:

In its simplest form, what I want to do is to choose $g$, $r_1$, and $r_2$, compute $g^{r_1}$ and $g^{r_2}$. To confirm the computation, I will later compute $g^{r_1+r_2}$ and compare it with multiplication of the previous values.

How can I achieve this in PBC?

I point this out because a fair number of practicing cryptographers aren't aware: PBC is slow and outdated and a pain to work with. MIRCAL and RELIC are the two main alternatives.


Is there a developer's resource that ties encryption methods and strengths to the appropriate usage scenarios? I'm not looking necessarily for implementations in any language (although it would help to list those resources as well), but what I am most interested in is a discussion of what advantages and disadvantages certain encryption methods have when applied to a given scenario. Just for a frame of reference:

I want a user to enter a username/password that will be stored in a database.
I want to encrypt a PDF file and send it to a friend and have her decrypt it.
I need to encrypt a small amount of plain text and have someone else decrypt it.

I'm sure there are better examples, and there is sure to be some crossover, but it seems like much of the time spent on encryption is deciding what is the best method given the variables or scenario involved. Is it a one way hash? Do others need to decrypt it? Am I the only one to decrypt it? Is it binary or text? Are there file size limits? Is it stored, or sent over a network?

Start with NIST Computer Security Division:

FIPS (Federal Information Processing Standards) specifies multiple use scenarios in their Publications and Special Publications, many of which include the type of scenarios on your short list, as well as related scenarios. These are primarily for federal use, but if your use case matches that of the government their publications will apply.

Additionally, there are numerous books, including one called "Cryptography for Developers", which goes more into the application development side of implementing cryptographic systems. Niels Ferguson and Bruce Schneier of the Twofish team have written several books on practical design and implementation of cryptosystems that focus more on the cryptography side of things.

For more of of an open discussion try the sci.crypt newsgroup, where you can specify a specific scenario in detail and engage in debate; there are also other moderated locations to do this as well.

Hard as I try not to do the "list/recommendation" answer, thats kind of how it turned out, there really is not a better way to answer that broad of a question, individual questions on specific scenarios that are not answerable by the wiki/google method will provide more specific answers.


Can one hide a text in an image and then hide that image in another image? Using a steganographic algorithm like least significant bit, can one hide a text in an image and then hide that image in another image?

Yes!

For bitmap images, if you use all the pixels of the image (bad idea, it's very detectable) you need a first image 8/3 times bigger than the size of the text you want to hide (you can compress it).

8 because you need 8 pixels to hide one byte (one bit per pixel).
1/3 with color images, because you can hide a bit per channel/pixel.

After this, you can hide this image into another image 8 times bigger (again, 1 byte into 8 pixels).

For JPEG images the approach is different, because you are hiding information into the DCT coefficients. But it's the same idea.


No way to do ECDH with OpenSSL from the command line? I've scoured this website and the OpenSSL wiki pages, and done numerous internet searches, and I've come to the seemingly incredible conclusion that one cannot generate an ECDH shared secret key using a given public key and a given private key from the openssl command line. There is at least one other post on this web site that claims you can, without providing an example.

I know the wiki does provide 'C' code examples, but my use case is such that having the command line capability would've been much preferred.

If anyone can kindly disabuse me of this notion by providing an example, I would surely appreciate it.

Here's one way to do roughly what you described:

openssl genpkey -out alice.pem -algorithm EC \
  -pkeyopt ec_paramgen_curve:P-256 \
  -pkeyopt ec_param_enc:named_curve
openssl pkey -pubout -in alice.pem -out alice.pub
openssl genpkey -out bob.pem -algorithm EC \
  -pkeyopt ec_paramgen_curve:P-256 \
  -pkeyopt ec_param_enc:named_curve
openssl pkey -pubout -in bob.pem -out bob.pub
openssl pkeyutl -derive -out alicebob.key -inkey alice.pem -peerkey bob.pub
openssl pkeyutl -derive -out bobalice.key -inkey bob.pem -peerkey alice.pub
cmp alicebob.key bobalice.key

But, who knows whether this implements a secure DH system?  You should really consider using X25519, e.g. via NaCl crypto_box, rather than stringing together generic OpenSSL incantations like this.


What if we increase the key length of DES and use ECB Mode, then will we get the different output as ECB mode encrypt with the same key? I am looking for an answer as if we have DES having 64 bit key and we are encrypting an image it with ECB mode but it doesn't encrypt well. so if we change the key length then will it effect the output or not?

Increasing DES's key size (by using 3DES instead) won't mitigate at all the weaknesses of ECB mode. That's because the block size in unchanged, and the same identical blocks in plaintext will remain identical blocks in the ciphertext. See Wikipedia's illustration for what that can imply for raw bitmap images.

To some small degree, using a block cipher with a larger block size, such as AES, will give some level of mitigation (e.g. when enciphering a raw bitmap image, it will be less recognizable). But that's very partial (doubling the image's resolution will more than offset the mitigation).


Perfectly secret cipher can leak about the key? As defined by Shannon, a cipher is perfectly secure if ciphertext leaks no information about the plain text.

Under this definition, can ciphertext leak something about the key? Are there any ciphers for which this is true?

mikeazo's answer clearly covers what the question asks. However, I want to go further and answer this:

How much information does a perfectly secure cipher leak about the key?

Exactly all the excessive information of the key that does not help in finding anything about the message.

In simple words: if the key length is $k$ bits and the message is $m$ bits long then in case of a perfectly secure cipher by knowing the ciphertext you know exactly $(k-m)$ bits of the key.

Formally: By knowing a ciphertext which is ciphered using a perfectly secure cipher the uncertainty about the key is exactly equal to the uncertainty about the message.

Or using entropy function:

$$H(K|C)=H(M)$$

Where $H(K)$ is the entropy of the key, $H(C)$ is the entropy of the ciphertext, and $H(M)$ is the entropy of the message.

The equation above can be deduced from the following equations:

$H(M)=H(M|C)$, $H(M|C,K)=0$


ISO 9797 MAC algorithm 3 for 7 bytes I should implement ISO 9797 MAC algorithm 3 with initial transformation 1, without truncation, and using DES as a block cipher.
I should add padding of 0x80, then enough zero bytes if the length is not multiple of 8.

I want to know what will happen if data is only 8 bytes?

I should feed data directly to 3DES algorithm or I should first feed it to des then feed to 3DES?

I want to know what will happen if data is only 8 bytes?

If the data is already 8 bytes then you need an additional block that contains 8000000000000000 (15 0s) since the Padding method 2 is mandates adding 1 and necessary 0's.
Note that the Padding Mechanism 2 is not byte-oriented, it is bit-oriented. Whenever the data finishes you add 1 and add necessary zeros in minimal so that the data size is multiple of the chosen block cipher.

for 7 bytes

In this case, you just add 0x80. 7 zeroes are added after 1 to fit 64.

I should feed data directly to 3DES algorithm or I should first feed it to DES then feed it to 3DES?

This MAC is as known as

ANSI Retail-MAC
CBC-MAC-Y or
ISO/IEC 9797-1 algorithm 3.

With the DES it is also called the DES Retail MAC and uses two keys $K$ and $K'$.
Firstly it works as DES-CBC then the output performed like 3DES in Encrypt-Decrypt-Encrypt with two keys on the last block x-ored with $H_{q-1}$. One doesn't need a 3DES implementation to achieve this.
\begin{align}
H_1 & = e_K(D_1) \\
H_i & = e_K(D_i \oplus H_{i-1}), \quad (2 \leq i \leq q)\\
MAC & = e_K(d_{K'}(H_q)).
\end{align}
If we re-write the equation
\begin{align}
H_1 & = e_K(D_1) \\
H_i & = e_K(D_i \oplus H_{i-1}), \quad (2 \leq i \leq q-1)\\
MAC & = e_K(d_{K'}(e_K((D_q \oplus H_{q-1}))).
\end{align}
The Triple-DES (EDE) will appear in the end.
The attacks on DES Retail MAC
The attack on DES Retail MAC formalized as four tuple $[a,b,c,d]$ where

$a$ is  the number of offline block cipher encipherments
$b$ denotes the number of known data string/MAC pairs
$c$ denotes the number of chosen data string/MAC pairs
$d$ denotes the number of on-line MAC verifications, and
$k$ is key size
$n$ is the block size
$m$ is the zeros of padding.

On 1996, Preneel and Oorschot achieved  $[2^{k+1},2^{n/2},0,0]$ on
Key recovery attack on ANSI X9.19 retail MAC
On 1998, Knudsen and Preneel achieved $[2^k,1,0,2^k]$ on
MacDES: MAC algorithm based on DES
On, 2002 Mitchell achieved $[2^{k+1},0,0,(\lceil n/m \rceil +1) 2^{(n+m)/2-1}]$ on A new key recovery attack on the ANSI retail MAC

Therefore, if there is no specific usage, don't use it.


How small can the error be in LWE? For modulus $Q$ and stddev $\sigma$, [GHS12] suggests that, to achieve 128-bit security, just choose the dimension $N$:
$$
N\geq(Q/\sigma)\cdot 33.1
$$
This seems to suggest flexibility to choose smaller $\sigma$ ("as long as it is not too tiny"), but just paying a price on $N$.
Many instantiations seem to favor a fixed $\sigma$ about $3.2$ ([GHS12]). Especially, the homomorphic encryption standard said:

The standard deviation that we use below is chosen as $\sigma = 8/\sqrt{2}\pi \approx 3.2$, which is a value that is used in many libraries in practice and for which no other attacks are known. (Some proposals in the literature suggest even smaller values of $\sigma$.)

There are schemes using a smaller $\sigma$. Frodo is looking at approximating $\sigma\approx1$.
My question:
In my use case, I do need the noise to be very small.

Can one do $\sigma\approx0.1$?
If not, how small can $\sigma$ be, if one needs to minimize it?
Is it because we need to approximate continuous Gaussian, so $\sigma$ can never be too small?

Note that $\sigma\approx 0.1$ seems unreasonable, since, with a high possibility, all sampled values will be zero (by making it an integer). And [GHS12] mentions explicitly that the $N\geq(Q/\sigma)\cdot 33.1$ check does not apply to "too tiny $\sigma$", although the paper did not explicitly mention what is considered "too tiny".
Yet, the LWE estimator seems "okay" with $\sigma\approx0.1$. I guess small $\sigma$ is beyond the scope of the LWE estimator?

Per Mark's suggestion, I looked into the "hidden" tests in lwe-estimator and read a few papers. I summarized my findings as an answer here:

Arora-Ge attack, and the improved version using Grobner bases, work better when $q$ is small, but it starts to be impractical once the number of samples $n$ and $q$ is very large, e.g., $q=2^{64}$. This seems to be due to the time needed for linearization.

Another hidden test, MITM (Section 5.1 in https://eprint.iacr.org/2015/046.pdf), can be useful here---MITM considers $\alpha q$, and it is important that $\alpha$ cannot be way too small. Reflected in lwe-estimator, this would disallow one to use $\sigma\approx0.001$.

Still, more discussion is welcome. For my own use case, it seems that $\sigma=1$ or $\sigma\approx0.8$ may be generally okay since my $q$ is large.


Understanding need for PKI For simplicity let's say I only have RSA and AES on my hands and I want Alice to talk with Bob over a secure channel. With secure I am implying no MITM and Alice and Bob know they are talking to each other and not someone else.

When Alice wants a secure channel with Bob, Alice will ask Bob for his RSA public key, sign a randomly generated AES key with her RSA private key, encrypt the signature and AES key with Bob's RSA public key and send this to Bob. Bob will ask Alice for her RSA public key, will decrypt the signature and AES key with his own RSA private key and verify the signature with Alice's public key. Now Alice and Bob can use the AES key for further communication ...

Am I correct that the part where Alice and Bob exchange their public keys is a potential MITM vector? How can Alice be sure she got Bob's public key and vice versa? Is this what PKIs primarily solve, as in Alice and Bob trusting a third party upfront that - for example - signs their public keys? Or am I missing the point completely and everything of the above is bogus?

Your understanding is correct. PKI would be the service that verifies that Bob's public key really belongs to someone named "Bob". As long as Alice trusts the certificate authority that certified Bob's public key, she can implicitly trust that the public key she sees really is Bob's, not Eve performing a MITM.

The internet is secured with web PKI, which is the network of Certificate Authorities that certify that a websites' public key really belongs to the domain it claims to belong to (for Domain Validation, or DV). It's far easier to trust a handful of CAs than it is to trust every single website you'll ever visit.


What's the maximum length for AAD in GCM? int mbedtls_gcm_starts( mbedtls_gcm_context *ctx,
                int mode,
                const unsigned char *iv,
                size_t iv_len,
                const unsigned char *add,
                size_t add_len )
{
    int ret;
    unsigned char work_buf[16];
    size_t i;
    const unsigned char *p;
    size_t use_len, olen = 0;

    /* IV and AD are limited to 2^64 bits, so 2^61 bytes */
    if( ( (uint64_t) iv_len  ) >> 61 != 0 ||
        ( (uint64_t) add_len ) >> 61 != 0 )
    {
        return( MBEDTLS_ERR_GCM_BAD_INPUT );
    }
}

Above is a part of the implementation of GCM (Galois/Counter Mode) by mbedtls.

The implementation puts a restriction on the length of AAD (additional authenticated data), that is, the length of AAD cannot be greater than $2^{61}$ bytes.

My questions:

Is there an actual limit on the length of AAD, or that's just an implementaion-specific restriction?
Theoretically, can I input an AAD of any length?

From the GCM specification:

  Additional authenticated data (AAD), which is denoted as A. This data is authenticated, but not encrypted, and can have any number of bits between $0$ and $2^{64}$ .