Using a hash of data instead of the full raw data for authenticated data in AES-GCM I am serialising JSON objects, and would like to encrypt some of the values.  I plan to do this with AES-GCM.

I would also like to ensure the integrity of the overall object.

The requirements are for integrity of the overall object, confidentiality for some of the values, plus a requirement for plaintext for other values.

There are a small number of known top-level keys.

For example, if my "plaintext" JSON object were

{
    "id":"823623672",
    "address": {
        "line1": "2000 Broadway",
        "line2": "New York",
        "zip": "12345"
    },
    "telephone": "+1 212 555 1234",
    "last-accessed": 1543946340
}

I would like an "encrypted" object to be something like

{
    "id":"823623672",
    "address": "URAVvDTOrovXBehz2ms8ej9BRCaKdx8LsmuA81IkESM=",
    "telephone": "0gAtx7Hh/kPD7chfNGy90A==",
    "last-accessed": 1543946340
}

Now, I can easily serialise the address and telephone and encrypt them, and provide the values of id and last-accessed as the associated data.

However, the actual objects I will be using will have quite a bit more data in the "do not encrypt" keys.

So instead of using the values of id and last-accessed as the associated data directly, I would like to hash these values and use the hash as the associated data.  (Probably SHA-512/256, if it matters.)

To decrypt, I will re-create the associated data (hash) from the input data, then decrypt each of the encrypted keys; if any of the decryptions fail then the overall decryption fails.

(And using the hash means I can create the associated data using hash "updates" with the values of the known keys one after the other, rather than having to create a single contiguous data item with the values all concatenated.  In this instance I would be hashing 823623672 then '\0' then 1543946340 then '\0'; the separators are to ensure an attacker couldn't change the id to "82362367" and the last-accessed to 21543946340, for example.)

(I do not have to worry about an attacker adding additional top-level keys; the ones that have semantic importance will be in the associated data/hash.)

It seems to me that using the hash should not weaken the security of the encryption, but I'd like to check.

Is using a hash rather than the full data going to weaken the security of the encryption?

If I understood you correctly, you will hash everything you need to authenticate and include that in the AAD. This will be secure, as long as the hash is a secure collision resistant hash function. However, I don't understand what you gain. You can compute on all of this data in the AAD but only send what is necessary for reconstructing it. In this way, you don't have to store/send anything more than needed. In addition, the GCM authenticator is actually much faster than SHA256/SHA512, so it will also be more efficient.


Security concern about reducing hash value using modulo operation As stated in the title, what I am looking for is information about a  "technique" that I would like to use in some of my algorithms.

Sometimes I need to map a hash function's result into a range of numbers that is not as large as the hash function's codomain; to do so I use the modulo operator. I take the hash function's output and treat it as an integer; then to this integer I apply the modulo operation
$$h(x)\bmod n\text,$$
where $n$ is the excluded upper bound of the allowed numeric range $\{0,\dots,n-1\}$.

Now what I would like to understand is if this leads to some security risk, other than the fact that the obtained "hash" size is smaller (so a brute-force attack is easier), for instance that a modulus operator could break randomness of the hash function in some way.

Thanks in advance for clarification.

Let's assume that $h(x)$ returns a value between 0 and $k$ (exclusive). If $h$ is a good hash, this distribution will be uniform.

Computing $h(x) \mod n$ will introduce a bias if $k$ is not a multiple of $n$. This bias is significant if $k$ is only slightly smaller than $n$ and decreases as $k/n$ grows. How large $k/n$ needs to be depends on what level of bias is acceptable to you.

The DSA algorithm needs to generate an unbiased number. NIST recommends (FIPS 186-4 in appendix B.2.1) that you should use at least 64 extra bits, i.e. that $k/n > 2^{64}$. This is a reasonable since it means that the bias only becomes detectable if the attacker sees around $2^{64}$ samples. I doubt that you'll generate that much data.

So if you take a cryptographic hash of at least 128 bits, interpret it as a big integer and take it modulo a number smaller than $2^{64}$ the resulting bias will be negligible.

If your application is less sensitive to bias, it might be acceptable to reduce a 64 bit number modulo $n$. This avoids the need for a big integer library and is the approach I took for my random string generator.

Another approach to avoiding bias is rejecting values between $\geq k - k \mod n$. But this means that you need to consume a potentially unlimited amount of random values, so it's probably not the best fit for your application.


Security exists or not in Modification in schnorr signature In Schnorr's digital signature protocol (https://en.wikipedia.org/wiki/Schnorr_signature), the signature is $(s,e)$ where $s=k-xe$.
Assumption:
 $k$ and $x$ are assumed to be secret value of user.
So, ($k,x$) value is never changed except $e$.
$s_{i}=k_{i}-x_{i}e$ for $i$ users
Unlike Schnorr's signature, $e$ is also kept secret so that only valid users, who knows respective k and x values, can reveal it.
Even though different $k,x$ values, $e$ is selected uniformly randomly from $ Z_{q}$ and assumed to be same for all valid users.

Does the modification secure to securely deliver different values of $e$ for every time ?

There are quite a few errors in your thoughts:

  k and x are assumed to be secret value of user.
  So, (k,x) value is never changed except e.

As stated in the signing algorithm, $k$ is drawn uniformly random from the set $\mathbb{Z}_q^{\times}$. This means, it is random (and different with overwhelming probability) for every single message. Using the same $k$ might not be secure at all - I am quite sure it won't, but don't have a proof right now.

That means, in every message $k$ has a different value. This ipmplies, that $e$ has a different value (again, with overwhelming probability). And again, $s$ has a different value with overwhelming probability.

This wouldn't work, since a fixed $k$ just does not fit the algorithm's assumptions.

  Unlike Schnorr's signature, e is also kept secret so that only valid users, who knows respective k and x values, can reveal it.

This is a quite pointless in this case. If some information is known to anyone whose role isn't specified in the protocol, you have to assume that the value is publicly known.

  Even though different k,x values, e is selected uniformly randomly from Zq and assumed to be same for all valid users.

This doesn't make sense at all. Every user has his own fixed value of $k$, the protocol clearly describes how $e$ has to be calculated. If you choose $e$ independently, the whole signature does not work any more.

Adn then you write in the comments:

  Instead of signature, just consider for simple, secure delivery of e.

I thought, $e$ is the same for all users? I guess you meant $s$.

But this would mean this: Your value $s$ does not depend on the message any more. $s$ is always the same for every message.

Summary

This isn't a modification, it has nothing to do with the signature scheme any more. If your only modification would be a fixed $k$, chances are quite high that you already have a fatal security flaw in your setup. My guess would be, that two signatures actually reveal the secret value $x$ then.


Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes? I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.

A collision is between two values. If you take a random pair of values you get a 1/2n chance of having a collision.

With 2n/2 values you have about 2n-1 pairs, so you could expect about 1/2 chance of collision.

(That's just the "intuitive way" of thinking about it; in practice, there are mathematical details.)


Why is knowing M not enough to break Blum Blum Shub? In Blum Blum Shub, the generator is $x_{n+1}={x_n}^2 \mod M$ where $M=p \cdot q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, knowing $p$ and $q$ is enough to break the system. But if I know M, I can calculate the next number in the sequence, so there is no need to know the two factors. Why isn't that sufficient?

Update: Since I wasn't think all those times I read about BBS, just ignore the part about directly calculating the next number. Instead, why would knowing the period provide an attacker with any additional information?

Knowing $M$ is not enough to break Blum Blum Shub because the internal state of the random number generator, $x_i$, should never be revealed. Therefore, while you are correct that knowing the current state allows you to know the next (and all subsequent) states, a secure implementation of BBS should not reveal the internal state.

For provable security, only one bit should be revealed at each iteration. That said, you shouldn't be using BBS in practical applications at all.


Can we place the WOTS scheme into a Merkle tree structure? In post-quantum signature schemes that are (to put it simply) built out of merkle trees, they usually employ some sort of OTS scheme on the very bottom leaves.  I.e WOTS Winternitz scheme.
A relatively simple scheme such as Merkle is making a bunch of Lamport/WOTS keys and putting them on a merkle tree.
Is it possible to instead put the WOTS scheme itself on a tree, where each leaf represents a byte value, and where each leaf is a simple chain of 1 hash?
By tripling the computation required to make a single use WOTS key, it becomes a potentially finite use key, and you don't have the problem of being able hash forward that is usually resolved with checksums.
Are there some obvious security downsides to doing this?

This question is essentially "can we put the HORS scheme on a tree".  And the answer is yes, as it is the basically HORST.
The question adds confusion by mentioning a Merkle tree and not mentioning an index.  The actual question is (or should've been) "can x HORS public key sets be put on trees with each HORS tree being used to sign each of the x bytes".
Maybe it is not normal to think of HORS/T as WOTS compressed (or Lamport inflated) on an index/tree, but I will leave the question in case it helps anyone else who does.


Identifying the type of algorithm for a PRNG that uses modular multiplication and addition GNU libc uses the following pseudo-random number generator: $$(\mathit{state} \times 1,103,515,245) + 12,345 \pmod {2^{31}}$$ where state is the result of the previous call to the generator.

My questions are:

What are PRNGs using this algorithm - possibly using different numerical
constants - called?
Assume that this generator has the maximum possible period. What is its
period?
Given the result of a call to this PRNG, show how to obtain the result of
the previous call symbolically?

For the last question it is not required to perform any numerical
calculation.

This question was in my cryptology final-exam and I could not solve it and could not find the answer in internet, slides or books. I am really curious about the answers. I would appreciate if someone explain it to me.

These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^{31}$ in that case).

Finding the previous value is a matter of inverting the iteration: $(\text{state} - 12345) \cdot 1103515245^{-1} \bmod 2^{31}$.


What's going on with the complicated implementations for map_to_curve in draft-irtf-cfrg-hash-to-curve? I've been looking into implementing cPace, and I saw that two cipher suites defined for it refered to draft-irtf-cfrg-hash-to-curve for its protocol definition. Part of cPace requires mapping a string hash to a point on the elliptic curve, so it uses the other standard's methods for doing that, in particular its choice of map_to_curve for each curve.
Looking through draft-irtf-cfrg-hash-to-curve, its provided options for map_to_curve, such as Simplified SWU and Elligator 2, seem rather complicated to me. It seems to me that, for example, Elligator 2 is performing a lot of steps to be able to perform this mapping. There is also the issues of (some implementations of) map_to_curve that require additional steps, such as summing two calls to map_to_curve to even the distribution and having to remove the cofactor from the result.
It seems to me that it should be simple enough to map an integer/field element $u$ to a curve point by just using $uG$ with $G$ being the generator for the curve. I can't figure out why this method wasn't used instead. Through my research into Elligator 2, I found that it was originally designed to be a two-way mapping, but the (draft) specification is using it in a one-way context.
What is (or might be) the reason why algorithms like Elligator 2 are being used for this instead of just using $uG$? My best guess so far is for efficiency because Elligator 2 is faster than computing $uG$, but I haven't found any evidence that was the consideration, and I don't know if it even is faster.
As a follow-up question, would it be wrong to replace Elligator 2 with $uG$? I.E. would it result in making the protocol cryptographically weaker? I was looking to implement cPace, but the library I'm using (OpenSSL) doesn't provide an implementation of Elligator 2 nor provide an interface for working directly with curve points on X25519 to help with my own implementation, but it does provide access to performing $uG$ as part of its DH implementation.

It seems to me that it should be simple enough to map an integer/field element $u$ to a curve point by just using $uG$ with $G$ being the generator for the curve.

That is indeed simple; however using it would forfeit the security properties of cPace.
Here's why; cPace essentially works by having both sides map the secret password (and some nonces) to an elliptic curve point, and then having both sides perform a DH operation with the elliptic curve point.  The general idea is that if you are an active attacker who has a guess of the password (and that guess is wrong), you won't know the secret the valid system (who does know the password) will use, and so you won't be able to predict the shared secret (or even be able to recognize it).
However, here is what an attacker could do with your password hashing scheme; the attacker can pick a password, and implement the protocol assuming that password was correct; that is, he generates a point $H = hash(password)G$, generates a random value $x$, computes $xH$, sends that to the system under attack; that system sends a point $J$ (which is his $yH$ value) and you compute $xJ$; the system under attack then sends a message encrypted based on the secret he computed.
If the attacker's guess of the password were correct, then both sides will generate the same secret, and so the attacker can decrypt the message - no surprise there.  However, suppose the initial password guess was wrong.  Then, what the attacker could do is takes a second password guess, and compute $H' = hash(password')G$ and compute $x' = hash(password) hash(password')^{-1} x$.  Note that the values $x'H' = xH$, and so with this password (and modified $x'$) we would have sent the exact same DH public value; so, we can then compute $x'J$ (based on the point the other side sent), and use that to compute the shared secret and then decrypt the encrypted message - if he second guess to the password was correct, then that would work.
He can perform the same procedure to allow him to check every password in his password dictionary; this is a violation of the security properties cPace is supposed to have, which is that, after a single exchange, the attacker can learn whether one guess to the password is valid, and absolutely nothing else.
The map_to_curve procedures are designed to avoid this - given two points generated by two different passwords, you are unable to determine the relationship between the two (and hence the above attack does not work).


Is it possible to encrypt data in such a way that it cannot be decrypted with the key used to encrypt it but can be decrypted with another key I'm very new to cryptography and encryption so I apologize if the answer to this is well known, but I can't find anything in my research.

The crux of the problem is the need to store data on an offline device which cannot be trusted. Is it possible to encrypt the data in such a way that it cannot be read by the device that encrypts it, but can be read by a server that the device later uploads the data to?

The device can communicate with the server before going offline and capturing data so an exchange of keys can take place before any data is encrypted if that helps.

Yes.  Use public-key encryption: encrypt the data using the server's public key.  You should be able to fill in the details from there.


What Java actually stores inside Keystore when generating Keys? When we use Keytool to generate a Keystore to store Private/Public keys, what Java actually stores inside the Keystore file ?

I have observed that Keytool asks for the keypass and alias to generate the key, the alias can be used to retrieve any key from the keystore given that correct keypass is provided.

So, what actually stores inside a keystore file ?

1) an actual key ?
or
2)  the pair of keypass and alias, and the key is generated using that keypass/alias ?

What I think is, the keypass and alias are stored in the keystore and key is generated if correct data is provided, am I correct ? , If not, and Raw key is stored inside a keystore then what is the need of keypass at first place ?

For your convenience, here is more detail about keytool,

  Java Keytool is a key and certificate management utility. It allows
  users to manage their own public/private key pairs and certificates.
  It also allows users to cache certificates. Java Keytool stores the
  keys and certificates in what is called a keystore. By default the
  Java keystore is implemented as a file. It protects private keys with
  a password. A Keytool keystore contains the private key and any
  certificates necessary to complete a chain of trust and establish the
  trustworthiness of the primary certificate.

Parameters of keytool command

Keystore Parameters

genseckey
Generate SecretKey. This is the flag indicating the creation of a synchronous key which will become our AES key

keystore
Location of the keystore. If the keystore does not exist, the tool will create a new store. Paths can be relative or absolute but must be local

storetype
this is the type of store (JCE, PK12, JCEKS, etc). JCEKS is used to store symmetric keys (AES) not contained within a certificate.

storepass
password related to the keystore. Highly recommended to create a strong passphrase for the keystore

Key Parameters

keyalg
algorithm used to create the key (AES/DES/etc)

keysize
size of the key (128, 192, 256, etc)

alias
alias given to the newly created key in which to reference when using the key

keypass
password protecting the use of the key

Nitpick: keytool accepts both alias and keypass if specified; if not specified it prompts for key password if needed but defaults alias to mykey. A JCEKS file can be operated on either by keytool or by other code.
JCEKS can support three types of entries: privateKey, trustedCert, and secretKey (the older and default JKS file can do the first two).

The operations and algorithms you ask about are "symmetric" (not "synchronous") and use a "secret" key NOT "public" and "private" keys which apply to algorithms like RSA, DSA, ECC.
Also symmetric keys including AES are NEVER in certificates.

A secretKey entry contains the secretkey encrypted using the keypassword (using a PBE aka key-stretching algorithm). The password itself is not stored, which would be totally insecure, and instead must be provided on any attempt to access the privatekey. Note that you can change the alias of a secretkey entry and/or re-encrypt with a different keypassword without changing the key.


zero knowledge proof application Suppose I have a secret 'X'. Which can be use as a seed to a deterministic random number generator to generate a number 'Y'. Is there any way to prove to others, that I have the secret 'X' which generated this number 'Y' without revealing the secret 'X' using zero knowledge proof, such as Schnorr's protocol.

So let's assume you have the function $f$, which is publicly known, and you publish the value $y = f(x)$. And then you want to prove that you know $x$. You said $f$ is a deterministic random number generator (and I guess you meant a CSPRNG) - but from the given information I guess it's just important that it is one-way?

Anyway, there are two cases for $f$:

$f$ is defined in algebraic structures like finite groups/ rings/ fields and can be expressed as a polynomial, has structure preserving properties (like being bijective), etc. Then it might be possible to create an elegant proof of knowledge for that specific function, similar to Schnorr's protocol. But there is no catch-all method for all possible functions $f$, and it's possible that you can't find a proper proof of knowledge without revealing $x$ - it all depends on the function.
$f$ is actually non-algebraic, e.g. binary input and binary operations, and it most likely does not preserve structure of any kind, for example the practical hash functions and CSPRNGs. Then the following paper might give you an indication how this could be achieved: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently by Jawurek,Kerschbaum and Orlandi (2013). SHA256 was one of the examples in there - however this is a very different kind of proof of knowledge than Schnorr's identification protocol. And of course, in this case it would also depend entirely on $f$, if this works - and if you are willing to accept its overhead. The example  in the paper took around 5 seconds for a single proof of knowledge of a SHA256 preimage.


RSA given q, p and e? I am given the q, p, and e values for an RSA key, along with an encrypted message.

Here are those values:

p                 = 1090660992520643446103273789680343
q                 = 1162435056374824133712043309728653
e                 = 65537
sample ciphertext = 299604539773691895576847697095098784338054746292313044353582078965

I tried calculating d with the Extended Euclidean algorithm, but came out as 1.9404359e+59, which I am almost certain is incorrect. How should I calculate d?

I used the following python code to compute the private exponent and perform decryption. It uses the extended euclidean algorithm:

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def main():

    p = 1090660992520643446103273789680343
    q = 1162435056374824133712043309728653
    e = 65537
    ct = 299604539773691895576847697095098784338054746292313044353582078965

    # compute n
    n = p * q

    # Compute phi(n)
    phi = (p - 1) * (q - 1)

    # Compute modular inverse of e
    gcd, a, b = egcd(e, phi)
    d = a

    print( "n:  " + str(d) );

    # Decrypt ciphertext
    pt = pow(ct, d, n)
    print( "pt: " + str(pt) )

if __name__ == "__main__":
    main()

The private exponent is:

$522550976146069021499058157764354003336248628589338241039193114657$

The plaintext is:

$83678269879577658472958479799572658268$

which works out to a 128-bit value, so I'm assuming it's correct.


Can one construct OTPs without using XOR? The typical version of the one-time-pad (OTP) uses XOR to combine a key pad and a message. ($c=m\oplus k$)

Now let's assume some other scenarios which have the practical application of blinding. Do the below "OTP" constructions provide perfect secrecy?

The key $r\in (0;n)$ is chosen uniformly at random such that $r^{-1}\bmod n$ exists and shared between both parties. Furthermore both parties share some common modulus $n$ which may be an RSA-modulus or a prime. For a message $m\in (0;n)$, is the construction $c=m\cdot r \bmod n$ perfectly secure?
$r\in (0;n)$ is chosen uniformly at random  and shared between both parties. Furthermore both parties share some common modulus $n$ which may be an RSA-modulus or a prime. For a message $m\in (0;n)$, is the construction $c=m + r \bmod n$ perfectly secure? (I strongly suspect the answer to be "yes" here as this is a "commonly" cited method for secret message transmission via radio where $n=10^4$)

Both constructions are not perfectly secure!

In an attempt to express things a bit more mathematically, I'd say you can implement a one-time-pad with a message $m$ and a key $r$, when

$m$ and $r$ are elements of $\mathbb{Z}/n\mathbb{Z}$, the additive group of integers modulo n, or when
$m$ and $r$ are elements of a group $G$ isomorphic to $\mathbb{Z}/n\mathbb{Z}$.

Such groups would be a natural choice to implement an OTP.

There are however also other possibilities. For instance one can easily imagine a perfectly secure OTP construction where the key $r$ is an element of a group $G$ and the message $m$ is an element of a subgroup of $G$. (The key is then larger than the message).

Now, lets come back to your constructions. In both constructions you assume $r,m\in \{1,...,n-1\}$ using the unconventional notation $r,m\in(0;n)$.

Construction 1: You compute $c=r\cdot m $ mod $n$. If $n$ is a prime, then you have the multiplicative group of a prime field and it will work. As you already found out, it will not work when $n$ is composite.
Construction 2: You compute $c=r+ m $ mod $n$. It would be perfectly secure if you had $\mathbb{Z}/n\mathbb{Z}$. However, since you exclude the 0 element, you know that you always have $m\ne c$, and it is thus not perfectly secure. :)


How is it possible to trust a public key that can confirm a message's signature? Let's assume I am able to confirm a certain message's signature with a public key that seems to be from Alice.
So I should be sure that the sender of that message is really Alice. But what if I have a public key where I think it is from Alice but actually is not and it still can confirms the signature of the message I got. So I am thinking it is from Alice since I used a key that is published as Alice's Public Key just from somebody else and that can confirm a message's signature I got where I think it is from Alice.

How can I be sure that both the message and the public key are really from the person they are named to be from?

There might be some weird thinking mistake I did here so I'd be happy to get enlightened.

Tried to visualize it.

Thanks in advance.

I am not commenting for what purpose your are going to use public key and answer your main question:

  How is it possible to trust a public key ...?

This one of the most important questions in cryptography: key distribution. Here are some possible solutions:

You can for instance meet Alice and exchange keys personally (but it is applicable in rare real cases).
Or you can use some channel that you trust to exchange keys.
Or you use PKI. Namely some certification authority issues a certificate confirming that the public key belongs to a particular person. The advantage is, that you can exchange certificates also via insecure channel. But to use PKI you need of course trust particular certification authority.


What is the advantage of a probabilistic PKC over a traditional PKC? While reading through a textbook, I came across the idea of a probabilistic public key cryptosystem, which uses a probabilistic TM to generate the public encryption and private decryption algorithm; it is possible the encryption algorithm is probabilistic. If the encryption algorithm were not probabilistic, would the PPKC have an advantage of a traditional, non-probabilistic PKC? Can a traditional PKC offer a probabilistic encryption algorithm?

Every secure public key cryptosystem must have a probabilistic encryption algorithm.

Suppose this was not the case and consider the usual IND-CPA game.
An attacker can now win this game with probability 1 as follows:

He chooses two distinct messages $m_1,m_2$ at his liking and submits them to the challenger.
The challenger chooses a bit $b\in\{0,1\}$ uniformly at random and answers with $c'=c_b=E_{pk}(m_b)$.
The adversary computes $c_0=E_{pk}(m_0)$, if $c_0=c'$ he outputs 0, otherwise 1.
As the encryption algorithm is non-probabilistic, ie deterministic his choice for $b$ is right 100% of the time because he can be sure to always to the same value as the challenger.


Byte order in AES-CMAC test code I'm looking at the AES-CMAC RFC and I found somehow counter-intuitive the way test vectors are used in the test code.
Let's look at the key K
K      2b7e1516 28aed2a6 abf71588 09cf4f3c
The least significant octet is 0x3c, right? If this is true, why it becomes key[15] and not key[0] in the test code?
 unsigned char key[16] = {
     0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6,
     0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c
 };

Keys for AES are not numbers; they are defined as bits / octets (or bytes). They therefore do not have a "least significant octet", they just consist of octets. So the same order from lowest index (left) to highest index (right) is being used.
As common the bits are indexed from right to left though; this is probably due to humans having some trouble converting hexadecimal digits otherwise. It just shows that humans are terrible at thinking in little endian.
The exact ordering is specified in the AES specification as mentioned by fgrieu int he comments.


Would the encryption of bigrams and trigrams weaken the code? Supposing a rotor machine of the 1940s or 50s, with 36 characters instead of 26. Would the encryption of the ten additional characters as the most frequent bigrams or trigrams weaken the code? What better use of these (or any) additional characters would there be?

What you essentially do is compressing the plaintext before encrypting it. If the rotor machine offers a secure encryption, it should be secure for any type of input, including the compressed one. There is, however, a caveat: The ciphertext leaks the length of the plaintext and if you compress the plaintext, you change its length and therefore change what is leaked. Depending on how the encryption is used, this can actually cause problems. See this question.


Can I say "I have encrypted something" if I hash something? As I understand it, a hashing algorithm is some kind of encryption, just a specific kind of it. So is it wrong to say "I encrypted this value." if I "only" hash it?

I understand that it gives the wrong impression, but I think it is not absolutely wrong, or is it?

Encryption algorithms and hash algorithms both belong to the realm of cryptography but are two different things: Encryption doesn't contain hash functions.

As stated on Wikipedia:

  In cryptography, encryption is the process of encoding a message or information in such a way that only authorized parties can access it and those who are not authorized cannot.

An encryption algorithm turns some data into a ciphertext which can later be decrypted again to its original content by using the encryption key.

If you generate a hash of some data it can't be "reversed" back into its original content, because a hash function is (theoretically) a one-way function with loss of data.


Length of ECDSA signature I am using "secp192k1" curve to generate the key for data signing using ECDSA scheme. Signature is generated using "SHA3-256withECDSA" algorithm provided by BouncyCastle.

Theoretically, the length of the signature should be 192*2/8 = 48 bytes. Instead, this length varies from 54 to 56.

My application demands a signature of fixed length. How can I achieve this?

To encode the signature you first have to parse the ASN.1 structure also shown in the linked answers provided by dave_thomson_085. Once you have got two integer in the programming language / runtime of your choice then you need to encode them as two statically sized integer encodings. These integers (usually) need to be big endian / network order, unsigned integers.

To do this you need to implement a function called I2OSP from the RSA specifications. You feed this the two numbers and the key size (the size of the order of the curve) rounded upwards to bytes (that's $192 / 8 = 24$ bytes).

There are two ways to do this:

directly implement the mathematical functions and concatenate the resulting bytes or
encode the integer back to bytes - most platforms have a function for this - and then adjust the encoding by padding and possibly reversing the encoding

The latter is probably faster as it just requires byte operations. I usually opt for the latter, but I've seen many cryptographers (naively, in my opinion) do the first.

Finally you simply concatenate the numbers and presto - you're done (there is also OS2IP in RSA, in case you need to do the reverse).


HMAC256(K,m) vs HMAC256(K,K) I have a key size of 128 bits. My message size is fairly short (e.g., 32 bits - and widely known). Although I am doing a SHA256, the result of the HMAC will be truncated to 128 bits.
So my question is: is there a significant strength difference between the following?

HMAC256(K,m)
HMAC256(K,m||K)
HMAC256(K,K) 'note that in this case, there is no message) - I just need the result of the hash).

I am trying to prevent someone who knows m and the 128-bit result from figuring out the 128-bit key.

So my question is: is there a significant strength difference between the following?

From a theoretical perspective, yes.
Namely the first one requires us to assume that the SHA-256 compression function behaves like a dual-input PRF whereas the last two add the assumption of circular security on-top.
While assuming circular security is not entirely unheard of, it's one of those "non-standard" assumptions (PDF) - because you can't achieve it using only simple one-way functions - and should thus be avoided if it doesn't bring significant gains.

HMAC256(K,m) - Assuming that the SHA-256 compression function is a dual-input PRF (which is very reasonable as this even applies to the MD5 compression function), HMAC-SHA256 is a PRF and therefore when keyed with a uniformly random key any unique (per-key) message will output a value that is indistinguishable from a random string. Relevant papers are these three here.
HMAC256(K,m||K) - This likely has the same security properties as above but you'll also have to assume that HMAC offers circular security (which is not entirely unreasonable but gains you nothing over the first construction).
HMAC256(K,K) - This requires circular security again and because the message is not involved is more likely prone to repeat keys where repetition is unecessary thus potentially allowing easier higher-level attacks.


Activation keys and asymmetric encryption To me it seems that a quite safe way of creating activation keys is by using asymmetric encryption, so that the end-user could only reverse-engineer the validation method. This way the company keeps the generation algorithm (and key) safe.

Assume one uses RSA encryption with 1024 bit keys. They sign some data with the private key and the result is 128 bytes long.

How can he fit this into an activation key that is much shorter than that? e. g. 16 or 20 chars or so.

The validation algorithm must now decrypt with the public key and see if the message is really coming from the company. How is it done when the full cryptographic message is unknown?

Is there an error in my assumptions above or is it in fact done like this?

You can not compress an RSA signature much below the private modulus size. All methods that I know double the cost of either signing or verifying for each extra bit trimmed, after the first one or two which comes nearly for free.

The higher-order bit of an RSA signature can be trimmed: just use a padding scheme such that the padded message $R$ verifies $2R<N$ (the two padding schemes of PKCS#1 have this property); normally the signature would be $S=R^d\bmod N$, but rather use $\tilde S=\min(S,N-S)$, which is at least one bit less than $N$ is. On the verifier side, after computing $\tilde R=\tilde S^e\bmod N$, get back the original $R=\min(\tilde R,N-\tilde R)$.

At the expense of more work, the signer can trim more bits by using a randomized signature scheme (that is, one such that multiple signatures of the same message using the same key are different, because there is randomness in the message representative; an example is RSASSA-PSS of PKCS#1), and signing multiples times until the signature happens to be suitably small (say 16-bit less than $N$ is).

At the expense of more work for the verifier, we can trim still more bits, that the verifier can find by trial and error (says the low-order 24 bits).

So pulling every of these tricks together, the signer will need to make in the order order of $2^{13}$ signatures (I'm assuming the public modulus is chosen on the low side of the interval defined by the modulus size), and the verifiers $2^{23}$ checks (which will remains bearable, especially with $e=3$. Problem is we saved less than 4% (for 1024-bit modulus).

One thing to consider is a RSA signature scheme with message recovery, which squeezes a message in the signature. An example is ISO/IEC 9796-2 which allows about $n-h-16$ bits of message in a signature with $n$-bit public modulus $N$, and a $h$-bit hash; for 1024-bit RSA and SHA-256 that's 94 bytes of message (some of which must be scarified to remains compatible with the tricks above). If there is a message to convey that is near or above that recoverable size, and it does not matter that the message is unintelligible until after the signature has been verified, nothing beats RSA (or Rabin) with message recovery when it comes to compactness.

However, for a really short signature when message recovery won't apply (including when the message to sign needs not be transferred with signature, including e.g. a customer identifier known by the verifier), we need to move away from cryptography based on Integer Factorization

For a long time, the systems giving the shorter signatures have been the Schnorr signature scheme (description and references here), based on the Discrete Logaritm problem, which has $3b$-bit (resp. $4b$-bit) signature for conjectured (resp. proven) $b$-bit security. e.g., for 80-bit conjectured security (sometime compared to 1024-bit RSA), a signature can be 30 bytes.

There are message-recovery variants (references here) which allow to embed a $b$-bit message in a $4b$-bit signature with provable security.

And we can trim some few bits by the same tricks as for RSA, and the same curse that each bit trimmed doubles the effort of one of the signer or verifier.

There's even better, notably Boneh–Lynn–Shacham signature, which approach $2b$-bit signature for $b$-bit security. However, the parameters to use are not easy to find (hence this question), and my understanding is that computational requirements are non-trivial.


Is it possible to generate a 6-digit number using 256-bit encryption? Reading through some documentation on a piece of software, it claims that a 4-6 digit number is created using a 256-bit encryption process for the purposes of access control. The whole process works as follows:

A 4-6 digit "start code" (key?) is chosen by the user and programmed into the client software and into the management software as a new "client software record".
Using the management software, a new access code that will open the client software can be generated by selecting the previously created client software record.

It is clear that the 4-6 digit start code is used to introduce some form of uniqueness to each instance of the client software, and that start code is used to generate the resulting access code which when entered into the start screen of the client software, will allow the software to open.

My question is how could that process be using 256-bit encryption?

One thing which is clear is that there are only 10^6 possible combinations to open the client software thus in theory it wouldn't make much difference whether encryption or hashing is used to generate an access code.

Why such as number only access control is used is beyond the scope of this question. I am aware that this is pretty poor access control for software. Am just intrigued by the claim of 256-bit encryption.

I believe the claim of using "256-bit encryption" is primarily being done for marketing purposes.

Despite the best efforts of industry experts there are many people with a limited understanding of cryptography, and they associate "bigger key sizes" with "better security."  (While this is generally true, it's a very narrow view that excludes many important security factors; besides, key size differences become almost trivial beyond a certain threshold.)  Sadly, that's a surprisingly large number of people.

Marketers know the money coming from people who don't understand the details spends just as well as money from people who do.

So what can you do about it, or what should you do about it?  Perform a security analysis reviewing what the product is capable of, given the facts you have.  Is six digits enough to stop people from guessing in the time limit given them?  Do they have a three-tries-then-lockout mechanism?  What is the value to you of the system they're protecting?  What is your risk exposure should it be violated?  Are there other access controls in place, and should there be?


Is HMAC necessary if the AES ciphertext of a message includes the CRC of the message? I've seen that encrypting an image with AES-CBC then calculating the HMAC-MD5 value for authentication is a somewhat common and sound way to secure data. Alternatively, can I just calculate the CRC of the data, and then encrypt the data+CRC with AES-CBC?

I am concerned about a ciphertext-only attack modifying the data and that data then being decrypted and executed/processed. Can I assume that it is unreasonably difficult to maliciously modify encrypted data in a way that results in the same CRC or modifies the encrypted CRC to match? If that assumption can be made, then is it necessary to also do an HMAC-MD5 calculation of the encrypted data?

In crypto, we like designs that are secure in (most) all use cases. There is a use case of your proposal that is trivially insecure.

Consider the AES cipher run in a stream-like mode (e.g., CTR). Due to linearity of CRC (i.e., $CRC(X\oplus Y\oplus Z)=CRC(X)\oplus CRC(Y)\oplus CRC(Z)$ and the malleability property of stream ciphers, it is very easy to modify the plaintext and then change the CRC so that it will still be correct.

I don't know if non-stream-like modes (e.g., CBC) have issues with your proposed design, but the fact that some modes do should steer people away from it.

So where we are is, the proposal is shown to be trivially insecure for a number of modes. I don't know if it is secure for certain other modes or constructions. So, yes, HMAC (or some other MAC) is necessary even though a CRC of the data is encrypted. In other words, CRC (even though it is encrypted) is not a good MAC.

P.S. you may find this question interesting.


How to use SPHINCS+? Based on the NIST submission it looks like the SPHINCS+-256s algorithm comes in at public key sizes of 64 bytes, private key sizes of 128 bytes, and signature sizes of 29,792 bytes.

What I can't seem to locate (or understand from the submission documentation) are implementation details suggesting how to use it.  For that I have the following questions (all specifically for the SPHINCS+-256s algorithms)

How many signatures can you safely get out of it?
Are the signatures one-time use, or can you sign something and have it verified repeatedly without giving up the private key?  (I'm assuming this is the "stateless" aspect, but want to be certain I'm not misunderstanding it.)
Are there any specific caveats involved?

The protocol I'm thinking of implementing with it would be along the lines of:

Publish the public key, signed with a different signature algorithm.
Retain the secret key.
Sign N messages, post signatures and messages publicly for verification.

What I'm trying to avoid would be the one-time signature aspects of most hash-based signature protocols where you sign something, distribute the thing, then post the solution proving you signed it at some later point while simultaneously making it unverifiable to future parties (since you give up the private information in the process of proving the signature belonged to you.)

Most of this was already explained in the comments but let me summarize this.

a) SPHINCS+ as SPHINCS are stateless signature schemes like RSA or (EC)DSA. You can use the secret key to sign a virtually unlimited number of messages. In practice, you can sign up to $2^{64}$ messages with SPHINCS+ ($2^{50}$ for SPHINCS) without allowing any kind of forgery.

b) Your idea of a one-time signature is wrong. A one-time signature scheme is a signature scheme which allows the user to sign a single (arbitrary) message securely. The resulting signature is a standard signature as you know it from RSA that can be verified by everyone and as often as you want. The limitation of one-time signature schemes is just that you can only use your key pair to sign one message. As soon as you sign two different messages, security drops almost instantly to zero (depends a bit on the setting, but lets ignore this). So, a one-time signature is no interactive protocol. Just think of it as an RSA signature where you are only allowed to use your secret key once.

c) SPHINCS (with and without +) is no one-time signature scheme as a) already states. It internally uses a one-time and a few-time signature scheme. So, you can use it like RSA / (EC)DSA.

[Details]
If you would use a key pair more than $2^{64}$ times (which is almost impossible if you don't rent a massive server farm that does nothing else than signing messages with the same key pair for the next 20 years or so) security will slowly degrade as the probability of using a few-time signature key pair too often increases.
[/Details]

d) There are no specific caveats involved. As stated above, you can use it like any other signature scheme. (Actually, it follows the NIST call so you can see the requirements there...)

e) As there also seems to be some confusion about stateless vs stateful: The difference between stateless and stateful signature schemes is that stateful schemes require the secret key to change after every signature. So, we should rather talk about a secret key state than a static secret key. The crucial point is, a secret key state must not be used twice. This means, you have to make sure that you do not accidentally reuse it (e.g., back-ups are a problem in this case if you cannot recover the last used state somehow). Stateless schemes are actually the "standard setting", i.e., RSA, (EC)DSA are stateless. For hash-based signatures stateless schemes are not trivial to build. They avoid all this trouble with state handling at the cost of worse performance.


Proving that a node is the only child Say I have a graph of messages like this:

   A
   |
   B
  / \
 C   D

By including the parent hash in the message to be hashed I can show that B is a child of A, and C and D are children of B.

For example

Hash("This is message A") = ab3ed
Hash("This is message B + ab3ed") = e4c90
Hash("This is message C + e4c90") = 83e39
Hash("This is message D + e4c90") = 456aa

This way I can prove that C and D are children of B, and descendants of A.

Is there a way I can cryptographically prove that a certain node is the only child ie has no siblings?

Given only the information in the original question, it would be easy for an attacker to calculate generate an arbitrary message E, then calculate the Hash("This is message E + ab3ed") = 31415, and if the system can be tricked into trusting that 31415 is the hash of a valid message, there's no way to prove that E isn't really a valid sibling of B.

This may be why every hash tree implementation I've ever seen doesn't include the hash of the parent in the hash of the child.
Instead, it includes the hash of the children in the hash of the parent.

Say I have a graph of messages like this:

   A
   |
   B
  / \
 C   D

By including every child hash in the message to be hashed I can show that B is the only child of A, and C and D are the only children of B.

For example

Hash("This is message A; its child has hash e4c90") = ab3ed
Hash("This is message B; its children have hashes 83e39 and 456aa") = e4c90
Hash("This is message C") = 83e39
Hash("This is message D") = 456aa

Assuming a cryptographically secure hash, and assuming I somehow get the root hash ab3ed from a trusted source,
This way I can prove that C and D are the only children of B, and B is the only child of A -- i.e., B has no siblings.


Anonymity in end-to-end encryption Considering a scenario of anonymous data transfer between seller and buyer using proxies. If we consider that there are three proxies that are being selected by the buyer to obtain data from different sellers (like in emule), how can we make sure that these proxies do not collude with each other to obtain the copy that is being requested by buyer?

For example, if we use onion routing, then in this case, each of three proxies will have plain-text data at the end, and this plain-text data would be transferred to the buyer. What mechanism should we employ that will prevent the three proxies to collude? If they combine the files, they will get the copy of the same file being requested by buyer.

Thus as a solution, if we use end-to-end encryption, will the buyer and seller remain anonymous to each other?

If the buyer is selecting proxies to use as trusted third parties, presumably the buyer needs to trust that at least one of them is honest and not colluding with the other three.  Therefore, if you need to be sure that they're not colluding, the answer is that the buyer should choose the three proxies to ensure that they're not colluding.

Precisely how to do that depends upon the system and upon what knowledge the buyer has of the proxies.  One scheme is to choose randomly from a list of vetted proxies, and count on the fact that most parties on that list are honest so it's unlikely that you (by chance) happen to pick three that are evil and colluding.  Another is to choose three proxies who have a good reputation or who you have some other reason to trust.  But ultimately, this is not so much a cryptographic question as it is a systems design question for the particular system.

No, end-to-end encryption on its own is not enough to guarantee anonymity.  You need to also use some sort of system designed for anonymity, like Tor, and take other steps to protect your anonymity.


Number message limits of Galois/Counter Mode (GCM) per key In
https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf
page 27,
it is said that

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

I could not find any reason for this. What will happen if I encrypt more than $2^{64}$ messages with the following settings

The same key is used
The tag length is 128-bit
IV length is 96-bit
Unique IV is chosen for each message
Each message has less than 2^32 blocks

What is the attack? What is the security level of my setting...

If you encrypt 264 blocks or more than an attacker can forge encrypted data, i.e. you lose authentication.
Also, be careful about how much total data you encrypt with a key (no matter how many unique IVs are used).  Schneier, et.al. once recommended that with CBC mode you encrypt at most 232 blocks, but with CTR mode you could go to 260 or so blocks due to the fact that you didn't have to worry about reusing IVs with CTR mode like you do with CBC mode (birthday problem).  However, subsequent research suggests that the limit for CTR mode is the same as CBC mode, see this.  However, it depends on how long the data needs to remain secure and your tolerance of risk.  If you want to encrypt data for tape and it needs to be secure for 30 years without being re-encrypted you might want to greatly lower than amount to 220blocks.


Counter Mode (CTR) and mult-CPA I am not sure if Counter Mode (CTR) encryption is mult-CPA (chosen-plaintext attack) secure or not.

CTR mode encryption, instantiated with a secure block cipher, is IND-CPA secure under the usual definition (Bellare et al., 1997; Rogaway, 2011).

The term "mult-CPA" does not appear to be in widespread use, but it's found e.g. in these German lecture slides (Kiltz, 2011).  In the slides, it is defined (on slide 66) in a similar way as ordinary IND-CPA security, except that, instead of just single messages $m_0$ and $m_1$, the attacker is allowed to submit two vectors of messages $M_0 = (m_0^1, m_0^2, \dots, m_0^t)$ and $M_1 = (m_1^1, m_1^2, \dots, m_1^t)$ of length $t$ to the challenger, where the individual messages $m_0^i$ and $m_1^i$ have the same length for all $i$, and receives a vector of encrypted messages $(E(m_b^1), E(m_b^2), \dots, E(m_b^t))$ in return.

The same slides also contain a proof that mult-CPA security, as defined above, is equivalent to ordinary IND-CPA security.  The proof takes the form of a hybrid argument, and essentially shows that, if an attacker can distinguish encrypted vectors of length $t$ in the mult-CPA game with advantage $\epsilon$ over random guessing, then they can also distinguish individual encrypted messages in the ordinary IND-CPA game with advantage $\frac\epsilon t$.


Difference entity authentication and implicit key authentication From the Handbook of Applied Cryptography, in discussions of key sharing algorithms, I see definitions:

Implicit key authentication is when one party is assured that no other aside from a specifically identified second party has the possibility to determine the secret key (§12.2.1).
Entity authentication is when one is corroborated of the identity of another party, and of the fact that this party is alive (active) during the protocol (§10.1).

Somewhat further (§12.6) it is stated that MTI/A0 provides mutual key authentication without key confirmation or entity authentication.

This made me wonder what the difference could be between entity authentication and implicit key authentication aside from the alivelinees property. I see the "specifically identified second party" and "corroborated of the identity of another party" as the same thing. Is this correct or do I interpret things wrong?

In entity authentication, the parties do not necessarily exchange a session key, but authenticate to each other by providing some proof related to their identites. For instance, if one party signs a challenge given by its partner, this party proves its identity.

Implicit key authentication merely guarantees that the partner (with whom you are talking right now, but who could be unidentified) is holding the same key, and no one else is.

Example:

A chooses random $x$ and sends $g^x$ to B.
B chooses random $y$ and sends $g^y$ to A.

Only A and B can know $g^{ab}$, but they do not authenticate to each other. Hence, the protocol provides implicit key authentication but no entity authentication. The above protocol is actually not secure against man-in-the-middle attacks; it merely serves as an separation example.


implementing long term archive encryption Let's say I want to create private archives for the long term (e.g. more than 30 ). The archives' sizes could be anywhere from 1 GB to 30 GB. As far as I understand I could go down two ways:

The first would be for example using plain AES-256 encryption in CTR mode with a random key stored on paper.

The second, more suitable solution for backups, is using the Offline Private Key Protocol, e.g. generate a 4096 bit RSA key pair and encrypt with random AES-256 keys that get stored with the archives (key-wrapping) while the private part is again stored on paper. Kind of like Safeberg does.

My question is which of the two methods would be least susceptible to currently envisioned attacks in the next 30 years, coming from adversaries with resources such as your average government (i.e. not the NSA). What about quantum computing? Additionally I would like to know if there are any other, better alternatives or any improvements that I could make to both ideas without changing their practicality.

Thank you!

The AES solution will fail if either:

the secret key is leaked, or
AES-256 is broken.

The RSA+AES solution will fail if either of the above happens, or if:

RSA-4096 is broken.

Thus, even without considering the relative likelihoods of these events occurring within the next 30 years, it is clear that the AES-only solution cannot be any less secure than the RSA+AES one.

Of course, the RSA+AES solution has the practical advantage that the system performing the bulk of the work (AES encryption of data) need not know your secret RSA key (although they will, of course, still need access to the AES key used to actually encrypt the data, not to mention the data itself).  You will need to decide for yourself whether this extra feature outweighs the risk of complicating your system by introducing an extra point of potential failure.


Does High Frequency Randomisation of valid and dummy messages in a high volume channel add security? This was originally posed as this question: "Does randomisation of valid and dummy messages in a high volume channel add security?"

But due to the reformulation based on answers provided, Tylo (https://crypto.stackexchange.com/users/4082/tylo) suggested it be posed as a new question.

Note that this question is possibly more communications management rather than true cryptography.

Scheme: valid messages in a high volume comms channel are identified by a pre-shared random number sequence interspersed with a large volume of random noise messages. These are ignored by the receiver but can be used to consume the resources of an attacker regardless of the attack mechanism/approach.

Any such arrangement using high volumes of noise must allow the receiver to ID valid messages. A truly random pre-shared number list would appear to be superior to any other sequencing.

Mechanism: Controller A has different RNG'd lists for each of his field agents B to Z. Controller A wants to send a msg to B. He looks up B's list and the next number on that list is 527. He sends 1000 msgs marked to B's attention. All are random noise but msg 527 which is encrypted with the key that A uses to contact B.

B captures all 1000 msgs and decrypts only msg 527. The attacker must attack all 1000 msgs, does not know who the msg is sent to, has 25 different keys to attack (25 agents) and only 1 real message encrypted with 1 real key per 1000 msgs.

For B to contact controller A he looks up his RN list and sees that 641 is the next number. The procedure is the same as A contacting B but made more complex by B using the key that only he uses to contact A. Now the number of keys is 50.

Since the number lists sequencing this traffic are truly random and
cannot be cracked and are never contained in ANY msg or disclosed in any way, then this seems to me to be a useful form of deception that just made the attacker's task 1000 times harder based on volume and 50 time harder based on key variation on top of any decryption difficulty for each key.

Questions: Is this interpretation basically correct?
Is the scheme practical or useful? When used as a mechanism for radio contact it would seem to provide one of the most powerful protections possible: not knowing who is a message receiver (as opposed to someone physically logging in from somewhere to open an email), not knowing if a message is a message, and not knowing any key.

In addition to Paul's analysis, I'd point out that theres a few other issues.  The primary one is that, at best, you have increased the workload of your attacker by a factor of 1000, in exchange for increasing your own work load by a factor of 1000.  Let's say you're using a very poor encryption scheme that's known to be breakable in, say, 2^50 operations.  (after all, that's why you're relying on this obscuration right? because you didn't trust your crypto?)  Now the attacker needs to spend 1000*2^50 2^59.9 operations to crack it.  For the amount of extra resources you applied to send that much extra fluff data, you didn't get very much of a leg up on your attacker.

Worse, if your encryption is as bad as you think it might be, there's no guarantee that the attacker must fully process each message to discard it.  It may be very easy to identify which message is real because you may be able to identify the signature of the broken cryptography in the first place.

Finally, consider that you are absolutely dependent on the quality of your random number generator.  If you have a PRNG like that, and you have resolved all of the synchronization issues that Paul mentioned, you might as well have just used the PRNG to generate a one-time-use pad.  It would give you more security for less trouble.


Practical (and secure) PRGs Does anyone know if there exists a PRG construction which takes as input an (RSA-sized) integer seed and outputs a fixed number of bits? There are number-theoretic PRGs such as the RSA, Micali-Schnorr, and BBB algorithms (see http://cacr.uwaterloo.ca/hac/about/chap5.pdf), but these require one to know both the seed and other parameters used in the construction (e.g., the modulus $n$). I need a construction that only requires the random integer seed as input. I'm aware that I could potentially fix a universal set of public parameters and then just specify the integer seed, but I'd like to avoid that since the parameters would likely need to be refreshed after a certain number of invocations or uses.

Use any DRBG (deterministic random bit generator) in the NIST FIPS (the NIST 800-90 publication series).  Except... don't use Dual EC DRBG, which has serious problems and is likely to be withdrawn.  Use any DRBG in that standard other than Dual EC DRBG.

Or, hash the seed with SHA256, then use AES256 in counter mode to generate output.

Either of those will work fine.

Don't use BBS.  It has major problems (search on this site for other examples).  There is no reason to use any of the number-theoretic PRGs in practice.


Is this a good way extracting randomness from some physical process? Let's say the system has a hardware randomness generator, generating random numbers using a proven truly random process. The distribution of the numbers though, is unknown.

Assume the randomness source generates data blocks $P_1$, $P_2$, ..., $P_n$. There is an one-way function $f(x)$. The output data blocks are $Q_1$, $Q_2$, ..., $Q_n$. There is an initialization vector $Q_0$. The length of $P_n$ blocks, $Q_n$ blocks, $Q_0$, input and output block length of function $f(x)$ are all equal.

For each output block $Q_n$, there is:

$$
Q_n = f(P_n \oplus Q_{n-1})
$$

Questions:

Can the process above extract the randomness from the hardware source, given a proper $f(x)$ and $Q_0$?
What is the requirement for the one-way function $f(x)$ and the initialization vector $Q_0$ for this process to work properly?
Can I replace the $\oplus$ with something else without breaking the randomness? (Replacing it can allow me to relax the block length restriction.)
Can I extend this method into combining multiple randomness inputs?

If hash collisions of f don't exist then information is neither created nor destroyed by f and $f(Q_{n-1}\oplus p_n)$ has as much entropy as $Q_{n-1}\oplus p_n$ which has as much entropy as $p_n$. If (for example) $p_n$ only introduced one bit of entropy then someone with $Q_{n-1}$ and access to the same randomness source can deduce the only two possible values for the next hash.

By "extract randomness" I think what you mean is that all blocks of P should have as much entropy as there are bits in P? A good hardware random number generator should already do that. If it doesn't then bits must be destroyed to turn them into entropy. Either $P_n$ gets mapped onto a space of fewer bits or you take multiple instances of $P_n$ and compress them into one. For example you could use the central limit theorem to take several samples from your unknown distribution and generate a normal distribution. Then you can turn the normal distribution into a uniform one.


Could an HMAC be used as a hash? MD5 is considered broken and SHA-1 is closely following, but HMACs built around either are still considered relatively secure. It makes me wonder if MD5 and SHA-1 HMACs can be used as secure hashes.

Settle on some constant $C$ that will serve the role of $K$.
Define a new hash algorithm as $H_C(x)=HMAC(C, x)$.

Could this work?

HMAC remains unbroken with MD5 and SHA1 because it has a secret key that the attacker doesn't know. Therefore, the attacker cannot carry out huge computations on itself (as is required for finding collisions). [A parenthetic comment: please do not misunderstand me; MD5 is completely broken and should not be used anywhere including in HMAC.] In contrast, when you fix the HMAC key and make it public, you can once again find collisions. In fact, the specific collision-finding algorithms that we know for MD5 and SHA1 (via differentials) work for any IV. When using a key for HMAC that is known, this just gives a different IV. Thus, there is no problem whatsoever finding a collision (in practice, given known methods; not just theoretically).

The solution to SHA1 being broken is to move to SHA256 (and later to Keccak after some more validation time).


How does TLS_FALLBACK_SCSV help? After reading through https://tools.ietf.org/html/draft-ietf-tls-downgrade-scsv-0, I could understand that this option is recommened for use when one has legacy SSL Servers which only support SSLv3.

But could not understand how this option helps even after reading couple of articles.

Can anyone help me in understanding this?

In a better world, TLS_FALLBACK_SCSV would not be necessary: SSL has been supporting downgrade-proof version negotiation since at least SSL 3.0, so a man in the middle should never be able to limit a connection to a version older than the mutually supported maximum.

However, out there are some broken servers that don't really support that kind of version negotiation; simply receiving an unknown, i.e. newer, version number, or unknown TLS extensions in a ClientHello causes them to crash. (Compliant servers would not crash, but simply tell the client that they want to use a lower version of the protocol; the connection would be established using the highest mutually supported version.)

Ideally, clients would simply refuse to connect to such broken servers; the problem would be swiftly fixed by the server vendor, and proper version negotiation would be restored.

As it turns out, quite a lot of server vendors or administrators couldn't be bothered to do that. Many browsers will now try to fix the problem on their end by connecting using a "legacy" ClientHello that doesn't trigger the buggy server behavior, which is essentially a second connection attempt using only SSL 3.0.

Unfortunately, this opens up an attack possibility for a man in the middle: By simply suppressing client connection attempts using new TLS versions to the server and simulating a buggy server response to the client, they force an SSL 3.0 connection attempt; the connection using SSL 3.0 will eventually be established, with the server thinking that the client uses a really old SSL library, and the client thinking that it is talking to a buggy SSL-3.0-only server.

Essentially, TLS_FALLBACK_SCSV allows clients to send a hidden version number in the downgraded connection attempt in a way that doesn't trigger the server bugs.

Informally, the conveyed message might be interpreted as follows:

  Hey Server, even though I only claim to support TLS version $x$ in the version header, I actually support TLS versions up to $y$. If you support anything better than $x$, this means that there is something sinister going on here!

Practically, the backwards-compatible signal is a special "dummy" cipher suite that will be ignored by servers not supporting fallback prevention (whether they are broken SSL 3.0 or fairly recent TLS 1.2 servers).

Only servers supporting the draft specification will be able to interpret the signal and act accordingly; older servers will simply think that the client supports some additional cipher suites that they don't know about, and will continue the handshake as usual.


Is the reduction from left-or-right IND-CPA to real-or-random IND-CPA tight? A modern trend in cryptography consists of defining security as rigorously as possible, and then designing schemes which are secure according to those definitions. Proving security comes in the form of reducing one scheme to a more basic problem or scheme. Furthermore, there are many different ways of formalizing security, and equivalence between security definitions is shown via reductions as well.

The concrete security approach for reductions, as introduced by Bellare, Desai, Jokipii, and Rogaway in FOCS '97,  moves away from polynomial reductions and instead focuses on finding concrete bounds, so as to provide a more nuanced view of security. They discuss various formalizations of security for symmetric encryption schemes, including indistinguishability under chosen plaintext attacks (IND-CPA). Two variants of IND-CPA they come up with are left-or-right (LoR) and real-or-random (RoR), which they prove to be equivalent in the following sense:

Let $\mathcal{E}$ be an encryption scheme. For all adversaries with time complexity $t$ making at most $q$ queries to $\mathcal{E}$ totalling at most $\mu$ bits,
$$\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu) \le \mathbf{Adv}_{\mathcal{E}}^{\text{lor-cpa}}(t,q,\mu) \le 2\cdot\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu)\enspace.$$
Note that the bound on the right-hand side includes a factor 2. There are encryption schemes for which the factor of two is absent. For example, for the identity function we have that $\mathbf{Adv}^{\text{ror-cpa}}(t,q,\mu)$ approaches $\mathbf{Adv}^{\text{lor-cpa}}(t,q,\mu) = 1$ for $\mu\to\infty$,
which leads me to my question.

  Does there exist an encryption scheme $\mathcal{E}$ for which  $$\mathbf{Adv}_{\mathcal{E}}^{\text{lor-cpa}}(t,q,\mu) = 2\cdot\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu)\ ?$$

Here's an artificial example:  Start with some secure encryption scheme with encryption function $\mathcal{E}(\cdot)$, and construct a new scheme with encryption function $\mathcal{E}'(\cdot)$, which for any input message $m$ copies the first bit, $b$, of the message, and outputs $b||\mathcal{E}(m)$, where $||$ denotes concatenation.

For such a scheme, there exists a LoR adversary $\mathcal{A}_{lor}$ with Advantage 1 using only one query.  $\mathcal{A}_{lor}$ merely has to submit a query $(m_0,m_1)$, where $m_0$ starts with a 0 and $m_1$ starts with a 1.  Assuming wlog that the Challenger has a coin $c$ and returns the ciphertext $\mathcal{E}'(m_c)$, $\mathcal{A}_{lor}$ then bases its guess for the value of the Challenger's coin on the first bit of the returning ciphertext (i.e. for a returning ciphertext with first bit $b$ it outputs the guess $c = b$).  This guess will always succeed, because with such a query, the first bit of the ciphertext does indeed equal the Challenger's coin $c$.

However, the RoR advantage for any adversary similarly restricted to just one query can be no greater than $1/2$ (again assuming that the underlying scheme we started with is secure).  Because the underlying scheme is secure, any adversary $\mathcal{A}_{ror}$ must base its guess entirely on the first bit of the resulting ciphertext and whether that first bit is equal to the first bit of its query.  Wlog we can assume $\mathcal{A}_{ror}$ submits a query $(q)$ with the first bit set to 1.  If the output ciphertext starts with a 1 then $\mathcal{A}_{ror}$ guesses the Challenger is running the $Real$ oracle, and if the output starts with 0 it guesses the Challenger is running the $Random$ oracle.

Recall the definition of the RoR adversarial advantage function,

$$\mathbf{Adv}^{ror-cpa}_{\mathcal{E}',\mathcal{A}_{ror}}(k) = \Pr[\mathbf{Exp}^{ror-cpa-real}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] - \Pr[\mathbf{Exp}^{ror-cpa-random}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real].$$
If the Challenger is running the $Real$ oracle then the first bit of the output ciphertext will be a 1 with probability 1, and so $\Pr[\mathbf{Exp}^{ror-cpa-real}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] = 1$.  However, if the Challenger is running the $Random$ oracle, then it will return the ciphertext $\mathcal{E}'(*)$ for some random string $*$ equal in length to the query $q$.  The first bit of $*$ will be a 1 with probability $1/2$, and so $\Pr[\mathbf{Exp}^{ror-cpa-random}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] = 1/2$.

As such, for adversaries restricted to one query, the maximum RoR advantage versus $\mathcal{E}'$ is half the maximum LoR advantage.


How to formally prove that random guess is the best attack How to formally argue that there exists no efficient $A$ who can come up with a $e$ such that $$\begin{align}x&=PRF(e,0) \land \\ y &= PRF(e,1) \land \\ x &= H(y)\end{align}$$ where $H$ is a secure hash function and $|x|=|y|=\ell$?
Note that it's easy to argue that if $A$ just guesses randomly, the success probability for each guess is negligible (something like $\frac{1}{2^{\ell}}$). But how to argue there is no better algorithm than guessing?

But how to argue there is no better algorithm than guessing?

Show that, if there is a better algorithm than guessing, you can distinguish the PRF from random.


Can somebody help me understand RC4 Spritz? (Three Questions) So ever since I first took a stab at understanding stream Ciphers, not one stood out more than RC4, because it's so fantastically simple. As most people reading this will know, with its fantastic simplicity comes with easily done cryptanalysis and RC4 has certainly been subject to plenty of it (leading to RC4's total failure, more or less).

Now, when breezing over the wikipedia article on alternative constructions of the PRGA stage of RC4, we get this rather neat little alteration, dubbed spritz:

#// All arithmetic is performed modulo 256
while GeneratingOutput:
    i := i + w
    j := k + S[j + S[i]]
    k := k + i + S[j]
    swap values of S[i] and S[j]
    output z := S[j + S[i + S[z + k]]]
endwhile

Now a bunch of things spring to mind about this alteration (that is seemingly far stronger, albeit, unfortunately much slower) but what's at the forefront of my mind is:

THREE Specific questions I'd like to know the answer to are:

Can we safely assume that from any given setup of S[], we can get to another set up of s[]? Or does it follow, that there will be some impossible states, like the Finney States of RC4?
Can anybody actually link me to any paper attempting any cryptanalysis of spritz, being as a DRBG, Stream Cipher or Cryptographically Secure Hash?
Finally: I know the question should be more specific: But given it's similarity to RC4? How many problems from RC4 could we expect to pop-up in Spritz?

There's a few questions here, the reality is I'd be grateful to get an answer on any of these, as papers on this algorithm, don't seem to be an easy google search away... but my own limited tests (and thought experiments), make me think we're certainly onto a better version the PRGA for RC4 (apart from the fact, it's 40-50% of the speed).

All input appreciated!

(edit: I removed the question about what values of W can we use: the answer is 1..3..5..7, up to 255, presuming the range of S, is 256)

The reference definition of Spritz seems to be: Ronald L. Rivest and Jacob C. N. Schuldt, Spritz - a spongy RC4-like stream cipher and hash function, presented at Charles River Crypto Day (2014).

The code snippet of the question shows how the state of Spritz repeatedly used in DBRG output mode is updated and its next output byte $z$ produced; the state being permutation $S$ coded as $N=2^8$ distinct bytes, and byte variables $i$, $j$, $k$, $z$  (in the context $w$ is a constant odd byte depending on input of the DBRG).

It seems highly unlikely that this code snippet cycles over all the $256!\times2^{4\times 8}\lesssim2^{1716}$ states, or even the $256!\times\lesssim2^{1684}$ values of permutation $S$, for the expected maximum cycle length of an iterated random mapping of a set of size $s$ is $\approx0.7825\sqrt s$. This however is not a proof.

The above leaves entirely open the possibility of analogs to Finney states of RC4 (states that would give RC4 a very short period). It seems quite plausible that there exists such short cycles, and that (contrary to Finney states for RC4) they could be reached for some inputs to Spritz used in DBRG mode. However the design of Spritz strives to make it computationally impossible to reach a desired state, thus exhibiting a state giving a short or moderate cycle (which seems quite possible) would not by itself qualify as a break of Spritz.

I found two reports of cryptanalytic attempts, but neither claims to be even close to practical for the full Spritz, or even practical for a drastically reduced version (with $N=32$ instead of $N=256$ , that is $\approx2^{320}$ potential states instead of $\approx2^{1716}$ ).

Bartosz Zoltak, Statistical weakness in Spritz against VMPC-R: in search for the RC4 replacement (IACR Cryptology ePrint Archive, 2014-12); this claims a distinguisher for a reduced Spritz with $N=16$  (that is, $\approx2^{60.25}$ states) using $\approx2^{41.4}$ bits of output. The attack is not claimed to break the full Spritz ( $N=256$ ) better than the distinguisher for $\approx2^{89}$ output bits acknowledged by the designers.
Ralph Ankele, Stefan Koelbl and Christian Rechberger, State-recovery analysis of Spritz (IACR Cryptology ePrint Archive, 2015-08); the attack is acknowledged to be entirely impractical for the full Spritz (time $2^{1400}$, reducing to $2^{99}$ for $N=32$ ).

Spritz is designed with the intend to fix the known issues in RC4, and I know knew no reason why the techniques used towards that goal would fail.

Update: there is now a true attack on Spritz: Subhadeep Banik and Takanori Isobe, Cryptanalysis of the Full Spritz Stream Cipher, in proceedings of FSE 2016.


What's the actual difference between RSA encrypting and Descrypting and RSA Signing? this question arised because I'm working with Windows' CNG library and it has 4 functions for RSA:

BCryptEncrypt (private key, message)
BCryptDecrypt (public key, message)
BCryptSignHash (private key, hashed message)
BCryptVerifySignature (public key, signature, hashed message)

So I was wondering, is there any difference between "Encrypting + Decrypting" and "Signing + Verifying"?
I mean, if I hash the message and then encrypt it, wouldn't that be the same as Signing it? or Am I missing some logic that is behind that function? (talking about RSA in general, not about how windows' CNG work).

The only visible difference I see is:

For Encryption and Decryption I can use OAEP and PKCS1 padding.
For Signing and Verifying I can use PKCS1 and PSS padding.

But again, is this because of how those functions are made in this library? or because the "operation" and the output are done in different ways depending on if it is Signing or Encryption?

If they are different, then why do we need the Signing part? Isn't encrypting with private and decrypting with public secure enough to "sign" it?

So I was wondering, is there any difference between "Encrypting + Decrypting" and "Signing + Verifying"?  I mean, if I hash the message and then encrypt it, wouldn't that be the same as Signing it?

First of all RSA or any public key is not preferred for encryption, we prefer a hybrid-cryptosystem where a key is transferred/exchanged with public-key cryptography and the message is encrypted with a symmetric encryption scheme with the transferred/exchanged key.

RSA encryption to be secure requires a padding scheme like PKCS#v1.5 or OAEP. The letter is preferable since there is a security proof. The modulus size prevents you from encrypting arbitrary sizes so you need to encrypt a message dividing part like in block ciphers then perform the slow encryption many times.

RSA signature with PSS requires hashing not only for the security but for the message size. There is also RSA Full Domain Hash (FDH) Signature that hashes and signs and it has existentially unforgeable under adaptive chosen-message attacks.

If you hash a message then encrypt, then except you, nobody can verify the signature. You need to use your private key for signatures even for RSA-FDH. Keep in mind that it is not advisable to use a key for both encryption and signatures.

So the main difference in encryption vs signature is the used key and padding requirements. If you encrypt a message without padding you will have many attacks like it is malleable and see more here Twenty Years of Attacks on the RSA Cryptosystem

  But again, is this because of how those functions are made in this library? or because the "operation" and the output are done in different ways depending on if it is Signing or Encryption?

Yes, the operations are done differently since they require different padding to be secure.

  If they are different, then why do we need the Signing part?

Because they are different so one needs different functions. Even if they are the same one still needs these functions to remove the ambiguity. Think about there is only encrypt and decrypt functions and the developers need to tell everyone to use decryption for signature and encryption for verification. Some people will use the encryption for the signature that will reveal unwanted information. Unfortunately, this is due to the RSA that has both encryption and signature.

  Isn't encrypting with private and decrypting with public secure enough to "sign" it?

No, you need hash then sign for RSA-FDH and hash and apply PSS then sign.

signature = RSA-FDH(Hash(message))

of

signature = RSA-PSS(Hash(message))


Combining public key signature schemes and private key encryption I'm working on my bachelor thesis and I have some questions.
I want to combine a CPA-secure private key encryption scheme and some unforgeable public key signature scheme (in my case some sanitizable signature scheme but I think it doesn't matter). The resulting scheme should be CCA-secure.
How can I do that?

If I use a MAC instead of the signature scheme, I get a CCA-secure scheme, but I have to use signatures, since I'm in a juristic context.
I tried to combine both schemes them by signing the message and then encrypting the signature together with the message. But I struggle with proving that such a scheme is CCA-secure. CCA Security is only defined for private-key encryption schemes or public key encryption schemes but I have to prove it for the combination of priv key encr. and pub key signatures.

So my questions are:

How can I combine an unforgeable Public key signature scheme with a CPA secure private key encryption scheme, such that the resulting scheme is CCA secure?
How can I prove CCA Security for such a scheme, since it is not defined?

I tried to combine both schemes them by signing the message and then encrypting the signature together with the message. But i struggle with proving that such a scheme is CCA-secure.

I believe that the reason you're running into issues proving that is that CCA-secureness of this system doesn't actually follow from the CPA-security of the cipher and the unforgability of the signature.  That is, you could design a CPA-secure cipher that, with unforgable signatures, that the system is not CCA-secure.

Consider a CPA-secure encryption where the attacker can modify the ciphertext in a way such that the decryption of the modified ciphertext might result in the original plaintext, or might not (and whether it does or not would give the attacker information on the secret key).  CPA-secure allows such a vulnerability, as it doesn't consider modified ciphertexts.

It's fairly obvious how a CCA-attacker would break such a system; they would modify the ciphertext, and give it to the decryption oracle.  The decryptor would first recover the signed plaintext; if it was the original signed plaintext, then the signature algorithm would accept it (because it's not a forgery if it's bitwise identical to a previously signed text), and so the decryption oracle would emit the plaintext.

You could place additional constraints on the CPA-encryption to ensure this doesn't happen.  However, a better approach (both from a provability standpoint, and from an implementation standpoint) is to reverse the order of operations; first CPA-encrypt the plaintext, and then sign it.  I believe you'll find that easy to prove CCA-secure.


How does SafeNet MobilePASS generate passwords? We use MobilePASS at work but the latest version of the android client seems to be buggy so I wanted to have a go at implementing the algorithm myself.

You can download the client to play with here: http://www.safenet-inc.com/support-downloads/mobilepass-download-page/

It looks to be based on the HMAC-SHA256 OTP algorithm. The client provides the user with the secret key when creating a new token which is copied into a web interface server side.

The bit I'm unsure about though is the pin. It looks like this is also included in the process but I'm having trouble determining exactly how.

Is there a standard way of extending HOTP to include a pin?

So I was finally able to work this out. The pin code isn't important and is simply used to decrypt the activation code locally (not sure why our server asks for it in that case).

The activation code is a base32 encoding of a seed where every fifth character acts as a checksum for the previous four.

The seed is then passed through KDF1 to generate the shared secret.

That is then in turn used as part of the HOTP algorithm.

You can see my reimplementation in python here: https://github.com/datr/MobilePASSER/blob/python/mobilepass.py


Altering the message space of Paillier Is there any obstacle if we restrict in Paillier the plaintext values to be drawn from $\mathbb{Z}_N^*$ instead of $\mathbb{Z}_N$ as the original scheme indicates.

Nope, you can always restrict your message space to a subset of the message space for which the scheme is defined (which is the case here).

Note that in practice you will deal with messages relatively prime to $N$, i.e., from $\mathbb{Z}_N^*$, anyways (any message not coprime to $N$ - except zero - would allow you to factor $N$ - thus its very unlikely to hit such a message).


Rabin-Williams, blinding and size of Integer r? I was reading the paper Breaking the Rabin-Williams digital signature
system implementation in the Crypto++ library. The library uses blinding, but it was not enough to stop key recovery.

But my question is about the Integer r used for blinding. Crypto++ uses a random integer in the range [1, n-1]. Then, the operation proceeds by calculating m * r (mod N); (m * r)d (mod N); and finally (m * r)
d * r-d (mod N) = md (mod N). If n is 3072 bits, then r is effectively 3072 bits.

Since r needs to provide a mask at an equivalent security level of 128-bits, wouldn't a 256-bit integer suffice to mask the operation? In this case, its 128-bits times 2 because there's a 50/50 chance of selecting a 0 or 1. So someone trying to build a system of equations to deduce bits in the private key would need a table at least 2128 in size.

Is there criteria in selecting the size of the blinding integer r for Rabin-Williams? Or is it convention (or required) to always use the size of the modulus?

Blinding is usually applied on the whole modulus, and I see no incentive to do otherwise; random is cheap.

In RSA, blinding is not always applied as described in the question and article, for efficiency and security reasons: the technique described requires computing $r^d\bmod N$, which is just as costly as the $m^d\bmod N$ operation being protected, and involves the private key, which could be a security issue. Rather, the archetypal (external) blinding goes:

draw random $r$;
compute $\hat r=r^e\bmod N$, the blinding factor (since $e$ is typically short compared to $d$, this is much less costly than computing $r^d\bmod N\;$; further, only the public key is involved in computing $r^e\bmod N$, therefore a successful side-channel attack here can't directly endanger the private key);
compute $\hat m=m\cdot \hat r\bmod N$, the blinded message (or signature);
compute $\hat c=\hat m^d\bmod N$, the blinded result;
compute $r'=r^{-1}\bmod N$, the unblinding factor;
compute $c=\hat c\cdot r'\bmod N$, the result.

If $r$ was reduced from the width of $N$ to say $256$-bit:

it would be proportionally less trouble to generate, but that's almost a non-issue in modern security environments, where random is relatively cheap (precisely to enable blinding and masking techniques);
there would be a problem with very small $e$ like $3$, where $\hat r$ would not have all its bits random; we'd have at least a worry making a convincing argument that this is not a problem w.r.t. power analysis and timing attacks;
when there's not this problem, the saving in step 2 would be marginal at best; in any case, step 4 dominates all the others for common $e$ like $e\le2^{16}+1$, or even random $e$ as sometime practiced (typically $e<2^{(2^k)}$ with $k\in\{5,6,7,8\}$; see footnote for unusually large $e$);
we'd save in step 5, significantly relative to step 5, but overall negligibly;
we'd have at least a worry making a convincing argument that $r'$ is unpredictable enough for our blinding purposes.

So all in all there's no appreciable saving reducing the width of $r$, it can only make attacks even so slightly easier, so why bother?

Footnote following comment: computing $r^d\bmod N$ for narrow $r$, rather than wide $r$, can indeed make a difference (like a saving of $1/3$ on this operation) if we use left-to-right scanning of the binary expression of the exponent; because then, while computing $r^d\bmod N$, about one in three modular multiplications is by $r$ (other faster modular exponentiation techniques do not allow so much saving). If we indeed use this exponentiation method and compute $r^d\bmod N$ (or compute $r^e\bmod N$ for unusually large $e$), narrow $r$ would be a saving worth consideration, saving up to about $1/6$ of the overall execution time for large size of $N$, and I do not immediately see that it would cause a security issue.


Breaking One Time Pad with CCA I was taught that:

although OTP is CPA secure, it is not the case with CCA.

I'm trying to figure how to break OTP with CCA by showing how it fails the IND test.

Note: Saw this answer, but didn't manage to extract a proper proof.

So according to the test, the attacker chooses two messages m1, m2 of the same length, and sends them for the tester.
In the next stage, the tester privately creates an encryption key, randomly chooses which message to encrypt, and returns c* which is the chosen message encrypted.
Now, the attacker is able to use his chosen-ciphertext capability and decrypt any message he wants to (maybe messages - I'm not sure about this detail), as long as his chosen message is not c*, in order to guess which message was encrypted (m1 or m2).

What I already thought of:

Maybe we could split c* apart, decrypt both parts and concatenate.
Or we could also add a 0 in the end of c* and then decrypt the result.

But both methods wouldn't work since the key is in the length of the original message - so it cannot decrypt messages in other lengths.

So I add a condition of which the attacker can only decrypt messages in the same length of c* (and the original messages, obviously).

So now I thought about decrypting c* but replacing the last bit to 0.

Assume c* length is n, so the in the encrypted result, denoted as r*, I know the first n-1 bits are of m1 or m2, except for the last one, so I'd distinguish between the messages by comparing the n-1 bits with each of them (of course that'd require sending different messages for the test).

I feel like I'm missing something but can't figure out what exactly.

Does anyone have better example of breaking OTP with CCA, or can justify my answer?

P.S. Just a clarification: I assume of course that key is replaced in each encryption (but it doesn't matter here because decryption is done with the same key).

It's actually fairly straight-forward; the attacker knows $m_0$, $m_1$, and the challenge ciphertext $c = m_r \oplus s$, for an unknown bit $r$ and an unknown string $s$; his job is to recover $r$.

One thing he can try is selecting an arbitrary ciphertext $c'$ (which needs to be distinct from the challenge ciphertext, but can be anything else of the same length), and ask for it to be decrypted.  The decryption is $m' = c' \oplus s$; he can then recover $m_r = c' \oplus m' \oplus c$; he can then compare $m_r$ to $m_0$ and $m_1$ to deduce $r$.


Proof of concept for RSA malleability I'm trying to see how easy RSA malleability is.

I generate 2 ciphertexts with a public key:

cat file1 |  openssl rsautl -raw -encrypt -pubin -inkey public.pem >messageA.encrypted
cat file2 |  openssl rsautl -raw -encrypt -pubin -inkey public.pem >messageB.encrypted

Where file1 and file2 are filled with '1's and '2's resp. I assume -raw means no padding schemes. The files are 256 bytes and the keypair is a plain openssl generated RSA keypair of 2048 bits.

Then I read the files per byte and NAND them with a python script:

with open("messageA.encrypted", "rb") as f1, open("messageB.encrypted", 'rb') as f2, open("messageC.encrypted", "wb") as fb:
for i in range(256):
    b1 = f1.read(1)
    b2 = f2.read(1)
    out = (~ (b1[0] & b2[0]) & 0xff) # simple '~' is not enough
    outByte = out.to_bytes(1, 'big', signed=False)
    fb.write(outByte)

Afterwards I try to decrypt the file, however it fails as follows:

openssl rsautl -raw -decrypt -in messageC.encrypted -inkey private.pem
RSA operation error
139710772687296:error:04065084:rsa routines:rsa_ossl_private_decrypt:data too large for modulus:../crypto/rsa/rsa_ossl.c:411:

where file "messageC.encrypted" has a size of 256 bytes

Am I wrong to have expected the above to at least to not fail during decryption?

/update, I would have expected the 'O' (capital 'oh') to be in the decrypted "messageC.encrypted".

NAND is not the appropriate combiner for RSA malleability , and can causes the issue observed by making what's produced larger than the public modulus $N$.

RSA malleability applies to textbook RSA, where encryption goes $$x\to \text{Enc}_{(N,e)}(x)=x^e\bmod N$$ and malleability is the property $$\text{Enc}_{(N,e)}(x_1\cdot x_2\bmod N)=\text{Enc}_{(N,e)}(x_1)\cdot\text{Enc}_{(N,e)}(x_2)\bmod N$$ where $\cdot$ stands for integer multiplication (just nothing to do with NAND).

Verifying this with plaintext consisting of files with bytes containing 1 and 2 requires extracting $N$ from the public key, and large-integer arithmetic modulo $N$.


Find the prime factorization in the DLP Suppose we have $g^x \equiv h \pmod N$ Where $N = pq$ and $p$, $q$ are distinct primes. Also $(p-1)/2$ and $(q-1)/2$ are primes.

If we know what $x$, $g$ and $h$ are, is it possible for us to know what $p$ and $q$ are?
I'm trying to find out but I'm running into closed doors.
I tried the following:
 $gcd(p-1 , q-1) = 2$
$g^{(p-1)(q-1)/2} \equiv 1 \pmod {pq}$
so $1 \equiv h^{(p-1)(q-1)/2} \pmod {pq}$

Any help is appreciated.

As a hint, suppose we pick a random $h$, and compute $g = h^3 \bmod N$.  We then find the minimal value $x$ where $g^x \equiv h \pmod{N}$ (and, yes, such an $x$ will exist, assuming $p, q > 7$).

What can we deduce from such a value of $x$?


How would Keccak attain a 512-bit security level? I am well aware that the general consensus is that a hashing algorithm with a security of 512 bits is unnecessary, but I'm just curious about how that would be implemented for Keccak despite that.

According to SHA-3 block sizes / bitrate calculation?, the bitrate of the algorithm would be calculated by 1600 - 2c = r. However, with C being 1024, one would get a negative value, which I assume would mean the algorithm will not work for that capacity.

Am I wrong in my assumption? Are there any workarounds that would allow for a capacity this high?

Again, this is just a theoretical question to sate my curiosity. I am well aware that such a level of security is considered unnecessary.

The highest capacity possible is 1599, which means you repeat the permutation for every bit you enter into the state.

For a ‘512-bit security level’ (which is (completely meaningless)^2, since a 256-bit security level is already past the threshold of meaning), it suffices to choose capacity 1024 and digest length 1024 to thwart all generic classical and quantum attacks limited to $2^{512}$ cost.

The SHA-3 parameters for the fixed-length functions SHA3-256 etc. were overdesigned partly out of paranoia and partly for political reasons.  The XOFs SHAKE128 and SHAKE256 were more reasonably designed to give a 128- or 256-bit security level, respectively, assuming adequate output length; if ‘SHAKE512’ existed it would use capacity 1024.