#StackBounty: #rsa Security of RSA variants with $e=n-2$ and $e=n$

Bounty: 500

RSA as defined by PKCS#1v2.2 allows public exponent $e=n-2$. And textbook RSA was born with $e=n$ (see second bullet here).

Are these variants essentially as secure as (textbook) RSA with fixed $e$? With random $e$? Can we reduce the security of one to the security of the other, or of another variant of RSA?


Note: as in RSA with fixed $e$, we choose $p$ and $q$ large random distinct secret primes. And further:

  • for $e=n-2$, it must hold $gcd[q-2,p-1]=1$ and $gcd[p-2,q-1]=1$ ;
  • for $e=n$, if must hold $min(p,q)$ does not divide $max(p,q)-1$.


Get this bounty!!!

#StackBounty: #rsa #key-generation #accumulators Criteria for public modulus of RSA accumulator

Bounty: 500

What are criteria for generation of an RSA public modulus used in an RSA accumulator, and their rationale? Are there special requirements in some sub-cases, like for «one-way» accumulators?


Josh Benaloh and Michael de Mare’s One-way accumulators: A decentralized alternative to digital signatures, in proceedings of Eurocrypt 1993, prescribes the public modulus to be a rigid integer. That’s defined as $,n,=,p,q,$ with $p$ and $q$ safe primes and $,|p|,=,|q|,$ (equal bit size). Then $,n=(2p’+1),(2q’+1),$ with $p$, $p’$, $q$, $q’$ (large) primes. The subgroup of quadratic residues of $mathbb Z_n^*$ has order $n’=p’,q’$. And the function $e_{n,y}(x)underset{text{def}}=x^ybmod n,$ is a permutation of this group when $gcd(y,n)=1$. The authors argue:

Thus, if the factorization of $n$ is hidden, “random” exponentiations of an
element of this group are extremely unlikely to produce elements of any proper subgroup. This means that repeated applications of $e_n(x,y)$ are extremely unlikely to reduce the size of the domain or produce random collisions.

More precisely, what kind of disaster can strike if we used random primes? Is there a positive security argument relying on safe primes? Also, is there a justification for $,|p|,=,|q|,$ beyond getting $,|p|approx|q|,$, which helps against ECM factorization?


What about the different recommendations in Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic’s An Efficient Dynamic and Distributed RSA Accumulator (arXiv), 2009), originally in proceedings of ISC 2002? They ask strong primes without justification, referencing the HAC’s definition:

A prime number $p$ is said to be a strong prime if integers $r$, $s$, and $t$ exist such that the following three conditions are satisfied:
 (i)    $p−1$ has a large prime factor, denoted $r$;
 (ii)   $p+1$ has a large prime factor, denoted $s$; and
 (iii)  $r−1$ has a large prime factor, denoted $t$.

When the application is RSA signature and encryption, these requirements are obsoleted¹ by the need to dimension $,n,=,p,q,$ for resistance to GNFS. Are these requirements appropriate in the case of RSA accumulators, and if so for what quantitative meaning of large?


¹ FIPS 186-4 appendix B.3 drops these requirements for 1024-bit or larger primes, and that seems conservative. There’s a discussion in Ronald L. Rivest and Robert D. Silverman’s Are ‘Strong’ Primes Needed for RSA?, but it does not consider the interest of (i) and (ii) in multi-target attacks, where the adversary’s goal is to factor any of many public moduli.


Get this bounty!!!

#StackBounty: #rsa #discrete-logarithm #trapdoor RSA like trapdoor permutations in Discrete logarithm

Bounty: 50

In RSA, given only $(n,e)$, where $n =pq$ and $e$ is the public exponent, it is hard to find $p$ and $q$. It also seems hard to find $d$. So we came up the RSA conjecture that is RSA defines a trapdoor one-way permutation. Namely, given, $N,e$ defining $f,x mapsto f(x)$ is easy; $y mapsto f^{-1}(y)$ is hard; but $f^{-1}$ is easy given $p,q$ (or $d$).

In their lecture notes Goldwasser and Bellare, claims that;

Note that this trapdoor is a property the discrete logarithm problem did not have.

They have a trapdoor ( actually backdoor), at least since 92′ the Gordon’s work;

Designing and Detecting Trapdoors for Discrete Log Cryptosystems. The abstract;

Using a number field sieve, discrete logarithms modulo primes of special forms can be found faster than standard primes. This has raised concerns about trapdoors in discrete log cryptosystems, such as the Digital Signature Standard. This paper discusses the practical impact of these trapdoors, and how to avoid them.

and many, some listed in Is it possible to generate backdoored DH parameters?

So the question is

  • Is there proof of Goldwasser and Bellare’s claim that is discrete logarithms cannot have trapdoor permutations?
  • if not, the lecture notes are written in 2008, is there any advancement on this?


Get this bounty!!!

#StackBounty: #rsa Where is RSA-KEM used as of 2020?

Bounty: 100

RSA-KEM is introduced by Yuliang Zheng and Jennifer Seberry

and compared the security against OAEP variant by Jakob Jonsson, in 2002

I’ve found some documents that may indicate the usage of RSA-KEM in the wild.

What are the noticeable usage of RSA-KEM in the wild as of 2020?


Get this bounty!!!

#StackBounty: #rsa #padding #chosen-plaintext-attack #chosen-ciphertext-attack #blinding IND-CCA1 RSA padding?

Bounty: 50

I’ve found a way to complete a task which I’d solve with passwords or by sending keys over the wire (otherwise) by using RSA’s homomorphic property.

I’m restricted to RSA (any padding; for hardware reasons) to implement “blindable decryption”, where one party holds some encrypted data, blinds it, sends it to the decryption oracle, receives it and recovers the embedded key by unblinding.

For this a “secure-as-possible” version of RSA is required which still has the multiplicative homomorphic property.

So what is the best padding for RSA that keeps this property?

Note: An IND-CCA1 version of RSA would be perfectly fine.
My definition of best (in order of preference): Highest security level, easiest implementability, fastest run-time.

Edit: I removed the ECDH unit as the question is way more interesting this way. The ECDH unit can solve the problem using ElGamal and an ECIES like approach.


Get this bounty!!!

#StackBounty: #rsa #number-theory Proving the knowlege of e-th root in an non-interactive way

Bounty: 50

Just like in this question: Protocol for proof of knowledge of $l$-th root

I want to prove that for $u^e = w$ I know $u$ without revealing it.
Three other requirements are:

  • e is small (65537)
  • The proof has to be non-interactive
  • The proof should be as efficient as possible (not several megabytes)

EDIT

So the best solution I have come up so far is to use the Guillou-Quisquater protocol together with a Fiat-Shamir heuristic to make it non-interactive.
This would work the following way:

The prover

Step 1.

The prover generates 10 numbers $T1,T2 … T10$ where each number is calculated using the following formula and where $r$ is a secure random number:

$T = r^e$

Step 2.

calculate a hash $m’ = h(T1||T2 … T10||m)$ where $m$ is the message or challenge the prover wants to sign.

Note that if the hash contains 2 successive zero bytes or a zero byte followed by a byte of the value 1 of which the probability is low the prover has to go back to step 1 and generate new T numbers

Step 3.

The prover selects the 160 leading bits of the hash and splits them into 10 pairs of 16 bits numbers $d1,d2 .. d10$. Then for each of those 16 bits numbers calculates $t1,t2 … t10$ such that

$t = u^d r$

Note that in this case to calculate $t1$ the prover will use the random number $r$ that we used to calculate $T1$, for $t2$ the number $r$ used in $T2$ and so on.

Step 4.

The prover publishes the signed message $m$, the hash $m’$ and the numbers $t1,t2 … t10$

The verifier

Step 1.

The verifier starts by splitting the leading 160 bits of the $m’$ hash into the 16 bits number $d1,d2 .. d10$ then calculate the values $T1,T2 … T10$ from it:

$T = t^e w^{-d}$

Step 2.

Using the T values calculated in the previous step verify that $m’ = h(T1||T2 … T10||m)$ if this verification holds the proof is correct.

I do believe that doing this with 160 bits (proof with ten 16 bits numbers) is very secure, but what about doing it with 80, 96 or 128 bits?
Is there another way to improve this implementation or is there an error in it?


Get this bounty!!!

#StackBounty: #rsa #voting #blind-signature #blinding What is blindness and forgeability in chaum blind signature scheme?

Bounty: 50

I am going through the voting protocols. I know how blind signature works (Blind Signature), but why is blind signature – unconditionally ”blind”, conditionally ”unforgeable” (as highlighted in the following paragraph). How do you define blindness and unforgeability? Please explain. If possible give an illustration.

There is a possibility of guaranteeing the anonymity of voting unconditionally by means of conventional, i.e. classical cryptography, based on mathematical encryption. The corresponding voting protocol is based on the principle of ”sender untraceability”, meaning such a communication scheme, where the recipient of several messages from several senders cannot determine which message came from which sender. Such a communication can be realized with unconditional security in the sense that the recipient is unable to establish any relation between the messages and the senders, even being in possession of infinite computational power. However, the very property of untraceability creates, in the case of voting, an additional problem of determining which ballots come from legal voters, since illegal participants can send ballots in an untraceable way. This problem is solved by a special ”ballot issuing” protocol (based on the technique of ”blind signature”) providing each legal voter with an ”unforgeable” and ”blind” digital ballot, which is used for sending a vote. The term ”unforgeable” means that the ballot cannot be cloned, while the term ”blind” means that the ballots are in no way related to the identities of legal voters. The ballots in the ballot issuing protocol are unconditionally ”blind” but only conditionally ”unforgeable”, that is a person in possession of rich enough computational power is able to vote instead of legal voters. Thus, the property of ”non-exaggeration” is realized by the overall voting protocol in a conditional way only.


Get this bounty!!!

#StackBounty: #encryption #aes #rsa #decryption #instant-messaging Required a simple guide for secure messaging application

Bounty: 50

For my personal research, I have to create a messaging app, but security is only important part of application, security from MITM (man in the middle attack), at device end, and at server level. (note: this will not end to end encryption, as I want to backup messages on server for cross-device access like telegram).

I created the following model:

  1. Server creates RSA key pair first time at installation and keeps private key in a file on server, and broadcast public key with its clients, (A, B)
  2. A&B also create RSA key pair at first-time login, and stores private key at device level and sends public key to server.
  3. A sending message to B:
    1. create a random salt_key
    2. encrypt message with this salt_key (AES)
    3. encrypt salt_key with server’s public key (RSA)
    4. send RSA encrypted key, and AES encrypted message to server
    5. server can decrypt salt_key with RSA private key and then message
    6. server will do same as A did, but with B’s public key
      and B will decrypt salt_key with private key then decrypt message.

Is this a secure way, or any another way to secure my messaging app?


Get this bounty!!!

#StackBounty: #node.js #jwt #rsa #auth0 Node.js: Signature verification (PS256) succeeds in Node.js but fails in jwt.io debugger

Bounty: 50

I wrote a test script with which I’m signing and then verifying a JWT with the PS256 algorithm.

My code verifies the JWT successfully, but the verification fails in the jwt.io debugger.

I’m using jws@3.2.1.

This happens only when using the PS256 algorithm, not when using, for instance, RS256.

Am I doing anything wrong?

I generated my keys with:

openssl genpkey -algorithm RSA -out private_key2.pem -pkeyopt rsa_keygen_bits:2048
openssl rsa -pubout -in private_key2.pem -out public_key2.pem

You can try my code on repl.it: https://repl.it/@SamArtuso/Nodejs-Signature-verification-PS256-succeeds-in-Nodejs

Code:

const { join } = require('path');
const { readFileSync } = require('fs');
const jws = require('jws');

const ALG = 'PS256';

/**********
 * SIGNING
 **********/

const PRIVATE_KEY_PATH = join(__dirname, './keys/private_key2.pem');

const privateKey = readFileSync(PRIVATE_KEY_PATH).toString();

const payload = {
  foo: 'bar',
};

const token = jws.sign({
  header: { alg: ALG },
  payload,
  privateKey,
})

console.log('Token:');
console.log(token);

/************
 * VERIFYING
 ************/

const PUBLIC_KEY_PATH = join(__dirname, './keys/public_key2.pem');

const publicKey = readFileSync(PUBLIC_KEY_PATH).toString();

const result = jws.verify(token, ALG, publicKey);
if (result) {
  console.log('Verification successful.');
} else {
  console.error('Verification failed.');
}

Private key:

-----BEGIN PRIVATE KEY-----
MIIEvQIBADANBgkqhkiG9w0BAQEFAASCBKcwggSjAgEAAoIBAQDPR8CD/9V9fddR
vMk590JtuU4hPT9iPD/mYeWdvUTbkN2iPpg6LDADBntz8I9CzThCkgHmDQhh49Qz
AONiHfyHhKT6HHIBS78wGWfhE9ueFtkv19xisvFJTDO6IllGFMiioj8AkvOJwaY+
5ZKSFG32V0gMaglNSNTOh5KK6DsxgdH2KfMzn6uFwJkvsz1qwPiINu/rqvOQPOIK
JCbNHBOg/SvhPWBSEFDC9AkLm3ajhGAcnSlWi0KgUFz7iHuUR6s4GLdkc40uAooY
ExEWsZyoByT18tXln2hPAvE1Ata2PSbtLHuwvMQt4vzZi80K4BXqOiqvNMo1A1aT
oSQnmOwtAgMBAAECggEAPpHTPEVS5aHCCItrVtMbu1FvkzsQ0g+L3nh4vqfujDTr
olkwzIagK5meVH4uUKTwMbAvYIlYmWwTlx3ShcC1hRb2UgWaKGf8G4HfyKKc7djJ
0NZhUW3gxhZ5mttZhX0qn2VIjVzOpSvOijf0iaIfG3h3aD/t9OViT8G+6610iNmz
Oygmi9kQaBAS2A2sLSSMhdyddIPEpZ8QOHwGCRvBXWO100BCV9ROQzYxW+U9VPaJ
I0tXDL1L1H7y1EbxccPfOsfUPMtF9LQWQZ6ksJuSRwkBAnfKpzexguph29sLDjCQ
X23rQN/NwiU+zRmn+cW7VqkZsbSqucP9t+d19UdWpQKBgQDn9sThxAZvx4OS0noD
AWJX5CliDNlagmLqr4c0QoYI+fPL7FcK9tQYUZ869jnebX7UPHTuDhMoIvWknZbB
QhoogpRoX+XFtxzPwjtBBGc5TYacYnOR4xPSjvDlIrY7FQiH8TgpAGzenSBiD8O0
xW4zSaHLUDHEMFEyPq8tdMmBewKBgQDkwjUnVMPlA9AOD+KQNXgf2kV9z0ZA5idt
9WcsXsxpO2W6S0ntkr29Yr3VuuuJTRH7Fm+bPDJ6C1bfZ746hn3iLMZbMxgGVEf/
cN0nNXjfG5G7EEIU9WFges1I5rec/5W38kIco6soP36Qj5HcUBXt6AHy3k1IbEL2
84Bp1SZ0dwKBgF19mhCcXzPCKAePCVoYvrhJ31wDbb8K+i84m7e2cCtCAr7X/KUQ
op9Clni/MMezPgDwdPhVd+cfX/3+/fnaWIynRIVk0UkE6nnaAOPNkIUJ+A0jqQzN
hvnAXtsbSHM7oPqZgFcWMsrubVTYobpEMIw/SxSUt9oo1zD3Dse1YFntAoGBAIAL
AIuKU7f9gVhNpehINXvGxfzcpxsueEWBBgX87fe9CnzTJYc4CsJV4aIfZTVOEVF0
xnWipTJQ5IhZ3k2N+CpAG6ryl3D7fe1J9E+9C3H+UXzeZc6rZp0FP6Cdm4riOKBk
loLHTcdSevpZkjA6F3w5z9Vsft+Z0YW+2FLkvwiTAoGAdjUYcGTaEhGNtHQszAeY
2VbeVHwgnajKhaZpKMNTVp/AFgeS5k1lSATlT5wQHD3OAhUn+NAEwUOUBBWOpg+i
jML8loplEcVmdHkfGFsrIvzFFIIXQOWy77s/McTCh2jLkLYO8kIOrGy08JBiZnQ/
Ki/HFS/2yaUbG6UdH8FFp2g=
-----END PRIVATE KEY-----

Public key:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAz0fAg//VfX3XUbzJOfdC
bblOIT0/Yjw/5mHlnb1E25Ddoj6YOiwwAwZ7c/CPQs04QpIB5g0IYePUMwDjYh38
h4Sk+hxyAUu/MBln4RPbnhbZL9fcYrLxSUwzuiJZRhTIoqI/AJLzicGmPuWSkhRt
9ldIDGoJTUjUzoeSiug7MYHR9inzM5+rhcCZL7M9asD4iDbv66rzkDziCiQmzRwT
oP0r4T1gUhBQwvQJC5t2o4RgHJ0pVotCoFBc+4h7lEerOBi3ZHONLgKKGBMRFrGc
qAck9fLV5Z9oTwLxNQLWtj0m7Sx7sLzELeL82YvNCuAV6joqrzTKNQNWk6EkJ5js
LQIDAQAB
-----END PUBLIC KEY-----

Edit: Clarifications on how to reproduce my issue.

  1. Run my script with: npm init -f && npm install jws && node test.js
  2. The script will output the token and Verification successful.
  3. Copy and paste the token in the “Encoded” field on jwt.io
  4. Copy and paste the public key in the “Public key or certificate” field.
  5. A red “Invalid Signature” message appears at the bottom.

The below is an example of the token my script will generate. Bear in mind that PS256 has a probabilistic rather than deterministic signature, so the signature will be different every time you run the script.

eyJhbGciOiJQUzI1NiJ9.eyJmb28iOiJiYXIifQ.Rn6i-94ovuKOVRc2jzLVS40MpMmBkIfkyvF56JK3tM8wvg-DW943NNbXf01bhRdyoUj0A73NSQtz0kB4WfXN1uAH1omzNr0ww-iTfC23AX0OcjbsE7CcDz_ZQWWOzwEGGFVfV9ez5yn1pKRYVdFaKqApk3irP-ej_WGrrJfgeZVs683lNk0WjKOYhj6vsryuz52c0OEJ0UmYy7hSSfL38jgL6bdE0awg2DgiaU6qszZEkMjSnugoMobeAUUyOiXHsR79NryuhCQko-I9P1vKd1dEA3zM1iut5sW5FwB8K9Fi49gaQy0zHk72txJvUWdxW5ns0Svft3qLke5XMuqm2g


Get this bounty!!!