Using compression to test encryption Is the uncompressibility of encrypted data a necessary property for a good cryptographic algorithm?

To make a crude experiment, I encrypted an 8K file with all 'A' and then compressed both the encrypted and the unencrypted file.

The compressed unencrypted file went down to less than 200 bytes while the conpressed encrypted file became larger than the encrypted file.

I think that while this result says nothing about the goodness of the encryption, the opposite result (i.e. if the encrypted file would shrink after compression) would have revelead a weakness of the encrypting algorithm.

Am I correct or am I missing something about the relation between encryption and compression?

Yes, a ciphertext of a bulk encryption algorithm normally should not be compressible to less than the plaintext size¹ (at least, if the compression function does not know the encryption key), other than in some corner cases which will occur only with negligible probability (like you hitting the one plaintext which will encrypt to the all-zero-string).

¹Of course, if the encryption algorithm applies some encoding after encrypting which makes the ciphertext larger, like PGP's ASCII-armor, Base64 or Hexadecimal encoding, you can compress this resulting encoded ciphertext, but not to less than the original plaintext size. Similar things could occur with some asymmetrical encryption algorithms, which have slightly biased output, when (mis)used for bulk encryption - don't do this.

If the compressor knows the algorithm and key, it can simply decrypt the ciphertext and then compress the plaintext, of course.

With bad modes of operation, such as ECB mode, some repetitions in the plain text will also show through in the cipher text (see this famous example in Wikipeda), which then might show by compressibility of the ciphertext (the ECB image is bigger than the plain"text" one, but still smaller than the CBC one).

On the other hand, non-compressibility of ciphertext with generic compression algorithms is given by every not totally trivial encryption algorithm, even if they have to be categorized as broken by every aspect.


Formal proof of theorem concerning the Random Oracle Model Reading a book on cryptography by Douglas R. Stinson I've met the following theorem, which is stated without proof (see here).

Thereby, $\mathcal{F^{X,Y}}$ denotes the set of all functions from $\mathcal{X}$ to $\mathcal{Y}$ and $|\mathcal{Y}|=M$.

Is no proof given because it is hard, or because the proof is obvious ? Nothing is said about whether the message space $\mathcal X$ is finite or infinite. I guess, I could see informally that the probability must be constant if this space is finite.

Could someone show the formal proof or lead the way ?

As @K.G pointed out in the comments - the proof is obvious.

I'll explain:

We sample the function $h$ from the set of all possible functions that maps from the set $\mathcal{X}$ to the set $\mathcal{Y}$, where the size of the set $\mathcal{Y}$ is $M$. We denote the set of all possible functions from $\mathcal{X}$ to $\mathcal{Y}$ by $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$.
Note that it doesn't matter whether $\mathcal{X}$ is finite or infinite, as far as every function in $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ is defined on every value in $\mathcal{X}$ (which is the case, of course, by the definition of $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$). Then, if $|\mathcal{X}|$ is infinite, your question is in place: how can we hold such an $h$ (its size is infinite while our memory is finite)? The answer is that we can determine $h$ on-the-fly, whenever $h$ is being queries on $x$ first check whether $h$ was queried on $x$ beforehand, if so, there is an entry $(x,y)$ in $\mathcal{x}_0$ and we return $y$. Otherwise, if $h$ was not queried on $x$ before then we sample a uniformly random element $y$ from $\mathcal{Y}$ and add $(x,y)$ to $\mathcal{X}_0$.
Also note, that although the author only mentioned that

  $h\in \mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ is chosen
  randomly

he actually meant that $h$ is chosen randomly from a uniform distribution over $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ (otherwise the theorem is incorrect).
Now, take some $x\notin\mathcal{X}_0$, i.e. $h$ wasn't queried on $x$ before (thus, we don't know its answer to such query yet). Since $h$ was chosen uniformly at random from all possible functions it means that for every query $x\in\mathcal{X}$ $h$ would answer with a uniformly random element from $\mathcal{Y}$ and since $|\mathcal{Y}|=M$ every $y\in\mathcal{Y}$ has the same probability to be chosen as the answer for the query $x$. This probability is simply $Pr[h(x)=y]=1/M$.
Note that the above probability depends only on $M=|\mathcal{Y}|$ and not on $|\mathcal{X}|$ because the result of $h$ when applied to the query $x$ is an element which is chosen randomly from a uniform distribution over $\mathcal{Y}$, thus, every element $y\in\mathcal{Y}$ has the same probability to be chosen.


What is the threat to a PKI when the root CA certificate is generated using SHA1? We have thousands of servers that have been issued certificates signed by our CA using SHA256 but the our root CAs own certificate was generated using SHA1. Assuming SHA1 is no longer secure for our purposes what exactly is the threat to our infrastructure if our root CA certificate was signed using SHA1?

None.

You don't trust the Root CA certificate because it was signed by anything - you trust the Root CA because you (or someone on your behalf) placed it in your trust anchor store.

A Root CA certificate has a signature simply because it is mandatory within the X509 specification - it serves no other purpose.

Technically, the trust anchor doesn't have to be a certificate, but most (all?) operating systems have taken the decision to use the X509 certificate format to store the trust anchor - there are others defined (RFC 5914) that don't have a signature, but as far as I'm aware, they are not used.

SHA1 deprecation has been in the limelight lately.  If your subordinate CA certificates or your end-entity certificates are signed by SHA1, browsers will complain.  However, if you sign your Root CA certificate with MD5 or MD4 (or even something earlier if you can find the tools to do so) then everything will still work.

If you take a look at Google, Facebook, Microsoft (and no doubt many more) you'll find that they still have SHA-1 signed Root CA certificates.


RSA padding: risk of using constants Assume I want to make my RSA secure because I heard that textbook RSA, especially in conjunction with low exponents, is very risky. I decide to limit my message length to 100 and subsequently construct my padded message as follows:

m = '\x01'*70 + m + '\x01'*70

To improve performance, I choose $e=3$.

Why is this risky? After all, the padded message is large enough, i.e. knowing that $c=m^3 + k*n$, $k$ will be too high to bruteforce. At first glance I don't see any attacks that could work here therefore it should be safe?

By narrowing the space of messages and ciphertexts you are willing to consider to a tiny fraction of fewer than $1/2^{1000}$ of them, you cannot prove that an algorithm for breaking this translates to an algorithm for computing cube roots modulo $n$ in general.

Consequently you can't rely on the decades of work that have been put into failing to find a way to compute cube roots modulo $n$, and you have to redo those decades of failure anew in order to get confidence in the system's security.


Elliptic curve point addition clarification In a book I am reading currently, it asks to perform the addition of $(2,7)$ and $(5,2)$ in the elliptic curve defined as $y^2=x^3+2x+2 \mod 17$.

Now, I believe this is impossible, as these points are not part of the group, hence it is not possible to compute the third point. Is that correct?

Pretty sure I am correct, but just would like clarification that i'm not making a huge mistake, as this book has not had any errors so far so I'm suprised to see one.

What happens if you naively plug those numbers into the addition formula?  Anything obviously untoward?

This may be an exercise in the impact of invalid-curve attacks.


What was the BassOmatic cipher, and what made it so weak? According to Wikipedia, this homebrew cipher was originally used in PGP, before Phil Zimmermann replaced it with IDEA. Supposedly, insecurities in the algorithm were pointed out to him, leading to this change. While I have read the PGP 1.0 source code and saw the implementation of the cipher, that didn't help me actually understand it. I can't seem to find any complete description of the algorithm or, particularly, its weaknesses other than what is provided on Wikipedia:

  The chosen key schedule produces a total of 8 permutation tables, each a permutation of the numbers 0 to 255. Each round consists of 4 operations: XORing the block with one of the permutation tables, shredding or permuting individual bits throughout the block, an unkeyed diffusion called raking, and a substitution step using the permutation tables as S-boxes. The shredding step can either permute all 8 bit-planes independently, or in groups of 4, depending on control bit 3. The permutation tables stay the same through all rounds of encryption on a given block, but if control bit 5 is set, then the tables are regenerated after each block.

I could also find a published quote from the book which Wikipedia used as a citation:

  After Biham and Zimmermann go their food and sat down, Zimmermann took out a few pages of computer listings.  Within minutes, Birham was finding fundamental flaws in Bass-O-Matic.  Some of the flaws were subtle-weaknesses that made the algorithm susceptible to differential cryptanalysis, which was Birham’s speciality. Others were more embarrassing, like a conceptual error in Zimmermann’s algorithm that prevented the last bit of each byte from being properly encrypted.  After ten minutes of Birham’s onslaught, Zimmermann realized that Bass-O-Matic was a lost cause.

How did BassOmatic work, and what were the weaknesses that lead to its replacement?

Phil Zimmermann did not use DES or the RSA-owned RC-2 as models for the Bass-O-Matic cipher.
For the basis of that symmetric cipher, he used the work of a man named Charlie Merritt. Zimmermann's strong suit was not mathematics but programming in C, so he needed help. Merritt had called Zimmermann by phone (at Metamorphic Systems, a 1980 startup by Zimmermann), and after that fortunate call, they talked more than once a week for several years.
Merritt, a computer programmer from Arkansas,

specialized in writing public-key cryptography implementations. Merritt wrote the
first commercially successful implementation of RSA for a personal
computer and taught Phil Zimmermann how to do arithmetic with
hundred-digit numbers on a personal computer. [1]

Merritt was an expert in assembly language. He had developed an implementation of RSA that was running on Z-80 computers with the CP/M operating system. It took, by the way, ten minutes to generate a 256-bit key. In 1980, Merritt's success in doing this inspired Zimmermann. They talked about Zimmermann putting crypto on his 8088 card for the Apple II, and everything else having to do with cryptography.
Merritt and Zimmermann, "PRZ," got along over the phone. Merritt said,

He began talking about protocols, in great detail. For hours, on the
phone. I hate protocols, that's for the Phone Company. But he needed a
brick wall. Then he began asking exactly how math was implemented on a
Z80. I mean detailed stuff about memory allocation, and adding two
giant numbers and what about the carry bit. We were back in my
territory. [2]

They finally met face-to-face in the summer of 1986.
Zimmermann labored in the wilderness for years. In November 1986, Merritt was working on a conventional cipher for the U.S. Navy, and this cipher was the basis for the Bass-O-Matic. Zimmermann then made it stronger by adding several rounds of substitution.
Time for the character in black to enter the stage: the NSA periodically threatened Merritt at this time. "They always travel in pairs," Merritt said. Unworried, Merritt started selling his encryption system, the DEDICATE/32, which used 256-bit keys.
Merritt's DEDICATE/32 was slow, and this convinced Zimmermann to create a hybrid system: slow RSA to exchange keys and something quicker for the bulk encryption.
The plot thickens: in 1991, a U.S. Senator sneaked this into a draft bill (S.266):

It is the sense of Congress that providers of electronic
communications services and manufacturers of electronic communications
service equipment shall ensure that communications systems permit the
government to obtain the plaintext contents of voice, data, and other
communications when appropriately authorized by law. [3]

Thank you, Senator Joe Biden.
Interestingly, Biden's clause in the draft bill got removed because of the outrage it caused. The furor pushed Zimmermann to release PGP 1.0. PRZ was angry.
Zimmermann let PGP 1.0 loose upon the word, but he said, "the Bass-O-Matic has not yet (in 89) been through a formal security review and has had only limited peer review."
Zimmermann needed to get an expert opinion on the Bass-O-Matic, so he attended Crypto '91 in Santa Barbara, California, in August. He and Eli Biham sat down in the UCSB cafeteria, and Biham told him that the Bass-O-Matic was vulnerable to differential cryptanalysis attack (Biham's specialty). Additionally, the most embarrassing error "prevented the last bit of each byte from being properly encrypted." So, the Bass-O-Matic was unceremoniously thrown into the trash.
Biham had destroyed the Bass-O-Matic in ten minutes over lunch.
Zimmermann then took up IDEA, added key certification, and PGP 2.0 was born.
[1] Garfinkel, Simson (December 1, 1994). PGP: Pretty Good Privacy. O'Reilly Media. p. 372, ISBN 978-1-56592-098-9.
[2] Ibid., 90.
[3] Ibid., 97.


Confusing terminology about stream ciphers In their book, Understanding Cryptography, on page 37, Christof Paar and Jan Pelzel write:

  Definition 2.2.2 One-Time Pad (OTP)

  A stream cipher for which

  the key stream s0,s1,s2,... is generated by a true random number generator, and
  the key stream is only known to the legitimate communicating parties, and
  every key stream bit s[i] is only used once

I have a problem with the third statement. Perhaps I am confused because of the way it is expressed in the English language.

It says every bit s[i] has to be used once.
How come: s[i] is either 0 or 1? So, as soon as I use value 0 for s[12], does it mean I can't use value 0 anymore?

I am confused as to what the authors mean.

Furthermore, they also say:

  Key stream bits cannot be re-used. This implies that we need one key
  bit for every bit of plaintext

Why does it imply that we need one bit for every plain text ?

If you used the randomly generated keystream bit $k[i]$ twice (think of it as a random variable, uniformly and independently generated at time $i$) at positions $i,i+\tau,$ then you'd have
$$
c[i]=p[i] \oplus k[i]
$$
and
$$
c[i+\tau]=p[i+\tau] \oplus k[i],
$$
then adding the ciphertext bits would yield the plaintext bit "difference"
$$
p[i+\tau]\oplus p[i],
$$
destroying the property that
$$
c[i]\oplus c[i+\tau],
$$
is independent and uniformly distributed, and making the conditional distribution of $c[i+\tau]$ given $c[i]$ dependent on the plaintext difference $p[i+\tau]\oplus p[i],$ which need not be uniform.

Thus the ciphertext sequence is no longer purely random (independent and uniformly distributed) which destroys the perfect secrecy property of the OTP system, since the ciphertext distribution is no longer independent of the plaintext distribution.


Appending ECDSA signature to a message I need to authenticate a message sent to an embedded device (which limits my options in terms of just using an existing convention).  I can run ECDH/ECDSA on the device and can use SHA-256 as a hash function but pretty much anything else is beyond the resources of the device.  Also I can pre-share a public key on the device.

If I simply create a hash from the message, sign the hash using ECDSA with the private key, then append the signature to the message, send it to the device, then on the device verify the signature on the device using the public key against the message hash, is this secure?

Any traps to be aware of?

Edit:

The resource I was looking for is here Authenticate encryption, but I now realize I don't understand secure communication well enough to know what questions to ask.

As per @fgrieu's suggestion I investigate RSA rather than ECDSA, and found that for a NIST-256 curve signature verification takes 0.740s on the device whereas RSA-1024 signature verification takes 0.230s.  Code sizes are about the same (3.5k) but the stack usage for the RSA was too high (3.5k) for the amount of RAM I have available.  Going down to secp160r1 EC gets the verification time down to about the same as the RSA.

If the message is small enough to be stored in full with the signature in the embedded device, and the software on the embedded device is trusted to not be altered (including the embedded public key) or worked around (a JTAG port or a clever upset can change PC across a test), this is fine, and an intended usage of ECDSA. Most implementation traps are on the signing side.

I doubt that "pretty much anything else is beyond the resources of the device", though. RSA (or Rabbin) signature verification in software is much simpler (thus uses less code) and much faster (like a factor of 10 for usal key size) than ECDSA signature verification. Reasons to prefer ECDSA in this particular application can only be:

RAM is horribly limited; but 1k byte (used only during signature verification) is ample for RSA-2048.
The signature size matters much (it's 256-byte with RSA-2048 versus 56-byte for ECDSA P-224 or ECDSA P-256/secp256r1 or secp256k1) and we can't use RSA signature with message recovery (ISO 9796-2) because

the signature must be separate from the message (RSA signature with message recovery embeds part of the message in the signature, e.g. 222 bytes in a 256-byte signature; that part becomes available only as a byproduct of signature verification)
or the message is too small (below 200 bytes) for message recovery being a space saver.

Performance on the signer side is a limiting factor. ECDSA (or better, EdDSA as in Ed25519) has a clear edge there.
Some regulation/constraint prescribes ECDSA (like there's already an implementation, and there's not one for RSA, and time to market is the essence).
(Update per comment): code size; but that can only realistically be when there's already some code (ECDH) that already does a large fraction of ECDSA, and uses arithmetic code that for some reason can't be re-purposed for RSA  (e.g. it handles fixed-size arguments only; or its modular reduction is specialized for moduli of a certain form); and space is badly missing, as RSA itself can fit under 3kByte including public key (add <1.5kByte for SHA-256).


Key-Exchange in Steganography I know there are key-exchange methods in Cryptography. But in case of Secret-key Steganography, what actually stego-key means and how can we use the key and once used how we exchange that with the receiver?

The way in which the stego key is used depends on the type of media and algorithm used for hiding data. For example, in image steganography the stego key is used to select the pixels where the data will be hidden. An attacker without the key does not know what pixels he have to read.

Note that before hiding data is usual to encrypt the message so a crypto key is also needed.

On the other hand, the mechanism used to exchange a key using steganography is known as Public-Key Steganography. Check the following reference:

https://www.cs.cmu.edu/~biglou/pubkeystego.pdf

A simple option is to use public key cryptography hiding the message encrypted with the public key into the image (we do this without stego key, so that anyone can extract it).
An attacker that extracts the message will not be able to tell whether the data extracted is a cipher text or random noise. Only the one with the private key will be able to read the message.


FIPS 140-2 compliance across symmetric and asymmetric primitives I'm looking to learn more about FIPS compliance.
I noted that it seems FIPS 140-2, is a holistic article, that then cites sub articles like FIPS 197...
It's tricky to ascertain the full picture. Is there a document anyone knows of that will specify:

Approved symmetric ciphers
Approved elliptic curves
Approved signature algos
Approved hashing functions

If not is there any resource you know of that can simplify interpretation of the regulation?

Start with Annex A: Approved Security Functions.  That will give you a good idea of the approved functions.  A few caveats:

Not all modules support all approved functions, e.g. OpenSSL doesn't support quite a few of them (OpenSSL's validation isn't active anymore anyway)
FIPS 140 is a constantly evolving target, so today's validated module is tomorrow's no longer validated module.  For instance, the reason OpenSSL's validation is no longer active is because FIPS 140 changed to disallow the generation of RSA keys with 1024 bits and signatures that used 1024 bit keys, though it still allows signature verification with 1024 bit keys.
Just because an algorithm is FIPS 140 approved doesn't mean customers will accept it.
Both 3DES and SHA1 are still FIPS approved algorithms, but customers will complain about the use of either (both have been deprecated by NIST).


64 bit clock cipher with CFB mode. One-byte defected from ciphertext. What is the number of bits defected from plaintext I have a question from an exam;

We encrypted a message of size 100 Bytes with CFB. In the transmission, byte number 12 got defected. How many bits defected will be in the decryption. The answer is 72 bits and I don't understand why?

The decryption of CFB mode as follows;

$$ P_i = E_k(C_{i-1}) \oplus C_i$$
$$C_0= \operatorname{IV}$$

Bit flipping attack in CFB

If there is a Bit Flipping attack in the ciphertext then we have two cases.

$\color{red}{\textbf{Red case:}}$ The last ciphertext bit is flipped. This only affects the corresponding plaintext block. So the attacker can change a plaintext bit without affecting any other bits.

$\color{ForestGreen}{\textbf{Green case:}}$ Assuming that the $i$th ciphertext bit is changed, $ 0 \leq i < n$ where $n$ is the total number of blocks, then this time two plaintexts blocks are affected. We can also see from the equations, too;

$$ P_i = E_k(C_{i-1}) \oplus \color{blue}{C_i}$$
$$ P_{i+1} = E_k(\color{blue}{C_{i}}) \oplus C_{i+1}$$

Note: Bit flipping on IV of CFB mode has no good effect as in CBC mode.

Your question

Since you have 100 Bytes, and 64-bit block cipher has 8-byte block size, the 12th-byte number falls into the second ciphertext. If it falls into the last one then only one byte is effected, $\color{red}{\textbf{red case}}$.

Now, since we are in the $\color{ForestGreen}{\textbf{green case}}$, for a defected one-byte $C_i$, we will see two plaintexts are effected $P_i$ and $P_{i+1}$. $P_i$ has one byte defection and $P_{i+1}$ has full block defection.

Fgrieu gave the probabilities of the defection in the comments. As noted, the defection is not clear about how many bits are flipped. It may be 1 or 8. Also, the affected full block is not under control. For example, if we assume that the cipher has avalanche criteria we expect each of the ciphertext bits has 50% probability to have a flip. Therefore we can say it is between 1 and 64. So the total number of affected bits is between 2 to 72.

Let finish this with mitigations:

The attack/defection is possible since there is no integrity on the data. A MAC or an HMAC can be used to prevent, or better use authenticated encryption which provides confidentiality, integrity, and authenticity. In TLS 1.3., CCM and GCM are standardized authenticated encryption modes.


Hash function and Digital Encryption Algorithm I am familiar with the fundamentals of cryptography as well as Digital Signatures. I understand how DSA like RSA works and the fundamentals of mathematics behind digital signing and verification. I also have a reasonable understanding of how bitcoin works. However I can not understand the role of hash function (SHA-256) in bitcoin blockchain.

The role of a private key and its corresponding public key seems clear to me.

A public key can be used by the sender of a message to encrypt the message than can only be decrypted with the private key of the recipient.
A private key can be use to sign a message, so when the message is encrypted with the private key the recipient can verify, by using the public key, that the message must have been signed by the owner of the private key.

The questions rises is bitcoin protocol.
I understand that the public key is use to derive the bitcoin address. Therefore, having the private key associated to that address allows you to prove that you are the owner of that address.

The hash function (SHA-256) is used to make the digest of the of the transaction and block in the block chain. Somewhere I read that “To save time, digital signature protocols are often implemented with one-way hash functions (...). Instead of signing a document, Alice signs the hash of the document.”

I've got three related questions:

Is that the only role of the hash function in the bitcoin protocol?
What is the role of the hash function in the verification of the ownership of the address?
Couldn’t we get the same result of proving ownership without the hash function?

One reason ECDSA (the elliptic curve variant of DSA used by Bitcoin) first hashes data is to make forging signatures harder. Consider the first two steps in ECDSA:

  Calculate $e = \text{HASH}(m)$, where $\text{HASH}$ is a cryptographic hash function, such as SHA-2.
  Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$is the bit length of the group order $n$.

Suppose instead that $z$ is the $L_n$ leftmost bits of the message $m$ instead. In that case the resulting signature is a valid signature for any message $m$ with the same $L_n$ leftmost bits. In the case of ECDSA in bitcoin $L_n = 256$, or 32 bytes (which would be 32 characters in ASCII encoding). This gives a lot of possible ways to forge a message as only 32 characters need to be the same for the signature to be valid.

The way to avoid this would be use all the bits of the message in the signature, but with arbitrarily large messages this can cause huge performance issues as we're now performing public key crypto on potentially much larger amounts of data.

So the idea of using the hash function is to take an arbitrarily large amount of data and transform it into a much smaller amount of data before performing any of the expensive operations on it. But we also need this to happen in a way such that it is hard, given message $m_1$, to find another message $m_2$ that produces the same hash output. Otherwise we again have the case that the signature for $m_1$ is also valid for $m_2$. The property of cryptographic hash functions (which SHA-2 falls under) known as (second) pre-image resistance gives us this property.


Storing passphrase and encrypted private key I have to protect a key pair with a passphrase and to store these information someway in a table. I read that I can protect the key pair (specifically, the private one) using a digest of the passphrase as a symmetric key for a symmetric algorithm.

I also found that a good way to store a password (and therefore, I think also a passphrase) is hashing it with a salt with a password hashing algorithm (e.g. PBKDF2, bcrypt, etc.) and save the digest and the salt.

The problem is that I'm pretty sure that storing together, the salt, the digest of the passphrase - which is at the end the symmetric key used to encrypt the private key - and the private key itself, encrypted with the digest of the passphrase, is a naive solution.

But if I don't save the digest of passphrase together with the encrypted private key, how can I be sure, when decrypting the private key with an inserted passphrase, that the passphrase and the obtained private key are the correct ones?

I tried to look for an answer on the forum but I didn't find any good solution to my problem. Can you help me?

The problem is that I'm pretty sure that storing together, the salt, the digest of the passphrase - which is at the end the symmetric key used to encrypt the private key - and the private key itself, encrypted with the digest of the passphrase, is a naive solution.

Storing the digest of course negates both the PKBDF function and the encryption. Storing the salt and wrapped key is of course not a good idea.

  But if I don't save the digest of passphrase together with the encrypted private key, how can I be sure, when decrypting the private key with an inserted passphrase, that the passphrase and the obtained private key are the correct ones?

The easiest way to do this is to use the key for authenticated encryption such as GCM or SIV. If the authentication succeeds then you know that the key was encrypted with the key derived from the passphrase.

So you'd store:

salt | authenticated_ciphertext

where the tag is the authentication tag calculated by the authenticated encryption.

You'd calculate the salt by using a secure random number generator, the ciphertext as:

key = PKBDF2(password, salt, iteration_count, key_size)
authenticated_ciphertext = SIV_AES(key, encoded_rsa_key, [])

Now decryption will fail as SIV_AES includes an IV that doubles as an authentication tag. [] is the additional authenticated data (AAD) which is the empty array, i.e. it is not present.

A disadvantage of this scheme is that you don't know on failure if you have the wrong passphrase or the wrong ciphertext. The simplest way to deal with this is to include a specific ID with the ciphertext and treat it as Additional Authenticated Data in your authenticated encryption. Furthermore, you might want to indicate the protocol version:

protocol | id | salt | authenticated_ciphertext

and the calculations:

key = PKBDF2(password, salt, iteration_count, key_size)
authenticated_ciphertext = SIV_AES(key, encoded_rsa_key, protocol | id)

so now you've got a protocol and id which are also protected by the authentication tag.

Notes:

in above scheme the iteration_count and key_size are considered configuration parameters (i.e. stored separately from the ciphertext), possibly derived from the protocol in the later version;
the above scheme has the disadvantage that the authentication tag can only be verified after decrypting; this is both a disadvantage with regards to security as well as the legit user having to wait a long time for large plaintext - I won't go into the details of these weaknesses here;
note that if active attacks are possible that the stored data may be altered; in that case you should consider that any part of the data (including the protocol, id or just the authentication tag) may have been altered - relying on any specific error condition is in that case not possible anymore.
don't forget to zero your sensitive data in memory after you've concluded your private key calculations or if you've encountered an error condition;

If you're starting to see the full scale of what you're attempting, you might want to use an existing scheme instead.


Combining several symmetric ciphers using XOR I have seen a talk by Rüdiger Weis, where he says that you can combine two symmetric ciphers using XOR. According to him, that has the effect that its sufficient if only one of the ciphers is secure.

How does he do that? I have thought of

ciphertext = twofish(message) XOR aes(message)

but I can't see how the receiver would decrypt that, as he does not know either twofish(message) or aes(message).

I also thought of

ciphertext = twofish(aes(message))

But there is no XOR involved. So whats the problem with the above approach?

I have seen this answer but I don't think its relevant anymore. Using multiple ciphers may be needed to defend against NSA mass surveillance.

EDIT: The two formulas is what I came up with. Rüdiger Weis only said, "you can combine ciphers and XOR is involved".

The usual method to do this is to turn the block cipher into a stream cipher. In that way the ciphertext is generated by XOR'ing the plaintext with a generated key stream. This key stream in turn is generated by the mode of operation that turns the block cipher into a key stream. There are several of these modes, but CTR mode of operation is most often used (in new protocols anyway). You don't need to do this for stream ciphers of course.

Now you can just use $C = P \oplus K^1 \oplus K^2$ where $C$ is the ciphertext, $P$ is the plaintext and $K^1$ is the key stream of one cipher and $K^2$ is the key stream of the other cipher. As XOR is associative and commutative you can see this as first applying key stream 1 or key stream 2, and then the other. The key streams will have the same size as the plaintext.

This is similar to applying two one-time-pads to the plaintext. Given a secure block cipher, a key stream generated using CTR is secure but not perfectly secure. So it's not identical to using two one-time-pads. One difference with a one time pad is that CTR mode requires a nonce; the same nonce can be used for both stream ciphers though.

In contrast to one time pads it is possible to cryptoanalyze a stream cipher. This means that the key streams should be sufficiently independent of one another. So the stream ciphers should be created using separate keys and ciphers. If you would use the same key, IV and cipher then key streams would cancel each other out, leaving you with the plaintext after encryption.

Small stream cipher introduction

With a stream cipher a key and a nonce are used with the cipher to generate a key stream of any size. Usually the plaintext is not needed as input at this stage. The key stream is then XOR'ed with the plaintext. As the key stream should be indistinguishable from random to an attacker, it should be impossible to invert this operation without the key and nonce. Decryption is identical to encryption and if a block cipher is used then you may only need to use the block cipher in one direction (encryption or decryption). You can encrypt and decrypt by applying the key streams in any order as the XOR operation is associative and commutative.


The differences between the attackers in the definitions of IND-ATK and NM-ATK I read the definitions of IND-ATK and NM-ATK in a paper. Let $\Pi = \left( Gen, Enc, Dec \right)$ be a public key scheme. And let $A = \left( A_{1}, A_{2} \right)$ be an adversary attacking $\Pi$ in the sense of IND-ATK. Let $B = \left(B_{1}, B_{2} \right)$ be an adversary attacking $\Pi$ in the sense of NM-ATK.

The inputs of $A_{1}$ and $B_{1}$ are both the public key $pk$. The output of $A_{1}$ is $(x_{0}, x_{1}, s_{A} )$ but the one of $B_{1}$ is $(M, s_{B})$.

What makes the outputs different? Why not the output of $B_{1}$ just includes two messages instead of a set of messages?

Actually, $A_{2}$ and $B_{2}$ are both used to compare two messages in some sense.

You say:

  Actually, $A_2$ and $B_2$ are both used to decide which one of two
  messages are encrypted for the challenge.

However, this is not true. The definition of the IND and NM games are different. This difference is summarized in this paragraph from the very same paper [Section 2.3]:

  The goal of the adversary, given a ciphertext y, is not (as with
  indistinguishability) to learn something about its plaintext $x$, but
  only to output a vector $\mathbf y$ of ciphertexts whose decryption $\mathbf x$ is
  “meaningfully related” to $x$, meaning that $R(\mathbf x, x)$ holds for some
  relation $R$.


Is ElGamal IND-CCA1? We all know that textbook ElGamal falls due to chosen ciphertext attacks, because of its multiplicative homomorphic property ($E(A)*E(B)=E(AB)$).

However these attacks require the ciphertext ($E(A)$ or $E(B)$) to be given, meaning as per this answer this would mean ElGamal isn't IND-CCA2, but IND-CCA1 as the access to a decryption oracle before the ciphertext is known doesn't help anything.

Hence my question:
Is the ElGamal encryption scheme IND-CCA1 or "only" IND-CPA?

"Bonus" question:
If the ElGamal encryption scheme isn't IND-CCA1 how would the CCA1 attack look like?

The CCA1 security of ElGamal is a big open question. There are no attacks known, but standard reductions don't seem to work.

In 1991, Damgard proposed an ElGamal variant and proved it to be CCA1-secure (albeit under a very problematic non-falsifiable assumption, called the "knowledge of exponent assumption"); see the paper here http://link.springer.com/chapter/10.1007%2F3-540-46766-1_36.

More recently, Lipmaa here showed that ElGamal can be proven to be CCA1-secure under a non-standard (but falsifiable) assumption. The assumption is that DDH is hard even given access to a static CDH oracle (that computes the Diffie-Hellman function for a fixed "secret" exponent). [Caveat: I haven't read the paper so I can't vouch for correctness...]


Why do I need to add the original salt to each hash iteration of a password? I understand it is important to hash passwords over multiple iterations to make things harder for an attacker. I have read numerous times that when processing these iterations, it is critical to hash not only the result of the previous hashing, but also append the original salt each time.

In other words, I think I need to not do this:

var hash = sha512(salt + password);
for (i = 0; i < 1000; i++) {
    hash = sha512(hash);
}

And instead, I can do this:

var hash = sha512(salt + password);
for (i = 0; i < 1000; i++) {
    hash = sha512(salt + hash);
}

My question is regarding the math here. Why does my bad example above make things easier for an attacker? I've heard that it would increase the likelihood of collisions but I am not understanding why.

 reposted from https://stackoverflow.com/questions/21003216/why-do-i-need-to-add-the-original-salt-to-each-hash-iteration-of-a-password

Given that SHA-512 is used, there is no practical benefit to iterating hash = sha512(salt + hash) compared to iterating just hash = sha512(hash). For some parameters, it even weakens the scheme by a factor of nearly 2 against the attack that most matters: guessing the password.

Let's first justify the weakening. Assume salt is 125 bytes. salt + hash is 1512 bits long, and two SHA-512 rounds (each hashing 1024 bits) will be used by the legitimate user to compute hash = sha512(salt + hash), rather than one round for hash = sha512(hash). On the other hand, the adversary trying millions of passwords can pre-compute the result of one SHA-512 round for each of the $2^{24}$ 1024-bit strings starting in salt, then replace the first round of each computation of hash = sha512(salt + hash) by a table lookup in that 1 MiB table. The ill-advised idea of hashing salt prevents legitimate users from about doubling the number of iterations at constant effort/time, when it is only a marginal annoyance to attackers.

In theory, when using some unspecified hash function H, it is a reasonable idea to perform something like

var hash = H(salt + password);
for (i = 0; i < n; i++) {
    hash = H(hash + i + salt + password);
}

A rationale behind hashing i is that it makes it highly implausible that a short cycle could be reached in the iteration, regardless of considerations on the width of hash. Without this precaution, if hash is $b$-bit, odd of entering a cycle on or before $n$ iterations are about $n\cdot(n+1)/2^{b+1}$ (when $n\ll2^{b/2}$).

A rationale behind hashing salt or/and password or/and i is that it makes it impossible for an adversary to perform a precomputation that would be conceivable for iterated hash = H(hash) if the adversary can hope to ever perform next to $2^b$ hashes and store next to $2^b/n$ values. Assuming that, an attacker could pre-compute the result of $n/2$ iterations for values of hash less than $2^{b+1}/n$. During the normal computation for a given salt + password, there is good chance that such low values of hash is reached, and the precomputed table usable as a speedup. Edit: it seems quite likely that the number of hashes or/and the memory necessary can be greatly improved, perhaps even to $O(2^{b/2})$ hashes or $O(2^{b/2}/n)$ values, though I can't figure how for now.

The above two things could be an issue when $b=128$ (e.g. when using MD5); but are a complete non-issue when $b=512$ (our situation since SHA-512 is used).

A rationale behind putting hash first is that it avoids the pitfall we first studied, when H is an iterated hash function starting with the beginning of the message, as most practical hash functions are.

Update following comment: a rationale behind not iterating hash = H(hash + password) (but rather including salt and i in the mix), when the width $b$ of the hash is small, and the number of iterations $n$ high, could be that in the former case an adversary might get some advantage by a strategy where for each plausible password she performs some precomputation on common values of password giving it some sizable advantage in recognizing password from the final value of hash, especially if many pairs (salt, full final hash) are available.

As an example of such a strategy, assume that $b=64$ and $n=2^{30}$. For any given password, a sizable fraction of salt values are such that a cycle is entered during the legitimate computation, and a powerful adversary can tabulate, independently of salt, a sizable fraction of the lower values of hash reached in such cycles. Then, for each final value of hash at hand, and each password, the adversary can iterate perhaps $2^{26}$ times, test if any of the (smaller) values reached is in the precomputed table, and in the affirmative make a full test for this password. Odds of recognizing a (salt,password) pair for a given effort are improved compared to pure brute force (at least when the number of password tested is such that a few are among the (salt,password) pairs, and neglecting the cost of the precomputation and table lookups; and I guess, with some refined strategies, even accounting for these costs).

Again, using $b=512$ is plenty appropriate to make iterating hash = H(hash) entirely satisfactory (assuming an attack using classical computers). It even seems possible to make a formal reduction from any attack against that to an attack on the hash (to keep the proof simple, it might help to prevent salt + password from having the same size as hash, e.g. by using a 65-byte salt).

And notice that there is at least one excellent reason not to include password in the mix: making it less likely that password could leak by some side channel on a legitimate user's platform, perhaps by a mechanism remotely similar to this.

Final note: the state of the art is not iterating a hash, but rather iterating a function requiring a large (and preferably parameterizable) amount of memory, and as an aside such that the efficiency on the legitimate platforms using commodity multi-core CPUs is as good as possible, which makes dedicated hardware less attractive for the attacker; see scrypt, or bcrypt (still more common although it lacks parameterizable memory size, use of multiple cores, and seems less close to optimality on commodity CPUs).


Useful additional data to employ in GCM Are there any requirements for the additional data to be used in the GCM block cipher mode?
And are there any "classic" used informations worthwile to be used? Can for example a username or the name and surname of a person be suitable to encrypt a message with AES GCM?

There are few requirements for the additional data in the GCM document of NIST.

There are some limitations on the size of the AAD, the maximum is $len(A) ≤ 2^{64}-1$ in bits.

Furthermore the following recommendations about the size apply for 128 bit tags:

  Therefore, the total number of blocks of plaintext and AAD that are protected by invocations of the authenticated encryption function during the lifetime of the key should be limited. A reasonable limit for most applications would be $2^{64}$, consistent with the requirement on the number of invocations in Sec. 8.3.

and for shorter authentication tags Appendix C applies further restrictions on the length of ciphertext (or equivalently plaintext) and AAD combined.

Those are all the restrictions that apply according to the NIST document.

I'll however add another restriction: AAD is defined in bytes. Whatever you do, for a successful authentication, the AAD must be encoded to the same bytes. That is: the encoding of the AAD must be a canonical encoding. Obviously if you encode a sequence number in little endian and later in big endian then you're in trouble. Same thing if it is unclear where one field ends and the other starts.

  Is there any "classic" used information worthwhile to be used? Can for example a username or the name and surname of a person be suitable to encrypt a message with AES GCM?

NIST again offers a few options:

  The controlling system or protocol may protect against such an event by monitoring for any duplication of the IVs that are presented for authenticated decryption. Alternatively, certain identifying information can be incorporated into the AAD. Examples of such information include a sequential message number or a timestamp.

I'd say it's a good idea to include as much identifying data in your AAD as possible. Note that you do not have to send the AAD data as long as you can produce it at the sender and the receiver. At least you should be able to prevent replay attacks and to distinguish between sender and receiver. If you cannot do this using the key/IV combination then you'd have to use the AAD (or plaintext) for that.

So yes, name and surname are a good idea as they identify the sender. Beware that names are however often not unique (hence UUID's etc.), something you'd sorely want in an identification scheme.

One thing you do not have to include is the IV, the IV is authenticated by default. And in case you're a greenhorn in cryptography, including the key is a bad idea as well.


Key derivation on Arduino The ATmega2560 is slow - it's a single core, 16MHz 8-bit AVR. Despite that, I need to use some encryption on it, and since it is limited to a few blocks, AES-256 can be used.

However, the key derivation is a problem. A computer can easily do a PBKDF2-HMAC-SHA256 with a million iterations in less than a few seconds. The Arduino struggles to perform 100 iterations in 4 seconds (to be exact, the time required with the implementation I use is 4.37s); that also applies when optimizations are enabled.

The current NIST recommendation is to use at least 10,000 iterations, in which case PBKDF2 may not be a good fit for my case.

When it comes to Key Derivation Functions, are there any solutions that are cryptographically safe for low power devices, and more generally IoT devices?

Since I cannot add comments I'll edit to answer them:

I'm not sure what is meant by "if the key derivation is performed only once", so to be more precise: the key derivation is performed only once, yes, but the devices shouldn't block for more than a few seconds before it can actually be used. 4 seconds is not a lot, but I sure don't want to go over that.
The key can - and will - be created beforehand, but it still needs to be computed each time the device is powered on. It would make absolutely no sense to store a key in plaintext.
The device is safe from attackers while it is being used, however it may not be safe while powered off (it is meant to be plugged in, unlocked, have one or two interactions with it and powered off). I guess a similar device would be the "Mooltipass Hardware Password Keeper", except that I don't have access to smart cards nor do I intend to use it as a keyboard while an operating system is up and running. Unless I missed something though, smart cards aren't easily accessible (the SLE4442 is NOT read protected).

There aren't many KDFs that will be faster on an AVR than PBKDF2. In your case, it's likely that the only thing you can do is find a hash which can be implemented efficiently on an ATmega2560, and implement it with as many optimizations as possible. A highly-optimized implementation of a hash algorithm is likely to improve speed significantly. That's really all you can do: Find/write a very fast AVR implementation.

If you find that PBKDF2-HMAC isn't giving you optimal performance, you could try to use a similar KDF such as S2K of the OpenPGP standard. It works by concatenating the password and salt and feeding that data into some chosen hash function. It is fed, repeating, until the configured number of bytes have been processed. See RFC 4880 § 3.7.1.3 for the specifications. It does not require any optimizations beyond optimizing the hash itself, unlike PBKDF2-HMAC. Benchmark it and see if it's good for you.


Decrypting DES with decrypted and encrypted data I got two 8-byte strings.

One which is decrypted is:

FF FF FF FF FF FF FF FF

and one which is encrypted is:

16 05 78 B0 0A C2 78 7F

Encryption mode is CipherMode.ECB

I need the key used in DES encryption.

Do you know anything at all about the key?  If not, then what you have is a "Known plaintext attack" - you know the cyphertext is 16 05 78 B0 0A C2 78 7F and the plaintext is FF FF FF FF FF FF FF FF.

DES has some weaknesses, but it isn't that weak.  A cypher that can be cracked with a mere 8 bytes of plaintext/cyphertext would be very weak indeed.

Can you generate more cyphertext/plaintext pairs if you want to?  That might allow you to use linear attacks and differential attacks.

Apart from that, you will have to try to brute force all possible keys and see which one works.


Are there any asymmetric key encryption/decryption algorithms? When it comes to encrypting some data (where data being something of a large size),  symmetric key cryptosystem is predominant. Symmetric key algorithms like AES, DES, Blowfish, IDEA etc. are explained in greater lengths, on how they function and work and why is one better then the other.

But the same han't been done in the case of asymmetric cryptosystems. In general asymmetric cryptosystem is referenced, in a hybrid cryptosystem. Where the Symmetric key is used the encrypt the actual data, and then the Symmetric key is encrypted via the public key.

Even in the wikipedia page of RSA the emphasis is only given to the key exchange process of RSA, rather then how the actual data is encrypted/decrypted via it.

The most I know about Asymmetric key Cryptographic algorithms is that:-

They are far slower then symmetric cryptographic algorithms;
They produce cipher texts of sizes larger then the original one.

This is the only thing that is available when it comes to actual encryption / decryption by asymmetric algorithms. And even this hasn't been explained, why do they possess such behavior?

Even though they may not be a good choice, when compared with symmetric key algorithms, but still at least some information about their working should be provided.

EX:- In RSA, this is the description of the encryption process:-

    CT = (PT^E) % N

    # where CT = Cipher Text, PT = Plain Text, N = Product of Two Large Primes, E = Public Key

But it has not be explained what happens in the encryption process.

I would like to get some intel on some asymmetric cryptographic algorithms used for encryption / decryption, so that I can analyze their internal working.

You are mistaken that there aren't any cryptographic standards that describe asymmetric encryption / decryption. You name RSA as an example and then you just show the modular exponentiation. However, in PKCS#1 - the predominant RSA standard - there are methods described to encrypt with a public key and decrypt with the private key. Currently it contains PKCS#1 v1.5 compatible padding (official name RSAES-PKCS1-v1_5) and OAEP (official name RSAES-OAEP). In the standard there are also some links to older standards that these schemes have been derived from.

In principle you can simply split up the blocks and encrypt each block. However, the input block size is indeed smaller than the output block size. Furthermore, modular exponentiation is way too expensive for the private key operation. There is simply not much reason to choose just RSA over hybrid encryption. You could say that you could rearrange the RSA blocks as they always would decrypt even in the wrong order, but AES-CBC doesn't provide any integrity or message authentication either, so I've always seen this as unfair. If you require integrity or message authentication then you'll have to sign the encrypted blocks (or sign before encryption, depending on the use case).

For DSA and therefore ECDSA there is no good encryption method. There is El Gamal encryption, but because the sizes of the keys are relatively small for ECDSA, it is even less efficient than RSA encryption.


Computational Assumption For the extended discrete logarithm Choose randomly $P\in G_1, (s,a \in Z_q)$.

let the attackers know $a,P$ and keep $s$ as secret.
Also the following is given.
 $$sP,(a+s)^{-1}P$$

Individually,

From $sP$, trying to reveal ($s$) will be discrete logarithm problem.

However, I don't know (computational assumption) how to prove  $s$ value cannot be revealed from $(a+s)^{-1}P$.

Moreover, are there any computation assumption to prove the secrecy of  $s$ value from both $sP,(a+s)^{-1}P$ instead of individually.

As there is no pairing operation, BDH, xBDH, wBDH cannot be used here.

Let $\mathbb{G}$ be a (multiplicatively written) group of order $q$ and let $g$ be a generator of $\mathbb{G}$. The $r$-SDH assumption (Strong Diffie-Hellman) [BB08] states that given
$$
g,g^x, g^{x^2}, \dots, g^{x^r}
$$
as input, it is hard to compute a pair $(a, g^{1/(x+a)})$ for some $a \in \mathbb{Z}_q$.

Writing group $\mathbb{G}$ additively and letting $P$ be a generator of $\mathbb{G}$, the $r$-SDH assumption is: Given
$$
P, sP, s^2P, \dots, s^rP
$$
as input, it is hard to compute a pair $(a, 1/(s+a)P)$ for some $a \in \mathbb{Z}_q$.

Your assumption is related to the $1$-SDH assumption in a cyclic subgroup of points on an elliptic curve over a finite field.  It is however weaker as the attacker is given the value of $a$ (in the SDH assumption, the attacker is free to choose the value of $a$).

[BB08] D. Boneh and X. Boyen, Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups, Journal of Cryptology, 21(2), pp. 149-177, 2008.


What does CMS standard mean by "initial input to the message digest" I'm really grinding my teeth against digest calculation explanation in the CMS standard.

Let's consider the case when the signedAttrs are present.

The first paragraph says

  initial input to the message    digest calculation process is the
  "value" of the encapsulated content    being signed.

To me that implies that whatever digest value that will be signed, somehow "starts" with being the digest of the message.

The second paragraph says:

  When the [signedAttrs] field is present, however, the result is the message
  digest of the complete DER encoding of the SignedAttrs value
  contained in the signedAttrs field.

To me this does sound like the result is solely derived from the signedAttrs value, but then the first paragraph seems to be contradictory because it said that no matter what, the digest must start with encapsulated content. The second paragraph does then mention that the content hash will be indirectly included, because it must be present, but to me that still doesn't negate implication made in the first paragraph.

P.S. Based on OpenSSL implementation, I figure that the "correct" behavior is only hashing signedAttrs.

Consider the two cases.

without signedAttrs: first we hash the content, then we sign that hash. The first thing we do is hash the content.

with signedAttrs: first we hash the content, call it hash1; then we construct signedAttrs which includes hash1 in the message-digest attribute; then we hash signedAttrs, call it hash2; then we sign hash2. Only hash2 is used in the digital signature operation, but to compute hash2 we must previously have the value of signedAtttrs, and to have the value of signedAttrs we must previously have hash1, which is the hash of the content, so the first thing we do is hash the content.

Either way the first thing we do is hash the content which uses the content at input. Since this is the first thing we do, the initial input is the content. And in particular the value octets, not the tag and length, which is the actual point being specified in that paragraph.


Can the Smart-Vercauteren Homomorphic Encryption be implemented as a practical fully homomorphic encryption scheme? Smart and Vercauteren proposed a homomorphic encryption scheme (PKC 2010) following Gentry's principles.  Though their scheme can achieve fully homomorphism theoretically, they admitted that "for practical values of n our scheme cannot be made fully homomorphic" (p. 16).

However, perhaps the only (see update 1 below) public fully (not somewhat) homomorphic encryption implementation libScarab, is claimed to be using the SV scheme.  The authors of that library also have a paper "POSTER: An Implementation of the Fully Homomorphic Smart-Vercauteren Crypto-System" (CCS'11) about their implementation.

There are several parameters chosen differently in the latter paper
from the original paper, maybe for achieving full homomorphism. But they did not explain the security of their choices, and I cannot figure out it by myself.

So my question is, can libScarab be viewed as a serious secure FHE implementation?

Update 1 (18 Nov 2015)

I've found there are two other public fully homomorphic encryption (including bootstrapping) libraries (HELib and FHEW) released by illustrious cryptologists Shai Halevi / Victor Shoup and Leo Ducas / Daniele Micciancio. Both are slower than libScarab, but I think they supply more security.

The SV scheme made some significant simplifications that turned out to hurt security.  Specifically, it's known how to break the scheme in subexponential time (roughly $2^{n^{2/3}}$) in the dimension $n$ of the lattice defined by the public key.  Moreover, it's known that the scheme can be broken in polynomial time by a quantum computer.  In short, the reason is that the SV scheme has an ad-hoc method of key generation, which tends to produce "weak" ideals that can be attacked more efficiently than arbitrary ideals.  See this paper for further details.


Weakness of Hash_DRBG when entropy is mixed in gradually NIST SP800-A states (Appendix C p. 89):

  There are known problems with Hash_DRBG when the
  DRBG is instantiated with insufficient entropy for the requested security strength, and then later provided with enough entropy to attain the amount of entropy required for the security strength, via the inclusion of additional input during a generate request. However, these problems do not affect the DRBG’s security when Hash_DRBG is instantiated with the amount of entropy specified in this Recommendation.

There is no such warning about HMAC_DRBG.

What are those known problems? The publication does not give a reference for this.

This may or may not be related to weaknesses in an early draft of Hash_DRBG. The concern is the same, but those weaknesses are supposed to have been fixed, so there shouldn't be any remaining “known problem”.

I know that HMAC_DRBG may be preferable for “theoretic” reasons — Hash_DRBG relies on much stronger assumptions about the underlying hash. But weakness in the face of an entropy source of worse quality than expected is a practical concern in many scenarios. In what way is Hash_DRBG weak when initially instantiated with low entropy, that mixing in entropy later doesn't fix?

It is hard to say what design rationale went into the design of the NIST DRBGs, which are ridiculously complicated ways to turn short-output PRFs into long-output PRFs typical of bureaucratic government crypto.

Certainly one can say generally that no entropy pool with incremental seeding can thwart an adversary who can witness outputs before adequate entropy has been supplied to the pool.  Here an entropy pool is a state with an ‘absorb’ and ‘squeeze’ operation (or ‘enter’ and ‘extract’); the usual notion of a PRNG or DRBG is a special case where you absorb a seed once and squeeze output forever after.

Why can't you thwart this?  Say the adversary is bounded to a budget of $2^{128}$ crypto operations.  (Here a crypto operation is, e.g., an absorb followed by a squeeze, and is some constant number of bit operations.)  If you absorb an input with 64 bits of entropy, from the attacker's perspective, and squeeze a long-enough output, the adversary can expect to try $2^{63}$ possible inputs before finding the one that matches the output.  Now the state has no entropy, from the attacker's perspective.  If you try to incrementally add another 64 bits of entropy, it's too late—it's as if you hadn't added the original input.

Why would NIST apply this warning to Hash_DRBG but not HMAC_DRBG?  I dunno, why would NIST not comment on the provenance of the standard $P$ and $Q$ base points in Dual_EC_DRBG even after John Kelsey personally asked the NSA where they came from and was rebuffed?  Government bureaucracies are formalized systems of exacerbating confusion of malice with incompetence.


Is there an asymmetric encryption algorithm where the public key cannot be derived from the private key Is there an encryption algorithm that will produce a public key and a private key such that the public key cannot be generated using the private key.

For example, if the private key is compromised but the public key is not then messages can only be decrypted and not encrypted.

RSA could do what you want: just put only the private exponent and the modulus in the private key, and not the prime factors of the modulus. Since the factors are not needed to decrypt, this will not hurt functionality.

This assumes, of course, that the party generating the keys has a reliable way to destroy the factors when they are not needed, but this seems to be implicit in what you are asking: since the key generation algorithm outputs both keys, if no reliable way to destroy data exists and the generating party is compromised, the attacker can both encrypt and decrypt.


Is the post-quantum scheme quantum-resistant without regard to QROM There are many "post-quantum" schemes have been proposed.
The security of most of them is only proven under random oracle model or uses forking lemma.
As described by Boneh et al. (Random Oracles in a Quantum World), post-quantum schemes should further consider the "quantum-accessible" random oracle (QROM).
However, many schemes that do not take QROM into account claim that they are quantum-resistant because their security is based on certain assumptions, such as LWE or SIS.
In addition, these schemes may only be proven under ROM and the security reduction depending on the time of Hash query.
So, are these scheme really quantum-resistant?
I have known that in some situation the ROM secure schemes can apply to QROM secure schemes (Survey on the Security of the Quantum ROM).

I think you are somewhat confused, so I'll try to briefly describe the state-of-the-art to see if it helps.
The general design paradigm of a post-quantum KEM is separated into two steps:

Build an IND-CPA secure PKE, generally based solely [1] on the hardness of some computational problem.

Apply a general transformation (usually some variant of the Fujisaki-Okamoto transform) to convert the IND-CPA-secure PKE into an IND-CCA secure KEM

The only part where hashing (or any kind of ROM type stuff) strictly needs to enter the picture is in the second step. Is this step done solely in the ROM, or the QROM as well? This is relatively straightforward to check --- many authors rely on A modular analysis of the Fujisaki-Okamoto Transformation, which has a section on transformations in the QROM.
Do the authors use this? You can check their design specifications --- here is the specification for KYBER, a NIST PQC round 3 finalist. Section 4 discusses their security analysis, which includes analysis in the QROM. This is typical of "serious" constructions.
Note that the underlying IND-CPA-secure PKE that KYBER is building on does not mention QROM (or ROM for that matter) analysis, as one only really needs it (and the security modelling of hashing overall) in the transformation from IND-CPA security to IND-CCA security.
Also note that in general the QROM results tend to be weaker than the ROM results - the reductions are generally not tight without making some slightly less standard assumptions.
This is of course a much different statement than there being no QROM analysis though.

[1] This is not strictly true, often practitioners reach for other primitives (say PRGs / extendible output functions) for efficiency purposes, but these are not strictly required if one is ok with a slightly less efficient construction.


Repeated NONCE in CTR mode My understanding is that, in CTR mode, the NONCE must be unique because, if a NONCE is reused, multiple plaintexts will be XORed with the same value and this gives an attacker leverage to decrypt the data.

If you have a situation where it is hard to guarantee that the NONCE will always be unique, but you have a fast (whatever that means in your context) encryption implementation, can I take away the leverage that repeated NONCES give by adding an additional encryption step the normal CTR mode process?

E.g. replace

AES256(key, NONCE) XOR Plaintext

with

AES256(key2, (AES(key1, NONCE) XOR Plaintext))

I understand I loose CTR mode's ability to work with arbitrary length plaintexts (which is fine for me, I'm happy working in blocks), and that I have doubled the amount of encryption I need to do,  but I think this retains the advantages of CTR mode (as opposed to ECB mode) while gaining some protection against repeated NONCEs.

Is this approach valid?  Is there a lighter way to gain some protection against repeated NONCEs?

I am focusing on CTR mode because my communication channel is not necessarily reliable and I worry about the need to "resync" if I use any of the chained modes.

This would be better than simply CTR if your nonces do collide, but it is still not very good.

Suppose you use the same IV for two messages $m_0||m_1||...m_n$ and $m_0'||m_1'||...m_n'$ where all the $m_i$ are 128-bit blocks. Each block is XORed with the same keystream value as the corresponding block in the other message. They then pass through AES, the same as in ECB mode. If any $m_i=m_i'$, they have the same ciphertext, so the cipher leaks information about the message.

SIV mode would be closer to what you are looking for. It should be approximately as fast, though it does require two separate passes over the data. In the case of nonce reuse it leaks the equality of the (complete) messages, but no further information.


Doubt about the possible attacks on HMAC I have a question about the security of HMAC:

If I know the value of the seed and the value of the HMAC but I don't know the key then I can't do the birthday attack because I can't generate an authentic message. I must see at least $2^{\frac{n}{2}+1}$ messages to have 50% of probability to find a collision.
But what happens if I have the seed, the value of HMAC, and the key?

The standard attack model for a MAC is that the attacker, not knowing the key, is allowed to ask the MAC for any messages s/he wants, and succeeds if later exhibiting a different message and its MAC that have probability sizably better than $2^{-n}$ to be correct.

Studying the birthday problem tells that that after $2^{\frac{n}{2}+1}$ random messages, probability is good (better than 86%) that two messages have the same MAC. But, for an ideal MAC, this is of no help to the attacker, because s/he has no clue about which messages collide before having asked the MAC of both, which invalidates these message as contributing to a successful attack. We have proof that this applies to HMAC, if the underlying hash function has suitable properties; see Mihir Bellare, New Proofs for NMAC and HMAC: Security without Collision Resistance, in Journal of Cryptology, 2015 (originally in proceedings Crypto 2006).

With the key, attacking any MAC is trivial: it's only a matter of computing the right MAC.

If for some reason we change the attack model and consider than the adversary wants to exhibit distinct messages with the same (H)MAC, knowledge of the key helps doubly:

The attacker no longer needs to ask MACs; s/he can compute them, presumably at a higher rate and without raising suspicion.
In the particular case of HMAC, that is likely to allow exploiting weaknesses (if any) of the underlying hash $\operatorname H$; specifically, with knowledge of the key $K$, it might be possible to find $M$ and $M'\ne M$ with $\operatorname H\big((K\oplus\text{ipad})\|M\big)=\operatorname H\big((K\oplus\text{ipad})\|M'\big)$, and it will follow that $\operatorname{HMAC-H}(K,M)=\operatorname{HMAC-H}(K,M')$. That would be trivial for $\operatorname H=\operatorname{MD5}$, and possible for $\operatorname H=\operatorname{SHA-1}$, given the weaknesses of these hashes (which include allowing to find colliding messages starting with any known prefix, very quickly for $\operatorname{MD5}$, feasibly for $\operatorname{SHA-1}$).


Highest prime number calculated on a regular PC The algorithm Sieve of Erastosthenes uses memory to do its work. The available memory determines the highest prime number, which can be found. On a regular PC, we have typically 4 GBbyte memory, which allows to store 32*10^9 bits. Therefore the highest prime number to be found with Sieve of Erastosthenes is 32*10^9-1 with 4GB RAM.

With Segmented Sieve Of Eratosthenes we can square this number, which then results in 10^21-1.

Another way to go further is to use the hard disk instead of RAM to store the bits for Sieve of Erastosthenes. A typical PC has 1 Tera Byte disk space, which is 8*10^12 bits, which then results in 8*10^12-1 as the highest prime number to be found. Using Segmented Sieve Of Eratosthenes we can square this and finally we realize that 64*10^24-1 is the highest prime number, which we can calculate on a regular PC.

But for cryptography key lengths of 1024 bit and more are common, which means that prime numbers of 10^300 are generated on a typical PC. How is this done ?
Are numbers randomly generated and then check whether they are prime numbers ?
Even checking whether a number with 300 digits is a prime is still a very extensive operation.

Please help me to understand this.

You don't use a sieve to find cryptographic-size primes.

One method chooses an odd number of the appropriate size at random, then tests it using a Miller-Rabin or Lucas pseudoprime test, incrementing the number by 2 until a probable prime is found; an alternative is to pre-sieve with small primes (less than 1000, say), and perform pseudoprime tests only on those numbers that survive the sieve. That works, and is commonly used in cryptographic practice, but is not guaranteed to find a prime number. An implementation of this method is available at my blog.

Also at my blog is an explanation of a better method for generating cryptographic primes:

  Sometimes you need to have a large prime, for testing, cryptography,
  or some other purpose. I’m talking about primes of several hundred to
  a few thousand digits that are certified — proven to be prime
  — rather than probable primes according to a Miller-Rabin or
  other probabilistic test. Henry Pocklington’s Criterion, which dates
  to 1914, gives us a way to find such primes quickly. Paulo Ribenboim
  explains it thus:

  Let p be an odd prime, and let k be a positive integer, such that
  p does not divide k and 1 < k < 2(p + 1). Let N = 2kp + 1. Then the following conditions are equivalent:

  N is a prime.
  There exists an integer a, 1 < a < N, such that a(N−1)/2 ≡ −1 (mod N) and gcd(ak + 1, N) = 1.

  This gives us an algorithm for generating large certified primes.
  Choose p a certified prime. Choose 1 ≤ k < 2p at
  random; we ignore the last two possibilities for k, so we don’t have
  to worry about k being a multiple of p. Compute N. For each a
  ∈ {2, 3}, test the conditions for primality. If you don’t find a
  prime, go back and choose a different random k. Once you have a
  prime N, “ratchet up” and restart the process with the new certified
  prime N as the p of the next step. Continue until N is big
  enough.

There is code and a more complete explanation at my blog.


Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers Given that much of our ECC crypto primitives provide “only” 128-bit security when defined over a 256-bit curve due to pollard-rho, is it then still safe in 2020 to consider 128-bit security safe for the medium term (5-8 years).

I’m looking for an answer from an energy/thermodynamic POV given advances in current lithography and GPUs, rather than with regard to a specific cipher, however for discussion I consider AES-GCM or Salsa20 as example symmetric ciphers I use with 128-bit keys.

Bruce Schneier speaks of AES-128 in Cryptographic Engineering as if it’s already broken!

I strongly disagree with saying that AES-128 is broken, in any way, shape or form, and likewise ECC with 256-bit keys. Note that even in this answer by @kelaka regarding AES-128, you would need over 34 million years of the entire bitcoin mining power to carry out a computation of $2^{128}$. This is far from broken. If quantum computers ever happen at scale, it is very very unclear how long it would have to actually run to achieve $2^{64}$ quantum computations for AES-128 (but ECC-256 would be in bigger trouble). Bottom line, these are far from broken. (I don't know what Schneier quote you are referring to, but anyway I completely disagree.)


Basic question about design of program with data encryption I need to store encrypted files on a hard disk. The actual code side is not important for me now (I plan to use C# and AES-GCM encryption from Bouncy Castle library, please tell me if you think that's a bad idea!), but I'm having trouble designing the actual high-level algorithm.

How do I deal with user changing password (The key will be generated from password.)? Should I decrypt all the files encrypted with the old key and then encrypt them with the new one? Should I store the old password?

How to actually verify the password? An obvious answer that comes to my mind is "try to decrypt one of the files" but that doesn't seem right to me, because then there is no way to verify the password when encrypting the very first file. Sorry if these are dumb, but I'm completely new to cryptography.

How do I deal with user changing password (The key will be generated from password.)?

Generate a random master key K. Use K to encrypt the files. Use the user's password to generate a second key, K'. Encrypt the master key using K'. Then when the user changes his password, all you need to do is decrypt the master key using the old password and re-encrypt it using a new key derived from the new password.

How to actually verify the password?

If you encrypt the master key using AES-GCM, then decryption will fail if the password isn't correct. (Make sure that you take advantage of GCM's authentication feature; for Bouncy Castle specifics, see sections 3.3 and 3.4 of http://blog.philippheckel.com/2014/03/01/cipherinputstream-for-aead-modes-is-broken-in-jdk7-gcm/#Example-AES-GCM-with-three-CipherInputStream-implementations.) This would not be the case if you used, e.g., AES-CTR or AES-CBC.

I would strongly encourage you to look pre-existing solutions to encrypting file systems or volumes. There's lots of ways to screw up a design or implementation, and this is the safest (and probably easiest) solution. (But kudos to you for choosing a mode like GCM, that protects both the privacy and integrity of the data.)


Searching over encrypted data Is there any library/tool available which can allow me to search over encrypted data?
I would like to encrypt data on client side, send it to cloud and perform search in cloud.

I've been reading about homomorphic encryption and though there is CryptDb available which makes it possible to run encrypted DB in cloud, but my use case is slightly different- in my case I want to let users send me encrypted data and I want to be able to do a keyword search (as opposed to user performing search).

I don't think there is an existing library that can satisfy your needs.
Homomorphic encryption is powerful and requires lots of computations. However, in your case which allows user-defined keywords, I suggest you to take a look at Searchable Encryption.
Searchable Encryption is the algorithm that should be of interest. It allows cloud server to search 'blindly' on client's encrypted data, based on a 'trapdoor' - a token that contains keywords to be searched for - sent by the client. Of course, client must also encrypt the keywords along the encrypted data before uploading them, which will surely increase the overhead. For 'blindly' it means the cloud server doesn't acquire any unnecessary knowledge about the searched keywords and the encrypted data, during the entire query process.
Some of the searchable encryption algorithms are based on pairing-based cryptography. In that case, you can build your application based on PBC library.


What are coding schemes for timing channels I know we can hide information in the inter-packet delays, e.g. we can generate a code-book that each code-word corresponds to a message and is generated by realization of a specific random process.

Is there a good, comprehensive resource about coding schemes like a “Poisson process”, or other processes?

For example: if the legitimate traffic is process $A$, can we make random variables according to that process and use permutations to represent different coderwords?

I am not sure if this is what you are looking for, however, the information theoretic capacity of a timing channel, where delays are manipulated, has been defined and analyzed in a number of papers, by using the Shannon formalism of maximizing the common information between the input and output to obtain/bound the capacity.

There is a tutorial which can get you started here. I am unsure if this tutorial is refereed or not, but it seems to introduce the basic concepts gently.

Basically you consider a queuing system such as ./G/1 (single server, general service time distribution) or ./M/1 (single server, exponential service time) and you manipulate the input arrival distribution to maximize the common information $I(X;Y)$ between the input $X$ and the output $Y$.

The first paper in this area was

V. Anantharam, S. Verdu, “Bits through queues”, IEEE. Trans. Inform. Theory, Vol. 42, No. 1, Jan, 1996

Also, if $C(\lambda)$ is the capacity of the pure timing channel, the quantity
$$
C_I = sup_{\lambda \leq \mu}≤[C(\lambda) + λC_0]
$$
where $C_0$ is the information capacity of the information channel, may indeed be related to the question you asked, about not just delays, but permutations of "marked(?)" packets/impulses in some fashion.

Chasing the references to the Anantharam/Verdu paper is probably a good idea.


Is this protocol for masking DB ids sound? Problem Statement

I don't want to expose my internal database ids (or other internal private ids) so to make it harder to abuse them, by e.g. guessing the next id of a sequence or similar. It is not feasible for me to add a new field with a public, non-guessable UUID for every entry in my DB. I therefore require a protocol that can mask my ids (reversibly).

Desired Properties

Ids in a sequence should be hard to guess and recognize when masked
Ids should be very hard to forge when masked
compromise of a single masked id should not make it significantly easier to comprise other masked ids
Masking the same Id should generate different outputs decided by chance
Masked Ids should not be too long
Masking should be reasonably fast

Current State-of-the-Art

There is a popular library that tries to tackle this issue: https://hashids.org/ with a e.g. Java implementation here. HashIds basically encodes the id with an specific alphabet which is dependent on a "salt" that is provided by the caller. Additionally they try to omit certain letters so the chance of generating an id with an english curse word is minimized. Ids are fully deterministic ie. the same number with the same salt creates the same output.

New Cryptographic Approach

I found the described issue interesting but was disappointed by the miserable security properties actually masking the id (to be fair HashId never claims to be more than obfuscation). My idea is probably similar a specialized version of key wrapping.

So my approach would be:

id         .... 8 byte number
entropy    .... 4, 8, 12, 16 byte random value
secret-key .... 16 byte high quality random key assumed to be stored in a safe manner

Primitives:
AES-CTR(iv, key)
HMAC_SHA256(key, data)
HKDF-Expand(PRK, info, L) -> OKM

For every id create a random byte array entropy between 4 to 16 bytes long.
Derive 64 byte key material km with HKDF-Expand(secret-key, entropy, 64)
Split the 64 bytes into:

roundSecretKey = km[0-16]
iv = km[16-32]
macKey = km[32-64]

Encrypt the id with AES-CTR(iv, roundSecretKey) -> encryptedId
Create mac with HMAC_SHA256(macKey, encryptedId | iv ) -> hmac
Truncate mac to 4-16 bytes -> truncated_hmac
Create output message with:
masked_id = entropy | encryptedId | truncated_hmac

Discussion

AES-CTR as encryption primitive was chosen because:

Basically every programming language has standard implementations for it
Is a stream cipher and can efficiently encrypt data smaller than 16 byte
AES can be reasonably fast (and is often hardware accelerated)

The big drawback is however that AES-CTR with key k1 must never be used with iv1 more than once.

HMAC is used to add integrity and authenticity for the generated id to prevent forging.

The random entropy part ensures that id1 masked multiple times will most probably create different masked ids.

Compromises

To keep the masked id short, entropy and the hmac is kept short (or very short depeding on configuration). Assuming the worst case: 4 byte entropy. The chance of a repeated iv is realistic, however seldom. The attacker should not be able to decrypt since the iv and the roundSecretKey is dependent on the secret secret-key which would requireing brute forcing it first. An option would be to switch to AES-CBC, but that would make the minimum output length 16 byte (most ids are either 8 or 16 byte).

Keeping the hmac small makes it easier to forge messages, however it should make it easier to get macKey.

Both of these issue can be solved by increasing the length of entropy and hmac to 16 byte. This would increase the output length to 40 byte however.

So the question to the community: Does this protocol make sense in accordance with the desired properties? Are the compromises reasonable? Is this basically a sound protocol. I am looking for general feedback, security issues, possible improvements - currently I am not looking for different ways to solve the public id issue.

Update for the interested reader: Here is the reference implementation of the id encryption schema on Github and here is a article about it.

What you are looking for is a randomized authenticated cipher of short bit strings, 64 bits long.  You seem to be willing to accept between 64 and 256 bits of ciphertext expansion.

With an $r$-bit randomization string, the probability of a collision after $n$ ciphertexts—which would, at the very least, reveal equality of masked ids—is at best bounded by about $n^2/2^r$.
With $t$-bit authentication expansion, the probability of forgery after $f$ attempts is at best bounded by about $f/2^t$.

You could use any randomized authenticated cipher you like, e.g. NaCl crypto_secretbox_xsalsa20poly1305, which has a 192-bit nonce and a 128-bit authentication tag; if you use a 128-bit nonce chosen uniformly at random (padded with zeros up to 192 bits), you're safe as long as you limit yourself to well below $2^{64}$ ids, e.g. limit yourself to a billion ids.  You could use AES-GCM, but the limits are even smaller because the nonce is 96 bits, so you need to limit yourself to well below $2^{48}$ ids.  A nonce collision here is catastrophic, of course.

If you want to build it out of AES and SHA-256, you could just use AES-CBC with encrypt-then-MAC and the 128-bit truncation of HMAC-SHA256.  Since the input is fixed-length, there's no need for padding; effectively, it would just be $$E_{k_1,k_2}(\rho, m) := c \mathbin\| \operatorname{HMAC-SHA256-128}_{k_2}(c), \quad \text{where} \quad c = \rho \mathbin\| \operatorname{AES}_{k_1}(\rho \oplus m).$$  In the case of a collision in $\rho$, this still leaks only equality of masked ids.  Obviously, you can derive $k_1$ and $k_2$ from a single 32-byte master key $k$ with HKDF-SHA256.

Here's a very simple approach that uses a single call to AES with a single key, to encrypt a 64-bit id $m$ with 64-bit randomization $\rho$ under key $k$: $$E_k(\rho, m) := \rho \mathbin\| \operatorname{AES}_k(\rho \mathbin\| m).$$  Here $r = t = 64$, so we're using 192 bits to encrypt a 64-bit id.  Let $\pi$ be a uniform random permutation; for any forgery attempts $\rho_1 \mathbin\| c_1, \dots, \rho_f \mathbin\| c_f$, the probability that there is any $i$ such that $\pi^{-1}_{64}(c_i) = \rho_i$ is bounded by $f/2^{64}$, where $\pi^{-1}_{64}(c_i)$ is the first 64 bits of $\pi^{-1}(c_i)$.  Consequently, the distinguisher and forgery advantage of any algorithm against $E_k$ is bounded by $(n^2 + f)/2^{64} + \varepsilon$ where $\varepsilon$ is the best advantage at AES from a uniform random permutation.  If you mask a million ids and your bandwidth limits the adversary to a trillion forgery attempts, the odds are less than one in eight thousand that the adversary will win.  Even if there is a collision in $\rho$, again this only leaks equality of masked ids, although forgery might be a bigger issue.

What about the scheme you described?  It's more complicated than necessary: you could do away with the IV, for example, and always use zero instead.  If you use a 32-bit randomization string like you suggested, then you'll see a collision with high probability after only a few tens of thousands of ids, and when this happens, this leaks not only equality of two masked ids, but the xor of the two masked ids.


Security Considerations in using SHA-1 for One Time Passwords SHA-1 is considered broken. That's why I'm assuming that using SHA-1 for RFC2289 OTPs is broken as well. Is this assumption correct?

Going further with this assumption using SHA-1 for RFC4226 HOTPs should be broken too, is it? Although this blog states the following: "it doesn't affect applications such as HMAC where collisions aren't important". Does this also applies for HOTP?

A detailed explanation would be really appreciated.

Thank you very much in advance.

The security property needed for one-time password generation is that of a pseudorandom function. HMAC is assumed to be a pseudorandom function, when the hash function has certain properties. Collision resistance is not a required property for HMAC to be a secure pseudorandom function. However, when collision resistance is broken, this brings into question the general security of the function. As such, although HMAC-SHA1 is not actually broken, it is worthwhile looking at phasing into HMAC-SHA256, when possible.

I will just note that HMAC-SHA1 does not require collision resistance in the normal sense, since it is designed so that the hash of the message is prefixed by a secret key. Thus, the attacker is unable to compute the hash of the message itself.


Unclear about the importance of Initialization Vectors I was reading about Ruby ciphers and found this:

  Although the key is generally a random value, too, it is a bad choice
  as an IV. There are elaborate ways how an attacker can take advantage
  of such an IV. As a general rule of thumb, exposing the key directly
  or indirectly should be avoided at all cost and exceptions only be
  made with good reason.

What does this mean?

First, a definition.  An initialization vector or nonce (and these are in fact different things) are  designed for one purpose, and that is to be a non-secret input to a symmetric cipher that allows it to retain semantic security by ensuring that the resulting ciphertext is indistinguishable from random when a given key is reused.

Remember, the only thing that must remain secret in an encryption scheme according to Kerckhoffs's Principal, is the key.  However, if we don't want to generate a new secret key for every single encryption operation, we still need the same message, when encrypted twice, to result in entirely different ciphertexts, indistinguishable from random (what we call IND-CPA).  If encrypting the same message twice results in the same ciphertext, well, we can clearly tell that it was in fact our message that was encrypted the second time, and not a randomly generated value.  This is the property that the initialization vector gives us.

So, first, reusing the key as a the IV defeats the purpose of either a) being able to use the key, or b) providing IND-CPA.   In the first option, we have to generate a new secret key for every encryption operation, track them so we can decyrpt, and keep them secret all the while, as Kerckhoffs's Principal says we must.  In the second option, we begin leaking information.  In a block mode cipher such as CBC, we leak whether two messages are the same, as illustrated above, or if two different messages begin with the same plaintext.   In a streaming mode or stream cipher, the construction is broken catastrophically when a key/nonce combination is reused, allowing potentially complete recovery of the plaintext and keystream.

We resolve these issues by having a separate key and IV.  The key we keep secret, the IV we MAC and can then transmit in the clear with the ciphertext with no loss of security.

One last point.  In addition to their being a very good technical reason for the IV to be different from the key, what I think they were getting at in the comment you quoted was a more general principal that is fuzzier, but still widely held as good practice, and that is that keys should not be reused for different purposes.   You wouldn't use the same key for both encryption and authentication functions, for instance.   You might derive encryption and authentication keys from a single master key using a KDF, but you wouldn't typically want to use a single random key for both purposes.   That, I think, is what they may actually be trying to say without having a terribly solid grasp on the specifics.


Schnorr's signature scheme with addition of modulus secure? In Schnorr signature scheme,$s=(k-xe)$$ s_1=(k-xe_1)$ If the same key $k$ is used, then it is possible to reveal $k$ and $x$ value by using $\frac{s-s_1}{e_1-e}$.
However, if we add $s=(k-xe) \bmod q$, $s_1=(k-xe_1) \bmod q$, $q$ is known by users. Will modulus usage prevent to reveal $k$ and $x$ value? If the modification scheme is secure, will there be more modification of Schnorr signature public key $g^x$ to something?

There's no chance to hide private key $x$ in case of re-using $k$ by calculating in the ring modulus $q$.
Formula $\frac{s - s_1}{e_1 - e}$ is well-defined over the ring modulo any prime $q$. In particular, extended Euclidean algorithm would do the division.


One Time Pad OTP : Optimal modular base per given plaintext space? Background:  my question at :

My pencil and paper One Time Pad works fine without modular math ...... or does it?

I am trying to understand, from a layman's point of view, how to make the best one time pad scheme.

From responses to my above referenced question in another post, I understand now why I should use modular math in the scheme, and that the keyspace should be at least as large as the plaintext space.

So, moving beyond those points, I would like to try to understand the best modular base per given plaintext space.   For example:

My alphabet's plaintext space is 40 characters, numbered 0 through 39.

So, I am using mod40 math.   But I am only using mod40 math because I read elsewhere that my modular base should equal the size of my plaintext space.
But I also know that my OTP will still function if my mod base is less than the size of my plaintext space or more than that size.  So, in my example, I could use mod30 math or mod50 math just as well as mod40 math.

Therefore, my question is: what is the importance of the mod base in relation to the plaintext space, and, is there an optimal relationship between the two, and, if so, how can I know the optimal ratio of  "mod base/plaintext space" in any OTP system?

I am assuming that your scheme encrypts $x$ to $x + k \bmod N$, where $k$ is the key and $N$ is the modulus.

If your modulus is less than the alphabet size, decryption does not work.

Suppose your alphabet size is $n$ and you work modulo $n-1$; then the plaintexts $0$ and $n-1$ are considered the same, since $0 \equiv n-1 \pmod{n-1}$. Thus, no matter your key, they will be encrypted in the same way, and when you try to decrypt, you cannot tell them apart.

If your modulus is greater than the alphabet size, you do not have perfect secrecy (hence not an OTP).

This was already covered in answers to the referenced question.


Why are Fortuna entropy pools reset after a reseed? I've implemented LibTomCrypt's version of fortuna and am wondering about the pool resetting after a reseed. In fortuna.c in libtomcrypt we have the following (which is that part that adds the entropy from the pools into the key),

for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
  if (x == 0 || ((prng->fortuna.reset_cnt >> (x-1)) & 1) == 0) {
      /* terminate this hash */
      if ((err = sha256_done(&prng->fortuna.pool[x], tmp)) != CRYPT_OK) {
         sha256_done(&md, tmp);
         return err;
      }
      /* add it to the string */
      if ((err = sha256_process(&md, tmp, 32)) != CRYPT_OK) {
         sha256_done(&md, tmp);
         return err;
      }
      /* reset this pool */
      if ((err = sha256_init(&prng->fortuna.pool[x])) != CRYPT_OK) {
         sha256_done(&md, tmp);
         return err;
      }
   } else {
      break;
   }
}

Once the pool has been added to the key, it is reset, why is that? I realise that at that point the entropy has been included in the key, so it has been used, but why not just keep adding entropy to the pool and have it keep all the entropy from the beginning of time? Is there any disadvantage if the pools are not reset?

If nothing else, it makes the output of the pool irrecoverable. One of Fortuna's goals is to make prior Fortuna outputs safe from a compromise (the discovery of all of Fortuna's current data by an adversary). If the pool continued on without a reset, with little or no entropy added before the compromise took place, the adversary could more easily calculate the past contents of the master pool.

Edit: Per M. Grieu (Merci!), let's make that "more easily verify guesses of past inputs to the master pool".

Also, I believe the OP's question is less about LibTomCrypt than about the Fortuna algorithm itself.


How to find m so that RSA cipher end with '\x00'+SpesificString , if we freely input the plaintext? I have an RSA encryption with public key $(3,n)$ with 2048 bits modulus $n$.
I want to find the value of the plaintext $m$ so that the ciphertext (in bytes representation) value ends with \x00+MySpesificString.
$ciphertext = pow(m,e,n)$
where $m$ can be any string and ciphertext has the following format
any string+\x00+MySpesificString
How I can find the possible value of $m$?

I assume this is homework (I have time imagining that this is a problem that you need to solve; if it is, turn "use real RSA padding").
Since this is assumed to be homework, I'll give you the initial steps, and let you do the rest of the work.
First off, what you're asking is to find a value $m$ such that $(m^3 \bmod n) \bmod 2^{136
} = \text{"\x00"} + \text{"MySpesificString"}$; noting hat $\text{"\x00"} + \text{"MySpesificString"}$ consists of 136 bits.
Now, we are not told anything about $n$, except that it is "2048 bits", that is, it is in the range $2^{2048} > n \ge 2^{2047}$.  Now, we want a value of $m$ that would work for any $n$ in this range; we can do this if $m^3 < 2^{2047}$, and so $m^3 \bmod n = m^3$
Hence, we're looking for a value $m$ for which $m < \sqrt[3]{2^{2047}} \approx 2^{682.333}$ and for which $m^3 \equiv \text{"MySpesificString"} \pmod{2^{136}}$.
That may still sound daunting; however can we find a value $m$ that satisfies the last equations modulo $2^1$?  And, if we have a value $m$ that satisfies the last equation modulus $2^k$, can we find a value $m'$ that satisfies it modulo $2^{k+1}$?