What kind of Quantum cryptography technology(protocols) can be used for Mobile Ad hoc networks(MANETS)? Typically ad hoc networks do not have a proper infrastructure and the routing is done only through the base stations which are connecting a wired and wireless network. Does quantum cryptography protocols and QKD provide a better security for such ad hoc networks.?

QKD aims at exchanging key material to be used with encryption based on OTPs between two parties and thus to achieve perfect secrecy for transmitted messages.

There are, however, several drawbacks for practical use in a wired setting of QKD (required hardware and their vulnerability to hacks, limited distance) which does not support their use for end-to-end confidentiality over longer distances. Consequently, it is required to run QKD between single hops and thus re-encryption is required and the plaintext is revealed to the intermediate hops). For the latter, nevertheless, there are some ideas to overcome this problem.

In the non-wired setting as it is the case for MANETs, however, it is very questionable if QKD could bring any benefit. This is due to required hardware (presumably not available at the nodes) and the missing fiber optic links. Regarding the latter issue, there are some studies with single photon sources doing QKD at night over the air - presumably far away from civilisation - and at a very low bit rate, but that seems rather esoteric at the moment.

Edit As Frédèric pointed out in his comment, over the air QKD is not that esoteric as I assumed, since there are works, e.g., this one, demonstrating feasability of over the air QKD at daylight.
/Edit

The most important issue from my perspective, however, in a MANET setting is due to missing infrastructure. With whom you want to exchange keys using QKD? Presumably, you do not trust your neighbours and then it makes no sense to exchange keys with them using QKD, since the respective node could read your messages. If you want to encrypt something for some far away party and therefore require end-to-end confidentiality, then you will very likely not be able to exchange a key using QKD with this party. So why using QKD in such a setting (besides the above mentioned problems)? Then you could pre-distribute key material, but using OTPs will be impractical due to the large key material required. So you will very likely drop the perfect secrecy requirement and come back to traditional (secret key or public key) encryption schemes.


Crypto libary with Commutative Encryption I want to implement Mental Poker in JavaScript as a toy program and lead in to a larger serious project so I did my research and found Massey-Omura cryptosystem and the Shamir three-pass protocol however I couldn't find any implementations of them, and the information on how to do SRA is scant. Would anyone be able to shed some light on how to implement Commutative Encryption with SRA(RSA) or know of a Massey-Omura/Shamir library?

Why can't you use RSA? Look at their description of a function on pp. 41-42, and you'll see that it is a perfectly valid choice.

So you have two users, $A$ and $B$, who want to play. One user, say $A$, selects $p \cdot q = n$, as per $RSA$, and sends that information to $B$. Both $A$ and $B$ independently choose large primes (or large numbers they confirm are coprime to $\phi(n)$) $e_A$ and $e_B$, and then compute $d_ae_a \equiv 1 \pmod n$ and $d_be_b \equiv 1 \pmod n$. Then, $E_A = m^{e_A} \pmod n$, and so on.

Any crypto library with $RSA$ support should allow for calling the encrypt and decrypt functions with your choice of exponent and modulus. The one downside is needing to generate a reasonably large new public exponent for each hand, but that isn't too bad on a modern system.


Authenticated encryption mode for stream cipher? Block ciphers have modes like GCM or OCB that combine primitives to provide both authentication and encryption.

Are there similar constructs for stream ciphers, which provide both authentication and encryption using only one cryptographic primitive - actual stream cipher (or keystream)?

An OCB like mode seems impossible with stream-ciphers. It's coupled tightly to the concept of a keyed permutation i.e. a (tweakable) block-cipher.

Many authenticated encryption actually combine two distinct primitives. It's just that the specification and API only expose the combination.

Essentially these xor a key-stream into the message to encrypt it (i.e. they use a synchronous stream cipher), and then authenticate the ciphertext using a MAC. Often they use part of the key-stream as one-time keys for the MAC.

AES-GCM is built by combining a polynomial one-time MAC called GHash with the stream cipher AES-CTR.

While AES itself is a block cipher, AES-CTR behaves like a stream cipher. GCM doesn't use AES in a way that'd prevent the use of a stream cipher.
Salsa20-Poly1305 is built by combining a polynomial one-time MAC called Poly1305 with the stream cipher Salsa.
Poly1305-AES is built by combining a polynomial one-time MAC called Poly1305 with the stream cipher AES-CTR.

Then there are some stream ciphers which provide authentication without a separate primitive. These constructions aren't synchronous stream ciphers, and can't be used together with a one-time-pad or plain key-stream.

Helix and Phelix are authenticated stream ciphers that merge authentication and encryption. There has been some criticism of their security, but I'm not sure if that criticism is actually valid.
Keccak (built on an unkeyed permutation) using the duplex constructio can considered an authenticated stream cipher


Is a message digest useful with symmetric encryption to check for integrity? I have some confusion that concerns the message digest.

I know that the message digest is the real message hashed with function and we use it to verify the integrity of the message.

I understand the usefulness of using this with asymmetric encryption but I can't find the utility of this with symmetric encryption.

I will explain my self:

We have Alice and Bob. Alice wants to transmit a message m to bob with symmetric encryption. Suppose that the two of them know the encryption key in advance.

Alice encrypts m with the key, hashes the message as hash(m) and sends it to Bob as (encrypt(m), hash(m)).

Bob decrypts the message and then hashed to verify the integrity.

In this case I think that the hash(message) is not needed because:

Case 1: If someone doesn't have the key they cannot cipher a message and send it to Bob pretending to be Alice because Bob will know that the message wasn't encrypted using the key. (We didn't use the hash message in this case).

Case 2: If someone has the key, they intercept the message of Alice and modify it to m2 then they encrypt and hash the new message and send it as (encrypt(m2),hash(m2)). When bob tries to verify the integrity of the message, the process will succeed (in this case using the hash didn't help to check the integrity of the message).

So in both cases the hashed message is not (or cannot) be used to check the integrity of the message.

Is this correct? Because I have argued with my teacher and he said that hashing the message helps to check for integrity in both symmetric and asymmetric encryption.

Is there some cases that hashing the message is useful?

Normally a message authentication code (MAC, for instance HMAC) is used for symmetric integrity and authenticity of the message. In that case a hash can be used with a secret key to protect the message; this is also called a keyed hash. Nowadays authenticated modes of encryption is also used a lot; for example an AEAD cipher such as GCM. AEAD ciphers combine message authentication code with encryption.

Sending encrypt(M) followed by hash(M) is certainly not secure, as the hash leaks information about M. If the message is "Yes" or "No!" then an attacker cannot distinguish between the two when CPA secure encryption is used. However, an attacker can simply test both possibilities by recalculating the hash over the message.

A hash over ciphertext send with the message isn't useful at all, as it would enable the attacker to simply change the ciphertext and then recalculate the hash. Before the hash was sometimes put over the plaintext as well and then encrypted, but that is still not as secure as performing a MAC over the ciphertext, and it may still allow for changing the ciphertext, allowing for instance padding oracle attacks.

With all that said, a hash can be used to secure the integrity / authenticity of a message, be it plaintext or ciphertext. In that case the hash itself must however be trusted. This can for instance be accomplished by putting the hash on a secured website, say apache.org. In that case messages (in this case applications) can be downloaded from mirrors and then compared to the hash, published on apache.org (hopefully over TLS, adding an additional layer of security).

With asymmetric encryption the hash can be trusted because it is verified that the hash was used together with the private key to generate the signature.


How is PKCS a syntax to digitally sign, digest, authenticate, or encrypt arbitrary message content I am really confused over PKCS. I saw this question but I do not have enough reputation to leave a comment so I am asking a new question to clarify.

I am trying to understand what exactly PKCS and in extension what CMS is. I have stumbled on the line from the RFC mentioned in the aforementioned question.

  This syntax is used to digitally sign, digest, authenticate, or encrypt arbitrary message content.

How can a syntax be used to digitally sign stuff?!! I can understand if it states it is a syntax used to describe digitally signed stuff...but signing? how can a syntax be used to sign?

This all tie into my confusion with PKCS/CMS and x509. I understand that x509 is a standard that describes what should make up a certificate, how is this different from PKCS/CMS?

Edit

The Wikipedia entry for CMS does not also help. For example it says:

  It [CMS] can be used by cryptographic schemes and protocols to
  digitally sign, digest, authenticate or encrypt any form of digital
  data.

Okay is CMS an encryption algorithm like RSA? No!! so why then say it is a protocol used to digitally sign or encrypt stuff?

PKCS stands for Public Key Cryptography Standards. The name was part of RSA Laboratories that managed to create and publish a very long list of standards, including:

PKCS#1 : RSA with various schemes for encryption + signature generation and schemes
PKCS#5 : Password Based Encryption or PBE
PKCS#7 : The Cryptographic Message Syntax or CMS
PKCS#8 : A scheme for storing / describing and and encrypting private keys
PKCS#11 : Cryptoki, a C based API for HSM's
PKCS#12 : A key & trust store format

PKCS in itself is not a scheme though. Many of these schemes use a language called ASN.1 that is used to describe data structures. It originated in the telco industries. For cryptographic purposes those data structures can be encoded using BER / DER binary encoding.

As RSA Labs was acquired by blood sucking capitalists, most of these standards have been supplanted by RFCs by now, including CMS, although you still see many mentions of PKCS#7.

As the name implies, CMS is a structure of cryptographic messages, described in ASN.1. As such it doesn't describe a method of creating signatures, it just describes how to store signatures and the signed content. Or indeed, how to store encrypted messages, possibly after signing them. CMS is a so called container format that describes what's inside, a bit like an archive or zip file but for cryptographic use.

Furthermore, it also describes how you can store X.509 certificates with the message that can be used to verify it. Verifying parties may not have the leaf / user certificate that was used to sign the document, but they may have a trusted CA certificate that can be used to create a certificate chain. X.509 certificates use a different structure also defined using ASN.1. Since certificates are basically also signed documents there are of course many similarities with CMS.

So no, CMS is not an algorithm, it is a container format for cryptographic messages. Those messages may be encrypted or signed using RSA, in which case CMS will reference the RSA algorithm. You can use the command openssl asn1parse or openssl -cmsout -print to view what the structure is and what's stored inside. You may have to use -inform DER if the input is binary instead of a textual PEM file (header, base 64 and footer).


N users must approve a request I have a locked-down production system that we'd like to process specific requests, picked-up (poll) from a less-secure location.  For security and "go slow, this is production" reasons, a request must be authorized by 2 (or N) people on the team.

I can imagine how to implement this fairly simply just using openssl and signatures -- e.g., the secure server has a pool of public keys (people on the team who can authorize a request) and any submitted request must be correctly signed (e.g., https://stackoverflow.com/questions/10782826/digital-signature-for-a-file-using-openssl) with the private keys of N different people from that pool.

But it seems like a common-enough requirement that it must already exist; any pointers?  I have a suspicion I'm just not searching for the right terminology...  Thanks!

What you are describing is called $(t,n)$-threshold signature, where you need at least $t$ parties (out of a total of $n$) to create a signature. Considering your description, it seems that in your case $t=n$, so it is necessary that all the keys are used for creating the signature.

This answer assumes that you want to verify the signature with a single public key (i.e., $n$ signatures, 1 verification). If you want to use $n$ public keys, then you can just require $n$ independent signatures.


Reference books in security and privacy preservation I am looking for books or reference guides to learn and teach "cryptography, security and privacy preservation techniques"? I need some advice to good resources that I can use.

You can start your learning
https://www.coursera.org/learn/crypto/home/welcome
An excellent course to start with all about Symmetric/Asymmetric encryption/TLS/MAC etc.
A free ebook is also available https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_4.pdf

https://www.schneier.com/books/applied_cryptography/


Drawback of ElGamal encryption I am trying to find out some disadvantages of ElGamal cryptography but I'm not able to figure out what's wrong with the algorithm. The only one I found is that a known-plain text attack is possible in ElGamal if the same $r$ is used twice during encryption.

Are there any other disadvantages of ElGamal encryption?

ElGamal is a scheme, that can be applied to any kind of group structure. The only requirement is that DDH has to be hard (e.g. not $(\mathbb{Z}_p,+)$).

If you use the most common construction with multiplicative groups $(\mathbb{Z}_p^*,\cdot)$, then you need larger groups, due to attacks like index calculus.

If you use elliptic curves, you can use smaller groups instead, because algorithms like index calculus are not known.

Elliptic curves with pairings are not suitable to be used, because in that case the DDH problem is not hard. Therefore, you can not design protocols with efficiently computable pairings.

One property of ElGamal is, that it is (semi-)homomorphic w.r.t. the group operation. If you see that as an unwelcome property, you can also call that malleable. If you consider this property useful or a security risk, depends on your point of view and your actual goal.


Is it possible to brute force a single smaller variable in $\operatorname{HMAC-SHA512}(k, a\ ||\ b\ ||\ c\ ||\ d)$? Given $c' = \operatorname{HMACSHA512}(k, a\ ||\ b\ ||\ c\ ||\ d)$ and the 32-bit integers $a$, $b$, $c$, and $d$ is it feasible to alter $b$ and produce a valid MAC under the unknown key?

I understand that typically it wouldn't be, but I am mostly wondering if it's possible with 4 small independent inputs being used.

Would it change anything if I could observe many MACs over time with all variables constant except one?

Is is feasible to alter b and produce a valid MAC under the unknown key?

We most certainly hope not.  The fundamental security property of a MAC is that, even if that attacker can get a huge number of valid (Message, MAC) pairs (where he gets to choose the messages), he still is unable to generate a MAC for a message he has not seen.  This fundamental property doesn't change just because the inputs are 'small'.

We believe that HMAC-SHA512 is a secure MAC (assuming an unguessable key); hence we believe that it is secure in your case.


One-one correspondance complete function I am reading the paper by John B. Kam and Georges I. Davida (1979) titled Structured Design of Substitution-Permutation Encryption Networks.

On page 749 it reads the following:
Definition: Given a one-one corespondence: f:{0,1}n   --> f:{0,1}n, f is said to be complete if, for every i,j belongs {1, ..., n}, there exist two n-bit vectors X1 and X2 such that X1 and X2 differ only in the ith bit and f(X1) differs from f(X2) at least in the jth bit.

My questions are:

What is meant by vectors here? (Can someone explain it using less math if possible?)
Can someone explain this, proably with a nice and easy example?
In general, what is the idea behind this?

If this is the wrong place to ask the question, please let me know so that I take this to the write place instead of voting negative or closing the question.

What is meant by vectors here?

Just the inputs and outputs of the function.  The function $f$ takes, as input, a sequence of bits (for example, 1010), and returns a sequence of bits (for example, 1100); the text refers to such a sequence of bits as a vector

  Can someone explain this?

Well, the idea is that every output bit depends on all input bits. That is, if we were to compute an output bit $j$, we would still need to know every single input bit (because for every output bit $j$, there is a pair of inputs $X_1, X_2$ for which input bit $i$ matters).  In other words, for any change in an input bit, there's a possibility that it may affect any output bit.

That sounds like a reasonable goal; however it turns out to be a very weak guarantee.

To see this, consider a function f that is made up of two operations:

Take the input, treat in as an $n$ bit unsigned integer, and increment it modudo $2^n$
Take the msbit of the result, if it is 0, the value remains the same, if it is 1, flip all the other bits.  This can also be viewed as xor'ing the msbit into all the other bits.
Return that as your result.

For example, consider the input $1010$; in the first step, we treat that as an unsigned integer (the value ten, as it happens), and we increment it to eleven (or $1011$).  Then, in the second step, we take the msbit (which is a 1) and exclusive-or that into the rest of the values, turning the lower three bits $011$ into $100$, giving us a final result of $1100$.

Now, this rather odd function just happens to meet the criteria of a 'complete function' for $n>2$; it's one-to-one (as both steps are invertable), and for every $i, j$ pair, we can find two inputs $X_1, X_2$ that differ only in the $i$-bit bit and $f(X_1)$ and $f(X_2)$ differs in the $j$th bit (and possibly elsewhere).

For example, for $i=4$ and $j=2$, consider $X_1 = 0010$ and $X_2 = 0011$. These two vectors differ only in the 4th location (counting 1 as the first bit); $F(X_1) = 0011$ and $F(X_2) = 0100$, which differs in the 2nd location (as well as the third and the fourth; we're allowed to change other output bits in addition to output bit $j$).

And, for $i=2$ and $j=4$, consider $X_1 = 0111$ and $X_2 = 0011$.  These two vectors differ only in the 2nd location; $F(X_1) = 1111$ (remember, we first increment $0111$ into $1000$, and then xor the top bit into the rest of them, flipping all three 0's into 1's), and $F(X_2) = 0100$, which differs in the 4th location (in addition to the first and the third).

I won't go through all the combinations, but such pairs exist for all $i, j$ values.

On the other hand, this example shows that it is a rather weak guarantee; I picked the specific function $f$ because it meets the criteria, but not in a particularly useful way.  For large $n$, yes, every $i, j$, you can find a pair $X_1, X_2$; however for most $i, j$ pairs, output $j$ rarely depends on input $i$.


Ed25519 is a signature or just elliptic curve Ed25519 is a signature or just elliptic curve?
EDDSA is signature, what using curve ed25519?

Your short answer is this: ed25519 is both a signature scheme and a use case for Edwards-form Curve25519. EDDSA generalises this signature scheme to any curve in edwards form (for example Ed448-Goldilocks, Curve41417).

Curve25519 first arrived in 2005-2006 (https://cr.yp.to/ecdh/curve25519-20060209.pdf), a few years before the Edwards Normal form papers on Elliptic Curves. Montgomery curves, the form of curve used for Curve25519, was originally used to speed up elliptic curve factorization (https://cr.yp.to/bib/1987/montgomery.pdf). The original proposal for Curve25519 was for use as a diffie hellman (key exchange) protocol. This is still its use and is now often called X25519.

Later, Edwards came up with his own form of elliptic curve (http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf). DJB, Tanja et al researched these forms and realised they too were fast, especially for signatures and we got Ed25519 (https://ed25519.cr.yp.to/ed25519-20110926.pdf) using the Edwards form of Curve25519. This was later generalised to EDDSA (https://ed25519.cr.yp.to/eddsa-20150704.pdf) so that other curves could be used with the scheme.

So, so far we have the following nomenclature:

Curve25519, Curve41417, Ed448-Goldilocks: generally the name of the curve itself, however it was originally presented (bear in mind they're often presented alongside use cases to justify them, like "it's fast").
X25519, X448, X41417 - DH key exchange schemes using the above curve.
EDDSA, Ed25519, Ed448 - the first being the generic Edwards variant of DSA, plus other fixes, the others being specific instances matched to their curve names.

Confusingly, Open Whisper Systems came up with XEdDSA (https://whispersystems.org/docs/specifications/xeddsa/). To quote them:

  XEdDSA enables use of a single key pair format for both elliptic curve Diffie-Hellman and signatures.

Hence, I suppose "X EdDSA" is taken to mean "exchange and EdDSA" of the given curve. In this instance, the key exchange part still happens using the montgomery form of the curve, but the signature part (eddsa) uses the same curve in edwards form.

As pointed out by Kostas Chalkias in the comments, the X may in fact be a reference to the use of the x-coordinate in curve25519. X25519 is performed on the kummer line, which is a fancy mathematical way to say that it suffices to know the x-coordinate to compute the scalar multiplication necessary for X25519 key exchange.


Will repeatedly applying a hash function to the prior result visit all possible hashes? If one were to take a message, say "Hello world!", and compute the MD5 hash:
86fb269d190d2c85f6e0468ceca42a20
Then, taking the MD5 hash of this, and repeating that procedure:
d522231cf8bd5bd3bceb31c640bcab9a
64bb07c8a424dbb918495fa428702998
ed64b3e94672013dd88c415b8575dede
95119774bf93c232892b4f3071348abd
0d1fff8e1426591625a888451ed893c2
3e858eba431292825240db61628a817a
055609b11d0a06b46eff40bcb52eca09
8860c0fbffff97c16f1aa617e3b243e5
518ca0b27a1990b5bac51799c2c1b636
b62fd7e949b2995312b9fbddccd6b19f
b1d831a1d1c6ed8a81e4cb908f5aa36e
dd4e0883a48b1fd3a3a08e26cbc6adc4
3f4a12f0cdc506141badd00bf498dbad
be536872dde5b558975fd3a7dfec4884
402b32bb6839f17028deb13e60dd32ad
...
Given an infinite number of repetitions of the above, is it possible that all possible hashes will be computed an infinite number of times? Is it possible that given some initial message, there may be a revisiting of the initial hash just shortly after the start of the procedure, ie. if the MD5 of 402b32bb6839f17028deb13e60dd32ad was 86fb269d190d2c85f6e0468ceca42a20 again.

Given an infinite number of repetitions of the above, is it possible that all possible hashes will be computed an infinite number of times?

Yes, it is possible; however it is (to the best of our knowledge) extremely unlikely.  Not only would MD5 (on 16 byte inputs) be a permutation, it would also need to be a single cycle permutation.

Is it possible that given some initial message, there may be a revisiting of the initial hash just shortly after the start of the procedure

That is also possible, but again, unlikely (just not as blindingly unlikely as the previous scenario); for a random function, the probability of this happening would be circa $2^{-64}$
The most likely scenario would be that we would fall into a loop that does not contain the initial hash.
All this can be shown if MD5 is assumed to act like a random function.  Now, MD5 is not a random function, and it might have some unknown behavior that would change things.  However, from what we know about MD5, that looks unlikely.


Pseudorandom functions: how are functions stored? I am wondering about the setup for testing if a function family is pseudorandom. We step into a room, and query the black box with $x$, which yields $f(x)$, etc... We don't know if $f$ is a random function, or if it comes from some preset function family $F$. In the latter case, what assumptions are made about the functions in $F$? Is it enough for each $f$ in $F$ to be listed as a table in the black box, so that $f: \{0,1\}^n \to \{0,1\}^n$ is listed as a table with $2^n$ entries? What if $f$ is described by some function of a polynomial with coefficients that are exponential in $n$? What are the restrictions on the functions in the function family $F$, if any?

For the definition of pseudorandomness, the family $F$ of functions can be any set of functions at all. But typically we take it to be a set where each function can be described by a rather short key/seed, and where one can efficiently compute the function output given the input (and the key). This is because we want the family $F$ to represent functions that we can randomly choose from and use in real life.

For example, $F$ could be the set of functions AES$_k$, taken over all 128-bit strings $k$ (where AES$_k$ denotes the AES block cipher with key $k$).  Notice that there are "only" $2^{128}$ functions in this family, which is much less than the number of functions mapping 128 bits to 128 bits (which is $(2^{128})^{2^{128}}$).


Secure Two-party computation In the secure Two-party computation problem with parties $P1$ and $P2$, let us assume the following construction:

$P1$ knows input $a$ and does the following: $a = a1 \oplus a2$ and keeps with itself $a1$ while giving $a2$ to $P2$.

Similarly, $P2$ knows input $b$ and does the following: $b = b1 \oplus b2$ and keeps with itself $b2$ while giving $b1$ to $P1$

So finally, $P1$ knows $a$, $a1$ and $b1$ while $P2$ knows $b$, $a2$ and $b2$.

To compute $o = a \oplus b$, $P1$ computes $o1 = a1 \oplus b1$ while $P2$ computes $o2 = a2 \oplus b2$. We know that $o = o1 \oplus o2$.

My question is where is the operation $o1 \oplus o2$ performed?
If it is on $P1$ (say), then $P1$ would know $o1$, $o2$ and $a2$ (because $P1$ knows $a$ and $a1$, he can recompute $a2$ as $a2 = a \oplus a1$) and we get $b2 = o2 \oplus a2$. Now since $P1$ knows $b1$ and $b2$, he knows $b$, which shouldn't happen.

What is the major flaw in my understanding of the problem here?

The protocol that you described computes the XOR function $a\oplus b$ in the presence of semi-honest adversaries. However, this function completely reveals the other party's input given your own input. Thus, no privacy is actually preserved. However, this is due to the definition of the ideal functionality and not a problem with the protocol.


What does signed fixed window method mean in ECC? I am studying (sliding) window method in Elliptic Curve Cryptography (ECC) but I am confused by the term, signed fixed window method. By the way term is used in a research paper and not in the book that I am reading.

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = d_0 P + b ( d_1 P + b ( d_2 P + ... + b(d_kP))) ...)$ (where the computation of $d_iP$ is done by a lookup of the precomputed values).

There are a number of tweaks we can do to that basic method, but most of those are irrelevant for this discussion.

One is, not, though.  It turns out that Elliptic Curves has one cheap operation that the group $Z_p^*$ does not; it is cheap to compute the inverse.  So, one improvement to this basic method we can do is represent $n$ in balanced notation, where we allow negative digits; $-b/2 \le d_i \le b/2$.  We then compute the values $1P, 2P, ..., (b/2)P$, and then when we need to do a lookup of a value $d_iP$, and $d_i < 0$, we just use the value $-(-d_i)P$, which is a lookup and an inverse.

What this allows us to do is double the size of $b$ at essentially no cost; the table we need to precompute is the same, and the number of additions we need to do is reduced.


Is knowing the private key of RSA equivalent to the factorization of $N$? Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems true as I know the public/private key pair. Can someone help me to prove this?

Please provide references so that I can read further into this subject.

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$.

Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.


SHA256 for large files I have a hardware engine for SHA256 which can process 64K of data, but the input data size I am getting is around 1MB. What should I do to process 1MB size.

What should be my input after 1st 64KB and what will be my IV (initial vector)?
Can anyone provide any idea?

Most likely, the hardware engine has an API accepting an IV of 256 bits (32 bytes) and a data block of some size multiple of 512 bits (64 bytes), and returns a result of 32 bytes.

Given that SHA-256 is a Merkle-Damgård hash, in order to chain invocations of that API, you want to pass the SHA-256 IV (given by FIPS 186-4 section 5.3.3) as the IV of the first call, and the result of the previous call as the IV of the next invocation. The last result returned by the API will be the hash.

Assuming the API does not perform the padding, the data blocks passed to successive invocations shall be the padded message (that is the message of $S$ bits followed by a single bit at 1, then $511-(S+64\bmod512)$ bit(s) at 0, then $S$ on 64 bits in big-endian binary), truncated into blocks suitable for the API, in the order they have in the padded message.

If the blocks passed to the API could only have 64kB size, that API would be usable to process the whole message only when $2^{19}-576\le S\bmod 2^{19}<2^{19}-64$; otherwise, some of the end of the computation would need to be done in software.


How to properly add ECDSA private keys? I'm currently working on an application that requires me to add two ECDSA private keys in order to make a new private key. The result has to have the property, that its corresponding public key is the same as one would sum the public keys corresponding to the first private keys.

I managed to get most of that going, but I have problems when the sum of the private keys gets so big that I need to mod it by the curve's $N$ parameter.

What are the correct steps I should take in order to ensure a proper private key sum is generated?

Well, the normal rules apply, i.e. $(aG + bG) = (a + b)G$, so as long as you add $a$ and $b$ correctly, everything should work fine. Note that you don't actually have to reduce the result of the addition for the point multiplication to give the same result, however your implementation may require the number to be smaller than the order.

Also make sure that you are working mod the order of the curve, and not mod some other number (e.g. the order of the underlying finite field).


Why don't block ciphers consist of a simple XOR operation with key like Stream ciphers? If the construction of stream ciphers is already secure why does the construction of block cipher involve pseudo permutations and complex operations that makes block ciphers less faster?
Is a construction of a block cipher defined as just Xor-ing a block of bytes with a block of key bytes (removing all permutations and other operations) not secure?

If the construction of stream ciphers is already secure why does the construction of block cipher involve pseudo permutations and complex operations that makes block ciphers less faster?

A stream cipher consists of more than just a single XOR operation. They first have to spend time generating the key stream from the key and nonce/seed. They actually use many of the same operations and take about the same amount of time as a block cipher does to do so.

For example, Salsa20 is a stream cipher that uses addition, rotation, and XOR to generate the key stream.

After the key stream is generated, it is combined with the message via XOR.

The stream cipher is only secure if the key stream is unpredictable. The complexity and time goes into making the output unpredictable.

  Is a construction of a block cipher defined as just Xor-ing a block of bytes with a block of key bytes (removing all permutations and other operations) not secure?

Yes, such a construction is insecure. Suppose that the adversary knows a single plaintext message. They can simply subtract out the known message to retrieve the key, which allows them to subtract out the key from any other ciphertext to recover the plaintext message.

$c \leftarrow m \oplus key\\
key \leftarrow c \oplus m$

Unless your messages are the output of a random number generator and have 8-bits per byte of entropy, then they are susceptible to a known plaintext attack. Any meaningful message will not have 8-bits/byte of entropy, and so you have to assume that the adversary already knows the plaintext messages when designing a cipher.

Additionally, assume that you have two messages $m_1$ and $m_2$ that differ by only a single bit. When you XOR the key into them, the only difference in the resultant ciphertexts is at the place where the messages differed by one bit. A block cipher should produce a random permutation of message blocks, and this is clearly non-random behavior. A block cipher needs to spend time creating diffusion, where flipping a single input bit flips approximately half of the output bits.


Attacking AES-128 with Grover's algorithm How many plain text / cipher text pairs are required by Grover's algorithm when it is used to try and discover a secret AES key?

I am trying to determine if having a device which limits the speed at which it produces cipher texts from plain texts will help protect against this attack.

Grover's algorithm is a brute-force quantum algorithm with complexity $\mathcal{O}(\sqrt{N})$ with asymptotically optimal on unstructured data. There is also "Quantum Computing and Hidden Variables" in  $\mathcal{O}(\sqrt[3]{N})$ by Aaronson.

Ensuring uniqueness of the solution

Requires ECB mode;

Let $n$ denotes the block size.

Let $r$ be the number of different plaintext-ciphertext pairs.

Let $r$ denotes the number of the simultaneous plaintext-ciphertext pairs  encrypted under two secret keys $k_1 \neq k_2$.

Then the expected result of having a different result if the $r$ plaintext are different;

$$ 1- \frac{1}{2^{rn}}$$

A good estimate on $r$ is given as;

$$r > \lceil 2^k/n \rceil$$

For AES-128

$n=128, k=128 \Rightarrow r=3$

For AES-192

$n=128, k=192 \Rightarrow r=4$

For AES-256

$n=128, k=256 \Rightarrow r=5$

for more details, see "Applying Grover’s algorithm to AES:
quantum resource estimates"  at #3.1


Using HMAC with AES modes that do NOT require padding I'm trying to use HMAC with AES modes that do not require any sort of padding.
Although I am aware that modes like AES-GCM and AES-EAX already provide
authentication, I want to know if HMAC is suitable with the modes that do not
provide any authentication. This is what I tried:
The code
from Cryptodome.Cipher import AES
import hmac

class DecryptionError(Exception):
    pass

class AESNonAEAD:
    def __init__(self, is_encrypting, key, mode, iv_or_nonce, digestmod='sha256'):
        self._is_encrypting = is_encrypting

        # Use KDF to derive key material from given key:
        # length of crp == length of key
        # length of authkey == (digest size of hashalgo for HMAC // 8)
        crpkey, authkey = derive_key_material(key, digestmod)

        self._auth = hmac.new(authkey, digestmod=digestmod)
        self._cipher = AES.new(key, mode, iv_or_nonce)
        if is_encrypting:
            self._update = self._cipher.encrypt
        else:
            self._update = self._cipher.decrypt

        self._auth.update(iv_or_nonce)

        self._updated = False
        self._len_ct = 0
        self._len_aad = 0

    def authenticate(self, data):
        if self._updated:
            raise ValueError('update has already been called')
        self._auth.update(data)
        self._len_aad += len(data)

    def _pad_aad(self):
        # pad to a multiple of 16 bytes
        if self._len_aad & 0x0F:
            self._auth.update(bytes(16 - (self._len_aad & 0x0F)))

    def update(self):
        if not self._updated:
            self._pad_aad()
            self._updated = True

        if not self._is_encrypting:
            self._auth.update(data)

        res = self._update(data)
        self._len_ct += len(res)

        if self._is_encrypting:
            self._auth.update(res)
        return res

    def finalize(self, tag=None):
        if not self._is_encrypting and tag is None:
            raise ValueError('tag is required')

        # pad to a multiple of 16 bytes
        if self._len_ct & 0x0F:
           self._auth.update(bytes(16 - (self._len_ct & 0x0F)))
        # include length of aad and ciphertext
        self._auth.update(self._len_aad.to_bytes(8, 'little'))
        self._auth.update(self._len_ct.to_bytes(8, 'little'))

        if self._is_encrypting:
            return
        if not hmac.compare_digest(tag, self._auth.digest()):
            raise DecryptionError

    def calcuate_tag(self):
        if self._is_encrypting:
            return self._hmac.digest()

Usage
Encryption
from Cryptodome.Cipher import AES

key = os.urandom(32)
iv = os.urandom(16)
enc = AESNonAEAD(True, key, AES.MODE_CFB, iv)  # or MODE_CTR

enc.authenticate(b'yes this')
encdata = enc.update(b'no not this')
enc.finalize()
tag = enc.calculate_tag()

Decryption
dec = AESNonAEAD(False, key, AES.MODE_CFB, iv)  # or MODE_CTR

dec.authenticate(b'yes this')
decdata = dec.update(encdata)

Questions:

Is this implementation acceptable?
Is this the proper way of using HMAC? Is it necessary to pad the HMAC for non padded cipher modes?
Can this very same scheme be used with Camellia cipher?

If I understand correctly, your input to HMAC is the ciphertext $c$, padded with null bytes (to a multiple of 16 bytes):
    # pad to a multiple of 16 bytes
    if self._len_ct & 0x0F:
       self._auth.update(bytes(16 - (self._len_ct & 0x0F)))

As a concrete example, suppose the ciphertext is $c=$ deadbeef00, then you will compute the HMAC tag as $t = $ HMAC(deadbeef0000...00), 16 bytes. But this is also a valid HMAC tag for different ciphertexts $c'=$ deadbeef as well as $c' =$ deadbeef000000 etc. I hope you can see why this breaks the authenticated encryption security property.
I'm not sure why you are padding/encoding the HMAC input in this way, but my guess is you are trying to "serialize" both the ciphertext and associated data into a single string that is given to HMAC.  This is a common pitfall for authentication: you want to authenticate a pair of things $(x,y)$, and so you authenticate the string $x \| y$. But many pairs $(x',y')$ get mapped to the same string  $x\|y$ (think of cases where the length of $x$, $y$ are variable)! In order to properly authenticate, you need an unambiguous encoding of the pair $(x,y)$ into a string. One good way would be to somehow include the length of $x$ as part of this encoding.
edit: also you never seem to use self._cipher?


Measuring Shannon's diffusion Shannon's idea of diffusion is fundamental to cryptography.

Besides being a descriptive idea, is there any work on measuring or expressing it? Saying something like "System A has more diffusion than B" or "The information in bit x is diffused 1/3 into bit y, 1/3 into bit z, and the remaining third among 11 more bits".

Is there a way to evaluate the diffusion of a transform? XOR does no diffusion, Add with carry does small diffusion, and a permutation may do a lot of diffusion.

In short: Diffusion is a great idea - how can we approach it mathematically?

UPDATE: For instance, we should be able to quantify the diffusion done by adding with carry.  This breaks both of the suggested answers: Adding may update the value of every bit.  Modifying one bit of the input may modify several bits of the output.  But adding still doesn't diffuse very well.

One way is to look at how many bits of the outputs are modified if you modify, say $t$ bits in the input. Actually, a function from $\{0,1\}^n$ to $\{0,1\}^m$ such that modifying $t$ bits in input modifies $m-t+1$ bits of output is said to achieve perfect diffusion.

Examples of functions with good diffusion are those associated with MDS matrices. For instance, the permutation layer of the AES is made of one such function (it is the "mixcolumn" part of the algorithm).


Is this a better GCM? Using the keystream from the block cipher for both parts of the GMAC key (initialization and encrypting the auth tag) seems to produce a better mode of operation than GCM, as successful forgeries and nonce reuse only compromise the particular (key, nonce) pair, rather than compromising integrity for every message encrypted with the given key.

It seems surprising that I can improve upon a well-known and widely-used algorithm as GCM, so I would like to know if there are flaws in this approach.

Is this a better GCM?  Not really.

You can derive an independent GHASH key for each message instead of using the same GHASH key for many messages as AES-GCM does.  It won't reduce security.  It's costlier without hardware support: you can't reuse the same GHASH lookup table to quickly leak secrets through timing side channelsauthenticate multiple messages.

But it's not much of an improvement in security: the difference is relevant only in the case that an adversary has already succeeded in forging a message and confirmed by the receiver that the forgery was successful (or the sender has reused a nonce, which works out to be just like the forger had made a forgery with the same nonce).

In this case, with AES-GCM, the adversary can forge arbitrarily many additional messages by recovering the GHASH key.
In contrast, with crypto_secretbox_xsalsa20poly1305, if the receiver demands sequential nonces or otherwise rejects repeated nonces, the forger can't use this to forge more than one message because the receiver will expect a different key for subsequent nonces.

It makes a difference only if the cost of a single forgery is small and you're really worried about how many forgeries you accept, which is not relevant to most applications—usually we consider a single forgery to be fatal, and strive to ensure it never happens.

This method is essentially what NaCl does in crypto_secretbox_xsalsa20poly1305: choose the Poly1305 key as the first 256 bits of the pad generated by the stream cipher XSalsa20, as suggested by Tanja Lange in 2006.  Exactly the issue you describe is addressed in the NaCl validation paper on p. 30, where Dan Bernstein points out the real security comes from bounding the forgery probability below $2^{-100}$.  This method is also by TLS with the TLS_*_WITH_CHACHA20_POLY1305_* cipher suites defined in RFC 7539 and RFC 7905, updated in RFC 8439 and included in TLS 1.3 in RFC 8446.  Of course, Salsa20, ChaCha, and Poly1305 also avoid leaking secrets by avoiding designs that present conflicts between speed and security in software implementations.  More on the background and shortcomings of AES-GCM.


When making public key fingerprints - is a sha1 hash still a good idea? I'm thinking about trying to save some space (and readability) when referencing 2k and 4k public keys (millions of them) by storing the fingerprint in some places instead of the full public key.

  The primary threat to the security of a fingerprint is a preimage attack, where an attacker constructs a key pair whose public key hashes to a fingerprint which matches the victim's fingerprint. The attacker could then present his public key in place of the victim's public key to masquerade as the victim.

  A secondary threat to some systems is a collision attack, where an attacker constructs multiple key pairs which hash to his own fingerprint. This may allow an attacker to repudiate signatures he has created, or cause other confusion.
  - Wikipedia

With this in mind, I was wondering about using a larger hashing algorithm like SHA-256 to help prevent collisions or collision attacks.

SHA1 seems to be the existing standard, but is it still the way to go?

I understand that in 2005 SHA-1 was found to have a security flaw and the now recommended standard for this kind of thing is SHA-2 (256 or 512).

This post may be of some use:
https://stackoverflow.com/questions/3897434/password-security-sha1-sha256-or-sha512


How do we compare performance of two encryption algorithms? Suppose I want to compare between RSA and Paillier encryption algorithms. I have coded two different programs in the same programming language. Now how to compare between these two and in what aspects they can be compared?

Are there tools available for same?

I'll collect the comments and build an answer from that.
First,

  [..] you just perform the operation, say, a thousand times for
  keys with similar security properties and record the time for each.
  Note that the speed is rather implementation dependent, so you're
  measuring the implementations of the algorithm rather than just the
  algorithm.

of course life and code development would be too simple with this, so

  [Y]ou also need to consider [..] the quality
  of the implementations. If you coded them yourself, do you know about
  the implementation tricks for both algorithms that a quality
  implementation would use? Comparing naive implementations might not
  tell you very much.

and still of course security developement has its own special issues which need to be respected before comparing speed:

  In addition to the above, it is not just the optimization level of the
  implementation that matters, but e.g. resistance to side channel
  attacks, so in some cases an implementation could even be faster than
  a good implementation.

So the logical conclusion is ...

  If you want to compare RSA and Paillier encryption algorithms, then
  you shouldn't compare two implementations of those algorithms, you
  should compare the computational complexity of the algorithms.

with this helpful comment on how to do so:

  In this case, one thing to consider is the different length of the
  modulus and numbers involved (In Paillier, calculations are done with
  numbers twice as long, if the same $n$ is used, due to $\bmod n^2$).

Credits to Maarten, poncho, otus, user2768 and tylo for this joint effort of an answer.


What inputs can SHA 256 take? I'm a complete cryptography beginner and I'm interested in the cryptography behind Bitcoin, hashing, key cryptography etc.
I suspect that SHA-256 can only take Alpha-Numerics but I was wondering if anybody could confirm this or explain otherwise, I've scrubbed the web for answers but found nothing.

SHA-256, as part of the Secure Hash Standard or SHS is defined to operate on bits, to be precise in Section 6.2: SHA-256:

  SHA-256 may be used to hash a message, $M$, having a length of $l$ bits, where $0 \leq l < 2^{64}$.

That said, you won't easily find an implementation that does precisely that; usually only bytes (or, by another name) octets are taken.

This is not just true of SHA-256 but also for many other algorithms such as the derived HMAC algorithm, block cipher modes of encryption, RSA (as specified in PKCS#1), etc..

In some sense 8 bit bytes are the atoms of computers. You can still split them up into bits (protons, neutrons and electrons), but the result is difficult to handle. So almost all cryptographic API's are defined on bytes instead of bits, while the algorithm is usually described using bits.

To handle any other data you need to encode the data as bytes. The reason to use SHA-256 is to generate a semi-unique value for a large input that cannot be converted back to the original value.

This means that the encoding of the data should be unique as well; this is called a canonical encoding. One example of this is ASN.1/DER, which is used to sign the X5.09 certificates used in your web browser.

Alphanumeric data can be converted to bytes using a character-encoding such as ASCII or UTF-8. Of course the encoding should be known in advance or you might get different values for the same string, e.g. if one is encoded using Windows-1252 and the other in UTF-16LE, to name just two random other character-encodings.

Note that some runtime environments contain SHA-2 implementations that implicitly convert characters to bytes. A platform itself may also have a default character representation (e.g. PHP).

Furthermore, the output of SHA-2 may also be converted to a hexadecimal string or something similar. This is however a decision by the runtime/API designer and not of the SHA-2 algorithm; the SHA-2 algorithm is defined to operate on bits.


Where should I store the private key (RSA) in a web application? My web application receives encrypted data from another server encrypted with RSA keys.  Where should I store the private key (RSA) in a .NET web application (Windows)? It seems that putting in it in the application data folder (app_data) probably isn't ideal.  Is there a 'best practice' for this?

I wasn't sure if it's possible to convert the public/private key pair into another format and perhaps store it in the certificate store, but I'm not sure an RSA public/private key pair is even a "certificate".

If this was a PCI compliance issue, it seems I would not even be allowed to store them on the same server, but I cannot then see how one could implement decryption on the server?

If you are in AWS, well and paranoid enough, you might want to use KMS. Google has a similar service. As for non-cloud environments, you can use either an HSM or a KMIP key server. Both HSMs and KMIP servers can be built in an High Availability way, and Amazon offer a good option to use SafeNet HSMs in the cloud, the service is called CloudHSM.

I am not a .Net expert, any more, but my understanding is that it has some adapters to plug in an PKCS#11 engine (HSM) transparently, so that you don't have to write any code for this to work. But it's probably a lot of configuration ugly work to get it to work.


How does Twofish avoid weak keys if it uses key-dependent S-boxes? From section 7.2.2 of the Twofish paper, the four S-boxes for the 128-bit cipher are generated with:

$$\begin{align}
s_0(x) &= q_1[q_0[q_0[x] \oplus s_{0,0}] \oplus s_{1,0}]\\
s_1(x) &= q_0[q_0[q_1[x] \oplus s_{0,1}] \oplus s_{1,1}]\\
s_2(x) &= q_1[q_1[q_0[x] \oplus s_{0,2}] \oplus s_{1,2}]\\
s_3(x) &= q_0[q_1[q_1[x] \oplus s_{0,3}] \oplus s_{1,3}]
\end{align}$$

Here, $q_0$ and $q_1$ are fixed 8-bit permutations, and $s_{i,j}$ are bytes derived from the keys indirectly via a Reed–Solomon matrix. They claim that this scheme does not produce any weak S-boxes:

  Few or no keys may cause the S-boxes used to be “weak,” in the sense of having high-probability differential or linear characteristics, or in the sense of having a very simple algebraic representation

Why is this? How can Twofish avoid weak keys while using key-dependent S-boxes?

The key to the answer lies within these two snippets:-

  These results
  help confirm our belief that, from a statistical standpoint,
  the Twofish S-box sets behave largely like a
  randomly chosen set of permutations.

and

  There should be few or no pairs of keys that
  define the same S-boxes. That is, changing
  even one bit of the key used to define an Sbox
  should always lead to a different S-box.
  In fact, these pairs of keys should lead to extremely
  different S-boxes.

Taken together, they describe an  quasi encryption/hash of the key  à la SEAL (but simpler). Perhaps akin to a  CRC calculation or a mini randomness extractor. Even prior to the MDS matrix. There's probably a better scientific term for it.

$q_0$ and $q_1$ are fairly good S boxes themselves. Even though they are random permutations, their arrangement has been numerically optimised for differential and linear characteristics of $ \frac{10}{256} $ and $ \frac{1}{16} $ respectively, and no more than two fixed points. Taken with the permuted arrangement in the three levels deep nested look ups of $q_0$ and $q_1$ within the definition of  $S_i$, it's extremely unlikely that you'd find pre-images that create all weak $S_i$. It's  difficult to algebraically define what a related key might look like for a given pre-image.  That's just a consequence of all nested look ups into   random permutations. The permuted nesting is highlighted below:-

Like you, the authors worried about weak keys too.  Hence a large § 7.2.3 Exhaustive and Statistical Analysis. Monte Carlo simulation seems to confirm their assumptions that weak keys are quite unlikely due to the pseudo permutation and avalanche behaviours. Your "very simple algebraic representation" doesn't occur due to the inherent randomness within $q_i$, where the shortest computational representation of $q_i$ is  $q_i$.


PKCS#7 message content I am using a vendor library that signs a text producing a PKCS#7 message. I'm not sure of the content of this message.

Does a pkcs#7 message have to contain the signed message, the certificate, the payload? Does it have to start with ----BEGIN PKCS7---- and end with ----END PKCS7----?

First, PKCS#7 -- almost always considered to include its successor CMS in the same way "SSL" usually means TLS -- supports several cryptographic functions; you appear to be asking only about signing, so I will ignore the other parts. If you want more, read the RFC and/or add to your question.

PKCS#7/CMS has two options for signed data, one where the data is contained within the SignedData message, usually called embedded,
and one where the data is not in the message but must be available to the recipient, usually called separate, external, or detached.

PKCS#7/CMS messages including SignedData (but not necessarily external data) are first encoded in ASN.1 BER or DER
which can then be transmitted and/or stored in binary or in PEM format using the dashed BEGIN,END PKCS7|CMS lines around a base64 encoding. (CMS messages
can also be used in S/MIME messages with a slightly different formatting, but those are usually called S/MIME not PKCS#7 or CMS. In particular, a "clearsigned" S/MIME message contains a detached encoded signature plus a more-readable direct encoding of the data as parts of one email message.)

A PKCS#7/CMS SignedData can carry one or more signatures, but more is rare;
it can carry certificate(s) and/or CRL(s) that the signer believes the recipient(s) will or may need to verify the
signature, but this is not required if the sender knows or believes the recipient(s) have or can get the certificate(s) and revocation info by other means.

In fact, PKCS#7/CMS SignedData can be used with no signatures and no data solely to carry some related certs (and possibly CRLs);
this is commonly indicated as "p7b" or "p7c" format. This doesn't apply to your case, but could be confused with it.

You can determine which elements are present in a given message by parsing it; if particular, if you have or get
OpenSSL openssl asn1parse will by default decode a PEM file (ignoring the type stated in the BEGIN,END lines, which can even be omitted) or with -inform der a binary DER file.


Proof that counter mode of operation and CBC mode are CPA secure when pseudorandom permutations? I know counter mode can be CPA secure, when used with block ciphers modeled as  random permutations. If we use pseudo-random permutations, is it still CPA secure? Is there a proof?

How about CBC mode? When used with block ciphers modeled as pseudo-random permutations, will it be CPA secure? Again, is there a proof?

Standard security proofs for CTR and CBC deal with pseudo-random permutations (or pseudo-random functions). Relevant references can be found in Sections 4 and 5 of Rogaway's survey. However, it is unclear what you mean by a proof with random permutations. Where is the key then?


Would buffering socket send resist timing attacks I have been reading and thinking about timing attacks on cryptographic systems. The answer to this question mentions the following:

"The way to defend against timing attacks is to make sure the time taken to execute cryptographic operations does not depend on any secret information."

My question is, assuming a model where an adversary is connected to an oracle via networking, would write buffering socket.send at the application level to only occur every x milliseconds protect against crypto operations that would otherwise leak data?

My idea is to use the select system call say, every .01 seconds, to handle any reads and writes. Since data would only leave the server at constant intervals, does it matter if short circuit comparisons or the like were used?

The most obvious downside I can think of is that it would add some latency to all application network requests, even non crypto related ones.

Is this a valid defense against side channel attacks in situations where networking delivers the queries/responses?

It will only help to a certain degree.

If you want to protect against ciphertext attacks you cannot just add random time. The reason for that is that the random time you add is probably in a range. Or in your case, the period between calls will be in a certain range.

This means that if you have a large enough sample set you can figure out the deviation of the calls. Say you find out the maximum timeout. If the call takes maximum + x then x will be the time that the cryptographic operation takes.

Of course, for this to become a problem, you need to have a bigger data set. Computers and networks are however insanely fast, so usually creating a bigger data set is often not a problem.

If you try to mess with things like buffering of networked data you may also have to protect against attackers trying to circumvent the buffering issue. The network is the initial interface for an attacker, so it will be the primary attack surface.

The network buffering and cryptographic computations are not directly related. This solution would tie the network implementations with the protection of cryptographic algorithms. This is probably not a relationship that you want to maintain.

Your solution will also not protect against DPA attacks or attacks on the CPU itself (using access to the CPU from user accounts). So the protection is limited to the networking interface.

Another issue is that CPU scheduling can be pretty obnoxious. Sometimes an operation may take much longer than average. In that case the timeout may not be sufficient.

All in all, this should definitely not be the only protection against side channel attacks, and the limitations of the approach should be well understood.


A patched SHA1 attempt for password verification This is a classical scenario: For our web based authentication platform we have a username and a password field. User enters these values and presses Log In. The browser gathers the user data, calculates a digest of the password and sends everything to the server side. We don't want to send the password over the network, it might not be safe.

On the server side we have the database which stores the hashes for passwords in a table (among other stuff).

Initially we were using MD5 for this purpose but after a while we threw out the idea as being the most over hacked message digest with large available rainbow tables, so once someone captures the packet they easily can guess the password (if it's a weak one).

Now we have switched to SHA1 for calculating the digest... There remains only one problem. The initial database layout was to use 32 characters for the message digest of the password (the length of the MD5 hex string) ... however the SHA1 is 40 characters long (when transformed to hex bytes). The bigger problem is that we don't want to increase the length of the message digest table's column (nor the length of the used message digest itself) since the digest value is used at some stages in a few algorithms and it relies on the fact that it has 32 characters.

So someone from the architecture team came up with the idea: Let's add an extra validation step to the login procedure and ask a 4 digit long pin from the user. And when we have this PIN we simply remove two times the characters found at the given PIN position from the SHA1 digest of the password (from the beginning and from the end), and this way we end up with a 32 character long digest, which cannot be traced back to the password since it hasn't got all the required information.

There is just only one thing which bothers us: what are the theoretical chances that two different passwords which give two different hashes after applying two different character removal algorithms (based on two different PINs) will give the same result.

And since we have no cryptanalyst nor cryptographer in our team we have to turn to the community :) Thank you for helping.

Short answer: don't. Use a password hash like PBKDF2, scrypt or bcrypt.

Also, if at all possible, use a library that takes care of the low level stuff like password database for you. E.g. passlib might work if you use Python. I'm sorry if that sounds blunt, but that's how it is.

To answer your actual questions:

  There is just only one thing which bothers us: what are the theoretical chances that two different passwords which give two different hashes after applying two different character removal algorithms (based on two different PINs) will give the same result.

The chances that two different password give the same final hashes are the same regardless of whether the PINs are different or not. The chance is $2^{-n}$ for an $n$-bit final hash. I.e. $2^{-128}$ for a 128-bit hash.

(To see why the PINs don't matter, consider the output hash as a random number. That's the best you can do. Different PINs would only matter if the password hashes are equal.)

You can instead just truncate the hash, including the PIN in the string to be hashed together with the password. Also, if you went this way, you might as well use SHA-256 which is believed secure, instead of SHA-1 which has theoretical attacks that truncation might make practical.

Again, you should not use just a normal hash to protect passwords. Further, your idea of hashing the password in the client is insecure:

  The browser gathers the user data, calculates a digest of the password and sends everything to the server side. We don't want to send the password over the network, it might not be safe.

This is a good instinct, but it doesn't work as you described it. Anyone who steals your password database will be able to use a hash to log in if you don't hash on the server side. (Your site/app may ask for a password, but the attacker doesn't have to use it.)

You can hash both on the client and the server, although that only protects the plaintext password in case the encryption is broken. That's nice for users who reuse passwords, but will not protect their accounts on your system any more than just hashing on the server.

(Unless the connection where you send the plaintext password over is encrypted, an eavesdropper can always just get the password/hash and log in!)

One more additional suggestion: if you really are limited to 32 characters in the password database, consider using base 64 encoding for the hashes if at all possible. That allows you to store 192 bits of the password hash. Binary would be even better, allowing the full 256 bits of scrypt or PBKDF2 with SHA-256.


XORing a nonce with a ciphertext vs XORing a nonce with plain text and then encrypt Consider a situation where a symmetric key encryption (such as AES) is used to encrypt the plain text. Moreover, a nonce is used to ensure that old communication cannot be used to perform a replay attack. In this scenario:

Is it better to XOR the nonce with the plain text and then encrypted the output to produce a cipher? Or XOR the nonce with the output cipher produced by encrypting the plain text? Which one would be more secure?

In my opinion, scheme 1- XORing the nonce with plain text and then encrypting the output seems to be a better option as it would produce a different cipher every time even if the plain text remains the same. Moreover, since the (nonce XOR plain text) goes through the permutation and substitution operations, the information about the nonce remains more secret. On the other hand, scheme 2 seems to be relatively less secure as the output (nonce XOR cipher) might give away some information about the generation of nonce (or about the PRNG or CSPRNG) if the attacker is able to collect enough cipher texts.

What do you think is the better way?

option 2 is insecure. Recall the nonce is public and must be sent with the ciphertext, which means it can be removed from the ciphertext trivially and therefor has no effect at all.
You are effectively doing ECB with some useless extra step and extra communication.


Is Poly1305 an information-theoretically secure MAC? I have heard some people say that the Poly1305 authenticator is a "nuclear" MAC i.e. it is information-theoretically secure. After reading the paper I see it is based on the Wegman-Carter MAC which is supposedly the natural authentication pairing with the one-time pad cipher.

Is it true though that Poly1305 is really an information-theoretically secure MAC? Here is an excerpt from the paper:

  1 Introduction

  This paper introduces and analyzes Poly1305-AES, a state-of-the-art secret-key
  message-authentication code suitable for a wide variety of applications.

  Poly1305-AES computes a 16-byte authenticator Poly1305r(m, AESk(n)) of
  a variable-length message m, using a 16-byte AES key k, a 16-byte additional
  key r, and a 16-byte nonce n. Section 2 of this paper presents the complete definition of Poly1305-AES.

  Poly1305-AES has several useful features:

  Guaranteed security if AES is secure. The security gap is small, even
  for long-term keys; the only way for an attacker to break Poly1305-AES is
  to break AES. Assume, for example, that messages are packets up to 1024
  bytes; that the attacker sees 264 messages authenticated under a Poly1305-AES
  key; that the attacker attempts a whopping 275 forgeries; and that the
  attacker cannot break AES with a probability above δ. Then, with probability
  at least 0.999999−δ, all of the 275 forgeries are rejected.
  Cipher replaceability. If anything does go wrong with AES, users can
  switch from Poly1305-AES to Poly1305-AnotherFunction, with an identical
  security guarantee. All the effort invested in the non-AES part of Poly1305-AES
  can be reused; the non-AES part of Poly1305-AES cannot be broken.

So it appears Poly1305 is only secure if AES is secure. So in theory if I do not like AES I can swap it out for something else like ChaCha20 (as many have done e.g. SSH and TLS 1.3). However then the authentication is still only as secure as ChaCha20 which in itself is not information-theoretically secure. So then, what if I need an authentication tag that will remain secure for a long period of time (100+ years) and even resist cryptanalysis indefinitely?

I understand the point of the Poly1305 is to re-use the keys for many messages as long as the nonce changes each time. However, assume a hypothetical system which has many one-time pads generated by a HWRNG and they are pre-shared between two parties via a physical exchange. The key material for each message is divided up as follows:

92 byte key for encrypting the 92 byte message using XOR $\oplus$
16 byte Poly1305 encryption key $k$ (formerly the AES key)
16 byte Poly1305 additional key $r$
16 byte Poly1305 nonce $n$

So in this scenario the $k$, $r$ and $n$ are unique and truly random per message sent. So per one-time pad encrypted and authenticated message it uses up 140 bytes of true random data. Now given that this construction creates the Poly1305 tag:

Poly1305$_r$($m$, AES$_k$($n$))

Can the AES$_k$($n$) portion be simply replaced with $k$ $\oplus$ $n$? In other words, encrypt the nonce with a one-time pad. Will this remain theoretically secure indefinitely?

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$?

No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational theoretic.

Here's why: Poly1305 is based on a polynomial universal hash.  This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^i)$, interpret the message being authenticated as a series of value $m_a, m_{a-1}, ..., m_1$, and compute the value:

$$m_a x^a + m_{a-1} x^{a-1} + ... + m_1 x^1 + f(k)$$

where the above additions and multiplications are done in $GF(p^i)$, and $f(k)$ is the 'unknown encrypted nonce' ($AES_k(n)$ in the Poly1305, $k$ in your case).

The idea here is if someone is able to find a second message and tag that authentications with the same nonce, then we can 'subtract' the two polynomials, and find a polynomial in $x$ that evaluates to 0.  And because $GF(p^i)$ is a field, that polynomial has no more than $a$ zeros; that is, unless $x$ is one of $a$ out of $p^i$ possible values, that polynomial won't be zero).

Now, with Poly1305, they use the values $p = 2^{130}-5$ and $i = 1$.  What this means is that the operation that adds $k$ is not bitwise xor; instead, it is modular addition.  Now, the above proof assumes that the addition is actually modulo $2^{130}-5$, not $2^{128}$; it turns out that it isn't hard to show that this increases the possible number of 0's by a relatively small factor.  I don't know of any corresponding proof if you replace the addition with xor, and hence using xor would appear to be foolhardy.


Can not use big prime number for pair of key of RSA Algorithm I'm new to cryptography. I have a binary image with 64x64 pixel in size. I perform an encryption to the image using RSA Algorithm. I wanna ask something bothering me, why can I not use big prime numbers as a pair of key for the RSA algorithm? Thank you in advance.

Although it is theoretical possible to create two large primes and use that to establish the private and public key, there are real issues doing so. First of all, let's check how big a modulus you need, as that defines the size of the two primes.

Let's assume color, and use the RGB color space without gamma, each color having 8 bits of color depth. That means each pixel uses 3 bytes. So your bitmap takes $64 \cdot 64 \cdot 3 \cdot 8 = 98304$ bits. That's excluding overhead of both the image as well as the overhead required for the padding required for secure RSA encryption (both of which may be insignificant with these kind of values).

This requires you to find two primes of half the number of bits to create secure RSA, assuming that you use the regular RSA and not multi-prime RSA. Unfortunately, even a modern CPU can take time to calculate an 8K-bit modulus. The problem is that each prime number is now close to 49152 bits. The density of primes is much smaller for such large spaces. Furthermore, doing primality testing on that kind of values will take a lot of time. So the time to find the primes $p$ and $q$ grows very rapidly (a factor of 12 to 16 for each additional bit). So the time to generate a key pair that size is prohibitively large (and depends on chance as well).

Just type in openssl genrsa 98304 on your computer to use it as a heater.

So key pair generation is a huge issue at these key sizes. Performing any modular exponentiation with these kind of exponents and modulus sizes will be a lesser-but-still-significant issue as well. Many cryptographic libraries will have maximum key sizes for these reasons (and others, such as limiting testing, memory usage etc.).

So what can you do? Well: you can simply split up your plaintext into blocks and encrypt each with RSA. This will still be slow and will expand your ciphertext significantly compared to the plaintext image size, as padding the blocks is required.

What most cryptographers do is to pair the RSA algorithm with a symmetric cipher such as AES. In that case you can generate a random AES key and use that to encrypt the image (using a secure mode of operation). Then the AES key itself can be encrypted using the RSA public key. This kind of scheme is called a hybrid cryptosystem.


Is a book cipher provably secure? I've seen ciphers (usually in spy drama shows) that involve taking a book and writing down an index to individual characters. Essentially it's a keyed substitution cipher, where the key is the name and exact edition number of the book.

Example:

Imagine a book that has 500 pages, with approximately 60 lines per page and 80 characters per line. We might write 238:4:64 to specify that we're on the 238th page, 4th line, 64th character. A five character message might be encrypted into 114:25:22 374:41:46 182:17:62 63:53:8 50:8:18.

Without knowing what the book is, I would imagine this is provably secure as long as the person encrypting never re-used an index. Am I correct in this assumption?

For fun, you could try this out:  12:9:3 183:15:7 238:14:11 310:9:38 194:11:17 7:1:1

I'm using a page:line:character format, ignoring titles, spaces and punctuation. The book is Charles Darwin's On The Origin of Species, 6th edition.

N.B: I'm not trying to get you to crack this, just adding it because it nicely demonstrates the way this works :)

Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and 321:42:36. Therefore, merely not reusing exact index values is not sufficient; you should refrain from using two index values from the same word. This reduces the lifetime of a given book as a cipher key.

Another problem is in the "random choice". When you want to encrypt a letter, you must choose one of the index values in the book which correspond to that letter. Human beings are very bad at making random choices in their head. But non-random choices can exhibit biases. So the encryption process is important, and not completely described. An unbiased process would have you use dice to select at random the page, line and column; and if that does not correspond to your target letter, try again. That's tedious.

Also, in order to avoid reusing a given index, you must keep a list of the index places you have used, e.g. by marking the already used letters in the book. The book then ceases to be an inconspicuous object: instead of a brain-only key ("use this book"), you have a physical key ("use this, I mean that specific printed instance, book").

And, of course, anybody who has scanned millions of book and extracted the text into searchable computer structures, can easily try all existing books in a few minutes, and report a hit when the decryption result appears to look like meaningful words. So you are at the mercy of Google (and of whoever acquires Google's services).


When to prefer exchanging cryptographic certificates over exchanging only public keys? Let's think of the following case:

A group of peers want to exchange messages with each other. They use public-key cryptography to sign and encrypt messages. Anyone with any name can join the network. There is no central trusted authority, such as a CA that could issue certificates. When a peer joins, he publishes either, A) a self-signed certificate or B) a public key only, that others can use to him send messages.

Would under such circumstances cryptographic certificates (A) provide any advantage over using just private/public key pairs (B)? As far as I have understood certificates can only make sense if  everyone trusts a central authority that issues certificates.

To my mind, that means if a peer joins the network it is sufficient that he broadcasts a message with his name+public key, signed with his private key. Everyone would know that he is in the posession of a private key for the specific public key.

That also implies that we cannot be sure a peer who claims to have a certain name really has this name. (Let's consider each peer has a name, that we don't know.)

What is your opinion about it?

There is another advantage that certs provide that has nothing to do with trust issues.  Certs are a pretty-much universally-recognised public-key bit-bagging format that's portable to pretty much everything, while there's no such equivalent for raw public keys. By placing your public key in a certificate, you're converting it into an interoperable form that almost anything (even some versions of PGP) can read.

This use of certs as public-key exchange formats is quite common, it's effectively what a self-signed cert is. In addition many crypto tools ignore the rest of the certificate (even when it's issued by a CA) and just use the public key, since that's all they care about, either because the cert/public key are communicated via authenticated channels and the use of a CA is just a distraction, or because all you need is the cert as a token to enable crypto without having to go through all the calisthentics of cert validation.

So I'd always use certs to exchange public keys, not because of any magic surround certs, but because they provide a useful interop format for keys.


How is the affine cipher a permutation? It seems there would be some collisions in what the different symbols map to, resulting in loss of information.

For example, say we use the English alphabet, multiply by 2 and take the congruence mod 26.  In this case, A and N will both map to the same ciphertext letter, regardless of what the shift value is.  Same with B and O, etc.  In fact, if the formula is $(ax + b) \mod n$ where $n$ is the size of the plaintext alphabet, then the ciphertext alphabet will have only $1 \over a$ as many symbols as the plaintext alphabet.

Am I misunderstanding something?

Multiplication by 2 modulo 26 is indeed not a permutation.  For example, $$2 \times 13 = 26 \equiv 0 = 2 \times 0 \pmod{26}.$$

The necessary and sufficient criterion for the affine map $x \mapsto ax + b$ to be a permutation of the integers modulo $m$ is that the multiplicative constant $a$ and the modulus $m$ must be coprime; that is, their greatest common divisor must be 1.

If this is the case, then we can find the modular multiplicative inverse $a^{-1}$ of $a$ modulo $m$ and use that to define the inverse map $x \mapsto a^{-1}(x-b)$.  It's easy to verify, based on the fact that $a^{-1} a \equiv 1 \pmod m$, that the composition of these two maps (in either order) yields the identity map $x  \mapsto x$, which is sufficient to show that these maps must be bijective.

Conversely, if $a$ and $m$ share a common divisor $g > 1$, then the map $x  \mapsto ax + b$ cannot be a bijection.  In particular, both $0$ and $m/g$ will be mapped to the same element $b$ by this map.


Reason for replacing mifare classic As you know there occured some successful attacks again mifare classic tags (manufactured by NXP) and therefore NXP recommends to replace these tags with some newer products like mifare pro desfire and others.

My question is why don't we encrypt data (with AES, ...) and then translate and store this data to the mifare classic's block, with present 32bit micro controllers it doesn't need so calculation time and there will be a good saving in cost . Why don't companies implement this approach ?

EDIT

tnx all answers.
at first my mind from 32 bit mcu was not tag's built in processor,i mean first we separately encrypt plaintext  to ciphertext in the mcu based on AES.
I have an extra scenario, lets find it's bugs:

as you know each tag has a Unique ID(UID) & we define a key for transacting data between tag & reader/writer chip that controlled by the mcu( PCD chip).
when tag entered to PCD's operation field,pcd read tag's UID
mcu make ENC_KEY with irregular combination of AES_INIT_KEY & uid (each tag will has seprate ENC_KEY)
mcu calculate plaintext'hash with its hash function(TEXT_HASH).
mcu encrypt plaintext based on AES with ENC_KEY(it makes CIPH_TEXT).
mcu transfer & stored CIPH_TEXT & TEXT_HASH to the tag's (mifare classic) via mifare algorithm .

then there are not problems mentioned in answer1, each tag's has unique key & same credit in different has not same CIPH_TEXT

in the second part:

mcu read tag's uid,make ENC_KEY with tag's uid & AES_INIT_KEY ,read CIPH_TEXT & TEXT_HASH with crypto1 & its key from tag,decrypt CIPH_TEXT & TEXT_HASH with ENC_KEY & checked plaintext integrity with its hash value.

i accepted  Maarten Bodewes's answer about price case .(tnx a lot)
I'm really concerned to read this approach's baugs
WBR

Enciphering data using AES and moving that to a card without effective security is not enough to solve some very real security issues; including most preeminently the possibility of

returning a prepaid card to its original state, re-crediting it after use (an adversary can copy the original enciphered data, and save it for future use when the genuine card is empty)
making duplicates indistinguishable form the original (which can multiply stored value, or allow to forge duplicates of an access cards)

Update: it was suggested that the content of the card be enciphered and integrity-protected using a symmetric key derived by the reader from the tag's Unique IDentifier and a master key. This effectively prevents an adversary (not knowing the master key) from altering at will the content of a card, or copying the content of a card to another card with different UID. It however gives no protection at all against attack 1 (which copies the original enciphered and integrity-protected data back to the original card); and only blocks attack 2 if an adversary has some difficulty making a duplicate card with the same UID as the original.

Note: Mifare Classic cards do not use a micro-controller, much less a 32-bit micro-controller (as I wrongly thought the question suggested), which are currently used in rather high-end Smart Cards; many Smart Cards ICs used in mobile phones SIMs, bank cards, transport cards, identity documents.. still use an 8-bit CPU, or 16-bit evolved from 8-bit, like these or these.


Encrypting twice with different modes? I was using a SOCKS5 proxy today (tunneled through SSH) and I began to wonder what the effect of encrypting twice (TLS over encrypted SOCKS5 in this case) would have on the security of the transmitted data. The proxy was using 256-bit AES in CTR mode, while the page I was viewing was using 128-bit AES in GCM mode. While I am not worried that this will be harmful at all, I am curious as to how much more difficult a scenario like this would make it for an attacker to break the encryption (assuming they could somehow bruteforce 128/256-bit keys).

When you are e.g. sending TLS encrypted data over a SSH tunnel, there are two things in particular that should be noted:

The TLS handshake will only commence, once the SSH connection has been established.
The bulk encryption keys of TLS will be completely independent of the SSH encryption keys.

Since the handshakes and keys are completely independent, there is normally no reason to worry about any bad interaction between the two layers. The TLS data is no different from any other kind of data, from the perspective of SSH. The SSH connection is no different from any other kind of serialized physical connection from the perspective of TLS.

That said, in some corner cases there might still be security issues with such combinations, but only if you e.g are using the same broken random generator for the pre master secrets, etc.

  I am curious as to how much more difficult a scenario like this would make it for an attacker to break the encryption (assuming they could somehow bruteforce 128/256-bit keys).

Most likely, not at all. If you picture yourself being targeted by an adversary with the ability to brute force 256 bit keys (which of course is not realistic), adding a second layer with 128 bit security will not increase the hardness in any significant way. This is (if not for any other reason) because the outer layer might be attacked separately. The TLS handshake is not encrypted, so a theoretical brute force attack on the SSH transport encryption will still only require a $2^{256}$ work factor.


Elliptical curve cryptography key generation time I am currently trying to learn more about Elliptical curve crypthography and have finally started to get things working and undestanding the different pieces.

I've written a small project in C# and are currently testing it using really big numbers (the .NET BigInteger class). So far I've implemented the key generation algorithm, the point addition, doubling, encryption and decryption.

Now my problem is the key generation. The formula for generating a key is:

Q = d * G

Where Q is the public key, d is the private key and G the generator point.

If I for example want to use a 256 bit private key n would become a BigInteger with 78 numbers in it right (2^256)?

Now to calculate Q this will take a lot of time since it means I will need to perform point addition an insane number of times unless I'm not understanding something about it.

How is this accomplished in practise? Am I thinking about it in the wrong way or will I need to perform the point addition up to 2^256 times? What is the expected amount of time for modern computer to generate the key-pair?

Thank you!

Now to calculate Q this will take a lot of time since it means I will need to perform point addition an insane number of times unless I'm not understanding something about it.

You're missing a point; elliptic curve point addition is associative; that is, for any three points $A, B, C$, we have:

$$(A + B) + C = A + (B+C)$$

Now, why is this a big deal?  Well, we can exploit that compute $G+G+G+...+G$ surprisingly quickly.

Our first step is to compute $G+G$ (which is $2G$); that's straight-forward:

$2G = G+G$

One point addition, no improvement over the naive method.  Ok, let us compute $4G = G+G+G+G$.  By the associate law, that is:

$4G = G + G + G + G = (G+G)+(G+G) = 2G + 2G$

So, we can compute $4G$ with two point additions, one to compute $2G$ and one to take $2G$ and use it to compute $4G$.

Then, to compute $8G$, that's $8G = 4G + 4G$, just one more point addition.

In general, we can compute $2^kG$ (which is $G$ added to itself $2^k$ times) using only $k$ point additions.

And, what do we do if $d$ doesn't happen to be a power of 2?  Well, by adding in previous results at various steps (e.g. $5G = 4G + G$), we can accommodate those with some additional expense.

One straight-forward way to extend this to any $d$ is found here; we know more efficient methods (some of which are also on that page); however it is quite reasonable, and a good place to start.

With this technique, you can generate an elliptic curve private key in milliseconds (and, this method of computing point multiplication will also be used when you use the key to actually do something)


Standard or guidance for entropy collection I need to write some high-level security requirements which include a random number generator suitable for use in cryptography. I don't need something very formal, this isn't a security certification or a work order. I just want to go to the next level from “supply a proper RNG”.

A proper RNG should be built on a cryptographic PRNG seeded from an appropriate entropy source. For the cryptographic PRNG and even the seeding method, it isn't hard to find applicable standards; for example, I'd be content to write that the PRNG must use one of the algorithms listed in FIPS 140-2 annex C, or attain an equivalent security level.

What about entropy collection or seeding? Is there a similar document that I can quote? Anything easily available in English would do, it doesn't have to be (or not to be) a government standard or an RFC or similar, but it's better if it looks somewhat official or trustworthy.

Offering concrete guidance would be a plus. However this could be hard since the requirements may need to be met in very different ways (e.g. a non-deterministic oscillator in an embedded device, a server with a radioactive source, a PC with someone wiggling the mouse, …).

As far as I can tell, NIST has only one official document about entropy collection. SP-800-90B.

  The purpose of NIST Special Publication (SP) 800-90B is to
  specify the design and testing requirements for entropy sources that can be validated as approved entropy sources by NIST‘s CAVP and CMVP.

It essentially defines a bunch of statistical tests to check the strength of a particular entropy source. Seeking entropy methods that meets the requirements is a good first step especially if you need "official" certification by NIST.


What should an identifer in the client-server model? I am fairly new to cryptography and I am trying to understand this picture here. I have some questions regarding this picture.

What should be an identifer for a side? For example, in the picture, it says that A sends an identifer with a nonce to B. Should I just set a fix alias for each side, something like String ID_A = "ID_A"?
Would AES make sense here, or would RSA be better?

Again, I apologize if these questions do not make much sense, but I am new and trying to grasp the idea.

EDIT: I have updated some further details.

There are a few non-standard/confusing things about this picture. I'll address them in a minute.

1) Yes, you can set a fixed alias for each party. You will want to make sure that the aliases are unique, public, and verifiable.

2) You're right that RSA is better to use here than AES. In particular, the encryption scheme here is asymmetric, that is, the encryption key is different than the decryption key. Since AES is a symmetric key primitive, it wouldn't really make sense to use it here.

The notation $E(PR_a,K_s)$ is syntactically incorrect. You don't encrypt using the private key in an asymmetric encryption scheme.

However, the real problem seems to be that you want to be using a signature scheme in that particular location rather than an encryption scheme. To understand why this is the case you need to understand the difference between privacy and authenticity:

Privacy ensures that nobody can read a message except for the person/people holding the decryption key. Authenticity ensures that a message really was sent by a particular person. Encryption schemes generally provide only privacy. However, if you want authenticity in the asymmetric setting, you probably want to use a digital signature scheme -- that is, person A can sign a message, and anybody can verify that the message was in fact signed by A.

(For RSA in particular, you could think of the decryption function as a signing function and then think of the encryption function as a verification function and this will give you a digital signature scheme. But this is not at all true in general. It only works for RSA because of the particular details of the RSA algorithm.)


Can I find a number, such that the its SHA-256 hash is all-0 I want to find a number, such that the result of its SHA-256 hash is all 0.
I don't know if this number exists.

For any output $z\in \{0,1\}^{256}$ it is very unlikely that there is no input mapping to it, since the input space is astronomically larger than the output space, and SHA256 has been carefully designed as a pseudorandom function. So, most likely yes such an input exists.
The number of trials you need to find such an input (no shortcut better than trying random inputs is known) is approximately $2^{256},$ this is the first preimage problem in hash function theory.


TRNG and Stream ciphers How do phenomena such as mouse movement or thermal noise are exploited as TRNG within a symmetric crypto-system  (e.g: Stream cipher)? I will really appreciate if anyone could provide me with a genuine use case in order to well understand the concept. Many thanks in advance.

I think you're confused about the module boundaries (so to speak) between the symmetric algorithms and the random number generator.

Symmetric algorithms generally expect some of their inputs to be randomly selected.  For example, symmetric algorithms generally expect secret keys to be randomly selected.  Some algorithms also want you to supply non-secret, randomly selected nonces or initial values (IVs).

But those are preconditions that the algorithms expect you to meet before you call them.  The mechanism for generating random values is external to them.

Here's a silly car analogy.  If symmetric algorithms are like cars, then random numbers are like fuel and random number generators are like refineries:

Cars use fuel, and fuel is made in refineries, but neither the fuel nor the refinery are parts of the car.
The car's function depends on the composition of the fuel, but not really on the design of the refinery—as long as it produces appropriate fuel, any refinery is fine.

Symmetric algorithms can be fed randomness directly from a random number generator, but very often they're "fueled" indirectly from intermediate sources that use an RNG.  The most significant of these is the Diffie-Hellman key exchange.

You may enjoy reading chapter 9 of Ferguson, Schneier and Kohno's Cryptography Engineering, which happens to be the one available as a free sample, which motivates and details the design of one cryptographic random number generator design, at an informal, introductory level.


Is this an acceptable way to increase the block size of a block cipher? Note: This is all for fun and learning. None of this will go into production code.

I'm studying something (sponge functions, specifically) that benefit from large block sizes. AES has a (comparatively) small block size of only 128 bits. Is this a safe construction for increasing the block size?

$E(x)$ and $D(x)$ are encryption and decryption in ECB mode respectively. The size of the input $b_0$ is a multiple of the cipher's block size. The encryption proceeds as follows.

$$c_n = E(b_{n-1})$$
$$b_n = shift(c_n)$$

This is repeated once for every blocksize chunk in the input. For example, encrypting a 512-bit block with AES (a 128-bit block cipher) will take 4 rounds, so the output will be $b_4$.

Decryption is a simple reverse of the above algorithm.

$$c_{n} = shift^{-1}(b_n)$$
$$b_{n-1} = D(c_{n})$$

$shift(x)$ is defined as lining up the blocks vertically and shifting each row by an amount corresponding to it's row. All operations are done on the byte level. It is similar to ShiftRows in AES.

For example, with a block size of 8 (bytes) and an input of aaaaaaaabbbbbbbb12345678, $shift$ would proceed like this.

ab1 <-- shift by 0            = ab1
ab2 <-- shift by 1            = b2a
ab3 <-- shift by 2            = 3ab
ab4 <-- shift by 3 (equiv. 0) = ab4
ab5 <-- shift by 4 (equiv. 1) = b5a
ab6 <-- shift by 5 (equiv. 2) = 6ab
ab7 <-- shift by 6 (equiv. 0) = ab7
ab8 <-- shift by 7 (equiv. 1) = b8a

The resulting output would be ab3ab6abb2ab5ab81ab4ab7a.

The intention is to diffuse it enough to make sure every plaintext bit has an effect on every ciphertext bit.

Are there any major flaws I'm missing here?

The purpose of a mode of operation for a block cipher is to get rid of the size limitation imposed by the block size, so what you're proposing is to use an insecure mode, tweak it to try to hopefully make it secure, and finally build a new block cipher with this... At the cost of 4 AES encryption to achieve diffusion (whereas the MixColumn and ShiftRow operations in AES try to achieve the same diffusion at a much lower cost.) So I'm not convinced by the performance of your block cipher and don't see why it is superior to, say, AES-CBC with a fixed 512 bits size.

Now, what flaw are you possibly missing?

Well, since you are using AES ECB, if your plaintext is for example a repeating block of 128 bits, it will get encrypted into the same AES block by AES ECB, which means that your Shift operation will do nothing, since all of its row will be filled with a repetition of the same byte:

111 <-- shift by 0            = 111
222 <-- shift by 1            = 222
333 <-- shift by 2            = 333
444 <-- shift by 3 (equiv. 0) = 444
555 <-- shift by 4 (equiv. 1) = 555
666 <-- shift by 5 (equiv. 2) = 666
777 <-- shift by 6 (equiv. 0) = 777
888 <-- shift by 7 (equiv. 1) = 888

which means that you'll end up with a block of multiple AES-ECB encryption of the exact same blocks, which will give you interesting patterns in your ciphertext, and leak information, so you do not achieve the ciphertext indistinguishablity one would expect from a secure block cipher.

Which basically means that "No, this is not an acceptable way".

Could you tweak it further to avoid this problem? Most likely, but if you want to build bigger block cipher, you can as well just build a bigger AES and have better performance than stacking multiple AES on top of each other.
Should you? IMHO, no. Stick with secure AES constructs such as CBC, CTR, GCM, etc., or use a secure stream cipher such as ChaCha.