Encrypting small packets with low data rate I'm trying to build my own layer of encryption on top of our bluetooth communication. We can't use bonding because of some specific features we need to support. I'm a beginner when it comes to encryption, and so I wanted to run this by someone with more experience. Please look over my planned approach and point out any flaws or improvements:

Communication is between an iPhone and a bluetooth peripheral. At the start of any connection, the iPhone will generate a random public/private key pair. The public key will be sent to the bluetooth device.
The bluetooth device will generate a random symmetric key, encrypt it using the iPhone's public key and send it back to the iPhone.
All future communication will now be performed using the symmetric key for encryption/decryption.
A security passkey that is generated once for the bluetooth device and used to identify an authorized user is encrypted and sent from the iOS device to the bluetooth device. If the passkey is wrong, the connection is killed. If it is correct, the iOS device now has full access to the bluetooth device via encrypted packet communication. Each new connection will have a new private/public key pair and a new symmetric key.

Because packets are maximum 20 bytes and data rate is around 1200 bytes/second, I plan on encrypting packets using AES256 CTR encryption, as this has the advantage of the encrypted data being the same length as the original data.
Are there some flaws to my approach that I'm not aware of? Are there flaws with my plan to use CTR so the encrypted data is the same length as the original? Is there a better approach to accomplish what I want?
Edit:
I have a few questions about my specific use case.

I only need to keep the security passkey that is transmitted at the beginning of communications secret, as without that, an attacker wouldn't be able to do any sort of replay attack since new security keys are generated each new connection session. Is this flawed thinking?

Using Diffie-Hellman to generate a symmetric key, then using a stream cipher (CTR) to encrypt communication, would this be secure? Each packet would be encrypted with a new counter value (initialization vector) that would not be reused for the session, which would also be sent with the encrypted packet for decryption on the other end. My understanding is that this method would be perfectly secure as long as I never used the same initialization vector to encrypt two different packets. Is this correct thinking? My main purpose in wanting to use a stream cipher is so my encrypted data length is the same as the unencrypted data length.

Due to point 1 above, is it possible for me to safely get away with using the same initialization vector for all packets encrypted for the entire session, as the next session will have completely different symmetric keys, or will doing this open my protocol up to being decoded by an attacker, enabling them to aquire the passkey mentioned in point 1?

Edit2:
Based on comments by Thomas M. DuBuisson, I see that there are several issues with my approach that I hadn't thought of previously. One major issue being I need to make sure I have a solid random number generator on the bluetooth device. In light of the points he made, and after doing more research on how to securely exchange keys with a limited resource device, I thought of another approach that might be easier with the available resources, and I hope a little more secure.
Sorry for my lack of experience in this area, but I'm trying to learn what I can and hopefully not make any stupid mistakes.

in general, a widely used algorithm to exchange/set up session keys is Diffie Hellman. While exchanging public keys, during the process a shared key is generated, that could also be used to encrypt the communication, without additonal AES.

I do not know how deep your knowledge of asymmetric encryption is- generally, there are two(three) problems that are used. None of them are trivial- factorisation, discrete logarithms and elliptic curves, the latter often combined with the first two.

However, I'm missing out some details that would help- would you rather have a fast encryption (because in that case I would recommend an elliptic-curve based Diffie Hellman, as ECDH) or an easy implementation (standard DH). Is it important that the algorithm is CCA secure(DH is not). How high shall the security be- how much computation power do you have? Can the key of the IPhone change, or should it always be the same? It would also be helpful to know what kind of bluetooth device it is.

Another approach would be using one-time keys. The communication could be initiated by the bluetooth device, which has a storage of several keys that may only be used once- in this case to encrypt the session key.

Last but not least, CTR mode is considered less secure than other cipher modes of AES. Personally, I would recommend GCM for you- because I like it, and because it also provides authenticated encryption, and can be pipelined easily. It has a 128 bit block size. If you expect many errors, OFB could be useful for you... but that goes too far. If you clarify your question a bit more as I‘ve indicated, I can help you out further.


how to use common modulus attack? I am struck with the following problem:

Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus $n_B$ and $n_C$ respectively with $n_B$ = $n_C$ But different public encryption exponents: $e_B \neq e_C$. Suppose $\gcd(e_B, e_C)=1$, and that Alice sends the same secret message to Bob and Chris.
Show how Eve can decipher the message.

Think about this: what does it mean that $\gcd(e_B, e_C)=1$. Formally that means there exist some $s_1, s_2$ such that $e_Bs_1 + e_Cs_2=1$.

Say you have two ciphertexts (the following math is all done modulo the shared modulus), $C_B=M^{e_B}$ and $C_C=M^{e_C}$. You can do the following:

$$\begin{align}
C_B^{s_1}*C_C^{s_2}&=(M^{e_B})^{s_1}*(M^{e_C})^{s_2}\\
&=M^{e_Bs_1}*M^{e_Cs_2}\\
&=M^{e_Bs_1+e_Cs_2}\\
&=M^1\\
&=M
\end{align}$$


RSA: how does it work and how is it more secure than symmetric systems Before starting the question, I know that RSA is naturally a key exchange cryptosystem rather than an antilogarithm fully implemented for encrypting and decrypting data since the length of the secret data relies on the key size of RSA. Now, we know that RSA is asymmetric means it has a public key and a private key.I know that one should not be able to decrypt an encrypted key using RSA by the public key while the secret is decryptable by the private key. I've also read that (may be I'm confused and mistaken) the public key is calculated based on the private key.

Now I have some questions, when using this algorithm in C# using the cryptography namespace, we have to serialize and export the private members of the key (private key) to be able to decrypt the secret. So what is the purpose of the public key, how is it public at all, and how does it introduce a higher level of security to the algorithm.

Let's say I do the same using AES, then I'm gonna have two Keys (Key, IV) which are only shorter in size. Except for the length of key, how RSA is more secure than AES then. If I don't exchange the public key, what is the purpose of it, if I do but nobody can use it to break the secret then what is the purpose of it again?

With regards to the public vs private keys, in RSA, the public key is used to encrypt information, the private key is used to decrypt it. Given only the public key, all you can do is encrypt. So, you can publish that online somewhere (key distribution is a very different problem). Anyone can use it to encrypt a message to you and only you can decrypt it.

Think of it this way. You give your friend a padlock and a wooden box. The padlock is unlocked. Your friend can put anything they want in the wooden box, put the padlock on, and lock the padlock. Now, only you, who knows the combination, can get at whatever was place in the box. In this example, the padlock is the public key, the combination is the private key. Having possession of the padlock (the public key) should not easily reveal the combination (the private key).


Relation between Key-exchange and Public-Key encryption schemes Recently we have seen a lot of papers on Post-quantum key-establishment (key encapsulation mechanism or Key-exchange), largely due to the standardization call of NIST for PQ-protocols. However, most of the work for example : Kyber, NTRU-prime, NTRU-KEM focuses on key-encapsulation rather than Key exchange. Now my questions are as follows :

KEM is a unilateral protocol whereas key-exchange is a bilateral protocol. i.e key is chosen by the client and server gets the key via decryption. Intuitively bilateral protocols (FRODO and NewHope) looks better than the unilateral (KEM) protocols. As both the parties participate in choosing the key. Then why there is more focus on KEM?
Consider this scenario, if we assume that Key exchange establishes a random key on both sides then Client can pick up a random string XOR with the key and send the XOR'ed value to the server. Since, server has the same key, server can easily retrieve the random string of client. Hence, a key exchange can work as PKE (as ElGamal from DH) and subsequently as a KEM. This scheme will be CPA secure as by assumption the established key is random. Hence, Key-exchange can is more flexible than KEM. Is it correct?
I understand that the current key-exchange schemes have a very high failure probabilities than KEMs. And, Hence they can be converted to CCA secure schemes by well known BLack-box transformations for key re-usability. But if we can come up with Key-exchange schemes with similar failure probabilities as KEMs and able to convert them to CCA secure schemes then should we favour Key-exchange schemes more than KEMs?

I appreciate your help.

First, some definitions.

A public key encryption scheme (PKE) is a scheme with public and private keys, where we can encrypt a message using the public key and decrypt using the private key.
A key encapsulation method (KEM) is a scheme with public and private keys, where we can use the public key to create a ciphertext (encapsulation) containing a randomly chosen symmetric key. We can decrypt the ciphertext using the private key.
A key exchange protocol (KEX) is a protocol that allows Alice and Bob to agree on a shared symmetric key. A two-move KEX is a protocol where Alice sends a single message to Bob, Bob replies with a single message to Alice, and afterwards they both have the same symmetric key.

Next, some context.

Any PKE with sufficiently large plaintext space can be trivially turned into a KEM.
Any KEM can be turned into a PKE by adding some symmetric encryption. (This is often called hybrid encryption.)
Any CPA-secure KEM can be turned into a passively secure KEX. (Alice runs KEX key generation and sends the public key to Bob. Bob creates a ciphertext containing a randomly chosen symmetric key and sends it back to Alice. Alice decrypts the ciphertext and gets the symmetric key.)
Some passively secure two-move KEX can be turned into a CPA-secure KEM. (The process that leads to Alice's message is key generation. The public key is Alice's message. Alice's state after sending the message is the private key. The process that leads to Bob's message and the shared symmetric key (in response to Alice's message, that is, the public key) is key encapsulation, and Bob's message is the public key.)
A passively secure two-move KEX can be turned into an actively secure three-move KEX using digital signatures. (Bob signs both messages and sends the signature as part of his message. Alice signs everything and sends the signature as the third message.)

In other words, these notions are tightly related. (There are lots of details and simplifications in the above, but morally, it should be roughly correct.)

Now to your actual questions (which are a bit unclear, but let's make an attempt at answers).

Compared to traditional PKEs like RSA-OAEP, designing a KEM and proving it secure is often easier. Likewise, compared to traditional key exchange schemes, designing a KEM and proving it secure is often easier. Then we can turn the KEM into a PKE using hybrid encryption, and we can turn it into a KEX with a standard conversion theorem. This is why KEMs are attractive objects to design and study.
Your sketch seems fundamentally similar to the above two-move KEX => KEM argument. However, that doesn't mean that a KEX is easier to design and analyse (from scratch). Experience suggests otherwise.
The traditional definitions of PKE, KEM and KEX doesn't allow the process to fail in the usual case. For traditional schemes, this has always been easy to guarantee. For newer schemes, this does not seem to be the case. Typically, there's some probability that things will go wrong (decryption failures). This makes analysis much more difficult, but not impossible (as NTRU shows us). Still, I don't think the presence of decryption failures changes the fact that KEM design and analysis seems to be easier than KEX design and analysis.


Replacing the PRF in PBKDF2 with Keccak I am unable to find a reliable, tested library for a decent password based key derivation function e.g. Scrypt in the programming language I am using, but I have a reliable library for PBKDF2 (which by default uses SHA2-256) and it also allows me to replace the hash function to use Keccak-256 (C=512) instead.

Is there anything wrong with swapping SHA2 for Keccak for use in PBKDF2? For example, maybe Keccak is not designed for this usage?

Would it be considered a better PRF than SHA2?

I understand it's not a memory hard function, so not as effective as Scrypt in slowing down a serious attacker, however I can compensate for that by restricting password length to at least 30 characters and 100,000 or so iterations.

Is there anything wrong with swapping SHA2 for Keccak for use in PBKDF2?

There are 2 main issues. Performance and implementation.

Performance

The performance issue is from an attacker-defender scenario, where the attacker is able to provide FPGA or ASIC resources. In this scenario, Keccak is several times faster than SHA-2. I will use a Blake comparison for SHA-256, as they perform similarly. Both Blake and SHA-2 are ARX type hash functions.

STM 90nm ASIC
Keccak-256 = 33333 Mbit/s @ 51 Kgates, Blake-256 = 4763 Mbit/s @ 37K gates, a 7X performance advantage with a 37% area disadvantage, 5.1X overall advantage

UMC 90nm ASIC
Keccak-256 = 43011 Mbit/s @ 50 Kgates, Blake-256 = 6966 Mbit/s @ 47.5K gates, a 6.17X performance advantage with a 5% area disadvantage, 5.86X overall advantage

Xilinx Virtex 5 FPGA
Keccak-256 = 12817 Mbit/s @ 1272 slices, Blake-256 = 2245 Mbit/s @ 1523 slices, a 5.7X performance advantage with a 20% area advantage, 6.83X overall advantage

It can be seen an attacker with hardware resources has a performance advantage of 6 times on average vs Blake. In software, Keccak can average half the speed of SHA-512 at the same security level, and can be faster vs SHA-256. This is dependent on the message size, as the block sizes are not the same.

Newer processors will also contain additional instructions to improve the performance of SHA-256 hashing, the level of improvement is yet to be determined.

Implementation

The main implementation issue is centered around the design and purpose of HMAC.

HMAC is designed specifically for MD type hash functions like SHA and MD5. Its purpose is to change the initial values to something other than those in the specification. MD type hashes work like a block cipher, with the message the key, and the initial values the plaintext. The ciphertext is then the hash digest. With longer messages, the cipher works in OFB mode, with a key change. The final ciphertext block is then the hash. HMAC works by cycling $[key \oplus ipad]$ for 1 iteration to get a new secret IV, then it processes the message. The output is then processed as the new message using $[key \oplus opad]$ to generate a different secret IV.

Keccak is not an MD type hash function, so the entire purpose of HMAC is lost. Keccak works using the sponge construction with a large internal state. The general rule is to simply prefix the message with the secret key in order to create a keyed hash construction. It is suggested that this would actually be stronger than HMAC because of the large internal state that is kept secret, vs HMAC where an attacker can see the entire state unless there is truncation.

Using Keccak in an HMAC construction is of course possible, but will be much slower than key prefixing, and may not have a security advantage.

The other implementation issue is with code size. On 32-bit systems, SHA-256 will have a massive advantage over Keccak, since blitsliced Keccak is larger and more complex. On 64-bit systems, SHA-512 is a better fit, and Keccak in native 64-bit code is quite compact. The fact that the round constants can be derived at runtime is an advantage, but is usually only used when small code is required, such as an RFID card.

NSA

I hesitated putting this section here, but since the comments on the question are a hot topic, I figured it would be pertinent.

Just because the NSA designed something, does not mean it is bad, or secretly backdoored. The NSA is not some super boogeyman, the employees are human beings, and their computers need to obey the laws of thermodynamics. They can not easily sneak something by the cryptographic community. Almost everyone suspected Dual_EC_DRBG was tainted, and advised against its use, even before it became a standard. The only reason it got used was either bribery or incompetence.

I know nobody who suspects the same about SHA-2. Additionally, SHA is one of the most widely studied hash families, with decades of analysis by cryptographers all over the world, including the Russians, Chinese, Iranians, etc. It has stood the test of time better than MD5 and RIPEMD. The only exploitable issues are those common to all MD type hash functions, and if used in HMAC they are mostly irrelevant. SHA-2 is used by the US government to protect state secrets from its enemies, confidently.

If you want to use PBKDF and still don't trust the cryptographic community's view on SHA-2 and all the public analysis for whatever reason, use Blake-512 instead. It has far inferior attacker advantage numbers, excellent software performance, and well analyzed security. I am a fan of truncating the output, I would only keep 256 to 320-bits.

  I am postulating that SHA3 may preserve the entropy in the salt and password better than SHA2

Not enough to compensate for the performance advantage of an attacker, if that is even the case..


If an attacker has a chosen-plaintext and encrypted data, can they determine the encryption type? This question differs from How to determine what type of encoding/encryption has been used?, which asked about a ciphertext-only attack. This question is asking about a chosen-plaintext attack.

Let's say an attacker was trying to perform a chosen-plaintext attack on an encrypted password server. This attacker is an internal employee with their own registered account. They can:

Specify an arbitrary plaintext password for their account.
View encrypted ciphertext passwords saved to the server.

This attacker doesn't know what encryption method is being used, whether passwords are salted, or what key is being used. However, they notice that the encrypted passwords are always the same number of characters (64).

Using their chosen plaintext and encrypted passwords, could an attacker determine what type of encryption was used?

In fact, good password hashing libraries do not try to hide the used algorithm but document it instead, because it allows to transparently change to a better algorithm without knowing the user passwords: when a user tries to login, the library looks at the registered hash and uses the documented algorithm to compute the hash from the clear text password. If then do not match, login is rejected. If they match and the algorithm is the current one, access is granted and nothing more happens, but if they match and the algo is not the current one, a new hash with the current algo is registered. For example, Modular Crypt Format prepends the hash with $digit$ where digit is (from man crypt):

       1.   MD5
       2.   Blowfish
       3.   NT-Hash
       4.   (unused)
       5.   SHA-256
       6.   SHA-512

Other crypt formats may be easily added.  An example salt would be:

      $4$thesalt$rest

If you are in that case, only one single hashed password is enough to know the used algorithm, and it is not a security problem, provided the algorithm is non invertible.


Proof that two parties can communicate Suppose we have three parties, Alice, Bob, and Carol. Alice can receive messages from Bob and Carol individually, but can only send messages to both simultaneously. Additionally, Alice cannot tell if Bob and Carol can send/receive messages to/from each other. This is what Alice wants to figure out

Bob and Carol are always both going to say that they can communicate, even if they can't. What challenge can Alice give to the two of them to ensure that they are not lying?

Designing such a challenge is Impossible.

If we assume that having a connection is equal to being able to exchange any piece of knowledge at any given time then the proof of impossibility of such challenge is as follows:

Proof. First assume that there is such a challenge and Alice is capable of querying such a challenge to correctly determine whether the connection exists.

We give Bob and Carol the exact same knowledge set $K$ prior to the start of the challenge. (Obviously this knowledge set could contain a random tape: an infinite sequence of random bits) Bob and Carol are going to give answers to Alice only based on the knowledge set $K$ and what they later learn from Alice during the challenge.

Since Bob and Carol share the exact same knowledge set both of them know exactly what would be the answer of the other one to any given question about anything they already knew (knowledge set $K$). Their answers to these questions would be either "I can't/don't know" (the question asks about information outside of the knowledge set $K$) or something that both of them are exactly aware of.

To elaborate more clearly, the answers to questions and challenge which require some sort of randomness such as "quote me a title or line from any famous song, book, movie or poem", "send me a ten digit prime number" or "name a tree" would be answered based on an already shared random tape. Which means that at any given time they know exactly which member of all possible correct answers in their knowledge set is the given answer of the other one.

To further clarify things, it should be mentioned that as Bob and Carol have the exact same knowledge set $K$ all questions and challenges that are related to each other in some form would have consistent answers. For example, if Alice asks Bob "Name all of your favorite supercars" and then asks Carol "Does Bob like to have a Ferrari?" should yield consistent answers.

Accordingly, there is no challenge that questions about the knowledge set $K$ which proves the "connection" since consistent answers do not require any "exchange" of information. So, the challenge should ask a question which at least partially assesses the information that Bob and Carol acquired during the challenge.

Assume that the knowledge set $K$ plus what Bob learned from Alice during the challenge is $K_B$ and for Carol it is $K_C$. For the challenge to prove the connection $K_B$ should not be equal to $K_C$ otherwise as discussed earlier both Bob and Carol would know exactly what would be the answer of the other one to any given question and the challenge cannot prove the "connection" since consistent answers do not require any "exchange" of information.

Thus, they should have learned different things from Alice which is impossible since they receive same messages simultaneously from Alice.


FSB Hash Functions and Convetional hash Functions I'm reading FSB cryptographic hash function and the authors say that security of this function depends on NP-Complete Problem: "Decoding Linear Code Unlike most other cryptographic hash functions in use today" and I'm agree with the first part of claim. But I have a doubt respect to conventional hash functions for example the family SHA. The security of these functions depend of any NP-Complete Problem? According my understanding this hash function will be able to express than multivariate polynomials equations and solve multivariate polynomial equations is proved NP-Complete. Then a question is: Am I right?

That Wikipedia article is full of errors and false claims. Most importantly, FSB has not been proven to be as hard as an NP-complete problem. This is because the syndrome decoding problem is NP-hard in the worst case, but FSB uses random instances of the problem. Indeed, these random instances may be much easier to break than arbitrary instances. There is no guarantee that these random instances are actually hard, nor do we know how to generate NP-hard instances of decoding problems.

More generally, there is no known cryptographic primitive (of any kind) whose security is provably based on NP-hardness alone.


Is it possible to crack AES 128 key if one can use the key to encrypt arbitrary data block? I know for now practically it is impossible to crack AES 128 key by brute-force attack.

But is it still true if one has the key and can repeatedly use it to encrypt or decrypt arbitrary data block? In another word, given any clear text A, they can get the cipher encrypted with that key.

Is there a term referring to this kind of crack which is 'crack key with the ability to encrypt arbitrary data block by the key'?

Thanks

Is there a term referring to this kind of crack which is 'crack key with the ability to encrypt arbitrary data block by the key'?

Yes. That's a Choosen Plaintext Attack. AES-128 is designed to resist that, and as far as we know does so very well. CPA is considered indispensable for any modern cipher or block cipher.

Beware however that in practice, an adversary might gather additional information (side channel attacks), like the power consumption during encryptions (Differential Power Analysis), the time it takes to make the encryption (timing attack), or the state of the data cache after that (cache as side channel), or the result of encryption when some of it is affected by errors (fault attack). An AES implementation could be vulnerable to these.


Does zero-padding the secret in Shamir's sharing scheme increase security? When performed in binary Galois fields $GF_{2^n}$, Shamir's threshold secret sharing scheme produces shares that are each the same bit-size as the secret. Though the scheme is "perfectly secure" in that less than the requisite number of shares provide no information about the secret, in practice it does leak information about the secret, namely its size (when performed in binary fields).

Would padding the binary representation of the secret (say to a bit-length that is a multiple of 1024, or something) increase the security of the scheme?

If padding improves security, would padding with random bits be better than zero-padding?

If random padding is better, when reconstructing the secret, what is the best way to know how many random bits were added? Should I have the first few bytes be a number that stores this info? Obviously, zero-padding does away with this problem, because any leading zeros can be dropped on reconstructing the secret.

I should add: I'm operating in $GF_{2^8}$, and computing each byte of the shares from a byte of the secret, with different random coefficients for each polynomial, as discussed in this question.

As you note, Shamir's threshold secret sharing is perfectly secure (or information theoretically secure), yet does leak some information about the size of the secret (same thing with one-time pad).

If you are worried about leaking some information about the size of the secret, then padding could be used to lower the information leakage (instead of knowing that say the secret is 32 bits, the attacker would now know that the secret is no larger than say 1024 bits, something along those lines). If leaking the size of the secret is a problem, then this indeed increases the security of the scheme.

Padding with random bits vs zero-padding would make no difference in security. The secret is already perfectly secure (except for the size of it). Zero-padding hides the length just as well as random padding.

So, what if the secret starts with a zero bit? One thing to do (and this works with random padding too) would be to prepend the length of the padding to the secret. Other techniques would work too.


Reusing IV but still generating different code? I'm in a beginner's cryptography class and I'm trying to figure out if I'm doing something wrong, or if I just don't understand why something is the way it is.

I created a simple .txt file of 124 bytes and encrypted it with AES-CBC three times: twice with the same IV of '135797531', and once with a different IV of '246808642'. I also used the same password for all of them. Then I opened all the encrypted files in a hex editor to analyze the contents, and I saw that--aside from the header bytes--the code of each one was completely different. Even the ones that used the same IV. I was under the impression that if I use the same IV and password to encrypt a file twice, then they would both result in the same code, and that explains why an IV should be different each time. But with what I have, it's looking like it shouldn't really matter even though I know that's not the case. Did I do something wrong, or is there another explanation?

Edit: Code that was used-

openssl enc -aes-128-cbc -e -in text1.txt -out text2.txt -k '0123456789' -iv '135797531'

The properties of CBC mode are only specific to when you are actually using a key and IV as specified for AES-CBC. That means, using a 128, 192 or 256 bit key - commonly specified as 16, 24 or 32 bytes - and a 128 bit key - as 16 bytes. Many tools allow other parameters such as passwords instead. Some tools, especially online tools, forget to mention that they allow different parameters than a direct key and IV, because they have been written by utter tools.

If you're using a password instead of a key it is likely that a password based key derivation method is used to derive the key. These PBKDF's commonly use a random salt and likely an work factor or iteration count. Because the salt differs each time, the derived key will differ each time as well. So in that case it doesn't matter that your IV is the same twice.

Similarly, if you specify an IV of less than 16 bytes it is likely that memory beyond the IV is used and that the result differs. However, in that case you would not be able to decrypt the first block correctly.

OpenSSL command line - by default - uses it's own PBKDF called EVP_BytesToKey using an (insecure) single iteration and an 8 byte salt. You can see this if you look at the header, as the first bytes spell Salted__ followed by an 8 byte salt (which is indistinguishable from the rest of the ciphertext).

If you want to use CBC as it is specified, you have to use the (uppercase) -K and (lowercase) -iv option and use 32, 48 or 64 hexadecimal digits for the key and 32 hexadecimal digits for the IV. These are hexadecimal representations of the binary key and IV - they are decoded by openssl to bytes before they are used.

So try something like:

openssl enc -aes-128-cbc -e -in text1.txt -out text2.txt -K '000102030405060708090A0B0C0D0E0F' -iv '000102030405060708090A0B0C0D0E0F'

instead. With whatever keys and IV's you want to try, of course.


Stacked LFSR - why not used? New to cryptographic, weak in math.

I have designed a PRG which consist of 33 LFSR's, each 32 bits wide.

I use one of the LFSR's as "selector", using the 5 LSB from this register to select one of the other 32 registers, from which I grab one byte and use as output. So each requested byte will thus come from one of 32 "randomly" selected registers.

My gut-feeling is that such a scheme will:

Hide the selector register from the outside world (rendering Berlekamp-Massey useless)
Expose an attacker to a very fast growing tree of possible combinations.
(If trying to sort out from which LFSR the last byte might emerge)

As it seems to me as this is an obvious way of creating a truly messy output, it surprises me that I haven't seen it described somewhere (with a name like "Rose-Morris-Nyqvist-Yang-Goldstein-scrambler"), so my conclusion is that it must be a bad solution. (Even beside the obvious hassle of seeding 33 registers and select feedback masks).

So my question is: Why not?

/Hans

Your design seems to be a byte-wise generalization of Jennings' multiplexed generator rather than the alternating step generator.

S. M. Jennings, “Multiplexed Sequences: Some Properties of the Minimum Polynomial,” Lecture Notes in Computer Science, vol. 149, 1983.

I believe designs like hers [may even be byte based for efficiency] have been used in satellite TV encryption in the 1980s-1990s, but can't find the reference now.

There has been cryptanalysis showing such schemes may not be as strong as first thought.

Jovan Dj. Goliv, Mahmoud Salmasizadeh, Ed Dawson: Statistical Weakness of Multiplexed Sequences, Finite Fields and Their Applications 8(4):420-433, 2002.


How to find modulus from a RSA public key? I am studying the RSA cryptosystem. The public key consists of $(n, e)$, the modulus (product of two large primes), and the encryption exponent. I want to separate the modulus $n$ and exponent $e$. A typical public key is expressed in base64, and is of the following type:

 -----BEGIN PUBLIC KEY-----

 MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
 FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
 3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB

-----END PUBLIC KEY-----

Now from the above key, it is not clear which part is the modulus and which is the exponent. How can I extract the two?

I wanted to help break down exactly what you're seeing.

If you take your base64 string:

  MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB

You then decode it into hex:

30 81 9F 30 0D 06 09 2A  86 48 86 F7 0D 01 01 01
05 00 03 81 8D 00 30 81  89 02 81 81 00 AA 18 AB
A4 3B 50 DE EF 38 59 8F  AF 87 D2 AB 63 4E 45 71
C1 30 A9 BC A7 B8 78 26  74 14 FA AB 8B 47 1B D8
96 5F 5C 9F C3 81 84 85  EA F5 29 C2 62 46 F3 05
50 64 A8 DE 19 C8 C3 38  BE 54 96 CB AE B0 59 DC
0B 35 81 43 B4 4A 35 44  9E B2 64 11 31 21 A4 55
BD 7F DE 3F AC 91 9E 94  B5 6F B9 BB 4F 65 1C DB
23 EA D4 39 D6 CD 52 3E  B0 81 91 E7 5B 35 FD 13
A7 41 9B 30 90 F2 47 87  BD 4F 4E 19 67 02 03 01
00 01

So the question is: what is this? Well it's actually the DER variant of ASN.1 encoding. ASN.1 is a horrible monstrosity, but you can use the web-based ASN.1 decoder to find that the values are actually this:

30 81 9F             ;30=SEQUENCE (0x9F = 159 bytes)
|  30 0D             ;30=SEQUENCE (0x0D = 13 bytes)
|  |  06 09          ;06=OBJECT_IDENTIFIER (0x09 = 9 bytes)
|  |  2A 86 48 86    ;Hex encoding of 1.2.840.113549.1.1
|  |  F7 0D 01 01 01
|  |  05 00          ;05=NULL (0 bytes)
|  03 81 8D 00       ;03=BIT STRING (0x8d = 141 bytes)
|  |  30 81 89       ;30=SEQUENCE (0x89 = 137 bytes)
|  |  |  02 81 81    ;02=INTEGER (0x81 = 129 bytes) the modulus
|  |  |  00          ;leading zero of INTEGER
|  |  |  AA 18 AB A4 3B 50 DE EF  38 59 8F AF 87 D2 AB 63
|  |  |  4E 45 71 C1 30 A9 BC A7  B8 78 26 74 14 FA AB 8B
|  |  |  47 1B D8 96 5F 5C 9F C3  81 84 85 EA F5 29 C2 62
|  |  |  46 F3 05 50 64 A8 DE 19  C8 C3 38 BE 54 96 CB AE
|  |  |  B0 59 DC 0B 35 81 43 B4  4A 35 44 9E B2 64 11 31
|  |  |  21 A4 55 BD 7F DE 3F AC  91 9E 94 B5 6F B9 BB 4F
|  |  |  65 1C DB 23 EA D4 39 D6  CD 52 3E B0 81 91 E7 5B
|  |  |  35 FD 13 A7 41 9B 30 90  F2 47 87 BD 4F 4E 19 67
|  |  02 03          ;02=INTEGER (0x03 = 3 bytes) - the exponent
|  |  |  01 00 01    ;hex for 65537

So encoded in there are the two important numbers in hex:

Exponent: 65537 (Nearly everyone universally uses 65,537 as their prime exponent)
Modulus: 00 AA 18 AB A4 3B 50 DE EF 38 59 8F AF 87 D2 AB 63 4E 45 71 C1 30 A9 BC A7 B8 78 26 74 14 FA AB 8B 47 1B D8 96 5F 5C 9F C3 81 84 85 EA F5 29 C2 62 46 F3 05 50 64 A8 DE 19 C8 C3 38 BE 54 96 CB AE B0 59 DC 0B 35 81 43 B4  4A 35 44 9E B2 64 11 31 21 A4 55 BD 7F DE 3F AC 91 9E 94 B5 6F B9 BB 4F 65 1C DB 23 EA D4 39 D6 CD 52 3E B0 81 91 E7 5B 35 FD 13 A7 41 9B 30 90 F2 47 87 BD 4F 4E 19 67

Or, in decimal, your modulus is:

  119,445,732,379,544,598,056,145,200,053,932,732,877,863,846,799,652,384,989,588,303,737,527,328,743,970,559,883,211,146,487,286,317,168,142,202,446,955,508,902,936,035,124,709,397,221,178,664,495,721,428,029,984,726,868,375,359,168,203,283,442,617,134,197,706,515,425,366,188,396,513,684,446,494,070,223,079,865,755,643,116,690,165,578,452,542,158,755,074,958,452,695,530,623,055,205,290,232,290,667,934,914,919

No need for OpenSSL and it's voodoo commands.


AES key vs sector key I have read about AES and different modes of operation (CBC, ECB etc) and have 2 questions related to disk encryption:

-AES data block is 16 bytes - how does it relate to sector sizes on the drive which is typically 512 bytes? Also who or what is responsible for dividing disk sectors into data blocks?

-disk encryption software lets me configure AES key size (128/256) and is stored somewhere on the disk. Does it mean that I will use the same key to encrypt all sectors? Or maybe this key is used to calculate/derive sectors keys/block keys?

To better understand the below concrete answers, a short background on how disk encryption is usually performed with AES. The most tools will use one of the following two modes:

CBC-ESSIV, which is just standard CBC encryption where each sector is one "message" and the IV is derived deterministically from the index of the sector to be encrypted as $\text{IV}=E_{\operatorname{Hash}(K)}(\text{SID})$ where $K$ is the AES key.
XTS which is the more modern choice because it doesn't suffer from CBC's malleability essentially turns AES into a tweakable block cipher and using a different tweak for data block to hide equal blocks.

  [How] does it relate to sector sizes on the drive which is typically 512 bytes?

The sector size usually must be a multiple of the block size of the underlying cipher so no space is wasted to padding and stream modes don't have to be used (which break even more horribly than CBC under chosen-ciphertext attacks).

  [Who] or what is responsible for dividing disk sectors into data blocks?

The disk encryption software will usually divide the 512-byte blocks into 32x 16-byte blocks for the AES encryption.

  Does it mean that I will use the same key to encrypt all sectors?

Yes.

  Or maybe this key is used to calculate/derive sectors keys/block keys?

No. However in ESSIV mode (see above) a hash of the key is used to generate CBC IVs.


What does "Worst-case hardness" mean in lattice-based cryptography? In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below:

  Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with some small non-negligible probability) is provably at least as hard as solving several lattice problems (approximately, within polynomial factors) in the worst case. In other words, breaking the cryptographic construction implies an efficient algorithm for solving any instance of some underlying lattice problem.

But what is the difference between "worst case hardness" in lattice-based cryptography and "average case hardness" in standard cryptography based on discrete logarithm, say ElGamal Encryption?

It's seems to be confusing. For instance, breaking into ElGamal Encryption also leads to breaking several other cryptographic constructions and solving well-known number theoretic hard problem:  computational Diffie-Hellman. However, that one does not considered a "worst case hardness".

One line: worst means any and average means random.

Lattice-based cryptosystem

Let me restate.
Fix security parameter $n$.
What the reduction shows is the existence of a solver for the lattice problem on input any $n$-dimensional lattice using the adversary breaking a lattice-based cryptosystem with the security parameter $n$ on the average case.

Since we can solve any instance, we can solve the hardest one of dimension $n$.

ElGamal encryption - average-case

We have a reduction that converts a random instance of the CDH/DDH problem into a random problem of one-wayness/indistinguishability game. This means that the security is based on the average-case hardness of the problem.

ElGamal encryption - worst-case

Correctly speaking, the security of the El Gamal encryption scheme can be based on the worst-case hardness of the DL-like problems over the group instead of the security parameter.

Fix a prime-order group. We can convert any instance of the DL/CDH/DDH problem on the group to a random instance of the problem on the same group.
( This property is as known as the random self reducibility.)
Combining it with the previous reduction, we can say the security is based on the worst-case hardness of the problem over the fixed group.


Checking the integrity of RSA public key Let's say I need to verify a digital signature and the public key is stored in untrusted storage which I need to fetch before I verify the digital signature. However, I can store the cryptographic hash of the public key in trusted storage and I decide to use the hash to verify the integrity of the public key. Now say I am using RSA PKCS #1 1.5 signature scheme, the public key contains (n, e), i.e., modulus and public exponent.

Here is the questions:
Can I compute the only hash of the modulus for integrity? Do I get any security advantage if I compute the hash of the modulus concatenate with the public exponent? Specifically, I wonder what could go wrong if the attacker can change the my public exponent? (Assume the signature is created with public exponent 65537)

Can I compute the only hash of the modulus for integrity?

Well, if we allow the attacker to modify the value of $e$ you use (because it's in untrusted storage and you don't verify it), how can he exploit that?  Well, the most obvious approach for him would be to modify $e$ to be the value 1; that would make generating forgeries really quite simple.

Now, if your signature verification software prohibits $e=1$ (and doesn't parse $e=-1$; likely it doesn't); well, it might be safe, as generating alternative values for $e$ where the attacker does know the $d$ value is equivalent to factoring, and there is no other known way to take $e$-th roots that's not equivalent to factoring.  This is, of course, assuming that your PKCS #1 1.5 signature verification code does all the checks; if not, then (depending on which checks are skipped) it's known to be possible to generate a forgery that passes the partial checks with $e=3$.

On the other hand, why take the risk?  It's easy enough to include $e$ in the hash, and that avoids the question entirely.  Alternatively, you can just bolt in $e=65537$ in your verification code; in that case, the attacker can't change it.


Generating non-repeating N-bit IVs, which are indistinguishable from randomness I'm implementing a protocol which needs a 64-bit IV for every encrypted packet.  The cipher in use (AES-GCM, more or less as specified in RFC 4106) does not require that these IVs are random, only that they are not repeated for any given key.  However, the protocol imposes the additional requirement that every byte on the wire be statistically indistinguishable from randomness.

What I need, therefore, is a PRNG that produces successive 64-bit numbers, and is guaranteed not to repeat itself until all 264 possibilities are exhausted.  I don't think this PRNG has to be cryptographically secure, but I imagine it would not hurt.  I would seed this PRNG at the same time as I generate the AES key (which is a short-lived session key) from a source of true randomness.

What PRNG algorithm should I use?

I suppose the easiest way to generate these initialization vectors is to use a 64-bit block cipher (like Blowfish or DES/3DES), and encrypt sequential values of a 64-bit counter.

Of course, the "indistinguishable from true randomness" property of good block ciphers is only valid if the attacker can't observe much more than $2^{32}$ such initialization vectors, as then a truly random sequence would start to show duplicate elements, while your one would not, by your requirement.

Actually, if the only requirement is a nonce, and your protocol messages arrive in sending order (like over a TCP connection), you don't have to send it with the actual stream data, as long as the other side has the necessary information to generate it. Then a simple counter, counted up at both sides (and never transmitted), will do nicely (and you don't have to think about another key which needs to be managed).


Partially-known-plaintext attack of a stream cipher based on modular arithmetic I have a function called $F$, using modular arithmetic as does RSA, defined as $$x\mapsto F(x) = g^x\bmod p$$ where $p$ is a 1024-bit prime and $g$ is a generator of $\mathbb Z_p^*$. A secret key $r$ is chosen randomly from all distinct exponents (ie $\mathbb \{0,\dots ,p-1\}$). The encrypted message is computed using a one-time pad stream cipher, with the keystream computed as $$K=F(r)||F(2\cdot r)\dots$$

How do I decrypt the entire message after obtaining $g$, $p$, and the first 1024 bits of plaintext-ciphertext pair?

Whenever you're trying to attack a scheme that is [algebraically] relatively simple like this one, a sensible first step is to write out everything you know. Now, considering the information you've been given, try and substitute things into oneanother, and see where this leads you.

Let $(m,c)$ be the first 1024 bits of the plaintext-ciphertext pair.

Now, some pointers

Given this is a stream cipher, how is $c$ created? In particular, $c=g(m,K)$ for some function $g$. What is this function? Substituting in the data you know, what do you learn?
Write out $F(x)$ and $F(a \cdot x)$. If I tell you $F(x)=y$, calculate $F(a\cdot x)$
Now, consider everything you know. Put it together and finish the problem yourself.


Probability that rank of a square matrix, whose each element is uniformly random from a ring of integers modulo prime p, is not full I am currently reading a paper from CRYPTO, which is a top conference in cryptology. In the paper, the authors use a thereom like the one given below without a rigorous proof:

the probability that $Rank(A)\neq n$ is upper bounded by $1/p$, where $p$ is a prime, $n$ is an integer, $\mathbb{Z}_p$ is a ring of integers modulo $p$, and $A$ is a square matrix which is chosen from $\mathbb{Z}_p^{n\times n}$ uniformly at random.

I am curious how to rigorously prove the thereom. I would appreciate it if anyone could teach me how.

I'll try to show the probability that the matrix has rank equal to $n$. Two important facts, since $\mathbb{Z}_p$ is a field and not just a ring:

Each column of the matrix can be considered as a random vector drawn from a set of an $n$-dimensional vector space over $\mathbb{Z}_p$, which has $p^n$ vectors.
The number of vectors in a $k$-dimensional subspace will be $p^k$.

So, model the construction of the matrix as drawing $n$ vectors independently at random. For the matrix to have full rank, after the $i$th draw, we need all $i$ vectors to be linearly independent. Assuming the previous $i-1$ vectors are linearly independent, they span a space of dimension $i-1$, so the $i$th vector must be outside of this space. A space of dimension $i-1$ has size $p^{i-1}$, so the probability that a random vector is in that space is $p^{i-1}/p^n$, and we want the opposite to happen, so the probability is:
$$1-\frac{p^{i-1}}{p^n}=1-p^{i-1-n}$$
This even holds for the first vector, which will have rank 1 as long as it is not the all-zero vector.

Thus, the total chance of being full-rank will be

$$\left(1-p^{-n}\right)\left(1-p^{-n+1}\right)\dots\left(1-p^{-1}\right)$$

This is less than $1-1/p$, which means its converse (that the matrix's rank does not equal $n$) must be at least $1/p$. Are you sure the paper didn't mention a lower bound?

Alternatively, since $(1-p^{-i})\geq 1-1/p$ for $i\geq i$, we can argue that the probability of a full-rank matrix is lower-bounded by
$$\left(1-\frac{1}{p}\right)^{n} \geq 1-\frac{n}{p}$$

and thus $\frac{n}{p}$ an upper bound on the probability that $Rank(A)\neq n$.


Unpredictability of X.509 serial numbers About X.509 certificates serial numbers the RFC 5280 says:

  The serial number MUST be a positive integer assigned by the CA to each certificate.  It MUST be unique for each certificate issued by a given CA (i.e., the issuer name and serial number identify a unique certificate).  CAs MUST force the serialNumber to be a non-negative integer.

There is no mention of the security concerns with the serial number generation. What are the good practices? Is there any security issues with predictable (for instance sequential or based on the certificate generation date) serial numbers?

A non-random serial number does not imply, by itself, a security issue with the signature scheme, but, as @Jack points out, it can be used to leverage an attack. On a general basis, signature algorithms begin by hashing the input message with a given hash function; if the message or hashing process is fully controlled by the attacker, then collision resistance of the hash function becomes an important issue. On the other hand, with some randomness inserted by the signer (e.g. a random serial number, added by the issuing CA of a certificate), the signature ought to be resistant to mere collision attacks, and, ultimately, work on preimage resistance (and MD5, with all its shortcomings, still appears to be optimally resistant to preimages).

Such randomness should be inserted in an "appropriate" way, which depends on the internal structure of the hash function. Halevi and Krawczyk have specified a generic way which should be good for all hash functions, and called it RMX. It has resulted in an Internet Draft and NIST Special Publication SP-800-106. Noteworthy points are:

RMX is meant to be applied on any binary message, but it requires generation of some random value, to be transmitted along with the message.
Since the hashing process is modified, the signer and verifier must be aware of RMX, right at the beginning of message processing.
RMX includes a description of how to extract the random value from the first half of a DSA/ECDSA signature (the "$r$" value, which does not depend on the signed message). This is meant to save bandwidth and be compatible with existing data formats (which do not have room for an extra "random value"), but it makes signature more complex, since the "$r$" value must then be generated before hashing the input message -- which can be cumbersome in systems where the hashing is externalized, in another module than the one holding the signature private key.
This is a recommendation which has not yet found its way in any notable standard.

Using a random serial number is the "poor man's randomized hashing" which has the fine property of being fully compatible with existing X.509 certificate verifiers (the hashing process and the certificate formats are not altered in any way) and many CA already implemented it, albeit not for protection against collision attacks. In a certificate, the serial number occurs "early enough" in the structure, with some big fixed elements between it and the public key (namely, subject and issuer names, validity dates...), so that it suffices, with existing MD-based hash functions (MD5, SHA-1...), to prevent leverage of collision attacks. Also, a long enough random serial number ensures uniqueness with overwhelming probability without having to look up anything in a database. For proper interoperability, use a positive serial number less than $2^{159}$ (this ensures that the value encoding, as specified in ASN.1 DER, will fit in 20 bytes).

Completely unrelated to collisions and signatures, but relevant for security, predictable serial numbers leak business information. As Peter Gutmann states it in his X.509 Style Guide (an old but fun and not completely obsolete text):

  by using sequential numbers a CA ends up revealing just how few certs it's actually signing (at the cost of a cert per week, the competition can find out exactly how many certs are being issued each week)


The notion of sub-exponential security I have been reading a paper where they construct probabilistic IO (indistinguishability obfuscation) from sub exponential IO. I want to know if the following two notions of sub-exponential security equivalent?

A scheme is sub-exponentially secure if a PPT adversary doesn't get more than 1/subexp(x) advantage.
A scheme is sub-exponentially secure if an adversary with sub-exponential computational power doesn't get more than negligible(x) advantage.

(x is security parameter)

The paper defines sub exp secure as defined in 1. But I have come across several notions where they define definition 2 for sub-exponential secure scheme.

Please clarify if both are equivalent. If yes please let me know the proof. If not then where does the equivalence fail?

Since noone has written down an answer, I'll give it a go.

There are two important parts of your (or of any) security definitions:

An adversary $\mathcal{A}$, with bounded computational power;
A bound ${\tt negl}(x)$ on the advantage of $\mathcal{A}$.

These lead to two important observations:

The more power we give $\mathcal{A}$, the stronger our security notion;
The tighter ${\tt negl}(x)$, the stronger our security notion.

Ideally, you'd give $\mathcal{A}$ unlimited power, and show that he can achieve 0 advantage.

What does this look like in your definitions? Let's first consider $\mathcal{A}$. In (1), your adversary has polynomial computing power. In (2), your adversary has sub-exponential computational power. From this perspective, (2) makes a weaker assumption on the adversary, and thus would provide a stronger security guarantee than (1).

But as mentioned, the security does not only depend on the adversary. In (1), the function ${\tt negl}_1(x)=1/{\tt subexp}(x)$. In (2), there is no definition of ${\tt negl}_2$. I'd say there are two options:

${\tt negl}_2(x)\leq{\tt negl}_1(x)$. Then (2) makes a weaker assumption on the adversary and has a tighter bound on the advantage. Thus (2) gives a stronger security guarantee.
${\tt negl}_2(x)\gt{\tt negl}_1(x)$. Now (2) makes a weaker assumption on the adversary, but (1) has a tighter bound on the advantage. In this case I'd say neither is better. It's basically saying "if we give the adversary more power, he can get more advantage". It would probably depend on context which of the two is applicable.

Edit: I may have misunderstood your question, if you mean (2) to have negligible advantage according to the usual definition. In that case the above is probably obvious to you, and does not help at all towards your question. I guess I'll just leave it in case it helps someone else..


What is the importance of AES add round Key (K0)? A high-level overview of AES is according to Wikipedia

Key expansion;
Initial round key addition;
9, 11, or 13 rounds;
Final round (making 10, 12, or 14 rounds in total).

I can understand all the steps except step 2 which is known as key widening.
What is the importance of the key widening step? How does it contribute to the overall security of AES? What is the importance of this step and how does it contribute to the overall security of AES?
[EDIT] I heard that it helps to in implementing the encryption recursively but can't see how is this possible. as this is done only time at start of encryption and end of decryption.  Implementing this in a recursive function will cause each round to XOR the input with 2 keys.
So what exactly are the benefits of this initial add key step?

AES-128 consists of 10 rounds. Each round  includes a public permutation (consisting of the composition of public permutations SubByte ShiftRows MixColumns except for the last round where MixColumns is ommited), and secret tranformations AddRoundKey (consisting of a XOR with a key-dependent and round-dependent value) before the first round, in-between rounds, and after the last round. Therefore there are 11 AddRoundKey. The question asks: why the first AddRoundKey?
Because without the first AddRoundKey, the public permutation of the first round would operate on the plaintext, thus be of no cryptographic value in attacks involving known plaintext.
Consider the most basic attack: brute force key search with a  known plaintext/ciphertext pair. With the first AddRoundKey, the input of the first public transformation changes for each key, adversaries must compute that permutation for each key tested, and it's output is very different for each key tested. But without the first AddRoundKey, the output of the first public permutation is a constant that adversaries can compute once at negligible cost; essentially, one round of AES is wasted.

Addition: the last AddRoundKey is here for the same reason. And the last round's MixColumns is removed because, should it be present, it would be possible to exchange that last round's MixColumns and the last AddRoundKey (after a linear transformation of the last subkey), and then that last round's MixColumns would be a public permutation operating on ciphertext, thus of no cryptographic value.

Addition: I do not see any substance to a claim that "the first AddRoundKey helps in implementing the encryption recursively".


How can we know who sent a MAC-then-encrypt message? I read about MAC-then-encrypt vs encrypt-then-MAC and I understood why MAC-then-encrypt is better but what if we have two parties that needs to know who signed the message before read it?

Example:

A and B want to communicate but they don't want to open suspicious files, B needs to know that the message received was sent by A. If they MAC-then-encrypt their messages, they can't know who sent the messages.

I was think about a MAC-then-encrypt-then-MAC solution but is this a good way to do this? I think this case has the same problem than encrypt-then-MAC.

Opening suspicious files kind of assumes that you immediately do something with the data after decryption. This is a bad idea for both encrypt-then-MAC as well as MAC-then-encrypt and even authenticated encryption.

Many authenticated modes of encryption such as GCM and EAX are online which means that you will immediately receive the ciphertext after encryption or plaintext after decryption. It depends on the interface of the cryptographic library (API) if the online property is available; some higher level API's require you to supply all of the ciphertext plus authentication tag before anything is decrypted.

If you however decrypt first and then keep the result buffered until authentication has taken place then this is not a big problem. As long as you do not process the data before authentication the security of your system should not be at risk (you may of course want to make sure that the ciphertext and tag size is within certain limits).

What is a problem with MAC-then-encrypt is that any vulnerability in decrypting altered ciphertext may result in leaking data. This means for instance that padding oracle attacks for ECB and CBC mode are possible. A lot of the differences between encrypt-then-MAC and MAC-then-decrypt are already explained here.


Calculating amount of time for brute forcing ciphertext depending on the size of the key I am a graphic design student and for my information graphic project I have chosen the topic of the history of encryption and how the security level developed over the centuries. It’s basically an information graphic to make people like me aware of encryption and its importance in times like these (see: news about the NSA et al.).

So I'm taking several encryption concepts like the Caesar cipher, the Jefferson Wheel and something more modern like AES to calculate the Brute-Force time of the maximum key size. The main point is that I want to show that the security level grew enormously and in which size they grew.

Now the problem:

I wanted to calculate the key size, so I did research on the key sizes of each specific encryption concepts. In addition to that, I wanted to calculate the brute force time of an attack for each encryption (to find out how long it takes to crack the individual encryption). I know, that is a simple approach but I wanted to keep it simple as possible.

Now I’m not sure if I calculated it correctly and I would really appreciate it if someone could explain what I did not understand about that.

For example:

The brute-force computer I found (www.orange.co.jp/~masaki/rc572/ratej.php) was 2096204400 keys/sec and it is set up like 1 brute-force PC vs. an PC which is using this specific encryption.

Everything was calculated with wolframalpha.com

Caesar Cipher

It got 25 possible combinations of characters (Wikipedia says its about 5bit) so that means the time 25/2096204400 seconds = 11.93 ns
Enigma

Wikipedia says it’s roughly about 77Bit long, so the possible keys are
20651321783174268000000 and 206651321783174268000000 keys/2096204400 (keys/s) = 3.124×10^6 average Gregorian years.

Are my calculations correct?

Your approach is too simple to give an accurate rating of the cryptographic systems. For any system that does not inherently suffer from short key lengths it is first and foremost its resistance to cryptanalysis that makes or breaks it.

The Vigenère cipher for instance is hundreds of years old and can easily be used with a very long key if so desired. That however does not prevent it from being a very poor algorithm by modern standards. It leaks so much information that if you know what to look for and have a decent length of message to work with you don't even need a computer to break it.

There can be no single way to compare wildly different cryptographic schemes, the very nature of their weaknesses differ. The best thing you can do is to list the requirements for breaking a given scheme, like:

Vigenère cipher:

A guess about the contents and words likely used in the message.
One or more messages using the same key, combined at least around double the length of the key.
A person who is reasonably good at performing basic algebra.
Some hours of that person's time.

Or:

One or more messages using the same key, combined at least around double the length of the key.
A person who understand and can use pattern frequency analysis of the language in which the message is composed.
Some days of that person's time.


Bitcoin mining: how is a block header of 80 bytes processed in SHA-256? Isn't it too big? The whole process of bitcoin mining was making sense to me until a moment of madness an hour ago, if there are 80 bytes of data to be processed in SHA-256, that's 640 bits of data to be processed in SHA-256.

In this 80 bytes we have: 4 bytes (version), previous block hash (32 bytes), merkle root (32 bytes), time (4 bytes), bits (4 bytes), nonce (4 bytes).

I thought SHA-256 accepted 512 bits of data, so that's 64 bytes of data. And on top of that, I need to add the length of the data to be processed in the last 64 bits of this 512 bits input but 64 bytes is well over the limit.

Then I saw that I would have to create basically two 512 bit input "blocks". The first block holds 512 out of the 640 input, and the second block holds the remaining 128 data bits, one bit to signal the end of the data and then padded up with 0s until the last 64 bits to indicate the length.

Can someone confirm if this is correct, and explain more on how this is done? I'm trying to implement my own SHA-256 module in VHDL since I couldn't find any but having more than a 256 input really makes it more confusing.

What am I missing here? Can someone help clear it up for me?

The SHA-256 compression function takes a 256-bit chaining value $h$ and a 512-bit message block $m$ and returns a 256-bit chaining value $f(h, m)$.

The SHA-256 hash function takes a padded message $m$ broken into an integral number of 512-bit message blocks $m = m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$, up to $\ell \leq 2^{55} + 1$ blocks long (the unpadded message length in bits, encoded into the last block, is 64 bits, allowing up to $\lceil(2^{64} - 1)/512\rceil = 2^{55}$ message blocks plus one more for the padded length), and iterates the compression function using a standard initialization vector $\mathit{iv}$ as the initial chaining value: $$H(m) = f(\cdots f(f(\mathit{iv}, m_1), m_2)\cdots, m_\ell).$$

If you are considering messages of the form $m_1 \mathbin\| m_2^i$ where you vary $m_2^i$ for the $i^{\mathit{th}}$ iteration, then of course you can precompute $h_1 = f(\mathit{iv}, m_1)$ and then use only a single evaluation of the SHA-256 compression function to compute $H(m_1 \mathbin\| m_2^i)$ by $f(h_1, m_2^i)$.


Is my identity exposed when publishing my public key or encrypting with PGP? Let's say I create my PGP keys with my appropriate name and email address.

Will these personal information be exposed if I publish my public key?
When I encrypt a message for sending it to my communication partner, if someone intercepts this encrypted message, will he or she get to know about my personal information?

Yes, your public key includes your UIDs. It may be possible to delete all before exporting though - for sure you could copy the key, add an "anonymous" UID and delete all others.
As long as you're not signing the message, nobody will know who sent the message (but have a look at the mail or other headers!).


A bit-sliced implementation (or the algebraic normal form) of the two FIDES S-Boxes I want to see a bit-sliced implementation of 5-bit and 6-bit S-Boxes of FIDES or, at least, a representation of these two functions in algebraic normal form. Where can I find it?

You can build this youself in a very mechanical process, it's only optimizing circuit size which gets interesting.

Take a 5 bit to 5 bit S-box, each can viewed as 5 different binary functions on 5 variables.

You can trivially construct any such function. A simple (inefficient) approach is to build it in normal form: write out the 32 different input values, and take only those whose matching output is 1. You can construct an expression which is the Or between sub expressions one for each row with 1 output. Each subexpression is the and between all variables optionally negated. Each variable will be as is if it is 1 on the given row and negated otherwise.
This results in a binary function for the required output bit.

You can obviously optimize this to get smaller circuits. A basic method for optimizing circuits is: https://en.m.wikipedia.org/wiki/Karnaugh_map
There are many more techniques including some which reuse structure between different bits of an S box and different S boxes.


Need help understanding this exercise's solution We were given this exercise, which asks us to identify the types of keys used on this diagram:

The solution was

Kxa -> A's private key

Kya -> A's public key

KxB -> B's private key

My question is, how is it possible that B knows the contents the first message coming from A since it was encrypted with A's private key ?
Also, B replies back to A encrypting the message with A's public key which is encrypting a message using B's private key.. I thought private keys were meant to be used to decrypt messages ecrypted by public keys.

I dont understand how come they know each other's private keys.

OK, so this takes a bit of guessing, but I'm assuming the following:

A is the identity of A, which can be used to select the right public key of A;
Kxa() is a signing operation (with message recovery) that signs the random Ra and a tag Ts which is used as proof;
Kya() is an encryption operation with the public key A, so that the session key Ks is kept confidential;
Kxb() is a signing operation (with message recovery) that signs the random Ra together with session key Ks;
Ks(M) is message encryption with the established session key Ks.

The general idea seems to be to perform authentication of both parties and session key establishment for message transport security.


Hardware Gaussian random numbers for lattice-based cryptography I have been recently reading about lattice-based cryptography.

I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and constant-time Gaussian samplers, which appears to need non-trivial algorithms. For what I got this is still something that could be improved in lattice-based cryptography.

I know that there are hardware random number generators that naturally produce Gaussian distributions. For example, thermal electronic noise from active and passive components often shows Gaussian behaviour. Also some optical random number generators are known to produce unpredictable and normally distributed random numbers.

My question is: could Gaussian hardware random number generators play a role in adding the Gaussian noise required for the security of lattice-based cryptography?

Or is there something fundamental that I am missing about how these Gaussian sampler must be built? Perhaps related to the choice of the standard deviation? Or because some determinism is preferred?

Any help in understanding this would be helpful, and also any instruction to where to find a good, (simple :-D ) introduction to Gaussian sampling in lattice-based cryptography.

I am very new to the field, so forgive me if I said anything imprecise or incorrect

Kind Regards,
Rafa

You are confusing discrete Gaussian sampling with Gaussian sampling.
A discrete Gaussian of parameters $\mu, \sigma$ is a random variable supported on $\mathbb{Z}$ with pmf:
$$\Pr[X = k]\propto \exp(-\pi \|x-\mu\|^2/\sigma^2)$$
A continuous Gaussian of parameters $\mu, \sigma$ is a random variable supported on $\mathbb{R}$ with pdf:
$$\Pr[X = r] \propto\exp(-\pi \|x - \mu\|^2/\sigma^2)$$
One natural hope would be that discrete Gaussians are simply "Continuous Gaussians rounded to the nearest integer". This is not the case (one is left with two distributions which, while similar, are not identical.
One particular difference is that I don't believe the sum of two rounded Gaussians is rounded Gaussian, but under suitable restrictions this holds for discrete Gaussians). That being said one can adapt certain proofs to use "rounded Gaussians", which this paper by Hulsing et al. does.

Note that the discrete Gaussian distribution is much harder to sample from than continuous Gaussians.
While (under suitable restrictions) it still satisfies a "convolution theorem" that sums of discrete Gaussians are discrete Gaussians, one needs certain restrictions which don't exist in the continuous case.
Another example of a difference is that no analogue of the Box-Muller Transform exists for discrete Gaussians, which is a fairly efficient way to generate continuous Gaussians from a uniformly random source.

Sometimes one can even use a random variable which seems less connected to Discrete Gaussians, namely Binomial random variables (which are quite efficient to sample from in constant time). See page 14 of the Kyber paper (a current NIST PQC round 2 KEM candidate) for some discussion of this. Dilithium (a NIST PQC round 2 signature candidate) uses uniform noise due to concerns with implementing discrete Gaussian sampling efficiently in constant time.

As for a good introduction to the literature, there has been some work before about hardware implementations (here, although I don't know enough about hardware to evaluate the work.
Beyond this Micciancio has some links to recent work, although it is missing some papers from the last year (which are essentially updates to current NIST PQC candidate's samplers).

I generically like Michael Walter's exposition of existing methods (see for example section 6 in this paper or section 3 of this paper). If one starts there, and then additionally looks at recent work on NIST PQC round 2 candidates (in particular the lattice based signature schemes Falcon and qTESLA) that'd be a very good start.


Is it possible to ensure security with zero pre-shared information? Is it possible to secure a communications channel against both passive (sniffing) and active (injecting / MitM) attackers without either legitimate party knowing any pre-shared information?

I know that this isn't possible using "traditional" asymmetric crypto, since an active attacker could create its own public keys and relay the information on both sides. A trusted third party implies pre-shared information, since at least one party must provide their public key to the third party.

Are there any schemes that make this viable, or is it completely impossible?

Update: By "zero information", I mean other than the "address" of the other person, e.g. their computer's IP address, or even their mailing address.

No. Consider using encryption to protect against a passive adversary. In this case, encryption needs to hold from the sender to the receiver. The sender can verify that the message leaves them encrypted but they have no guarantee that it is not decrypted before the receiver unless if they can authenticate the receiver. Authentication requires knowledge of some secret which would constitute preshared information in your definition.

The closest I believe you could come to a secure channel in this setting would be what is called Secure Message Transmission Protocols. The basic idea is that the sender would split up the message into shares (say 10 shares) such that some threshold (7 shares) are required to reconstruct the message. The sender would send the 10 shares over different channels. This is not secure against an adversary that is one all channels (which your question implies, which is why the answer is still likely "no") but if the adversary is on 6 or less, you get passive security. Active security is possible but the adversary is bounded to less than a third of the channels (byzantine agreement). Anyways, you could also argue that knowing the algorithm to reconstruct the message from the shares is pre-shared information (although not a secret).


uniform vs. non-uniform PPT I'm trying to understand PPT and in particular what the differences are in uniform and non-uniform PPT's. First, this is how I see it:

A probabilistic polynomial-time (PPT) algorithm $A$ is an algorithm that runs in polynomial time but also has access to some oracle which provides true random bits. So if we input $x$ into $A$, instead of getting an output $y = A(x)$ that is a deterministic value, we get a random variable $Y$ which has a certain probability of being a set of different values.

A non-uniform PPT $A$ is PPT whose description size (i.e., $|A|$) is not constant, but polynomially increasing with its input. I've seen definitions like $A = \{A_1, A_2, \dots\}$ where every $A_i$ is a PPT.

Are my observations/conclusions wrong? And if so, please correct me.
Some definitions I have seen for a non-uniform PPT is that we insert some "advice string" along with the input to $A$. But what exactly is that advice string?

Best regards

Your observations are basically correct. Informally it is as follows: For a uniform PPT algorithm think of a fixed Turing machine that has access to some random tape and the output of the algorithm is a random variable. For non-uniform algorithms it is best to think of a family of circuits indexed by the length of the input (so for every input length the algorithm may exhibit a totally different behavior). But you may also see a non-uniform algorithm as a uniform algorithm that takes an additional input-length dependent "advice string" that helps the algorithm to solve problems of that size (to make a non-uniform algorithm uniform, simply pass always the empty string).

For formal definitions just check your beloved complexity theory book. When it comes to crypto, there has recently been some discussion about these two models (typically reductionists proofs are in the uniform model). You may look at the page of Menezes (non-uniformity) and follow up discussion.


Would DES be secure with 128 bit keys? Assuming you only modify the key schedule so that each of a 128-bit key is used at least once, would DES be about as secure as other ciphers such as AES? I am not talking about 2DES/3DES or other drawbacks like performance etc.

No, DES* (which I'll call your "DES modified to use 128 bit keys") would not be as secure as AES; two reasons spring immediately to mind:

Block size; DES* would still have 64 bit blocks; most block cipher modes start to leak information when you get close to the birthday bound; for DES*, that'd be 32Gigabytes, which isn't that long for common use.  In contrast, AES (which has a 128 bit block size) has a birthday bound of circa 300Exabytes
Linear cryptanalysis; DES is known to be weak against linear cryptanalysis; depending on how you map the 128 bit keys to the DES* subkeys, DES* may very well be as well.  Of course, AES is known to be immune to linear cryptanalysis


What's the purpose of secret message numbers in CAESAR ciphers? The CAESAR call for submissions specifies that ciphers may accept as a parameter a secret message number. The requirements are that:

It must be possible to recover the plaintext and the secret message number from the ciphertext, associated data, public message number, and key;
Ciphers may impose single-use requirements on the secret message number, but can't otherwise assume any specific generation scheme (e.g., counter or random selection);
Ciphers must provide authenticity and confidentiality for the secret message number.

While this is quite clear about the requirements, I'm still at a loss at the purpose.  What uses or features do such secret message numbers enable?  Are there generic benefits to having such a message number, or is it something that individual ciphers would exploit for different ends?

Answers to the following older questions suggest that they may be used to provide some sort of nonce-reuse resistance or "hybrid encryption," but don't explain those scenarios in depth:

Single-algorithm authenticated encryption
What do associated data and message numbers mean?

And scanning through the third-round candidates' submissions doesn't shed a lot of light either—most of them don't support secret message numbers, and the one or two that did provide it as an optional feature

DJB answers this question on the crypto-competions mailing list.

In short, the idea is that using counter as a nonce can leak information that would be better not leaked in real world conditions where an attacker may not have a copy of every message exchanged (or even if they do if e.g. a timestamp is used as counter).  However, using a counter also makes it much easier to reject replays without the protocol designer needing to include a separate counter.


How to realize a hash function H:{0,1}* × G × {0,1}* -> Zq ？ I read papers about cloud storage data integrity audit, which needs PBC library and GMP library.
The author define encryption hash function  $H:\{0,1\}^* \times G \times \{0,1\}^* \to \Bbb Z_q$, used as $H(ID,R,RN) \bmod q$, $G$ is a cyclic multiplicative group with order $q$ ,$q$ is a large prime, $R, ID,RN$ are elements of $G$.
I don't know how to compute $H(ID,R,RN) \bmod q$ ,they may multiply or do exponent arithmetic ?or use hash function like SHA1 ? How can I construct this function?

If elements $R$ of $G$ can uniquely be expressed as a bitstring $\overline R$ (e.g. by taking the two components in a finite field of the affine coordinates of $R$, each uniquely representable as a fixed-size bitstring, and these are concatenated to form $\overline R$), then it is easy to construct a generic hash $H:\{0,1\}^* \times G \times \{0,1\}^* \to \mathbb Z_q$ from a standard $b$-bit hash $F:\{0,1\}^* \to \{0,1\}^b$, say SHA-512 with $b=512$, as follows:

$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$, which is a hash of $(\text{ID},R,\text{RN})$ in the set $\{0,1\}^b$
if $\log_2q>b/2\,$, expand $h$ as follows:

$g\gets h$
for $i$ from $1$ to $\big\lceil(\log_2q-b/2)/b\big\rceil\,$

$h\gets h\mathbin\|F(g\mathbin\|\overline i)\,$, where $\overline i$ is a bitstring uniquely representing the integer $i\,$ (e.g. encoding $i$ in big-endian base 256 as a minimal number of bytes, then converted to binary)

$r\gets \underline h\bmod q\,$, where $\underline h$ is the integer coded by the bitstring $h$ per big-endian binary

The result $r$ is the desired hash of $(\text{ID},R,\text{RN})$ in the set $\mathbb Z_q$.
This hash has nearly the same security as $F$ or an ideal hash in $\mathbb Z_q$, whichever is lower. Argument (or lack of a reference), under a model of the hash $F$ as a random oracle (and any security reduction is is with respect to that):

The step "$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$" is a generic composition of hashes, in order to hash multiple inputs of variable size (while maintaining collision resistance contrary to mere concatenation), and allowing a security reduction.
The step "if $\log_2q>b/2\,$, expand $h$" does that essentially as in MGF1, again allowing a security reduction.
The step "$r\gets \underline h\bmod q\,$" insures the output is in the desired range. It create a bias towards low values, but since at least $b/2$ bits are discarded this bias is low, and it's possible to upper-bound the advantage a distinguisher can obtain.


Aes Ctr non-secure PRNG I want to construct a seeder for a big state PRNG (xorshift1024 based) and have been thinking about using Aes Ctr using multiple 256 bit keys, where the counter is simply encrypted multiple times (similar to 3DES).

Would this in any way reduce the statistical qualities of Aes Ctr? Security isn't a concern, but uniqueness of the generated random number sequences is. The reason I'm considering Aes is because it's built into .net and mono.

There is really no need to go beyond 256 bit security. If you want to combine multiple keys - presumably because you are not sure they provide enough security regardless of the size - then you could concat them and use them as Input Keying Material to a KBKDF that provides extraction as well as expansion (e.g. HKDF). Then the output can be used to seed your PRNG.

It seems you are trying to build your own KDF using CTR mode. Such KDF's already exist, but they generally don't provide extraction of the entropy, just expansion of statically sized (128, 192 or 256 bit) keying material. Proving that your scheme does extract entropy well will be tough to accomplish.

The only drawback of using HKDF for this is that the keying material must be in memory to perform the calculations; you should make sure that this is (1) possible and (2) possible to secure. How big this drawback is depends on the situation.


What are the advantages of using Leveled Homomorphic Encryption over Somewhat Homomorphic Encryption? Is there a point in using LHE over SHE?

From what I understand, SHE is like an extended version of LHE, the only difference is that you limit the depth of circuits that can be evaluated. Therefore, I wonder which is better to use since they seem to be the same.

What is the effect of limiting the depth of the circuits? That does not make much sense to me.

I would take a look at Brakerski's survey to clarify the exact differences between LFHE and SHE.

In the survey it says

  Leveled FHE [...] refers to a family of FHE schemes that allow, for any depth bound $d$, to generate an instance of the FHE scheme that supports the evaluation of depth-$d$ circuits.

And also

  In early works on FHE, the term somewhat homomorphic encryption (SHE) was used to indicate a scheme with homomorphic capabilities against a restricted class of functions (depth bounded). The two terms are sometimes used interchangeably, however in the original SHE scheme [Gen09b, Gen09a] the parameters of the scheme grew exponentially with $d$.

So, even though both of them accept a restricted family of circuits, we see that with LFHE you can "plan" in advance which type of functions you want to compute (i.e. up to what depth) and then you can obtain FHE for that family, whereas with SHE this bound on the depth is more 'universal', in the sense that it doesn't scale well with the depth and hence you're forced to keep a relatively low depth (but you can still use bootstrapping if this depth is large enough).

Notice that LFHE actually makes sense in practice: You probably use an FHE scheme with some specific application in mind, and in that case you can find a suitable LFHE scheme that fits your function.


Why NIST insists on post-quantum standardization procedure rather than post-quantum competition? I have seen in many papers and even in communications from NIST that the ongoing standardization is a "procedure" or a "process". They carefully refrain from using the term competition like AES. I was wondering what is the reason for this? Is there any functional difference on how this process is conducted?
Thanks in advance.

Is there any functional difference on how this process is conducted?

One likely difference is the intended end goal.  The intended result of the AES process was to approve exactly one proposal, and that is what they did.  In contrast, they are likely to approve at least two proposals (both for kem/public key encryption, and the signature side of things, so that is at least four approved algorithms).
There are likely several reasons for this; for one, all the AES candidates did basically the same thing; hence it wouldn't make sense to approve multiple.  In contrast there are some significantly trade-offs between the PQC algorithms; for example, Rainbow has quite small signatures (and huge public keys), while Falcon/Dilithium have (by PQ standards) moderate signatures and moderate public keys.  Which is more appropriate is likely to vary by use case.
The other reason is trust.  When the AES competition happened, there was a fairly good understanding of block ciphers (as we had been examining them for over 20 years); in contrast, we have comparatively less understanding of some of these postquantum algorithms (especially against attacks by Quantum Computers); hence it makes sense to approve several (so that if one is broken by a new discovery, we have a backup).
Now, I'm not NIST, and so these are just my observations; I do believe that I had heard this logic by some speaker from NIST in the past.


Is there a mental poker algorithm that does not rely on commutative encryption? The algorithm for mental poker that I saw on Wikipedia and everywhere else relies on an encryption algorithm such that $E_k(E_j(P)) = E_j(E_k(P))$, but I can't find a modern and secure algorithm for which this is true. The only algorithm I found with this property is SRA (I believe that's what it's called) but it relies on modular exponentiation, which is slow and resource intensive compared to a more common algorithm such as AES, not to mention less secure.

Is there a mental poker algorithm that doesn't rely on this property?

Yes, there are some other algorithms that do not rely on commutative encryption.

The Wikipedia page for Mental poker lists some other examples. It describes a non-shuffling poker protocol that uses homomorphic encryption. It has this caveat, though:

  However, the method needs all cards that have already been dealt to be known to all, which in most poker-style games would beat its very purpose.

So it's not practical.

There is also a very interesting paper titled How to Use Bitcoin to Play Decentralized Poker. The authors demonstrate how you could use secure multiparty computation with identifiable abort (ID-MPC) to play a decentralized game of poker.

(Use this Internet Archive link if the Mental poker page has been updated.)


Is using ECDSA with AES-GCM viable? I'm pretty new to the whole cryptography scene, so please forgive me if I make any incorrect statements.

I have a 16MB image that I'm encrypting and authenticating using AES-GCM. I obtain a 16MB encrypted image and a MAC. From what I could tell, this should provide me both confidentiality, authenticity, and integrity. I might be wrong on this.

With that said, is it even necessary to perform ECDSA signing on this encrypted image? I understand that the purpose of ECDSA is to provide authenticity from the person who provides the ciphertext, but since the encrypted image was already authenticated via AES-GCM, this seems like a redundant option.

I have a 16MB image that I'm encrypting and authenticating using AES-GCM. I obtain a 16MB encrypted image and a MAC. From what I could tell, this should provide me both confidentiality, authenticity, and integrity. I might be wrong on this.

This is correct; AES-GCM is designed to offer confidentiality, authenticity, and integrity.

More details

You need to define who is supposed to be able to both verify the authenticity/integrity of your image, and who is supposed to be able to create authentic images.

In the case that you are the sole party that will be creating and accessing the image(s), then using ECDSA (or any signature algorithm) does not offer you any advantages. It will increase implementation complexity, and require more resources for no real benefit.

This situation applies if you are storing the image for personal use.

In the case that you are sharing that image with 1 other party, and both parties are allowed to create authentic ciphertexts, then AES-GCM is still sufficient by itself.

An example of this type of situation is secure instant messaging*.

If you want the world at large to be able to verify that a given ciphertext was created by yourself, without giving them the ability to create authentic ciphertexts themselves, then you would need to use ECDSA. Considering that the information is also encrypted, this seems like a relatively uncommon use case.

An example of this situation might be that you are forming some kind of cryptographic commitment to the image, which will only be revealed at a later date.

*Note: To set up a secured communications channel would likely involve the use of digital signatures; This appears to be beyond the scope of your question


Why cant Public Key Encryption be perfectly secure? I would be very grateful for any help. I cant figure out why (probabilistic) public key encryption schemes can never provide perfect secrecy? Any Ideas?

Excerpt:
In contrast to the private-key setting, perfectly-secret public-key encryption does not exist. (We stress that this holds regardless of how long the keys are and how short the message is.) In fact, given pk and a ciphertext c computed via c ← Enc_pk(m), it is possible for an unbounded adversary to determine the message m with probability 1.

(See comments for why this is not a duplicate.)

The threshold for a perfectly secure system is that a computationally unbounded adversary cannot conclude anything about the plaintext from the ciphertext. With a public-key system, the attacker can try to encrypt messages with the real public key; this is not possible with one-time pads. What the attacker can do, quite simply, is to try all one-bit messages, then all two-bit messages, then all three-bit messages, etc., looking for a matching ciphertext.

Now, a public-key encryption algorithm may involve some randomness. The way to handle this is to try all possible outputs of the random number generator. You can make an algorithm $\textsf{Check(c,k,m,r)}$, where $c$ is the known ciphertext, $k$ the known public key, $m$ the guessed message, and $r$ is a string of bits. This runs the public-key algorithm with key $k$ on message $m$. Where the algorithm needs a random bit, it takes the first unused bit of $r$ (so it starts with the first bit, then the second, etc.), so the algorithm becomes deterministic. If all the bits of $r$ have been used and it needs another random bit, or if the encryption completes and the generated ciphertext does not match $c$, it returns False; if the encryption completes and the ciphertext matches $c$, it returns True. You can then run $\textsf{Check}$ with 1-bit $m$ and 1-bit $r$, then 1-bit $m$ and 2-bit $r$, then 2-bit $m$ and 1-bit $r$, then 3 and 1, then 2 and 2, then 1 and 3, etc. (i.e. the sum of the lengths of $m$ and $r$ is two, then three, then four, etc.) This will terminate with $\textsf{Check}$ returning True; when it does, you know what $m$ is.


How is the recommended NIST modulus for DLP chosen/calculated? NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. From this answer it appears that the range of private key numbers is derived by calculating a prime modulus via $2⋅p$ where $p$ is a 256-bit prime and then adding $1$ to the result (e.g. $2p+1$). If the result $n$ is a prime number and $a$ in $a^2 \pmod{n} \ne 1$, then we can use $n$ as the modulus.

I believe the difference in the recommended size between the private key (256-bit) and the modulus (3072-bit) has to do with the General Number Field Sieve Attack which has to do with the size of the modulus and not the size of the private key exponent. So the modulus needs to be much larger than the private key exponent.

My question is how the 3072 modulus derived? Not to implement my own of course, but to understand how it works. For example, does one simply choose a 3071-bit prime, multiply it by $2$ and add $1$, testing for whether the result is prime? If it is prime then check whether $a^2 \pmod{n} \ne 1$, and if it's not, then we can choose $2$ for the base a random private key exponent that's at least 256-bits and know that the best attacks will still require $\sqrt{2^{256}}$ brute force exponentiations to determine the private key exponent?

How is the 3072-bit modulus derived?

Find the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c)$$ and $q = (p - 1)/2$ are prime, and $p \equiv 7 \pmod 8$.  In this case, $n = 3072$ and so $c = 1690314$.

Use $g = 2$ as the generator.

(Here $\pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/(2i - 1)]$ as is customary.)

Why this shape?

This follows the procedure of RFC 2412, Appendix E, and matches Group 15 of RFC 3526:

We choose $p$ to be a safe prime—that is, choose $p$ so that $q = (p - 1)/2$ is also prime—so that the only subgroup orders are $\{1, 2, q, 2q\}$, which limits Lim–Lee active small-subgroup attacks.
We choose $p \equiv 7 \pmod 8$ so that, by the law of quadratic reciprocity, $g = 2$ has prime order $q$, since $g = 2$ is a convenient base, and a composite-order subgroup would leak some of the secret exponent.

(If your key is $h \equiv g^x \pmod p$ and $g$ generates the whole group or a composite-order subgroup rather than a prime-order subgroup other than $\{-1,1\}$, then it is easy to tell whether $x$ is even or odd by testing whether $h^{(p - 1)/2} \equiv 1 \pmod p$ or not; the same idea generalizes to composite $q$.)
We choose a shape with no particularly nice pattern to prevent SNFS attacks.
We choose specifically the semi-rigid RFC 3526 groups from the RFC 2412 process with the particular nothing-up-my-sleeves constant $\pi$—rather than $e$ or $\sqrt 2$ or $\cos 1$ or, worse, randomly chosen bits—to give slightly more confidence that there is no back door in the prime choice.

Actually, even better, we just use the elliptic-curve-based X25519 which is faster, safer, and free of magic constants like $\pi$!


How HOTP values are validated according to RFC 4226 In Section 7.2 "Validation of HOTP Values" of the HOTP spec (RFC 4226) it says, in part,

  The HOTP client (hardware or software token) increments its counter
  and then calculates the next HOTP value HOTP client.  If the value
  received by the authentication server matches the value calculated by
  the client, then the HOTP value is validated.

I don't understand this. Doesn't the client send the value it calculated to the authentication server? Thus, wouldn't "the value received by the authentication server matches the value calculated by the client" always be true?

What I am misunderstanding here?

I agree that Gilles' interpretation in the comments is the only one that makes sense; the RFC clearly contains an editorial error, and should read either (emphasis indicates corrections):

  "If the value calculated by the authentication server matches the value calculated by the client, then the HOTP value is validated."

or:

  "If the value received by the authentication server matches the value calculated by the server, then the HOTP value is validated."

The first sentence in your quote isn't grammatical anyway: the words "HOTP client" appear to have been randomly and meaninglessly appended to it, perhaps as a result of careless copy-pasting.

The IETF has a whole bunch of errata for RFC 4226, but this particular mistake doesn't appear to be listed there.  You might want to report it yourself.


Determine hashing algorithm I have a plaintext and a hash output, two hash outputs to be precise.
One is HEX encoded, and I have no idea on the other one.

plaintext=halflife

hash=1e4dfacf77efceb3076bb551932e6e40

hash2=PN[6O265X^W6YEIK`/YJNVX54N\HY

I can't be actually sure which hash is output derived from my plaintext, and which isn't.
Is there a tool I could use to figure out how was my plaintext hashed, so it would come out like this?
If not, what procedures would you recommend?

UPDATE:
I now know that the hash2 is actually not the hash of the plaintext, but something else. I also know that if I change the plaintext > hash gets updated, and if I change hash back to it's original state > original plaintext is considered correct.

I just tried this tool to no avail

https://www.onlinehashcrack.com/hash-generator.php#res

My best guess is that the program is actually doing more than a simple hash, it may be a number of hash rounds or some other manipulations

You said that changing the plaintext makes the hash change. So you have a program which performs such unknown hash. Decompile it and work out the process behind. The algorithm is not "secret", it's stored in the executable