Parameters for elliptic curve prime192v3 I'm looking all over the internet for prime192v3's parameters. I think I may have found them here, but it doesn't say what variable each number matches to. Is there some central place where I can find this information?

You need to look at the constructors and see which values correspond to which parameters.

The ECCurveFp reference is here

Note that $P$ is given in decimal

$P = \texttt{6277101735386680763835789423207666416083908700390324961279}$

$a = \texttt{fffffffffffffffffffffffffffffffefffffffffffffffc}$

$b = \texttt{22123dc2395a05caa7423daeccc94760a7d462256bd56916}$

The X9ECParameters reference is here

Note that $G$ is in compressed form

$G = \texttt{027d29778100c65a1da1783716588dce2b8b4aee8e228f1896}$

$n = \texttt{ffffffffffffffffffffffff7a62d031c83f4294f640ec13}$

$h = \texttt{1}$

$seed = \texttt{c469684435deb378c4b65ca9591e2a5763059a2e}$


Naccache–Stern knapsack cryptosystem: How to calculate $p_i ^{s^{-1}} \mod p$? In the algorithm(link), for calculated n and chosen secret key s, we need to calculate $\sqrt[s]{p_{i}} \bmod p $.

As an example in original research paper (link) , For a given $p=9700247$ and $s=5642069$, It is given that $\sqrt[s]{2} \bmod p = 8567078 , \sqrt[s]{3} \bmod p = 5509479$  and so on.

So how to calculate this $\sqrt[s]{p_{i}} \bmod p $.

In the Naccache-Stern knapsack cryptosystem, it holds that $\gcd(s,p-1) = 1$. Hence, you can compute the inverse of $s$ modulo $p-1$ (the coprimality ensure the existence of such an inverse). Computing this inverse can be done with the extended Euclidean algorithm, which gives you $u,v$ such that $su + (p-1) v = 1$: as $su = 1 \bmod p-1$, $u$ is indeed the inverse of $s$ modulo $p-1$.

As $p$ is a prime, its multiplicative subgroup has order $p-1$, hence $\sqrt[s]{p_i} \bmod p = p_i^{s^{-1} \bmod p-1} \bmod p = p_i^u \bmod p$. So, once you've computed $u$ from the extended Euclidean algorithm, finding the $s$-th root of $p_i$ modulo $p$ is reduced to computing a modular exponentiation.


Counter based cipher using HMAC-SHA-256 After trying to invent my own AES mode, I decided to just implement something that's known to work, namely CTR mode with HMAC-SHA-256.

From what I understand, I can use the IV as a counter, and the IV only has to be unique for each key (generating unique IVs isn't a problem). Correct?

Is it a problem for HMAC-SHA-256 if I construct a SHA block using a 32 byte key, 16 byte counter and 16 zero bytes for padding, or is it better to generate a 64 byte key so it fits in one SHA block and make another block for the counter and pad that block with zero bytes?

If I want to add a salt to anything, I assume the salt is stored unencrypted. Correct?

Edit for clearing up some things:
Using the IV as a counter implies that it changes for each encrypted block. In this case I'll use a simple time stamp directly from the OS that's 12 bytes large (resolution is in ticks, which are 1/50th of a second, software waits one tick before generating an IV, system is slow so not a problem). The remaining four bytes are used as a block counter (simply starts at zero).
The intended HMAC setup is:
The first SHA-256 message is made of the first HMAC key, the IV, padding and the cipher text. The first SHA-256 block will be the first HMAC key (32 bytes), then the 16 byte IV, then 16 bytes of zero padding. The remaining blocks for the message are cipher text blocks, with normal SHA padding after the last cipher text block (normal SHA operation). The resulting hash is the first HMAC hash.
The second SHA-256 message is the second HMAC key (32 bytes) and then the first HMAC hash (32 bytes), with the normal SHA padding at the end. This is the authentication tag.
Second edit:
After searching the web some more, I found that I made some assumptions about the way the HMAC keys are used. I've used some test vectors from NIST to verify that I'm doing things properly, and that's now the case.
Proper HMAC-SHA-256 setup:
Take first 32 byte HMAC key, append 32 zero bytes, XOR IPAD over the resulting 64 byte block, append cipher text, hash.
Take second 32 byte HMAC key, append 32 zero bytes, XOR OPAD over the resulting 64 byte block, append first hash, hash.
I assume you can prepend the nonce to the cipher text so it gets hashed as well. Correct?

From what I understand, I can use the IV as a counter, and the IV only has to be unique for each key (generating unique IVs isn't a problem). Correct?

Not exactly. The IV needs to be unique for each block per key. You can use a message counter for the Nonce component of the IV, then the block counter component is incremented from 0 in CTR.
IV = [96-bit Message NONCE][32-bit Block COUNTER]

Since the Nonce does not to be random or unpredictable, a message counter is appropriate. I use a combination of message counter, time code, and random number, all 32-bits, which helps against accidental nonce reuse if the counter gets maliciously reset. The key needs to be changed before the message counter overflows.
IV = [32-bit RANDOM][32-bit Timecode][32-bit Message CTR][32-bit Block CTR]

There are other methods that can be used. You may not want timecode information to be sent with a message, or have an attacker know how many messages you have sent. You can even encrypt the nonce with another key before using it in CTR mode, but you will need a custom setup for that because it can be done VERY wrong and break security.

Is it a problem for HMAC SHA256 if I construct a SHA block using a 32 byte key, 16 byte counter and 16 zero bytes for padding, or is it better to generate a 64 byte key so it fits in one SHA block and make another block for the counter and pad that block with zero bytes?

That will change how HMAC operates, which is to only have the key as the key input. HMAC per spec will only hash the key input if it is larger than the blocksize, so you can input 512-bits of "key" data, although it is not necessary to include a counter as part of the input. Appending the nonce to the key should not have any negative effect on security, it may even strengthen it, but I will not say that with any certainty. It is probably better to prepend the nonce to the message input if you want it to be authenticated, rather than adding it to the key. Including the counter with the key also eliminates a specific kind of performance optimization you can use.
You may want to consider SHA-512/256 or SHA-3-256 instead. If you have 64-bit code and CPU available it is faster, and should be more secure against current and unknown attacks. MAC using SHA3 is different, it prepends the message with the key.

If I want to add a salt to anything, I assume the salt is stored unencrypted. Correct?

A salt is a non-secret piece of cryptographic information, so it does not need to be encrypted. You may want to add some kind of redundancy check or rebuild parity (such as Reed-Solomon) to be associated with it, if you feel there is a chance it can be altered accidentally. Keep a backup somewhere, a password without the salt will mean a lost key.
Finally, make sure you are using different keys for your cipher and your MAC. The reason is that an attack on one of them can break both. While that may be unlikely, it is still a good idea to use separate keys, and is FIPS compliant.


Hash function property Let $H$ be a hash function that is both hiding and puzzle friendly. Consider $G(z) = H(z) \Vert z_l$ where $z_l$ is the last bit of $z$. Show that $G$ is puzzle frielndly but not hiding.

This question is from this book, page 50). I'm stuck at proving $G$ as non-hiding.

  A hash function is hiding if: when a secret value $r$ is chosen from a
  probability distribution that has a high min-entropy, then given
  $H(r \Vert x)$ it is infeasible to find $x$.

Now for given function $G$, we have:

$G(r \Vert z) = H(r \Vert z) \Vert z_l$

I don't see how $G$ fails to be hiding. If we are given $G$'s output, we just know about one fixed bit of the input. $H(r \Vert z)$ (the part of the output excluding the last bit) still makes it infeasible to determine $z$ since $H$ is hiding. How can one bit of input prevent $G$ from hiding?

What if the input $x$ is only one bit? Would not $G$ leak all of $x$?

In otherwords, the hiding property should work for all plaintext spaces, even if your plaintext space is $\{0,1\}$. $G$ is not hiding for that plaintext space.


Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a? For any SHA-family of algorithms (including Keccak) except for SHA1, would it be theoretically possible for there to exist a pre-image a whose hash digest b is the pre-image to the hash digest c which is the pre-image to a thus completing a circle (i.e. circular hash or collision of pre-image a with the digest a)?

${{hash(A)\to B}}$, ${{hash(B)\to C}}$ , ${{hash(C)\to A}}$

Given the use of XOR and bit-rotations, as well as padding and pre-processing and the many steps involved in hash functions such as SHA256 or SHA512, would it be possible for the above circular hash scenario to exist? (despite the unlikelihood of it being found)

P.S. candidate values include an all-zero string for pre-image or digest, or any valid-length output (i.e. 256, 512).

We like to think of hash functions as random functions, and there is no reason a random function shouldn't have a cycle of size 3 which is what you describe.
Obviously it would be very difficult to find such a cycle, we can discuss how likely is it a random function over space size $n$ has a cycle of size 3.

Ignoring cycles of size 1 and 2 which acount for a small portion of the space we have $n/3$ independent size 3 prefixes. each of these has probability $1/n$ to close a size 3 cycle. the chance they all miss is $(1-1/n)^{(n/3)}$ which is $(1/e)^{(1/3)}$ or 0.71653131057.
so the chance of at least 1 such cycle is 28% which is consistent with simulation results in comments above by poncho.


Secret Sharing Encryption Suppose Alice shares a secret block cipher key, $K_{AB}$ with Bob, and a different secret block cipher key, $K_{AC}$ with Charlie. Describe a method for Alice to encrypt an m block message such that it can only be decrypted with the cooperation of both Bob and Charlie. The ciphertext should only be a constant size greater than m blocks. You may assume that Bob and Charlie have a pre-established secret channel on which to communicate.

The answer given is:

Alice can first pick a random key $K$ to encrypt the message $M$, and then she encrypts the key $K$ with both $K_{AB}$ and $K_{AC}$. In other words, Alice does the following:

$$E_{K_{AB}} [E_{K_{AC}}(K)]  || E_K(M)$$

May I know if in this case, that Bob wants to decrypt  $E_{K_{AC}}(K)$, can he complete this solely without the help from Alice? Thanks for the answer.

Since Bob already knows $K_{AB}$ he can run $D_{K_{AB}}(E_{K_{AB}}(E_{K_{AC}}(K)))$. Which will leave him with $E_{K_{AC}}(K)$. And to decrypt that any further (in order to get $K$) he would need either Alice or Charlie's help.


Logjam on Elliptic Curves? I think we're all aware of the Logjam attack.

From now on we know that re-using primes for DH is a bad idea.

But we also say that elliptic curves are safe from the attack (relying on the NFS), because it cannot be applied. I understand this.

Now in my mind this question arose:

Assuming we had enough computational power (maybe using ASICs) is there a similar pre-computation attack on ECDH?

And if it is possible, how high would the gains be?Could one reduce the workload per connection to a modest value ($\approx 2^{20}$), while still not needing to maintain a gigantic table ($>2^{60}$ storage)?It would already suffice if such an attack would work on secp256....

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a collision.

When we find two distinct pairs $(a_1, b_1)$, $(a_2, b_2)$ that evaluate to the same value $x_1 = x_2$, we recover the logarithm by finding $Q = dP = \frac{a_2 - a_1}{b_1 - b_2}P$, which follows from $a_1P + b_1Q$ $=$ $a_2P + b_2Q$. We expect this to happen after $\sqrt{\pi n / 2}$ elliptic curve group operations.

Since by the time we get to the second discrete log we already know the first one, we can reuse the distinguished points found during that log computation. This slightly increases the chances of finding a collision. Suppose we have a hit $a_1P + b_1Q_1$ $=$ $a_2P + b_2Q_2$, where $Q_1$ was the first discrete logarithm target, and $Q_2$ is the current one. Rewrite this as $(a_1 + b_1d_1)P$ $=$ $a_2P + b_2Q_2$, where $d_1$ is the first discrete logarithm. Now we have $d_2 = \frac{a_1 - a_2 + b_1d_1}{b_2}$.

This accelerates the second logarithm by a factor of $2$, the third one by a factor of $8/3$, and the $i$th one by a factor $\approx \sqrt{i}$ compared to if they were solved independently. So as you see, the benefits of precomputation exist, but are much more limited than in the number field sieve case.


Is ”generating transcripts that are indistinguishable from actual messages in a signature scheme” not universal forgery? In the Pointcheval paper “Security arguments for digital signatures and blind signatures”, they have proved the security of Schnorr signature for existential forgery under adaptively chosen-message attack.

The proof requires a simulator that can produce transcripts that are indistinguishable from the actual messages generated by the signer, without knowing the secret key.

I apologize if my understanding is wrong. Can someone shed some light on what they mean by simulating the transcripts without knowing the secret key?

Because – if that is possible – would it not become universal forgery?

Here and in many other signature schemes, $f$ is modeled as a "random oracle."  This means that on each distinct input, $f$ outputs a uniformly random value in $\mathbb{Z}_q$ that is independent of all other outputs.  (When queried on the same input multiple times, it always returns the same answer.)

The trick here is that the simulator has the power to "program" the output $f(m,r)$ to be the value of $e$ that the simulator chose.  In the "real" world, an attacker cannot control the outputs of $f$ like the simulator can.

Many more details can be found in the classic Bellare and Rogaway paper "Random oracles are practical."


Signing a message using SPHINCS Hash-based Signature scheme I have questions on “SPHINCS: practical stateless has-based signature” by Bernstein et al. And I really hope that someone can help me with it.
To help me understand it, I read the https://cryptoservices.github.io/quantum/2015/12/08/XMSS-and-SPHINCS.html blog.

SPHINCS is really composed of WOTS+, XMSS, and HORST building blocks. I understand each one of these alone, but I am still having a problem figuring out how to sign a message in SPHNICS. I understand the hyper-tree structure of layers of L-Trees (WOTS+ trees) where the final layer is the HORST tree. Here are my questions:

Q1. If I have to sign a message, M, do I randomly pick any of the HORST trees and sign my message? The signature is going to be pretty huge to reach all the way up to the PK. i.e. the signature must contain the authentication path of all roots to reach the PK. Is this correct?

Q2. According to the example parameters mentioned in https://cryptoservices.github.io/quantum/2015/12/08/XMSS-and-SPHINCS.html of h=3 and d=3 which yields three layers of height 1 each. In layer 2, each node in the two WOTS+ trees can sign k roots of layer 1 WOTS+ trees? So when I reach layer 0, the total number of messages I can sign is (2*k)^3. Is this correct?

Thank you very much for your help

If I have to sign a message, M, do I randomly pick any of the HORST trees and sign my message?

With the original Sphincs, yeah, that's what you do.

(As an aside, the designers of Sphincs+ (and IIRC, Gravity-Sphincs) realized that this was a nonoptimal design; it allowed a forgery to select the HORST tree that gave him the best probability of success; that is, the one that was used the most).  Hence, what they did in Sphincs+ to do specify a mapping from the randomized message to both a FORS (used in replacement of HORST in Sphincs+) few-time-signature AND the combination of FORS leafs; that way, the attacker doesn't get such an advantage).

  The signature is going to be pretty huge to reach all the way up to the PK

Well, yes, yes it is.

  According to the example parameters mentioned of h=3 and d=3 which yields three layers of height 1 each. In layer 2, each node in the two WOTS+ trees can sign k roots of layer 1 WOTS+ trees? So when I reach layer 0, the total number of messages I can sign is (2*k)^3. Is this correct?

Well, no; in the notation they use in Sphincs, h is the total number of XMSS levels in the combined hypertree, and d is the number of levels of XMSS trees (that is, the number of one-time signatures).  With h=d=3, then each XMSS tree is of height h/d = 1; that is, each XMSS tree has two leaf nodes (and so can sign two messages).  In addition, if h=3, then there is a total of $2^h = 8$ HORST trees (as h is the total hypertree height); of course, each HORST tree can sign several messages (and the security of the HORST tree degrades as it signs more messages)


Send content to owner of gpg public key, nested content symmetric encryption If I want to encrypt a text content file using a symmetric algorithm like AES,
is there a standard format gpg will expect, where it can detect a symmetric key (encrypted with recipient gpg public key RSA) in my output?  E.g. should the encrypted key be a fixed length field at the beginning of my output?

I am not able to use a suite gpg tools or command line.  I am restricted to manually using a subset of cryptography APIs supported in a legacy system.

From reading up at e.g.
 https://futureboy.us/pgp.html#Symmetric,
 https://www.gnupg.org/gph/en/manual/x110.html,
 https://tools.ietf.org/html/rfc4880
I see that this approach seems to be in use.

But I am struggling to find any reference that would help me manually construct an appropriately structured "package".

If you encrypt a text file with the GPG utility, it randomly chooses a symmetric key, encrypts the file using that key, then encrypts the symmetric key using an asymmetric algorithm, and embeds the encrypted symmetric key in the file. There is a format that GPG uses and expects, but it is not easy to work with.

There is an RFC that describes the OpenPGP file format. It's not fun reading, but with a lot of hex dumps and a lot of time with the GPG source, I did figure out the basics of a GPG-encrypted file.

I did take the openssh project and carve out the sftp piece to build a package that encrypts the files when it puts them on the remote server and decrypts them when it reads from the remote server. The format of the files is GPG-compatible, without using the GPG utility. You might find some useful code in there for generating GPG-readable files, mostly in the iron subdirectory. IronCoreLabs/ironssh GitHub project


Alternative sources of random numbers Considering that algorithmic methods for generating unpredictable streams are hard to come by, I've wondered if any of these potential sources are good for making keys, seeds, and the like:

stocks, bonds, and other economic indicators.
weather patterns, temperatures, humidity, stream video of the sky, and other environmental variables.
photos taken by anyone at all.
noise in a room.
traffic patterns.
seismic activity.

Are any of these methods used?

Potentially almost any data input can be used as seed. But in general you don't want to use information that can be trusted to have high entropy and be secret all the time. This rules out stock exchange and the weather for instance, as the stock exchange may be down, and there is not much entropy in a clear blue skye.

Almost all of the sources you mention rely on outside phenomenons, which means you have to trust the source. Moreover, you'll need a trusted path to your source, and the trusted path likely requires a random number generator. So you would get into a chicken/egg situation.

What is usually done is to rely on a local phenomenon and then use highly unpredictive measurements. Local phenomenons can be kept secret and measuring in the extreme will mean that you aren't dependent on large fluctuations. For instance a HDD can be used to inform the system about I/O times, and measuring in nano-seconds will give enough entropy for a few bits of seed.

Of course, you neverk know what kind of system you are going to find. So fortunately it starts to be commonplace to include a random number generator in CPU's. An RNG in the CPU or - for instance - in a TPM is probably the best RNG you can find.


Are there any long term RC4 bias based exploits? The RC4 cipher possibly exhibits low level bias in it's long run PRNG keystream.  I'm specifically excluding short term bias attacks which I'm defining as outputs < 1024 bytes.  Are there any real world attacks that exploit this feature?

I'm happy to have a crack at this one, providing I've understood your question correctly.

Firstly I wouldn't say the cipher possibly exhibits low level bias at any point. It experiences plenty of bias and I'll attempt to explain how we can use it to launch practical attacks. As I'd imagine you know, the strongest bias is found right at the start of the KSA, in fact there are numerous biases in the KSA, but the KSA only represents the first 256 bytes, assuming we don't drop any.

The problem is, there's plenty of evidence (not just speculation) of the biases extending to any point in the key stream (asin the PRNG or PRGA part). See this again.

Your question asked for real world attacks?
Well contrary to some prior belief that because BEAST did not effect RC4 TLS, that RC4 was suitable for TLS, I'd recommend reading this as suggestion otherwise or alternatively this.

The Bar Mitzvah Crypto attack, discovered and demonstrated by Itsik Mantin in 2015, should be the best proof that the IETF were onto something when they introduced the idea to ban RC4 altogether in TLS the year before.

I know you were probably looking for something more in an answer but considering the question, this is about all there is to be said. How practical you think The Bar Mitzvah Crypto attack is, may be a question for debate.... but if we accept that NSA gathering of information, constantly with the same patterns in it (do I really need citations for this?), then it absolutely is the case that long key streams show significant enough bias and having enough of them allows data recovery and even in the circumstances of especially weak keys, key recovery all together.

If we have a heavily biased round (the KSA) and a knowingly biased round (the PRGA) plus a handful of real world exploits, we can assume the attacks will only keep getting worse, but yeah: it's already practical to use bias to attack RC4, even in RC4-drop-768.

EDIT

It's probably worth reading this too Mathy Vanhoef and Frank Piessens, go into huge detail on biases


How to encrypt a 192 bit plaintext using AES-192? Can we use AES-192 bit algorithm for 192 bit plaintext? If yes, what are the changes we have to do?

Strange as it may sound, you should not directly use any block cipher directly as a means to provide confidentiality. A block cipher can only handle a statically sized plaintext, which in the case of AES is always 128 bits; it's not 192 bits, that's just the key size.

More importantly a block cipher will always output the same ciphertext if the key and input block remain the same. That means that if you input two 128 bit messages, for instance the ASCII representation of "affirmative, sir", then the ciphertext will be identical. If this message is the answer of two separate questions then an adversary can immediately detect that the answer of two questions is identical as well. This breaks the security of a cipher as it leaks information about the plaintext.

In the strongest semantic security that a cipher can obtain, IND_CPA, the ciphertext output should not leak any information even if the adversary may input as many input messages as he likes.

The simplest mode of operation is ECB mode; it just splits the plaintext into multiple blocks, and then encrypts each block in turn, possibly padding the last block so that the input to the block cipher always receives 128 bits. This solves the first part of the cipher only handling 128 bits, but it does nothing for the security mentioned in the previous sections.

Fortunately there are many modes of operation that do provide such security. AES-CBC is used a lot, but it requires padding - which in itself can be a security risk - as well as a unpredictable IV. This IV or initialization vector is used to change the ciphertext independently of the plaintext. AES-CTR (AES in counter mode) is also used a lot and doesn't require the padding and only a unique nonce (number-used-once) instead of the unpredictable IV.

Currently authenticating ciphers such as GCM are becoming more commonplace as they do not just protect the confidentiality but also the authenticity and integrity of the message. They are generally build using AES-CTR internally.

Note that the size of the plaintext is not automatically protected by AES using any of the modes of operation. This is one of many side channels that may leak information to the attacker. You cannot just encrypt "Yes" to 3 bytes ciphertext and expect that an adversary cannot distinguish it from the 2 bytes required for "No".

When you read about AES-192 is being used to protect your data then you should ask yourself how it is used to do this. To a seasoned cryptographer the use of AES, as the most common unbroken block cipher, only means that a small part of a system is possibly secure.

If you want to encrypt fully random data (such as an AES key) then you could right-pad your data using 64 bits set to zero. Then you could use ECB mode encryption (encrypt two blocks of 64 bits) and encrypt the two blocks of 128 bits. This process is called key wrapping. This is only secure for completely random data though and it is probably better to use more modern techniques such as AES in SIV mode.


One-time pad and zero key I'm doing some exercises before my exam, and I am stuck with task number 4 in this file: http://www.cs.umd.edu/~jkatz/crypto/f10/hw1.pdf

Could you help me with this task?

  When using the one-time pad encryption scheme, it can occur that $k=0^l$ and then the ciphertext is equal to the plaintext! It has been suggested to improve the one-time pad by only choosing non-zero keys. What do you think of this improvement? In particular, is it still perfectly secret? If yes, prove it. If no, reconcile this with the fact that encryption with the all-0 key completely reveals the plaintext.

In few words:

OTP has perfect secrecy;
For a cipher to have perfect secrecy, it is required that $|K| \ge|M|$.

Let $K=M=C=\{0,1\}^n$ be the set of keys, messages and ciphertexts. If you apply the "improvement", ie, if you remove $0^n$ from the keyspace, then you've created a cipher that cannot show perfect secrecy (because now $|K| = |M| - 1 < |M|$).

Therefore, the "improvement" completely breaks perfect secrecy, which makes this modified OTP worse than the original.

In many more words, with illustrating examples.

As you should know, the one-time pad has the perfect secrecy property, which is defined as follows: let $M,C,K$ be the sets of messages, ciphertexts and keys; $\forall k \in K, \forall c \in C, \forall m \in M: P[E(k,m)=c] = P[k \,\,xor\,\,m = c] = \alpha$, for some (tiny) positive real number $\alpha$.

In words, you have absolutely no information about the original message if you're given only the ciphertext. Suppose the cipher text reads:

The password of my bank account is my wife's birthday

What's the most probable original message?

The password of my bank account is my wife's birthday
The password of my bank account is my aunt's birthday
The password of my bank account is: b4nk-P4ssw0rd1234
Love of my life you've hurt me You've broken my heart

See? The "improvement" can't possibly improve this cipher. Actually, it makes it worse: by reading the ciphertext, the attacker can be sure that your password is anything but your wife's birthday -- he could get some information from the ciphertext!!!


AES-CTR with ephemeral keys vs IV Let's say that we have a key exchange of some sort, which leaves A and B sharing the long-term secret $S$. Then, A and B want to use AES-CTR for the communication, which leaves us with several possible strategies:

During the key exchange, A and B both generate and send nonces $N_a$ and $N_b$ which are mixed in the key derivation function with $S$ to produce a unique key for the exchange. We leave the IV = 0.
During the key exchange, A and B both generate and send nonces $N_a$ and $N_b$ which are mixed to produce and IV. The key is derived from S.
During the key exchange, A and B both generate and send $N_a$, $N'_a$, $N_b$, $N'_b$. $N_a$ and $N_b$ are mixed with $S$ to produce the key. $N'_a$ and $N'_b$ are mixed to produce the IV.

In other words: random key/fixed IV, fixed key/random IV or random key/random IV.

Which one is preferable? (Assume HMAC-SHA256 or similar for mixing keys/IV)

First, there is a non-security argument in favor of option 2.: if you can cache the AES key across key exchanges, you can save time in key setup. Whether that's relevant I'll leave for you to decide.

CTR fails when the same key-input pair is used twice. Let's first assume the nonces $N_a$ and $N_b$ are always unique, and that key derivation and mixing is strong.

Birthday bound for a key collision is $2^{64}$ for AES-128, $2^{128}$ for AES-256 etc.
If generating a 96-bit nonce, to use with a 32-bit counter, the birthday bound is $2^{48}$. With a 128-bit nonce and messages shorter than $2^{32}$ you can get a higher value, but unless you only have one block messages it's less than $2^{64}$.
With a 96-bit AES nonce the birthday bound is $2^{112}$ for AES-128 or $2^{176}$ for AES-256. Again, you can get a bit better bounds with a larger nonce and shorter messages, approaching $2^{128}$ and $2^{192}$.

Clearly the last is "best", but even with just a random 96-bit nonce you could have billions of key exchanges with a very small chance of even one collision. That one is a bit borderline, but any of the other options I would consider good enough.

Note the assumption made, that nonces are unique. If the nonces themselves collide, any data derived from them will also collide. For random nonces you'd want them to be at least as long as the total data derived from them. In addition, the exchange of nonces should be designed such that an attacker cannot affect it and cause a collision.

As an aside, option 3. doesn't necessarily require two sets of nonces. You can derive both a 128-bit key and a nonce with a single HMAC-SHA-256, or you can derive more material with two differently salted HMACs. Doing so will make the nonces depend on $S$, but that doesn't seem like a problem.


Fast PKI for embedded device We are creating a device with a small microcontroller (20 MHz CPU 16 KiB RAM).

We need some way to securely send signed files to device (only signature, no encryption necessary). An external company has come up with an elliptic curve solution but it needs about a minute to verify a signature, without counting the file hash time.

Could you suggest some other moderately secure algorithms that can run faster in such small CPU? (a few seconds would be OK, hundreds of milliseconds would be fantastic)

Given that the bottleneck on the embedded device is local non-interactive public-key signature verification, the best industry standard for that is RSA (with a standard signature padding, such as PKCS#1 RSASSA-PSS, PKCS#1 RSASSA-PKCS1-v1_5), which is usually significantly faster than ECDSA for signature verification including for the common $e=65537$; and for good implementations always faster when using $e=3$, which allows a speedup by a factor of about $8$. Rabin signature verification is nearly twice faster than RSA with $e=3$, and is also standard if not common, e.g. was in ANSI X9.31:1988 and is in ISO/IEC 9796-2:2010.

Note: the absolutely fastest seems to be Daniel J. Bernstein's A secure public-key signature system with extremely fast verification (2000); this is essentially Rabin with an expanded signature allowing extremely fast verification, using an idea he first outlined there.

Both RSA and Rabin are based on modular arithmetic modulo $N$ of secret factorization. The time for signature verification is dominated by $17$ (RSA, $e=65537$), $2$ (RSA, $e=3$), or just $1$ (Rabin, $e=2$) multiplication(s) modulo $N$, where $N$ has $n$ bits. $n=2048$ is acceptably secure till 2030 according to NIST and French ANSSI.

When appropriately implemented using standard (quadratic) algorithms working on $w$-bit words, the computation time for one multiplication modulo $N$ is dominated by $\approx(n/w)^2$ executions of an elementary operation consisting of

two multiplications of two $w$-bit word giving a $2w$-bit result
addition with carry of the corresponding two results into temporary values
three reads of a $w$-bit word
one write of a $w$-bit word
on register-starved CPUs only, some read-writes for temporaries

Notoriously, careful optimization of the core loop is essential (assembly language shines!); and using the wrong algorithm will impact speed (in particular: separating modular multiplication from modular reduction increases the memory accesses; Montgomery arithmetic at best does not help).

Actual execution time can be in seconds on a mere 8-bit CPU (for 2048-bit RSA, $e=3$, an implementation I wrote verifies a signature in $1.25$s on a 8051 core with 5M cycle/s and 4-cycle multiplication of bytes giving 16-bit result, and no hardware 16-bit addition).

Execution time decreases about quadratically with the word size, allowing time in milliseconds for a modern 32-bit CPU (the question does not specify which core is used; ARM CPUs tend to be good at this, especially those with UMLAL and UMAAL).

Per eBACS benchmarks, on an ARM Cortex-A8, RSA-2048 ($e=3$) is timed at a median of 555418 cycles (28ms scaled to 20MHz), versus 2594303 cycles for one of the fastest elliptic-curve signature system, ed25519.


Is there a way one can combine two correlated hash outputs to maximize the collision resistance? While practically diving into collision resistance, I am trying to first write a non-cryptographic hash (to learn from it) which is limited to arithmetic operations on 32-bit integers only. It produces two 32-bit results similar to MurmurHash2_x86_64 (aka MurmurHash64B), but each have differing initial states and are mixed together more thoroughly (MurmurHash2_x86_64 only mixes at the end). Essentially I aim to produce a fast, well-distributed and collision-resistant 64-bit hash using two 32-bit states.

Trying to learn some things by looking at MurmurHash2_x86_64, I noticed that at first glance, it produces a 64-bit digest. But the author had this to say on the SMHasher wiki:

  MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes them at the end, which is fast but means that collision resistance is only as good as a 32-bit hash. I suggest avoiding this variant.

Then I saw this exchange on the subject:

  Hacker News comment by martincmartin:
  Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.

  Hacker News comment (reply) by finnw
  Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.

This made me naively test MurmurHash2_x86_64 to find collisions in one 32-bit result, and I found that the second result had no collision. This confused me, because that seemed to be the very definition of collision resistance greater than what a 32-bit hash can provide… and it contradicted what Appleby said about his function.

This makes me ask:

How can two 32-bit results of a hash function correlate, or otherwise increase probability of collisions? Can the outputs from multiple functions correlate at all? And if, how could this weaken the collision resistance of their combination?
What can be done to avoid this situation, and to achieve the collision resistance of a 64-bit hash (or more) using multiple 32-bit results? Is there a way one can combine two correlated hash outputs to maximize the collision resistance?

Collision resistance is a property of a family of hash functions $H_k$ for a key $k$, measured by the probability that a random algorithm can achieve at finding a collision given a random key $k$.  Specifically, it is measured by $$\Pr[x \ne y, H_k(x) = H_k(y)]$$ where $k$ is a uniform random key, and $(x, y) = A(k)$ are chosen by a random collision-finding algorithm $A$.  There are generic algorithms $A$, such as Pollard's $\rho$, achieving probability near 1 with modest memory cost requiring $2^{n/2}$ evaluations of the function, where $n$ is the number of bits in the hashes, and there are various area-time tradeoffs available.  If this probability is negligible for any algorithm $A$ limited to area*time cost below $O(2^{n/2})$, then we call $H_k$ collision-resistant.

Concerning MurmurHash:

First, 64 bits is too small for any useful notion of collision resistance, because it generically takes only about four billion evaluations of a hash function to find a collision, and that cost is affordable on your laptop today—as in, before the end of the day.
Second, MurmurHash2 and MurmurHash3 aren't even collision-resistant in the formal sense, because there are better-than-generic algorithms for computing collisions under any prescribed key.  Actually, it's worse than that: there are pairs of messages that collide under every key in MurmurHash.  For example, 390b2e1717dfba58 and b9e9ba6497bd47a6 collide under every key in MurmurHash2.  The same applies to MurmurHash3 (and CityHash64), and can be extended into $m$-way multicollisions for any $m$ you want.  You can create more of them nearly instantaneously in the privacy of your own living room.

To address the letter of your questions, simply concatenating hash values derived by any iterated hash functions (which is how ~all hash functions are made to work on arbitrary-length inputs, MurmurHash included) fails to achieve collision resistance much better than the individual hash functions alone.  Concatenating $H_k$ and $H_{k'}$ with independent keys $k$ and $k'$ doesn't necessarily give worse than 32-bit collision resistance (which would mean a cost of less than a few tens of thousands of evaluations of the function to find a collision), but it doesn't give much better collision resistance either—it certainly won't even reach 64-bit collision resistance.

But since you're asking about 64-bit non-cryptographic hash functions, I can't imagine you actually want collision resistance.  Here are a couple of alternatives that you might actually want:

You might want a universal hash family, or a $\varepsilon$-almost universal hash family.  This means that for any fixed messages $x$ and $y$, and for uniform random $k$, the collision probability is bounded: $$\Pr[H_k(x) = H_k(y)] \leq \varepsilon,$$ a property which we can often prove of specific constructions.  Note that this implies nothing about the difficulty of finding collisions if you know the key: it is only a bound on the probability of collisions under uniform random unknown key.

This prevents an adversary from furnishing you a data set that will, when you load it into a hash table, have many collisions with nonnegligible probability.  On the other hand, it doesn't prevent an adaptive adversary from measuring timing of hash table operations to learn about the key $k$ and then furnishing in more collisions.  For that you will need a PRF—see below.

You can get smaller collision probabilities by concatenating independent universal hash functions.  Pick keys $k_0$ and $k_1$ independently; if $H_k$ was an $\varepsilon$-universal hash family, then $x \mapsto H_{k_0}(x) \mathbin\| H_{k_1}(x)$ is an $\varepsilon^2$-universal hash family.  Proof: A collision $x \ne y$ means $H_{k_0}(x) = H_{k_0}(y)$ and $H_{k_1}(x) = H_{k_1}(y)$, which, since $H_{k_0}$ and $H_{k_1}$ are independent, has probability
\begin{align*}
    \Pr&[H_{k_0}(x) = H_{k_0}(y), H_{k_1}(x) = H_{k_1}] \\
      &= \Pr[H_{k_0}(x) = H_{k_0}(y)]\cdot\Pr[H_{k_1}(x) = H_{k_1}(y)] \\
      &\leq \varepsilon^2.
  \end{align*}

A variation on this theme is relevant in cryptography for message authentication codes: an $\varepsilon$-almost xor-universal hash family, where $$\Pr[H_k(x) \oplus H_k(y) = \delta] \leq \varepsilon$$ for any $x$, $y$, and $\delta$, and random $k$, makes a good one-time secret-key authenticator.  For example, Poly1305 and GHASH are $\varepsilon$-almost xor-universal hash families with $\varepsilon \lll \lceil\ell/128\rceil/2^{100}$ where $\ell$ is the message length.  AES-GCM uses GHASH in Carger–Wegman's construction to authenticate many messages; NaCl crypto_secretbox_xsalsa20poly1305 uses Poly1305 in a different construction to authenticate many messages.

There are other variations on the theme, like $\varepsilon$-almost pairwise independent hash families, where $$\Pr[H_k(x) = u, H_k(y) = v] \leq \varepsilon^2$$ for any fixed messages $x$ and $y$, any fixed hash values $u$ and $v$, and uniform random $k$.  Zobrist hashes are a popular choice of pairwise independent hash families outside cryptography.
You might want a pseudorandom function family, or PRF.  This means that no cost-limited adversary given oracle access to a uniformly randomly chosen member $H_k$ of the family can distinguish from a uniform random function with the same domain and codomain: $$|\Pr[A(H_k) = 1] - \Pr[A(U) = 1]|$$ is bounded by a small constant, for any cost-limited random distinguishing algorithm $A$, where $U$ is a uniform random function.

Note that the adversary isn't given $k$ here—they are only given $H_k$.  Obviously, they could try to guess $k$ and use the oracle to confirm their guess, but this succeeds with negligible probability as long as the family, i.e. the number of distinct keys, is reasonably large, say at least $2^{128}$.

This implies that even if the adversary knows $H_k(x_1)$, $H_k(x_2)$, $\ldots$, $H_k(x_{m-1})$, that doesn't help them to guess $H_k(x_m)$ for a distinct message $x_m$.  That means that even timing information about hash table operations—revealing when collisions happened—won't let them guess what other keys will also collide.  It also means that a PRF makes a good message authentication code.

Concatenating independent PRFs, $x \mapsto H_{k_0}(x) \mathbin\| H_{k_1}(x)$, does not confer better PRF-security than any one of them alone.  Why?  An adversary need only guess one of the independent keys to win the PRF game and distinguish it from a uniform random function, so the generic security attainable by this construction is at most half the generic security attainable by a PRF with a double-size key.  That doesn't mean concatenating independent PRFs damages security—just that it never provides higher security than one of them alone.

We don't know a way to prove that a hash family is a PRF, but typical examples that we conjecture are PRFs are HMAC-SHA256, keyed BLAKE2, and KMAC.  For short messages and short, ≤64-bit outputs, SipHash is another popular example, particularly intended to replace MurmurHash where it failed to provide security.

P.S. The comments you quoted on the orange site are, unsurprisingly, meaningless nonsense, compounded by the fact that they are responding to a meandering answer to a confused question on another stackexchange, none of which questions, answers, or responses are grounded by, say, articulation of actual goals in a system.


Is XTS-AES a NIST-approved nonce-misuse-resistant AES mode? If I use XTS-AES and treat the tweak as a nonce/IV would the result be considered nonce-misuse-resistant?

I'm thinking of something like the following AEAD-like scheme:

enc(encKey, macKey, plaintext, aad):
  tweak = ... # 128 bits, generated like an IV or nonce

  # pad the plaintext to handle shorter-than-16-byte inputs
  # as well as determine the plaintext length after decryption
  a = AES-XTS(encKey, tweak, pad(plaintext))
  b = tweak || a
  return b || MAC([aad, b], macKey)

A tweak collision seems to only disclose whether the same plaintext was encrypted with the same key and the same tweak, which matches the definition of nonce-misuse-resistance I see here and differs from Rogaway's description of AES-SIV's properties in that the collision is apparent even if the AAD differs.

My motivation is looking for a nonce-misuse-resistant scheme that is NIST-approved. Having many existing implementations is also a benefit.

A tweak collision seems to only disclose whether the same plaintext was encrypted with the same key and the same tweak

Actually, XTS will disclose whether related plaintexts were encrypted with the same key/tweak.  Specifically, if two plaintexts had the same value for block N, then after encryption (assuming the same key/tweak), the ciphertexts would also have the same value for block N (and thus leaking the relationship between the plaintexts).  This is true even if other blocks of the plaintext differ.  This is leaking data beyond what is allowed for 'nonce-misuse-resistance'


A question about fully homomorphic encryption (FHE) Hypothesis: We define the messages on a field $\mathtt{F}_p$, where $p$ is a large prime number.

I am considering a dynamic outsourced private data scenario.

Assume we have 3 messages: $m_1=2, m_2=4$ and $m_3=77$.
We encrypt them using FHE, so we would have:  $E(m_1), E(m_2)$ and $E(m_3)$.

We send the three ciphertexts to a semi-honest server.

Later on, we want to remove $E(m_1)$  from the outsourced data (in fact we want to remove $m_1$ from there).

Question 1: If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it?

Question 2: Is there any other way to remove $m_1$ from the outsourced dataset without leaking any information to the server?

Please note that we are using semantically secure encryption (e.i. FHE); therefore, the ciphertexts of the $m_1$ are different.

If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it?

Nope; FHE allows a server that knows $E(m_1)$ and $E(m_2)$ to produce a ciphertext which is a representation of the value $E(m_1 \odot m_2)$ (for pretty much arbitrary functions $\odot$); what it doesn't allow a server to do is determine whether $m_1 = m_2$.  If it could, then it could decrypt (by guessing various values $m_2$, producing $E(m_2)$, and then checking if that was the same.

  Is there any other way to remove $m_1$ from the outsourced dataset without leaking any information to the server?

One thing that occurs to me is to produce $E(m_1)$, and have the server replace all values $E(m_i)$ it knows with $E(m_i \odot m_1)$, with $a \odot b = a \cdot (a-b)^{p-1}$ (and, of course, erase all the original $E(m_i)$ values.  In case you don't get the punchline, with this $\odot$, we have $a \odot b = a$ if $a \ne b$, and $a \odot a = 0$; hence any copies of $E(m_1)$ are replaced with an encryption of a fixed constant, while the copies of any other value are unaffected.


Is OAEP needed when encrypting a session (random) key using RSA? My question is two parts:

when encrypting a session key which is used to encrypt bulk data using a block cipher for example, is padding with OAEP really needed [i'm assuming the key is generated using secure random generator.
What benefits does OAEP provide compared to simple padding with random bits up to size $n-1$ where $n$ is the size of RSA.

The answers in
How does OAEP improve the security of RSA?
are very useful but I'm still wondering about the above questions.

when encrypting a session key which is used to encrypt bulk data using a block cipher for example, is padding with OAEP really needed ?

No if the session key is nearly as wide as the RSA modulus, or is padded with random bits up to that size (save for one bit or few high order bits). Absent other issues, we are safe if the actual session key keeps bits from the result of RSA decryption among those that have been chosen randomly, or is obtained by another key derivation step. That's the principle in RSA-KEM.

But yes, RSAES-OAEP is useful if the session key is directly the payload, and is much smaller than the RSA modulus (which is typical for a session key). OAEP gives a security reduction to the RSA problem under the random oracle model, when direct encryption of a short key with textbook RSA (as $C=K^e\bmod N$ ) is known to be insecure in at least the following two cases.

If the public exponent $e$ is small (less than about $\displaystyle\frac{\log N}{\log K}$ bits), then decryption reduces to computing the non-modular $e^\text{th}$ root of $C$, yielding $K$. This question asks for a bound for $\log K$ allowing attack, which it is slightly larger than $\displaystyle\frac{\log N}e$.
If the key $K$ is significantly less that twice as wide as the desired security level, then there's a meet-in-the-middle attack working for the sizable fraction of $K$ that (partially) factor as $K=K_1\cdot K_2$ with $K_1<K_2$ and $K_2$ small enough to be enumerated, requiring $O(K_2)$ time and $O(K_1)$ memory.
That would be a plausible attack for 128-bit $K$ and 4096-bit RSA with $e=2^{16}+1$.

  What benefits does OAEP provide compared to simple padding with random bits up to size $n-1$ where $n$ is the size of (the) RSA (public modulus) ?

None that I see beyond

availability of some secure implementations,
recognition (including explicit by some security recommendation),
detection of accidental cryptogram corruption or using unmatched public/private keys.

Beware that implementation of decryption using "simple padding with random bits" is far from foolproof; nothing manipulating secret or private key is. In particular, testing the high-order constant bit(s) leads to disaster by padding oracle attack. Fault attacks may apply (e.g. forcing the session key to be zero with targeted and timed laser pulses). Side channels may be problematic.


Does there exist a mode of operation that forces mac-then-decrypt? Alice sends Bob a message using AES-GCM. Bob is a software developer with just enough cryptography knowledge to be dangerous. He wants to start processing data as soon as he receives it. He observes that he can ignore the tag and just decrypt the CTR-mode ciphertext.

In every mode I can think of it is possible to decrypt a message without performing the authentication part. Does there exist a standard or named mode of operation that makes it impractical to try to skip or defer authentication?

It seems like such a scheme would necessarily be two-pass. It's fine if the first pass is always authentication and the second pass is decryption.

I had two (incomplete) ideas for how such an encryption scheme might work. I include their descriptions because it might aid to better explain the question asked above.

My initial idea involved first encrypting plaintext using an unauthenticated algorithm and random IV. Then the ciphertext would be fed to some kind of HMAC. The first 128 bits of HMAC output would become the message tag. The remaining bits would not be published and instead be used as a tweak for encrypting the IV.

(This prevents the recipient from decrypting the message without first performing the MAC algorithm because otherwise the IV remains unknown to the recipient. One issue is that the IV isn't authenticated.)

My second idea was to try adapting an all-or-nothing-transform, "an unkeyed, invertible, randomized transformation, with the property that it is hard to invert unless all of the output is known."

There is a type of AEAD construction, exemplified for example by the CAESAR candidate AEZ, which splits up into two components:

An enciphering scheme: "an object that is like a conventional blockcipher except that the plaintext’s length is arbitrary and variable, and, additionally, there’s a tweak" (p. 1).
An encode-then-encipher mode that enciphers the concatenation of a plaintext with a fixed number of zeroes (or some other alternatives).  On decryption, the authenticity check verifies that these final bits deciphered to zero.

The key thing is that in the enciphering scheme, a change to any bit of the ciphertext (or plaintext respectively) has a 50% chance of affecting every bit of the plaintext (or ciphertext respectively).  So attempts to modify a ciphertext will yield garbled plaintexts, and those garbled plaintexts will be safe to reveal.


plaintext decrypted form a cipher text using key = 3 in Caesar Cipher and that plain text with the following ciphertext to get the key how to use the plaintext from that was decrypted form a cipher text using key = 3 in Caesar Cipher and using that plain text with the following ciphertext to get the key.

Take original plain text as " PLEASEEECUSEMYDEARAUNTSALLY", note that I've ignored the 'X', so that rail fence with key(row depth) = 4 cipher text will be "PEMALLEEEYRUALESCSDANSYAUET" now using Caesar cipher with k=4 on this new text.
${C= (P+k)mod26}$ , you will get cipher as $${"TIQEPPIBICVYEPIWGWHERWCEYIX"}$$

Here we take row wise so P --> T, E-->I, M-->Q, A-->E, L-->P,
in second row L-->P,E-->I and so on...


Would hashing a password twice prevent naive attacks? A common way of using MD5 or any other hashing algorithms to store passwords is to hash the password with a salt $$\text{hash}(\text{password} \mathbin\| \text{salt}).$$ This way, if an attacker wants to brute force the passwords, they have to do this for each password since each password has a different salt. With this setup, a determined attacker could still brute force a password since they have the salt and they know the hashed password was generated with $\text{hash}(\text{password} \mathbin\| \text{salt}).$
Would storing the hashed password as $$\text{hash}(\text{hash}(\text{password} \mathbin\| \text{salt}))$$ be a way of deterring the attacker? The idea with this approach is that the attacker doesn't know the password is being hashed twice. This means that if they try to brute force the password with the assumption that the hashed password is of the form $\text{hash}(\text{password} \mathbin\| \text{salt})$, they will never be able to crack it.

We don't approach our security through obscurity, we live in a world that Kerckhoffs's Principles rules! We assume that everything is known by the attackers except the key/password is secret. Your modification only hardens the search a little; just one more hash!
Password hashing has gone a longs way and in modern password hashing, we want them

memory-hard so that massive GPU/ASIC searches are almost prohibited.
Non-Parallelizable so that the attacker cannot parallel even a single search due to the requirement of multiple threads for a single password hashing.
Many Iterations so that the attacker must need huge time for the calculation of a single password hash.

All of the above parameters can be adjustable ( depend on the password hashing algorithm) so that the system designers can fit them into their system, too. For example, having a huge iteration that takes longer than 1 second is not good from the user's perspective. 250K or 1M may be good depending on the server.
Don't fall into Schneier's Law on Security

Any person can invent a security system so clever that she or he can't think of how to break it.

Instead of designing your own, first understand the standard ones like Scrypt, PBKDF2, and the winner of the 2015's Password Hashing Competition; Argon2.


Is it necessary to generate a private key for each encryption process? I read about Asymmetric key cryptography like EG-ECC , RSA, ECDH. I understand the concept of mathematics to these algorithms. But I have wondered about the public key for sender and private key for recipient. In other words,

Any other user who wants to send an encrypted message can get the intended recipient's public key from a public directory. They use this key to encrypt the message, and they send it to the recipient. When the recipient gets the message, they decrypt it with their private key,
How much is the length of the message here is it necessary to have the message length smaller or equal to the length of the public key or the message can be any length of random words, can be divided into more than one block in this case we will use the sender's public key  more than one time. Is the process of generating keys occur in the process of block encryption or message (size greater than size key) encryption?

As you have correctly identified, there is a problem that with public key encryption you cannot encode long messages in an efficient way. Your message must be an element of a finite group and may therefore not exceed a certain number of bits.

Therefore often a hybrid approach with symmetric and asymmetric encryption is used. That is:

The sender encrypts his long message using a symmetric algorithm, using a randomly chosen secret key K.
The sender encrypts the secret key K using the public key of the recipient.
The sender sends the symmetrically encoded message and the asymmetrically encoded key K to the recipient.
The recipient first recovers K and then decrypts the long message.


Koblitz encoding a message to a point, what is the "associated auxiliary base parameter"? I am looking at the Koblitz method for encoding a message as an elliptic curve point.  The first step given in the paper I'm reading is:

  "Choose an elliptic curve and its associated auxiliary base parameter, k."

I have not heard the term "associated auxiliary base parameter" before.  Does it mean the order of the curve, or something else?

Based on a quick Google search, I assume you're reading the paper "Modified Koblitz Encoding Method for ECC" by Kodali and Sarma (Int.J.Rec.Tr.Eng.Tech., vol. 8, no. 1, Jan 2013).

The fact that the paper doesn't actually cite any source for the encoding scheme, or even cite anything by Koblitz, makes me a bit skeptical of the paper's quality.  For that matter, so does the fact that they seem to be using tiny curve sizes and encoding individual ASCII characters as curve points.  The security levels they seem to be claiming in their last figure also look absurdly low (9 bits, really??), which at least seems honest, if not particularly useful.

All in all, while I admit to only skimming the paper, and that I may have missed some crucial detail, at least at a glance it certainly trips my bullshit detector.  I suggest you, at the very least, read it with a highly critical eye.

In any case, I assume that, by "Koblitz's encoding method", they're referring to one of the three encoding schemes described in section 3 of Koblitz's original 1987 paper, "Elliptic Curve Cryptosystems" (Koblitz, N.; Mathematics of Computation 48(177), January 1987, pp. 203–209).  It's not 100% clear to me which one they're describing, but I suspect it's most likely the second one, where the plaintext $m$ is mapped to a curve point by multiplying it by some constant $k$ (1,000 in the example) and testing all $mk \le x < (m+1)k$ by brute force to (hopefully) find an $x$ that corresponds to a curve point.

Ps. You may also find these earlier related questions interesting:

Mapping of message onto elliptic curve and reverse it?
Fast hashing into elliptic curve

Pps. I took a closer look at the Kodali & Sarma paper to see which EC cryptosystem they're actually using, and I couldn't make any sense of it — it looks as if they're effectively just running a symmetric Caesar cipher over an elliptic curve (after first doing ECDH key agreement). If so, that still makes absolutely no sense to me; it's not semantically secure, and anyway they'd be much better off just feeding the ECDH secret (computed over a secure curve, not the tiny one they seem to be using) to a KDF and using it to key a standard symmetric cipher, like normal people do.


How to compute initial buffer of SHA-512? I'm reading Cryptography And Network Security of William Stallings.

In the SHA-512 section it is said that there is a 512-bit buffer is used to hold the intermediate and final result and every 64-bit obtained somehow (obtained by taking the first sixty-four bits of the fractional parts of the
square roots of the first eight prime numbers).

However, if I convert the first of the binary digits to base 10 I get:

a = 7640891576956012808

I searched the square root of 2 in high precision( https://apod.nasa.gov/htmltest/gifcity/sqrt2.1mil ) and did not match. Why?

What you've done is to shift the 64 bits that you require to the left, before printing out the values. So instead of looking at the bits directly, you are looking at a shifted representation of them. However, if you do that you multiply with a power of two, not a power of ten.

To be precise, if you shift 64 bits to the left then you multiply with $$2^{64} = 18,446,744,073,709,551,616$$
Of course, this number is far from a power of 10, so you would expect it to skew if you look at the result in decimals.

And if you look at the value then you'll see that it is indeed about 1,85 times the number you expect. You get a 7 something instead of a 4 something. In case you don't trust me, here's an interesting calculation for you...

In other words, you interpret the binary digits as if they are digits at the left of the dot, rather than at the right of the dot when you converted them to decimal. It matters where the dot is when you do base conversion and you want to look at the digits.


Secret sharing by using just "private secrets"? TLS is using 3 way handshake. Isn't that possible to use such 3 way handshake protocol to share a secret without using a public key scheme, for instance as follows: Let A, B be private secrets of Alice and Bob respectively, where A,B  are elements in a commutative groups. Alice wants to share the secret X with Bob, and sends Bob AX. Bob multiplies it by his secret B to create BAX, and sends it back to Alice, that Multiplied it By 1/A, creating BX, that is sent back to Bob, that multiplies it by 1/B, getting X, the secret Alice wanted to share. Is there a principle problem with this scheme?

The attacker sees AX and BAX, and just divides them to compute B. Then they see BX and divide again to compute X.


Does the IV need to be known by AES (CBC mode)? I was thinking about this today and thought I should ask. I think I understand IV's enough to say that they are basically the same thing as Salts when talking about hashes. They are there to improve randomness between messages. If the IV is simple appended, or prepended to the plain text, why does AES need to know the IV to decrypt it? Can't it just decrypt it, drop the first x amount of bytes and then it has the original plaintext or does AES do some special jizz-jazz with the first bytes in the stream?

The initialization vector is XORed against the first plaintext block before encryption in CBC mode, as shown in the Wikipedia article on block cipher modes. After the first block is decrypted, you still have an intermediate value which has been XORed with the plaintext — without this, you have little hope of recovering the plaintext. However, you do not need the IV to decrypt subsequent blocks.

You could perform CBC in a way that would remove the need to know the initialization vector (note: this is not recommended or encouraged, just pointing it out for the novelty). If you use a null IV and use a random value for the first block of plaintext, you can discard this value and only transmit the ciphertext. Note that this actually gains you nothing, because now the ciphertext is one whole block longer!


A Zero knowledge proof for set membership? Essentially, I am trying to build up a list of authorised public keys that will be stored in a database P by a verifier V. A public key will be considered authorised if belongs to a user in a database of verified users D. The problem is that it should not be possible for the verifier to ever link a public key to a specific authorised user.

I was thinking something along the following lines - Every user in D hashes a secret message that gets stored along with their account in D:

+-------+--------+
| User  |  Hash  |
+-------+--------+
| Bob   | abc123 |
| Alice | xyz789 |
| Eve   | 456fgh |
+-------+--------+

Then some sort of cryptographic accumulator can be used to combine the hashes. When a user wants to authorise their public key, they prove to V (in zero knowledge) that they know a message that when hashed, forms part of the accumulator. If V is able to confirm this, there public key is added to P, otherwise it is rejected.

To make matters even more complicated, a user should only be able to ever have one public key in P. In other words, Bob must not be able to continuously request multiple keys to be added to P. Thus, once everyone has had a public key authorised, P will look as follows:

+--------+
|   PK   |
+--------+
| MXH452 |
| B6HGJS |
| 67ZC6S |
+--------+

With it being impossible to know which public key belongs to which user. All we know is those public keys are verified and belong to one, and only one, user in D.

How can this be achieved? I have glanced at a few papers surrounding this issue, but they tend to get very technical very quickly.

I think what you want is a ring signature. This is a signature mechanism that allow you to prove someone signed within a set of actor without revealing which one.

You may want to read https://link.springer.com/chapter/10.1007%2F3-540-45682-1_32 and https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf


How often is Ratchet key pair changed in signal protocol? At first I thought the new ratchet key is created with each first incoming message. After that I believed it depends on the implementation. But after closer look at the signal documentation and following picture, I am left even more confused.

The picture above shows Alice sending message A2 and after that receiving message B2 from Bob, which uses his old key. How is this possible?
Shouldn't Bob update his key on receiving Alice's A2 message. Message A2 features a new ratchet key, and should trigger DH ratchet on Bob side and update his Receiving and Sending chain, thus his next message (B2) would use a newly created key?
What I am missing here?

First, how often is a new DH ratchet key is decided by the implementation.
Alice will trigger a DH ratchet step when she receives a new public key in the header of the message sent by bob (section 4.1 of double ratchet specification[0] goes into the detail of it). In this case, B2's header did not have a new public key, while B3 and B4 do.
Coming to your question, It doesn't matter if A2 had a new key or not. Why? Because this protocol allows for messages to arrive with old keys. Think of the case where Alice's message is not delivered but bob keeps sending message(s).
[0] https://signal.org/docs/specifications/doubleratchet/


Licensing software with asymmetric signed files NOTE: I know that there are numerous topics here on StackExchange about this but I've read them all and this question still persists.

I'm currently working to enhance the security of a windows based application that is sent to specific clients. We use AES encryption to create a big binary file with license data. In this data we have numerous hardware restrictions and things like user name and login. AES keys are stored within the application in a very secure and complicated manner and accessing the keys is done by a "random-based" routine that never uses the same key twice.

So far so good but new policies demand that everything should be signed by an asymmetric encryption scheme. I've being studding RSA and I can totally see how it works for most cases, but in this scenario there's a tiny thing that I still get into my head:

Most posts say that you should sign your license file and send it along with the public key so that it could be verified. So the software doesn't know the privet key, it only has a public key to check the license hash.

Question: What is preventing the user to just sign the license with his key and use his public key to verify it: How does the software can guarantee that the license is in fact made by me and no someone else?

Is more of an conceptual question because is really not clear how this signing will add security at all.

On symmetric encryption the software is build in with information that can decrypt and verify a license. But if the software is depending only on a public key, how does that work?

Thank you all in advance for you time

keys are stored within the application in a very secure and complicated manner

Secure and complicated are antagonist, except when it comes to security by obscurity. But, the later is the only practical way to implement "software licensing" (the politically correct term for copy protection) on modern computers without using some sort of trusted hardware or enclave (which this answer does not consider).

  you should sign your license file and send it along with the public key so that it could be verified.

That's insecure, as noted in the question: there's noting cryptographic to prevent an attacker from generating a fresh public/private key pair, using that private key to sign an unauthorized license file, and send the signed unauthorized license file with the fresh public key.

The baseline sound way is that the code implementing the license verification, and specifically the signature check, contains (or comes with) the publisher's public key, and it is assumed¹ attackers can not change that public key, no more than they can change the code to bypass all license verification.

There is one significant advantage to thus using signature: it gives strong cryptographic insurance that no amount of reverse-engineering will allow an attacker to generate new license files that will get accepted by unmodified genuine software. That's not possible with symmetric cryptography. It's not a silver bullet, though:

Attackers can and do modify software.
Legit license files could still be accepted in multiple identical virtual machines if they reproduce the authorized machine faithfully enough.

No cryptographic protection from the above two threats is obtained by adding bells and whistles like:

Key identifiers, with multiple public keys in the software, allowing key rotation and independent issuers.
Hierarchy of keys (PKI). With this, the license file could indeed come with a public key, with that key itself signed together with its metadata (the technical term is certified) by the publisher's public key(s), soving the question's security problem.
X.509 certificates
Revocation server

¹  This assumption must rely on some level of code obscurity. Among standard techniques:

Code tries to check that it was not modified, thru OS services (e.g. Authenticode² on Windows as pointed by SEJPM) or/and self-checks.
The public key is stored encrypted, and is deciphered and checked by the security code before use, using symmetric cryptography with a key in the security code. This mitigate attacks that work by altering the public key.
Some of the above keys are hidden among other material with similar redundancy, to foil attacks that locate keys based e.g. on the distribution of the bytes they contain.
If the masters of the executable platforms have no binding rules against it, reverse-engineering is complicated by having the security code

Processed by code obfuscators.
Stored encrypted, and deciphered before execution.
Compiled to pesudo-code for an interpreter, perhaps custom.


Parameters for comparison of Salsa, HC-128 and SOSEMANUK I am doing my final project of computer science and I need some help.

I understand how Salsa works, but I don't have the same knowledge of HC-128 and SOSEMANUK. I have to do a table with the advantages and disadvantages of each one.

What parameters can I compare?

HC-128 and SOSEMANUK are two stream ciphers that were studied by the "eSTREAM" project. A bunch of candidates were evaluated, and the "best" (in some way) were kept in the final portfolio.

From the eSTREAM project page, you will find a lot of information on these algorithms, including full specification, reference code, test vectors, and design descriptions. There are also links to benchmarks.

The point of making you write a table that compares parameters for these algorithms is, indeed, to have you read these documents and understand what parameters are relevant. Ideally, you would go beyond what is already documented to take into account some newer research (e.g. while SOSEMANUK is really fast in software, the natural implementation will use a lookup table with state-dependent addresses, which is a bad thing with regards to side-channel attacks; a fair assessment of the algorithms should discuss such things).


How does the attack on MD5 work that allows a file to show its own (full) hash? I've recently stumbled across this "moment" on Twitter, where there are three files, that show their own MD5 hashes.

As an example, this GIF (screen-shotted in the following image), has the hash:

f5ca4f935d44b85c431a8bf788c0eaca

They obviously match. Also this looks like the sort of attack that would normally take $2^{128}$ evaluations instead of the usual $2^{64}$ for a collision because you're going for a very specific message-hash pair.

So, how does this work, that a file can display its own MD5 hash?

TO understand what is going on, you have to consider how MD5 works and how the collision attack works.

MD5 is a Merkle-Damgård hash function: it process the input data by blocks (of 64 bytes each), with a "running state" of 128 bits. So there is an internal function $f$ that takes as inputs the current state $s$ and the next message block $m$, and outputs the new state. The state after processing the last message block is the hash value.

The known collision attacks produce pairs of two-block messages that trigger a collision, with an arbitrary starting state value $s$. That is, given a 128-bit value $s$, the attack produces blocks $m_1$, $m_2$, $m'_1$ and $m'_2$, such that $(m_1,m_2) \neq (m'_1,m'_2)$, and $f(f(s, m_1), m_2) = f(f(s, m'_1) m'_2)$. The important point here is that since $s$ is arbitrary, then one can "chain" collisions: taking as value of state the output $s'$ of the expression above (i.e. what you get after processing $m_1||m_2$ or $m'_1||m'_2$), then you can run the attack again and find a new colliding pair $m_3||m_4$ and $m'_3||m'_4$.

At that point you have a four-way multicollision: the following four messages:

$m_1||m_2||m_3||m_4$
$m_1||m_2||m'_3||m'_4$
$m'_1||m'_2||m_3||m_4$
$m'_1||m'_2||m'_3||m'_4$

all hash to the same value.

Now iterate that process, by running the attack 128 times. You end up with 128 two-block collisions that can be chained, allowing a grand total of $2^{128}$ messages (each consisting of 128 pairs of blocks, i.e. 16384 bytes in length) that all hash to the same value.

Another crucial consequence of the Merkle-Damgård structure is that once you have a collision, then you can add an arbitrary suffix to the colliding messages, and it is still a collision. Similarly, since the attack works with any starting state value, you can also have an arbitrary prefix.

The rest of the attack is non-cryptographic hackery. Basically, you need a document format that is flexible enough to perform a "selection": something that can print out different pictures based on specific bytes somewhere else in the file. Roughly speaking, the file will have this format:

prefix || multicollision || suffix

where the prefix and suffix select the picture to display based on the contents of the "multicollision" part. Then you just have to select the right combination in the "multicollision" part (among the $2^{128}$) such that what is displayed matches the intended output: since this is a multicollision, the choice does not alter the final hash value.

This "image selection" mechanism can be more or less easy based on how flexible the format is. With Turing-equivalent languages (e.g. PostScript), this is trivial(*). With PDF and animated GIF, this is doable. With some formats, this is extremely hard or even impossible (e.g. if the format is "plain ASCII text readable by a human, then there is no "selection" mechanism).

(*) In fact, with a fully Turing-equivalent format, one can use Quine techniques to display the file hash even without leveraging any collision. It would work with unbroken hash functions like SHA-256 as well. But that's quite something else, and is not really a question of cryptography.


Has anyone heard of matrix-based "Russian Doll" encryption techniques? I've been told that prime-number factoring is based on a "russian-doll" sequence of matrices, where a seed matrix of height Y and width X exists consisting of all zeros except for a single 1 at row Y column X.  For every x columns added, the matrix grows by y, and two closely related formulas sum the column vectors and the row vectors.

Put another way, given a matrix of height $Y+ny$ and width $X+nx$, the matrix consists of all zeros and ones such that the sum across the rows is less than $f((Y+ny)/j,Y+ny)$, and the sum across the columns is less than $g(X+nx,(X+nx)/k)$. $j$ and $k$ provide the noise or entropy of the encryption algorithm.

The distribution of products of numbers is an example of one method of filling out such a matrix.  Has anyone ever studied the relationship between $f$ and $g$ to come up with a family of "roman-doll" encryption techniques with difficulty related to prime-number factoring, but security closer to a "one-time pad" method of encryption?

Reference

I don't have a good online reference for this, but the methods are readily understandable by anyone with a junior high education level.  A similar approach is described at http://www.gbbservices.com/math/squarediff.html#Cracking_RSA

Postscript

The algorithm I'm familiar with has the following theorems:

$$
\begin{eqnarray}
\forall j \in \mathcal{N}\cdot h_{0,j}&=&1\\
\sum_{i\in \mathcal{N}} h_{i,0}&=&1\\
\forall J\times k \in \mathcal{N}^2 &\cdot& (\exists s\cdot (s^2=2*J+1)) \vee \sum_{j\in \mathcal{N}}{h_{2^k(2J+1),j}}=(k+1)\sum_{i\in \mathcal{N}} h_{i,J}\\
\forall J \times k \in \mathcal{N}^2 &\cdot& \exists s\cdot (s^2=2*J+1) \implies \sum_{j\in \mathcal{N}}{h_{2^k(2J+1),j}}=(k+1)\sum_{i\in \mathcal{N}} h_{i,J}-\lceil\frac{k+1}{2}\rceil
\end{eqnarray}
$$

An additional constraint that results in the "russian doll" effect are:
$$
\forall I \in \mathcal{N} \cdot I\ge X\implies \sum_{j\in \mathcal{N}} h_{I,j}=\sum_{j=Y+(y/x-m)(I-X)}^{Y+y(I-X)/x} h_{I,j}
$$

where x, y, X, and Y are as introduced in the original question.

Private keys are those rows whose sum is one.  Public keys are those whose sum is 2. The higher rows are more cryptographically secure.

Also, if the matrix is populated according to standard number system, then:

$$
\forall I \in \mathcal{N} \cdot \sum_{j\in \mathcal{N}}\sum_{i=1}^{I} h_{i,j}=\sum_{n=1}^{\lfloor\sqrt{I}\rfloor} (\lfloor\frac{I}{n}\rfloor-n)=(D(x)-u)/2
$$

where D(x) is the Divisor Summatory Function

Examples

Matrix 0:

1    (1)

Matrix 1:

1   0   1   (9)
1   0   0   (7)
1   0   0   (5)
1   0   0   (3)
1   0   0   (1)

Matrix 2:

1   0   0   0   0   0   1   ?   ?    (33)
1   0   0   0   0   0   0   ?   0    (31)
1   0   0   0   0   0   0   ?        (29)
1   0   0   0   0   1   0   0        (27)
1   0   0   0   0   0   1   (25)
1   0   0   0   0   0   0   (23)
1   0   0   0   1   0   0   (21)
1   0   0   0   0   0   0   (19)
1   0   0   0   0   0   0   (17)
1   0   0   1   0   0   0   (15)
1   0   0   0   0   0   0   (13)
1   0   0   0   0   0   0   (11)
1   0   1   0   0   0   0   (9)
1   0   0   0   0   0   0   (7)
1   0   0   0   0   0   0   (5)
1   0   0   0   0   0   0   (3)
1   0   0   0   0   0   0   (1)

This seems to be a derivative of the techniques presented in 1997.

Exploratory Factor Analysis, by Ledyard R Tucker and Robert C. MacCallum


How to calculate $v_k(s)$ in Quadratic Arithmetic Program? In the paper Pinocchio: Nearly Practical Verifiable Computation, there are some polynomials $v_k(x)$, $w_k(x)$ and $y_k(x)$ representing the structure of there circuit. However, as in the "concrete example" in page 3, the description of $v_k(x)$ are table items like $v_1(r_5) = 0$ and $v_1(r_6) = 1$, where $r_5$ and $r_6$ are roots of the constructed target polynomial $t(n)$.

But what is the textbook form of $v_1(x)$ like $a_0 + a_1x + a_2x^2 + \dots$? How to calculate $v_1(s)$ and $g^{v_1(s)}$, if $s$ is not a root of the target polynomial $t(x)$?

The canonical algorithm to construct the QAP polynomials from an arithmetic circuit does not yield a polynomial in the standard form ($a_0 + a_1x + \dots$), but as a set of $(x,f(x))$ points. In order to compute $f(s)$ for arbitrary $s$, as required by the protocol, you have to run some interpolation algorithm to reconstruct the polynomial from all the points. (This is indeed one of the major flaws of Pinocchio, because interpolation is a very expensive operation and takes most of the execution time, even though it is not a crypto operation.)


How does the IV or initial counter increase internally for each block in AES CTR mode? I am working on Intel AES-NI library and since the AES function is coded using low-level assembly instructions. I could not see how the IV or initial counter increases in CTR mode. In general, how does the IV or initial counter increase by itself for each 128-bit block (let's say we use AES_CTR_128)? Does it increase by one or some other value?

The entire block consists of a $n$ bit nonce and a $128-n$ bit counter. Typically $n=64$. The nonce needs to be large enough so that every message under the key can have a unique one, and the counter needs to be large enough that every message block can have a unique counter value.

Typically, the counter is initialized to 0 and then incremented by 1 for each block. However, this isn't mandatory, I don't think there's any reason for that choice beyond the fact that it's the simplest, clearest way to do it. Any initialization value and incrementing function is valid so long as the choice doesn't cause repeats of the counter for the desired message length. (Even the FIPS validation process allows submissions that implement CTR mode to choose both the initial value and the incrementing function their implementation uses.)


Tweaking textbook RSA to make the encryption a Pseudorandom function Lets say I want to tweak/alter the textbook RSA encryption function to create a pseudorandom function by pre-processing the input.

Suppose I do something simple like add 2 to the input before encrypting it:

$$c = (m+2)^e \bmod N$$

How do I know if this is not a secure pseudorandom function? Does this give any information about N?

I am aware that no tweak can make it a pseudo-random function. I am just trying to understand which values this setting cannot output so as to build a distinguisher. Sorry if I wasn't clear earlier. My question originally meant to ask which ciphertexts cannot be the output of this setting in order to distinguish it from a purely random function. I know 1 thing - This setting will never output 0 & 1 as the input is bounded $$0<=m<2^n$$

This is not a secure pseudorandom function.  No tweak is going to make this a pseudorandom function.  After all, it is a public-key operation, so anyone who knows your algorithm can compute $f(m)$ given $m$.  Consequently, it cannot possibly be pseudorandom: there will always be a trivial distinguisher.

What are you actually trying to accomplish?  Why do you think you want a tweak to RSA that makes it a pseudorandom function -- what problem are you trying to solve?  I think you may need to step back from the specific mechanism you have in mind and think through what are the broader requirements of your particular application.  Once you've done that, we may be in a better position to help you solve your problem.


Find IV and the key ? AES with CFB or OFB I have a question about the AES-128 and AES-256 encryption method. I need to encrypt 64-bit size data in and out. I want to encrypt them with AES.
So I turned to AES-OFB or AES-CFB because these methods do not require padding. I have at my disposal a number of 256 bits which are shared by the source and the receiver (this number is created internally by both, this number is totally unknown to the rest of the world). I would like to use half of the number for the IV and the other half for the key. The IV and the key would be fixed.
In my specifications, it doesn't matter if someone can decipher the messages. However, someone should not be able to send encrypted messages that would be recognized by the recipient.
So my question is this:

Can someone find the IV and the key from the encrypted messages?
If so, can they then generate the encrypted messages to take control of the system?

In my specifications, it doesn't matter if someone can decipher the messages. However, someone should not be able to send encrypted messages that would be recognized by the recipient.

If that's the case, then encryption is the wrong solution; you are looking for a Message Authentication Code (MAC), such as CMAC.
With CMAC, you hand the message and the key to the CMAC code, which generates a 'tag'.  You send the message and the tag to the recipient, which takes the message (and their own code of the key) and calls CMAC to generate their own tag.  If the tag they computed agrees with the tag you sent, they accept the message; otherwise, they reject it.
CMAC (and any other MAC) was designed with the security property that, if you don't know the key, you cannot find a message/tag pair that validates (even if you were given a large number of valid message/tag pairs).  This is exactly what you want; someone cannot generate a tag that would be accepted (except for the message/tag pairs they have already seen).
Of course, if replay attacks are potentially an issue (that is, if an adversary takes a message/tag pair verbatim and resubmits it, would that be an issue?); if it is, you can add further protection (e.g. include a sequence number with the message; this sequence number always increases; the recipient verifies that it is higher than the previously seen valid messages, and the sequence number is included in the CMAC computations).
Obviously, someone listening in can find the message (it's in the clear); however you said you didn't care about it.
I suggested CMAC in particular because you appeared to have AES in mind (and CMAC based on AES is not a bad option); other good message authentication codes are HMAC and KMAC.


Is $f(K, f(K, x))$ a pseudorandom function? Given a PRF $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$, is $f(K, f(K, x))$ a PRF, too?

My hunch is to construct a PRP similar to Feistel ciphers but with the property $f(K, f(K, x)) = x$, and disprove the statement with PRP/PRF switching lemma. However, I haven't found a concrete instance with the desired properties above yet.

Can anyone share some hints? Thanks!

I'm responding to:

  "If the oracle accessed by B is truly random, how to prove the oracle B constructs for A is truly random, too?" I'd like to know if a solution to (or a construction which avoids) this problem exists.

This is a "good" thing to get stuck on, because it's not something you can just push under the rug.
Concretely, let $f_k(\cdot)$ be a random function, so for any $x_i$, you have that $y_i = f_k(x_i)$ is uniformly random (and independent of any other $y_j$).
If we knew that $z_i = f_k(y_i)$ was also uniformly random, and independent of all other $z_j$'s, we'd be done!

Is this the case? The answer is almost. Specifically, provided that $\forall i : y_i\neq y_j$, it shouldn't be hard to prove that all of the $z_i$'s are uniformly random (and independent), so everything works out well.

Intuitively, a random function can be expressed as a lookup table (and this is the most compact way to express it), so to compute $f_k(0)$ we lookup some value $U_0$.
The entries in this table are uniformly random, independent variables.
We can think about using this lookup table for $f_k$ to compute $f_k\circ f_k$ by doing two lookups (so precisely the way you'd expect to).

Now consider computing $q$ values $((f_k\circ f_k)(1),\dots, (f_k\circ f_k)(q))$.
This will all be uniformly random values, but there's a risk there's some dependence between them.
Specifically, if $f_k(i) = f_k(j)$ for $i\neq j$, then we'll have that $(f_k\circ f_k)(i) = (f_k\circ f_k)(j)$, so the random variables $(f_k\circ f_k)(i)$ and $(f_k\circ f_k)(j)$ will be correlated (and therefore not independent).
In terms of our lookup table analogy, the event $f_k(i) = f_k(j)$ happening means that our lookup table for $f_k\circ f_k$ ends up having $i$ and $j$ point to the same "slot" in the lookup table for $f_k$, which is the cause of the problem.

So, we want to bound the probability $\Pr[\exists (i,j)\in[q]^2\setminus\{(i,i)\mid i\in[q]\} : f_k(i) = f_k(j)]$.
This can be done with the birthday bound (which you should look up if you're not familiar with it), and can be upper bounded by $q^2/2^n$, which is where the term that was mentioned in the comments comes from.


Is asynchronous perfect forward secrecy possible? DH key agreement protocols require the participation of both parties, so are only suitable for synchronous connections.  Is it possible to implement PFS in a fashion usable for asynchronous protocols, like e-mail, or storage?  I'm intuitively thinking not, but I haven't be able to find conclusive proof one way or the other.

Asynchronous forward secure encryption is possible if you allow users to have synchronous clocks. It seems impossible without that or a third party, though I am aware of no formal result.

A trivial(and hence awful) solution is to generate N key pairs  and use one for each interval, discarding them as we go. A somewhat more efficient solution is to use Identity Based Encryption(IBE) to have one public key and N private keys.

The most efficient scheme I know of  is due to  Canetti, Halevi, and Katz  in this paper. It provides for constant size public keys and $O(log(N))$ private keys where N is the number of time intervals. As far as I know, no paper has improved on that bound, though several have achieved that bound with more efficient techniques.

The gist of the design is you have a tree of keys where there is one root public key and messages can be encrypted to any node in the tree with the root public key and the index identifying the node. (So far, this is just an IBE scheme). Unlike IBE, the decryption key for a given node can be computed from it's parent key.

We now map time intervals to nodes using a pre order traversal (i.e. the root is interval one, the left child interval 2, the left left grandchild of root is interval 3 ...). So once time interval 1 is up, we derive the keys for both the left and right nodes and then delete the root key. Now messages encrypted to interval one are safe, but we can still decrypt everything targeted at the remaining N-1 intervals.


We are given $n>4$ and ciphertext $c\in(0,n)$ for textbook Rabin encryption. We want to solve for $x\in[0,n)$ the equation $x^2\bmod n=c$.  We found that $n$ is a square, computed $p=\sqrt n$, found that it is prime, solved $y^2\bmod p=c\bmod p$ yielding two roots $y_0\in(0,p/2)$ and $y_1=p-y_0$, and now want the solutions for the original equation.
Every $x\in[0,n)$ can be uniquely written as $x=y+z\,p$ with $y\in[0,p)$ and $z\in[0,p)$.
If $x=y+z\,p$ is a solution of $x^2\equiv c\pmod{p^2}$, then that also yield modulo $p$ since $p$ divides $p^2$, thus $y^2\equiv c\pmod p$, thus our earlier work did yield the possible values of $y$.
Now $(y+z\,p)^2\equiv c\pmod{p^2}$ becomes $y^2+2\,y\,z\,p\equiv c\pmod{p^2}$, that is
$2\,y\,z\,p\equiv c-y^2\pmod{p^2}$, that is
$\exists k\in\mathbb Z,\,2\,y\,z\,p+k\,p^2=c-y^2$, that is
$\exists k\in\mathbb Z,\,2\,y\,z+k\,p=(c-y^2)/p$, that is
$c-y^2$ is divisible by $p$ and $2\,y\,z\equiv(c-y^2)/p\pmod p$, that is
$c-y^2$ is divisible by $p$ and $z\equiv(2\,y)^{-1}\,((c-y^2)/p)\pmod p$
Thus we check that $c-{y_0}^2\bmod p=0$ (which must hold unless we goofed in computing $y_0$),
compute $b_0=(c-{y_0}^2)/p\bmod p$, then $z_0=(2\,y_0)^{-1}\,b_0\bmod p$,
then $x_0=y_0+z_0\,p$, and that's one solution. It can't be zero. The other is $x_1=p^2-x_0$.


Asymmetric algorithm for one time signing of small cleartext I want to generate a key pair such that the private key can be used once to sign a small message (1024 bytes) at some indeterminate point in the future and the public key can be used to verify that signature, what can I do to get better security than a regular asymmetric algorithm (e.g. RSA)?

The use case is allowing a user to "revoke" data by bundling the public key with the data. The user can then publish a revocation message (which can also contain some arbitrary but short message) with the private key.

And, do these requirements make any of the post-quantum algorithms especially suitable?

One algorithm that is especially suited to one-use key pars is lamport signatures. Like many (all?) other signature functions, lamport signatures first hash the message to get it down to a size that is more reasonable to sign.

For this use case, if you are willing to have $n^{2}$-bit signatures and $2n^{2}$-bit keys (public and private), you can sign a $n$-bit (or less) message with only a one-way function, by skipping the hash message step and just signing the message directly.

This is nice, because the security of all hash functions and many other algorithms relies on one-way functions. Using such a simple algorithm also removes most attack vectors (the remaining one is the one-way function, which is still an attack vector with most (all?) complex signature schemes).

There are various ways to reduce the sizes required.


How vulnerable is the C rand() in public cryptography protocols? I just learned about the basics of public cryptography a few weeks ago and I am curious as to why the C rand() function should not be used for crypto schemes. For example, say I want to generate a private key using the C rand() function, along with srand(). Lets say srand() generates a seed based on system time (as in example http://www.cplusplus.com/reference/cstdlib/rand/). Is rand() therefore not acceptably pseudo random because the system time is not random (what if I based the seed on something more random)?

If this is the case, then how does OpenSSL generate random private keys? Moreover, how could an attacker exploit an OpenSSL implementation that uses C rand() the way I specified above?

Thank you.

In the example you linked, the current time (specifically, a value representing the number of seconds elapsed since Jan 1, 1970 UTC) is used as the seed. If an attacker knows which year you generated your key, then that leaves only about 2^25 possible values for the seed --- and therefore only about 2^25 possible values for your key. At this point, he can guess your key pretty easily simply through brute force.

But let's say you find a better way to choose a seed, what then? Well, rand() will try to use this seed to generate a stream of random bits. But those bits won't be truly random, since they're based off a single seed value. So will they be close enough to random for cryptographic purposes? Probably not. Most PRNGs that aren't specifically designed to be cryptographically secure won't be good enough. They're designed for use in simulations and the like, not for times when there are smart and resourceful Bad Guys trying to do Bad Things.

OpenSSL seeds its PRNG using /dev/urandom (I'm not sure what it does on systems where this isn't available), and then uses its own PRNG to generate the random numbers. You can read a somewhat vague description here. (This is the first time I've looked up what OpenSSL is doing, and frankly, I find it a bit frightening --- it looks like someone is trying a roll-your-own-crypto, hash-functions-are-random-oracles approach. But I digress.)