texts: Unique numbers with $P^aQ^bR^c \mod N$ for each combination of $a,b,c$ possible? Would it be safer than separate form (like $T^a \mod P$ for each)?

texts:
Main question: Is the computation of $a,b,c$ in $P^aQ^bR^c \mod N$ (much) harder than in $T_p^a \mod P$, $T_q^b \mod Q$, $T_r^c \mod R$ ?

(assuming the first form exists)

$P^aQ^bR^c \mod N$

With $P^aQ^bR^c$ you create unique numbers (e.g. with primes $P,Q,R$) for combinations of $a,b,c$ with $a=0..a_{max},b=0..b_{max},c=0..c_{max}$, in total $(a_{max}+1)(b_{max}+1)(c_{max}+1)=M$ different numbers. The highest number you can generate will be much higher than $M$. (For usage purpose each max exponent value should be about the same size (<+/-25%)).

Now is there a way to remove the gaps and make it cyclic by computing

$P^aQ^bR^c \mod N$

instead, which still generates $M$ different numbers, but the highest number is much closer to $M$, best case $N<M+4$. For security reasons $P,Q,R$ and $M$ should be high numbers (impact?). Furthermore it need to by cyclic. So for values greater than max exponent values it starts again.

Or more general $a,b,c$ are part of a set of numbers each, instead of an continuous interval, e.g. $a \in A$ and $M=|A||B||C|$. Successor and predecessor of each member need to be quite easy to compute. Or higher $N$ with $N < kM$, and $k<<M$.

Use case and possible attack

Target use case would be an algorithm which computes some sort of ciphers $e$ which have the form $e_{abc}= P^aQ^bR^c \mod N$. But instead of direct computation it starts at a given $e_0$ (user dependend) and computes a next with e.g.

$e_{a+1}'=e_0P \mod N$ , or

$e_{b+1}'=e_0Q \mod N$ , or

$e_{c+1}'=e_0R \mod N$

or also combinations or multiple steps is possible, like

$e'=eP^2Q^{42}R \mod N$.

After this $e'$ will be the next $e_0$ and you can do the same again (any you like).
Different to most other crypto algorithms the cipher $e$ is not to main interest. The way how to compute it (out of another) should be secured.
A potential attacker does know the source code and all runtime variables. So he knows his current $e_0$ as well (and $P,Q,R,N$). He does not know his current $a_0,b_0,c_0$. It should be as hard as possible to compute those. Furthermore he can get the knowledge  of other $e_j$. As above it should be hard to compute $a_{j},b_{j},c_{j}$ with $e_j = P^{a_j}Q^{b_j}R^{c_j} \mod N$ and also the computation $e_j$ out of $e_0$, which need $a_{0j},b_{0j},c_{0j}$ in $e_j = e_0P^{a_{0j}}Q^{b_{0j}}R^{c_{0j}} \mod N$ should be hard in most cases.

How would an attacker derive $a,b,c$? 3 times discrete logarithm? factorization needed?

Separate form, like $T^a \mod P$

Alternative way would be

$u = T_p^a \mod P$

$v = T_q^b \mod Q$

$w = T_r^c \mod R$

With $P,Q,R$ primes and $T_i$ a corresponding prime root. (any better?)

Out of $u,v,w$ a single variable from $0$ to $M-1$ could be computed. But in use case those $u,v,w$  are internal variables of source code and a potential attacker can see those anyways. So in this case a cipher $e_0$ has 3 parts $(u_0,v_0,w_0)$. A next cipher $e_0'$ could be

$e_0'=(u_0T_p \mod P, v_0, w_0 T_r \mod R)$

In this case an attack need to compute 3 times discrete algorithm to get $a,b,c$, right?.

Assuming the form $P^aQ^bR^c \mod N$ exists. Would there be any benefit using it to increase the security of $a,b,c$?

Edit:

Did some testing. With $N=173, P=3, Q=5, R=7, a,b,c \in[0..3]$ this form generates 64 unique numbers. But it is not cyclic.

So far I only found a 2D which is cyclic as well: $N=126, P=17, Q=13, (R=1), a,b \in[0..5]$ generates 36 unique numbers.


texts: How to encrypt a string and decrypt a string but public can never figure out how to encrypt/decrypt a string

texts:
On my website I display an image. To generate this image, it require a string parameters. For example the string 1234,2423,1231 as the parameter.
Anyone can use my API (no authentication required). For example example.com/generate?param=1234,2423,1231. That is how my API works right now. To generate a different image, all you have to do is provide different numbers and different amount of numbers, like 2342,2423,234.
However, I do not want people to be able to keep generating images by themselves by simply changing the numbers. So if I encrpyt the parameter and then let the user load the image, they would never know how to generate an image themselves. So an example of an encrypted API request would be example.com/generate?param=s97dgfubYVd80fzhgdfufg0894rf which would correspond to example.com/generate?param=1234,2423,1231.
The add on to this problem is, I tell the user "we are going to generate an image with the parameters 1234,2423,1231. Here is the API link to generate this image: example.com/generate?param=s97dgfubYVd80fzhgdfufg0894rf".
So what encryption method can I use.


texts: DSA: Authentication and assurance of authorized parties

texts:
When dealing with Asymmetric cryptographic algorithms, usually the sender of the critical data asks the listener for a Public Key for encrypting the data and sending them. This is while the private key remains only known to the listener so that it can decrypt the data. The problem in this scenario is that, the eavesdropper can eavesdrop on the Public Key and send "Falsified" data to the listener. In an abstract level, I know that this problem can be solved by making use of DSA to authorize the parties.

In Microsoft .Net Frameworks, the DSACryptoServiceProvider, very much like the RSA, I see that DSA is also a asymmetric algorithm consisting of a public and private key. And I assumed that with different Keys, I will come up with different signatures for the same data. So I also assume that I have to send the public key to the sender of the data for the purpose of verification ( the padlock concept). But in this case it will not work for the reason I explained.

My question is that, how do I have to use the DSA to assure that the stream is coming from the authorized party.


texts: How to find the inverse of f(x) in NTRU key generation?

texts:
I work on a project that depends on the NTRU cryptosystem, but I don't know how to find the inverse of $f(x)$.

Please see the picture:

Please help me to understand this problem.


texts:
What would be the best approach for storing a list of hardcoded email addresses in plain sight (in a public JS file or such)?

The site is pretty low-key, for a small community of friends. Starting out, I'd like to just hardcode some email addresses as hashes, which would then be checked against a users input to check that they are an invited member of the site.

Rather than creating an api with authentication etc, I'd prefer to keep it all in the front end. The 'account' would only be used for tracking user and guiding them to the right resources. Nothing financial, or sensitive.

I understand I could use an MD5 hash, though I hear this would be easily cracked?


texts: Is a PRG more costly than AES or any other encryption standard?

texts:
I know that there are many encryption standards that take a key and sometimes an IV to produce a cipher-text (the most prominent one is AES). These standards usually involve many rounds of addition and multiplication. However, using an OTP is much easier than this. You XOR the plaintext with your pad, this is the only requirement computation-wise. However, the OTP comes with the problem of a key-stream as long as the plaintext. This key-stream is supposed to be random. My question is, is this randomness more costly than the encryption standards that are in use? Why don't we use an OTP in every case? What is the downside?
Let's say I cannot afford to use encryption algorithms, but I have a stream of data that is nearly-random. If I use this as an OTP (I know this is not perfectly random), what do I sacrifice in return? What can be done to obtain the best pseudo-random characteristics from this arbitrary stream of data, to make it as qualified as it can get to be an OTP?


texts: Frequency Analysis on DES, AES, 3DES using Cryptool2

texts:
I am trying to analyze symmetric block ciphers like DES, 3DES and AES, using Cryptool 2.
I want to do a frequency analysis on each of these ciphers, in order to comment whether this is an effective way for cryptanalysis or not.
However, the ciphertext these ciphers produce comes in hex form:

My question is - when performing frequency analysis on such ciphers, do I input the hex ciphertext or do I need to transform it into text? How can I comment on that (based on letter frequency or bit occurrence)?


texts: Could randomisation make for a better book cipher?

texts: Suppose that the file linux.words is used as the "book".  This is a publicly available list of just shy of half a million words.  And suppose that this book is used, not in its native alphabetic order, but in some randomised order.  The number of possible random arrangements is a decimal which is over two million decimal digits long. The cipher text will be a stream of numbers which index into the chosen random arrangement of the "book".  Does this approach make for an improved book cipher?


texts: Deriving 2 shared secrets from one private key and 2 different public keys

texts: I have a key pair, say $(d, Q)$. I send my public key $Q$ to 2 different people. I also get their public keys $Q_1$ and $Q_2$. Now I can derive 2 shared secrets, $d*Q_1$ and $d*Q_2$. The 2 other people can also derive  secrets $d_1*Q$ and $d_2*Q$. Assuming all key pairs were generated from the same elliptic curve, is it safe to use both the shared secrets in the same session for 2-way communication?


texts: Differential Cryptanalysis for Hash functions

texts:
How is differential cryptanalysis used to attack hash functions? I've been struggling through a couple academic papers and thesis's on the subject but they all sound like greek to me. Does anyone know who to explain this in simple enough (layish) terms?

I get how differential cryptanalysis methods work (a few of them) against Block ciphers but I'd really like to know how they can be used to target hash functions.


texts:
I am designing a set of low-power sensing motes. Each mote will communicate to a central base over RF.

I want the mote to be able to authenticate itself with the base, and send its data without being vulnerable to replay attacks while not using a lot of processing power.

Are there major flaws in the following algorithm?

Mote A sends a 'hello' message to Base. This message contains the ID# (public key of the mote) and a random nonce [R] (HW generated) encrypted by the base's public key.
Base decrypts the 'hello' and verifies the ID# against a whitelist.
Base sends an 'ack' message to Mote A. This message contains [R+1] and is encrypted by the ID# (mote's public key)
Mote A decrypts 'ack' and verifies received [R+1] matches stored [R+1].
Mote A sends ID#, data and [R+2] to base encrypted by Base public key.
Base decrypts and sends an 'ack' and [R+3] and is encrypted by the ID# (mote's public key)
Mote A verifies 'ack' and Communication is Complete.

The random nonce [R, R+1, R+2, R+3] will only be valid for a short period of time (< 1 second) as the base has no memory for session storage.


texts: Chance to find HMAC key/salt when having knowledge of the hashed data?

texts:
I'm not sure how to word this... I'm working with a HMAC (I think of it being a "salted hash"). I know the entire string being hashed, I do NOT know the salt. I also know the first 8 characters of the resulting hash. I can also, repeatedly, generate new hashes by changing the input string, and retrieve new first-8 characters.

Does that in any way make it even remotely possible to find the salt? Even via brute forcing, would that decrease the entropy at all, if I were able to modify the hashing algo (much like how bitcoin is mined by pre-computing most of the hash and only updating the nonce at the end, removing many many steps from the hashing itself)?

From all I've learned, I'm leaning towards a "no", that its no help whatsoever. That being said, I've never worked with a HMAC/salted hash before, so I'm not sure if that works any differently. Is finding the salt any easier because of how a HMAC is computed?


texts: Cryptographic security of PHP mt_rand() function using Mersenne Twister algo

texts:
At stackoverflow this question has been asked. It uses additional random entropy and a hash method (among others) to try and create a cryptographically secure pseudo-random number generator for PHP. PHP seems to use a Mersenne Twister algorithm with a large internal state and high period, but Wikipedia assures me that Mersenne Twister is not cryptographically secure.

Q: Could somebody please indicate what vulnerabilities there are using the PHP Mersenne Twister implementation as if it was cryptographically secure?

Additional Q: It would be very nice if somebody could go over to stackoverflow to see if the solution of H M is any better than using the default method and if it can be improved. Of course, the only really good way is to hold it against BSI and NIST test suites, but any improvement on the default implementation may be useful.

The source code in the stackoverflow question should be pretty easy to read, even for persons that are more mathematically inclined. Just as reference, I've included the source of the current methods within Zend PHP (which indeed seems to lack any kind of cryptographical algorithms).

Code is a partial copy of the Zend source for cryptographic analysis only. The ZEND source is protected by the PHP 3.01 license.

PS the initialization of the algorithm is just 32 or 64 bit, which is why I proposed at least to reseed it thouroughly on stackoverflow, but I wonder if that would be enough, as I've unfortunately proposed on stackoverflow (mostly because creating self defined cryptographic algorithms by users is frowned upon).

basic_functions.h

#define MT_N (624)

php_uint32   state[MT_N+1];  /* state vector + 1 extra to not violate ANSI C */
php_uint32   *next;       /* next random value is computed from here */
int      left;        /* can *next++ this many times before reloading */
zend_bool mt_rand_is_seeded; /* Whether mt_rand() has been seeded */

rand.c

#define N             MT_N                 /* length of state vector */
#define M             (397)                /* a period parameter */
#define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
#define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
#define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */

#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))

/* {{{ php_mt_reload
 */
static inline void php_mt_reload(TSRMLS_D)
{
    /* Generate N new values in state
       Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */

    register php_uint32 *state = BG(state);
    register php_uint32 *p = state;
    register int i;

    for (i = N - M; i--; ++p)
        *p = twist(p[M], p[0], p[1]);
    for (i = M; --i; ++p)
        *p = twist(p[M-N], p[0], p[1]);
    *p = twist(p[M-N], p[0], state[0]);
    BG(left) = N;
    BG(next) = state;
}
/* }}} */

/* {{{ php_mt_srand
 */
PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
{
    /* Seed the generator with a simple uint32 */
    php_mt_initialize(seed, BG(state));
    php_mt_reload(TSRMLS_C);

    /* Seed only once */
    BG(mt_rand_is_seeded) = 1;
}
/* }}} */

/* {{{ php_mt_rand
 */
PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
{
    /* Pull a 32-bit integer from the generator state
       Every other access function simply transforms the numbers extracted here */

    register php_uint32 s1;

    if (BG(left) == 0) {
        php_mt_reload(TSRMLS_C);
    }
    --BG(left);

    s1 = *BG(next)++;
    s1 ^= (s1 >> 11);
    s1 ^= (s1 <<  7) & 0x9d2c5680U;
    s1 ^= (s1 << 15) & 0xefc60000U;
    return ( s1 ^ (s1 >> 18) );
}
/* }}} */


texts: Why does Fortuna RNG use double SHA-256?

texts:
In the paper for Fortuna the authors say that you can use any good digest algorithm (obviously as long as its output is 256 bit) and then they recommend double SHA-256.

Why? What's the benefit? What happens if I use single SHA-256 or RIPEMD-256, for example?


texts: Can I still use insecure curves/ciphers for time relevant encryption?

texts:
Can Ciphers that are known to be insecure because their keysize is considered too small still be used in appliances that have a tight decryption timeframe?
In particular I am looking at ECC2K-130.
ecc-challenge.info states, that they need 2466 PlayStation 3's to carry out the required 2^60.9 iterations per year.
Let's assume I need to encrypt data only for one minute, after that time the data is useless.
Couldn't I still use ECC2K-130 as it would require 525600 times more PlayStations to crack it in a single minute instead of a year?
Or do I have a misunderstanding in the way this works?


texts:
One thing I don't quite understand is how to naively handle division operation in rank-1 constraint systems (R1CS).
supposedly A.s * B.s - C.s = 0 allows you to perform any addition/subtraction/multiplication/division operations, but how do you actually perform division from multiplication gate in any of the SNARKs system? the only thing I can think of is to use multiplicative inverse of the value you want to divide as your input for B in the A*Bpart, so that A*B becomes A*B^-1 which is same as performing A/B
My question is how does the verifier know the input prover send to the division gate is the multiplicative inverse of B? it seems that the verifier would need to either trust the prover sending the correct input (there is no way to check that the prover is sending B^-1 or some other B'^-1 ), did I miss something here?
-edited
My question is about how to build R1CS constraint on division. for example, how do I build a constraint matrix for (a*b)/(c*d) where a,b,c,d are inputs to an arithmetic circuit.


texts: Can I make fixed-length ciphertext with AES-256-GCM?

texts:
I have a question about AES-256-GCM encryption.

Can I make a fixed-length encryption output?

In my understanding, I cannot make a fixed-length ciphertext. To me, the fixed-length output is much more secure so that no one can guess the input length. If we cannot make a fixed-length output, can someone explain why this is still secure enough?


texts:
I should implement ISO 9797 MAC algorithm 3 with initial transformation 1, without truncation, and using DES as a block cipher.
I should add padding of 0x80, then enough zero bytes if the length is not multiple of 8.

I want to know what will happen if data is only 8 bytes?

I should feed data directly to 3DES algorithm or I should first feed it to des then feed to 3DES?


texts:
I have read too many different options for encryption that I now feel quite lost. I need a simple, secure (don't we all) scheme for encrypting integers (32-bit) with the following requirements:

Ciphertext is also an integer (32-bit) or a long (64-bit)
For integers x1=x2 then ciphertexts E(x1)=E(x2)
For integers x1<>x2 then ciphertexts E(x1)<>E(x2)
If I know E(x1) it will be very hard to decrypt x1 without the (private) key

Is there such a simple scheme?


texts:
I'm wondering about the concept of image hashing specifically SHA256. Like how do we do it? Can we hash the image based on the binary file? or do we need to convert the data into strings first then do normal hashing?
Are there any other ways on how to hash images in C++? without using any libraries?


texts: Design requirements for a keyed hash function?

texts:
I am actually preparing for a cryptography exam, and I found a question asked by the professor in the class, below are the lines that I copied from the slide :

  Example: Let $Ek$ be the encryption transformation of one-key cipher and
  $h$ be a hash function. Then $hk := Ek ◦ h$ is a keyed hash function, where $◦$
  denotes the function composition.

  Security: It should have good properties if both the one-key cipher and
  the hash function are well designed.

  Write down some design requirements for the underlying hash function and one-key cipher.

I searched a lot about keyed hash functions, but I couldn't find any good article about such a design.

Can anyone help me with that?


texts:
The Republic of Brutopia are updating the design of their library cards with a new security feature: a 2D barcode containing a cryptographically signed copy of the human-readable fields on the card. This will allow anyone to verify that a card is genuine and has not been tampered with.

Unfortunately, the library card is the principal form of government-issued ID in Brutopia. You'll probably show yours to almost-random strangers several times a day, whether you want to buy beer, open a bank account, or pick up a package at the post office. And now civil rights advocates and conspiracy theorists alike are up in arms about the privacy implications of using the new barcoded cards for that. Who can really know if the barcode only contains the data about you that you can see for yourself on the face of the card?

It didn't help the government that they published full specifications for the barcode content, including a DSA signature at the end. The critics pointed out that a DSA signature contains an ostensibly-random nonce, and there is no way you can check that it is really all random and doesn't secretly code for personally identifiable data.

It appears that what the government needs is to use something else than DSA for signing the cards. As far as I can make out, what we would ideally want here is a public-key signature scheme with the additional property that

  It should be infeasible to construct a valid public key $K_p$, a message $M$, and two different signatures $S_1$ and $S_2$ such that $S_1$ and $S_2$ are both valid signatures for $M$ under key $K_p$.

Does this property (or something like it) have a name?

And are there generally accepted signature schemes that provide this?

Naively I would expect that RSA, with the input being a hash of the message, padded to the modulus length in some deterministic way, might work -- but apparently best practice is always to use some random padding when using RSA for anything, so I'm not sure whether that would be vulnerable somehow.


texts: Why is the security of block cipher not a function of key and tweak?

texts:
The proofs and security of block ciphers constructed especially of Luby Rackoff Constructions and Feistel Networks is based on the number of queries and round functions. The security measure is always based on the probability with which the attacker can distinguish the randomness in the cipher text. For example Patarin's proof says the encryption can be distinguished in O($ m^2/2^{(l/2)}$)  where m is number of queries and l is length of input bits.

But in general the bigger the key length it is considered as good against brute force and adding tweaks is considered provides additional randomness. Then why is the  security measure not involving the key length or tweak length ? or is there a security measure that involves key and tweak ?


texts: Implementing a one-time pad without binary?

texts:
I found a program which takes a purely alphabetical message, converts the letters to their ASCII values and combines them with the ASCII values of an alphabetical key (wrapping around when it gets to Z).

(The key being used is fully random and is required to be at least a long as the message.)

But from what I usually read about one-time pads, the message and the key are in binary, and the bits in the message is XORed with the key to produce the ciphertext. Combining the ASCII values sounds like a similar but obviously very different process.

Is this a valid way to implement a one-time pad? Or does the process merely resemble the binary XOR and doesn't have the same cryptographic properties as a one-time pad?


texts: How can I use the whole potential of DES?

texts: I have recently programmed the DES algorithm. Right now it works just with integers (or better to say chars) in the range <0;255>. How can I use its whole potential - using just ASCII would be a waste (there are many characters I would never use).


texts: Most influential/illuminating papers/books/courses on lattice based cryptography?

texts:
I'm interested in some sort of "compendium" on lattice-based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of paramount importance. The other problem is that there are papers that are obviously influential, but they are hard to understand "from scratch".

To start with something I may notice some of them:

GPV framework:

"How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions".

Cryptanalysis:

"Learning  a  Parallelepiped:  Cryptanalysis  of  GGH and NTRU Signatures"

Basic courses :

winter school on lattice-based crypto (https://cyber.biu.ac.il/event/the-2nd-biu-winter-school)
Regev course on lattices in CS (https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/)
Vinod's course (http://people.csail.mit.edu/vinodv/6876-Fall2015/index.html)

Surveys:

"Lattice-based Cryptography" part from the book "Post-Quantum Cryptography".
"A Decade of Lattice Cryptography", Peikert.

Unfortunately, I didn't find anything on discrete Gaussian distributions and properties of continuous Gaussians (why is it "not far from" uniform over any "small" parallelopiped), how to generate them; on smoothing parameter and its "intuitive" meaning. Also, reductions from average to worst-case are somewhat tricky and uneasy to understand form Ajtai papers. And there is a direction of research on ideal lattices, which somehow related to integer rings of number fields ($\mathbb{Z}_K$), this is completely obscure.


texts: Is there a "two of three keys needed" encryption?

texts:
Sorry if this question is stupid, but is there an encryption algorithm where a message is encrypted with a set of n keys which can then be deciphered with any sufficiently large subset of those? E.g. encrypt with 3 keys and any 2 are sufficient to decipher the message.
AFAIK some blockchain wallets have a functionality similar to this.


texts: calculating the branch number/ active bundles of a cipher

texts: I have read the papers Wide Trail Strategy and Wide Trail Design Strategy for Binary MixColumns. These papers describe the need for a good linear transformation in a cipher, a provable mechanism to counter the differential and linear cryptanalysis, and also to determine the required rounds to mitigate these attacks. All these parameters are determined by determining the minimum number of active bundles after certain rounds. Now, my question is that for a cipher, if a single round transformation consists of Substitution-->> Permutation-->>Substitution; alternatively, a bundle/ byte(or some bits from one bundle and other bits from some another bundle) gets substituted multiple times in a recursive way. Can anyone tell that in such a scenario how to calculate the branch number/ active bundle weight? Any idea/ reference are mostly welcomed.


texts: implementing long term archive encryption

texts:
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!


texts: Securely re-using a shared key with NaCl

texts:
I want to modify this peer-to-peer communications software to allow parties to specify a shared secret key and have all communications encrypted with it.

[The software uses tweetnacl.js for the cryptographic operations.]

Re-using the exact same shared secret key for every message does not seem very secure. I have two questions:

Is this concern addressed by the presence of the nonce in nacl.secretbox(message, nonce, key) thus making it safe to re-use the shared secret key as long as the nonce is different every time? (which is a requirement anyway obviously).
Would it be even safer to derive a unique shared key for each message by hashing some salt and sending the salt along with each message so that the other side can do the same to obtain the unique shared key for the message? Or is this redundant?


texts: ECDH Public Key Recovery - Determine if valid key exists from just signature and message

texts:
If I have just the (r,s,v) values of the signature and the message hash, what is the most efficient way to determine if a valid public key exists?

I do not need to know the public key, just that the signature and message hash recover to a public key.

Lets say with the notation:

, are the values from the signature.
ℎ is the hash of the message being verified
 is the public key
 is the group generator
|| is the x-coordinate of the point
{,′} are the two curve points with x-coordinate

The recovery would be:

$$P \ \overset{?}{=} r^{-1}s\{R, R'\} - r^{-1}hG$$

My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P.


texts: How is the AEScrypt password related to the underlying AES key

texts:
AES uses a key that is at most 256 bit.

I assume AESCrypt uses AES.

When a file is encrypted with AEScrypt, there is no limit to the length of the password.

What is the relation between the AESCrypt password and the key size of the underlying AES encryption?


texts:
Summary: As a trainee, I got the task to extract encrypted passwords of our external password manager (Zoho Vault) and decrypt them. The documentation regarding how to decrpyt them is...none. I ask the support for help, but they send me only some pages of their documentation...
Research and attempts:
According of my account and the documentation of Zoho Vault API, the algorithm is a "PBKDF2_AES". I used at first the PBKDF2 encryption to generate a key, by using a passphrase + a salt + an iteration of 1000, which I received with some API calls. Next, I tried to use the Zoho Vault decrypting function (which decrypts AES encryptions), but I didnt got the result I wanted. After that, I checked an Online AES Encrypter/Decrypter and tried my luck there. After filling the forms with all the required info, I received an error. Just to be sure, that it was the right encrypt/decrypt method, I encrypted some other example data and the result had the same Base64 pattern password I tried to encrypt. After I checked the "PBKDF2 generated key" and mine. The one I made was for a AES-256. But the "PBKDF2 generated key" seems to be 64 byte long/AES-512.
Which I did some research and it almost seems it doesnt exist.
I just cant figure out how to continue...
If needed, I can share all required keys and encrypted data, since they are all dummies for the later used account anyway.


texts: How much (home PC) CPU time is required to generate a prime number of a given size?

texts:
How much CPU time is required on a typical home computer to generate a prime number of size 100 bit, 200 bit , 512 bit and 1024 bit using given random bits of the respective sizes?

Please note that the prime number computed should be immediately next to the given random number, e.g. if the random number is 15, the computed prime number should be 17.

I want to know approximate time range on a typical home computer for the above mentioned prime sizes.


texts: Efficiency of McEliece cryptography (ciphertext expansion)

texts:
Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys.

However I have never heard about the size (or length) of its ciphertext. ("Ciphertext expansion".) For example, McEliece offers the linear code of length 1024 and of dimension 524. That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency?


texts:
I was doing research on this attack and I am wondering, why is Diffie-Hellman always

associated with such an attack?  Aren't other public key cryptography schemes vulnerable

to the same kind of attack?  To be more specific, is RSA vulnerable to such an attack?

If so, which versions and how can they be carried out?


texts: Choosing finite field size in Shamir's Secret Sharing Scheme

texts:
The Wikipedia article on Shamir's Secret Sharing says to that to have information theoretical security the splitting algorithm should be evaluated using finite field arithmetic on the field $\rm{GF}(p)$ such that $p>n,p>S$ where $n$ is the number of shares and $S$ is the information to be shared. It suggests that on the one hand $p$ should be large because an attacker knows that $S\in\mathbb{Z}/p\mathbb{Z}$. It also suggests that $p$ should not be too large because an attacker knows that as $p\uparrow$ $\rm{p}\{f(x)\bmod p = f(x)\}\uparrow$. How should one choose the best value of $p$ and be confident about choice?

Charles Karney's implementation splits $S$ into $i$ pieces such that $\forall \,i,\,S_i\in\rm{GF}(257)$. I do not understand a specific reason to use $p=257$ over any other prime number. For instance the elements $S_i$ could be stored in in an 8 bit value if $p=251$ was chosen.


texts: ECKS-PS algorithm: searching in encrypted data; bilinear maps

texts:
I have found an encryption algorithm named ECKS-PS (published in the paper Efficient conjunctive keyword search on encrypted data storage system) that allows an user to search in encrypted data. All the steps are described here:

And I have written them a little bit more clear here:

I have tried to find a calculation example of finding two words multiple times:

but I never get a match.

Can anybody tell me what I am doing wrong and/or provide me with an example where you get a match (based on the ECKS-PS algorithm)? I know there may be other algorithms to search in encrypted data but I would like to know how to do it with this algorithm.

EDIT: with some advice from Barack and Gilles

$e(i,j) = 53 ^ {i*j} \mod 59 $

$ g=53 $,
$ \alpha = 7 $,
$ r= 16 $,
$ \theta = 3 $,
$ a_i = 6 $,
$ Hash(W_1) = 53 ^ {23} $,
$ Hash(W_2) = 53 ^ {18} $,

$e(g^{a_i \theta}, g ^r  ) = 53 ^ { 53 ^ {6*3} * 53 ^{16}} \mod 59 = 53 ^ { 53 ^{34}} = 9 $

$e(g^{a_i }, (Hash(W_1) * Hash(W_2))^{\alpha} * g^{\theta * r}  ) = 53^ {{({53 ^ {23} * {53 ^ {18} }}) ^ {7} * 53 ^{16*3} }} \mod 59 = 9 $

$e(g^{\alpha}, Hash(W_1)^{a_i}) = 53 ^ {{53^7}*{{53^{23}}^6}} \mod 59 = 19$
$e(g^{\alpha}, Hash(W_2)^{a_i}) = 53 ^ {{53^7}*{{53^{18}}^6}} \mod 59 = 27$

$\frac 9{19*7} => $ multiplicative inverse of $ 19*27 \mod 59 = 36$ => $29 \mod 59  \ne 9 \mod 59$


texts: In RSA, do I calculate d from e or e from d?

texts:
In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article on RSA) that one should first calculate $e$, and only then calclulate $d$ from it.

Which of these two methods are preferred, and why?


texts: Which of the following hash functions is collision resistant?

texts:
Let $H: M \to T\ $ be a collision resistant hash function. Which of the following is collision resistant: $
1.H'(m) = H(m \big\| m)$

$2.H'(m) = H(m) \big\| H(0)$

$3.H'(m) = H(m) \oplus H(m)$

$4.H'(m) = H(H(m))$

$5.H'(m) = H(0)$

$6.H'(m) = H(|m|)$

$7.H'(m) = H(m)[0,\ldots,31] $   (i.e. output the first 32 bits of the hash)

Is the answer functions 1, (2) and 4?


texts: Epsilon Perfect Secrecy: Size of Key Space

texts:
I am solving a homework problem which defines $(1-\epsilon)$-perfect secrecy as the secrecy satisfied by the encryption scheme when the following inequality holds

$\Pr[M=m\mathrel|C=c]\leq (1+\epsilon)\Pr[M=m]$

Then the problem asks us to prove that $|K|\geq \frac{1}{1+\epsilon}|M|$ where $K,M$ are the key and message spaces, respectively. I believe this problem is essentially the same as problem 2.12 in "Introduction to Modern Cryptography".

I have read the proof for Shannon Secrecy's key space limitation (which says $|K| \geq |M|$). I don't really see how this is connected to that proof, and I can't find any other way to approach. Can someone please give me a few hints?


texts:
I've seen the term mentioned in a paper by the Keccak team here, and by Adam Langley here when talking about properly authenticating stream ciphers.

What does it actually mean, and how does it work? What are its advantages in the case of encrypting and authenticating streams?


texts: is accessing elements of an array in secret order vulnerable to timing attack?

texts:
Suppose there is an array containing bytes 0...255. Suppose this array is shuffled using a key for random data.

Since this is indexing the elements of a table using secret data, is it vulnerable to timing attack?

If so, Suppose the array is shuffled again. Since the state at the beginning of the second shuffle is a secret, random permutation of bytes 0...255, is this second shuffle vulnerable to timing attack as well?

Basically, is the core of the problem accessing an index of an array based on secret data? Is knowing the contents of the array/table in question a prerequisite for this type of attack? Or is there something else to this altogether?

Background

More specifically, I am curious about the vulnerability of following construction to timing attack:

shuffle(Z256, key) # this randomizes key too
output = Z256[Z256[index]] for index 0...255
repeat

The problems that I see are the indexing based on secret data, both during the shuffle and output stage. However, since the set is shuffled every time, the key randomized, and the set iterated through completely, I think it should be resistant? My reasoning is that since the set is iterated through completely, the sum of the time spent accessing it should be more or less the same regardless of the order the accesses happen in. But I'm not sure exactly what causes the vulnerability to begin with.


texts: Random numbers for Rabin-Miller primality tests

texts:
I've implemented a Rabin-Miller primality test fuction following Wikipedia and the book Applied Cryptography. Now I'm using it for generating primes with a string seed. The book suggests the following for this:

Generate a random 'n'-bit number
Set the high- and low-order bits to 1.
Make sure it is not divisible by small primes $p\in[2,2000]$.
Perform a Rabin-Miller Test for some random $a$. Choose a small value of $a$ to make it go quicker. Do five tests (I'm doing 40 as a post suggested here, and instead of generating a random number, I increment by one and test again.

So, first I used a random generator with uniform distribution to generate $a$, but after reading this, I changed it to the standard C++ rand() with srand(time(0)) seed. It is faster, but I'm not sure if it is the best way. Using boost's Twister was slower, but gave a wider range of $a$. I have searched (maybe not with right keywords) but how does choice of $a$ influence the test?

Is it good if the range is pretty small compared to the size of the number I test (saying $a$ is 32 bits, and the number is 512 bits)? Will it increase the odds of a false positive (pseudo prime)?


texts:
Unsure it's the best place to ask, anyway:
I know symmetric encryption is the best for such tasks but I am planning to encrypt large backup files (between 10 and 100GB) with my private PGP key. My purpose here is to use several layers of encryption, each of them using a different algorithm to prevent 0day exploits on a specific algorithm. So you get me: AES first then RSA.
I have just tried to perform the above and while there is absolutely no problem with AES (takes about 20min on my file just using 7zip), PGP (using gpg4win / kleopatra) is taking a while until a time out message stops the process after more than 30min (I wasn't timing maybe it was an hour or two).
I have read there is no specific limit to file size for PGP encryption or it may be related to your memory size but nothing clear. Would you have more information about this?
Thanks


texts: Looking at the question Is this a UC-secure commitment scheme in the ROM?, I was wondering, is the commitment scheme proposed in the answer (which uses $H(M||r)$ as commit) secure in the UC-model, assuming the existence of a random oracle? In practice, are there any problems in using such scheme within UC-secure protocols, replacing $H$ with a (good) hash-function?


texts: Paid decryption scheme and possible attack surface

texts:
This is how ransomware can work as far as I understand:

Most ransomware works with symmetric encryption on individual files. For each file the script generates a new key. A list is then generated containing all the file-paths with their respective keys.

This list is then asymmetrically encrypted. The victim has to pay for the private key to decrypt the master list.

The malware then reads the list to unlock all the files.

Is knowledge of part of this list (all the file-paths) helpful in finding the private key?


texts:
When performing a key search, I've always wondered how you reliably detect a successful decryption once you hit the right key. I assume that you have to analyze the data and look for patterns: words, letter frequency, known file headers, statistical properties and so forth.

Is this a correct assumption and, if so, has anyone exploited this by enabling the introduction of decoy plaintexts in a cipher? Is there any research related to this?


texts: Does a trace of SSL packets provide a proof of data authenticity?

texts:
I'm wondering if it would make sense to record a whole HTTPS session,
publish its encryption keys and present it to third parties as a proof
that this particular data was sent by a given server identifying
itself with some signed certificate. Could such proof be forged in any
way?  Should this proof be convincing to third parties who receive it?


texts: How to find the order of a generator on an elliptic curve?

texts:
I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm:

Choose random point $P$ on the curve.
Find the order of a generator $\ell$.
Calculate the number of points $n=\#E(\mathbb F_p)$.
Calculate the cofactor $h=n/\ell$.
Calculate a generator as $G=[h]P$.

Here I can find $n=\#E(\mathbb F_p)$ using Schoof's algorithm. I need to find $\ell$. How is that possible? How can I find the order of a generator/base point of an elliptic curve defined over a prime field?


texts: Is there a standard definition of non-malleability for the encryption schemes?

texts:
I find some different definitions of non-malleability for the encryption schemes. They may be equivalent, but I am not sure which one is better or if there is a standard definition.

I give two definitions of NM-CCA2 for PKE schemes.

Relations Among Notions of Security for Public-Key Encryption Schemes:

  Def1 Let $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$ be a PKE scheme and let $A = (A_{1}, A_{2})$ be an adversary. For $k \in \mathbb{N}$, let
  $\mathrm{Adv}^{\text{nm-cca2}}_{\Pi, A}(k) = \left| \Pr \left[ \mathrm{Exp}_{\Pi, A}^{\text{nm-cca2-1}} (k) = 1 \right] - \Pr \left[ \mathrm{Exp}_{\Pi, A}^{\text{nm-cca2-0}} (k) = 1 \right] \right|$

  where, for $b \in \{ 0,1 \}$,

    Experiment $\mathrm{Exp}_{\Pi, A}^{\text{nm-cca2-1}} (k)$

    $(pk, sk) \gets \mathrm{Gen}(1^k);$

    $(M, s) \gets A_{1}^{\mathrm{Dec}_{sk}(\cdot)}(pk);$

    $(x_{0}, x_{1}) \gets M;~y \gets \mathrm{Enc}_{pk}(x_{1});$

    $(R, Y) \gets A_{2}^{\mathrm{Dec}_{sk}(\cdot)}(M,s,y);$

    $X \gets \mathrm{Dec}_{sk}(Y);$

    If $(y \not\in Y) \wedge (\bot \not\in X) \wedge R(x_{b}, X)$ then $d \gets 1$; else $d \gets 0$;

    Return $d$

  $M$ is a set such that $|x| = |x'|$ for any $x, x' \in M$. And $X = (X_{1}, X_{2}, \ldots, X_{l})$ and $Y = (Y_{1}, Y_{2}, \ldots, Y_{l})$ such that $X_{i} = \mathrm{Dec}_{sk}(Y_{i})$. $\Pi$ is secure in the sense of NM-CCA2 if for every P.P.T. algorithms $A$, $\mathrm{Adv}_{\Pi, A}^{\text{nm-cca2}} (\cdot)$ is negligible.

Bounded CCA2-Secure Encryption:

  Def2 Let $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$ be a PKE scheme and let the random variable $\text{NME-CCA2}_{\Pi, A, k, l}$ where $b \in \{ 0,1 \}$, $A = (A_{1}, A_{2})$ and $k,l \in \mathbb{N}$ denote the result of the following probabilistic experiment:

    Experiment $\text{NME-CCA2-}b (\Pi, A, k, l)$:

    $(pk, sk) \gets \mathrm{Gen}(1^k);$

    $(x_{0}, x_{1}, s) \gets A_{1}^{\mathrm{Dec}_{sk}(\cdot)}(pk);$

    $y \gets \mathrm{Enc}_{pk}(x_{b});$

    $Y = (Y_{1}, Y_{2}, \ldots, Y_{l}) \gets A_{2}^{\mathrm{Dec}_{sk}(\cdot)}(y, s);$

    Output $X = (X_{1}, X_{2}, \ldots, X_{l}) = \mathrm{Dec}_{sk}(Y)$ (If $Y_{i} = y$, $X_{i} = \text{COPY}$)

  It is mandated that $|x_{0}| = |x_{1}|$. $\Pi$ is secure in the sense of NM-CCA2 if for every P.P.T. algorithms $A$, any polynomial $p(\cdot)$, $\left\{ \text{NME-CCA2-0} (\Pi, A, k, p(k)) \right\}_{k \in \mathbb{N}}$ and $\left\{ \text{NME-CCA2-1} (\Pi, A, k, p(k)) \right\}_{k \in \mathbb{N}}$ are computationally indistinguishable.

In Def1, why does $A_{1}$ output a set $M$ instead $(x_{0}, x_{1})$?

Is every efficient relation can be the output of $A_{1}$?

Is every relation which is the output of $A_{1}$ efficient?

In Def2, can the distinguisher ask the access of $\mathrm{Dec}_{sk}(\cdot)$? (Or does the distinguisher know $sk$?)

Why are these definitions equivalent?


texts: Simple application of verifiable random function?

texts:
I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the correctness of their output". I'm having a little trouble seeing a clean example of a 'killer application' for such a primitive. Can anyone describe one here?

I guess I'm having trouble seeing the usefulness of such a proof of correctness for a pseudorandom function. What does it give you that a normal PRF can't?


texts: How secure is file-based encryption in Android?

texts:
I want to estimate the cost of breaking file-based encryption in Android given a password entropy. The only information I found so far is this:

The stretched credential is the user credential after salting and
stretching with the scrypt algorithm.

AFAIK, scrypt has several parameters. How do I know what parameters are used in Android? Probably, different derivatives of the Android Open Source Project use different parameters. I am interested in LineageOS.


texts:
I am trying to understand the use case for zero knowledge password proofs.

Clearly, it is not ideal for a remote server to store a password hash. Then

I need to upload the password to the server for verification. The server knows my password.
I need to rely on SSL so that people can't eavesdrop the password.
If anyone hacks the server, they can do a dictionary attack against my password.

But what does ZKPP buy us vs uploading a public key to the server. Then, when I want to log into the server, the server generates a nonce, and I sign it with my private key?

That involves storing my private key on my machine. Someone could steal this. So it is common to encrypt the private key with a password. The password might be weak, so someone could perform a dictionary attack to try to decrypt the private key.

Is this the kind of attack that ZKPP is suppose to stop?


texts:
The example for IND-CPA secure schemes given is generally:

for a random r,

  Enc_k(m) =(r|| E_k(r) XOR m) where E is a PRF

But does the role of r and k really matter--i.e. isn't this equally secure?

  Enc_k(m) =(r|| E_r(k) XOR m) ?


texts: Verbatim of early work on public-key cryptography?

texts:
In late 1997, the history of public-key cryptography was turned around with the announcement (then extended) that

public-key cryptography was theorized in a 1970 note [1] by James Henry Ellis: The Possibility of Secure Non-Secret Digital Encryption;
a feasible realization of that, similar to RSA, was described in a 1973 note [2] by Clifford Christopher Cocks: A note on Non-Secret Encryption;
another feasible realization, similar to Diffie-Hellman key exchange, was described in a 1974 note [3] by Malcolm John Williamson: Non-Secret Encryption Using a Finite Field, and a 1976 note [4] (same author): Thoughts on cheaper Non Secret Encryption.

An account of these discoveries is given in a 1987 note [5] by J. H. Ellis: The History of Non-Secret Encryption; this is my rendering of an April 1998 ps archive, and is very similar to this document obtained from the NSA by FoIA case #19136 (narrative).
This calendar of event is confirmed by the December 1977 document [6] by J. H. Ellis: The Authentication Problem, obtained (with references redacted) in the same FoIA case, containing:

Non-Secret Encryption has now reached the phase where it is being considered for possible applications, and I find that many people are worried that the danger of spoofing may make its use untenable.

There is a writing by Simon Singh (in the The Code Book) about J. H. Ellis, C. C. Cocks, M. J. Williamson, and the coming out of the story.

All versions of documents [1]..[5] that I could locate (in 2014) are clearly re-typesettings (with the possible exception of the FoIA source for [5]). Ross Anderson hypothetized that there might have been alterations in the declassification process as an attempt to deny the existence of the then-secret GCHQ by re-attributing the documents to the CESG.
Also, I observe a discrepancy between an indication about [2] given in [3] by M. J. Williamson:

The information rate of the system is low in that 3 bits are broadcast for every 1 of the message. (The ratio in the method of [2] is 2 for 1).

and [2] as we read it, where there is nothing suggesting a significant expansion of plaintext to ciphertext; which in modern terminology is per textbook RSA, with public exponent equal to the modulus, and splitting of message in ECB mode:

The sender has a message, consisting of numbers $C_1$, $C_2$, $\dots$ $C_r$ with $0 < C_i < N$
He sends each, encoded as $D_i$ where $D_i = C_i^N$ reduced modulo $N$.

This opens a possibility that the author of [3] had access to material about [2] different from what we have (perhaps, more extensive than the remarkably terse version that we know). For example it could be that M. J. Williamson considered a single $C$, and the overhead related to $N$, as would be natural if $C$ was the key to another cryptosystem.
Are there public verbatim copies of any of the originals, or hope to obtain these?
Also: Is there an account of the circumstances of the early diffusion of any of these documents?


texts: Should we trust the NIST-recommended ECC parameters?

texts:
Recent articles in the media, based upon Snowden documents, have suggested that the NSA has actively tried to enable surveillance by embedding weaknesses in commercially-deployed technology -- including at least one NIST standard.

The NIST FIPS 186-3 standard provides recommended parameters for curves that can be used for elliptic curve cryptography.  These recommended parameters are widely used; it is widely presumed that they are a reasonable choice.

My question. Can we trust these parameters?  Is there any way to verify that they were generated in an honest way, in a way that makes it unlikely they contain backdoors?

Reasons for concern.
Bruce Schneier has written that he has seen a bunch of secret Snowden documents, and after seeing them, he recommends classical integer discrete log-based cryptosystems over elliptic curve cryptography.  When asked to elaborate on why he thinks we should avoid elliptic-curve cryptography, he writes:

  I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

This suggests we should look closely at how the "constants" (the curve parameters) have been chosen, if we use ECC.  This is where things look concerning.  I recently read a message on the tor-talk mailing list that seems to suggest the NIST curve parameters were not generated in a verifiable way.  That message examines how the parameters were generated:

  I looked at the random seed values for the P-xxxr curves. For
  example, P-256r's seed is c49d360886e704936a6678e1139d26b7819f7e90.  No justification is given for that value.

and ultimately concludes:

  I now personally consider this to be smoking evidence that the
  parameters are cooked.

Based upon my reading of FIPS 186-3, this appears to be an accurate description of the process by which the P-xxxr curves were generated.  So, should people be concerned about this?  Or is this just paranoia based upon loss of trust in the NSA?

See also these slides from Dan Bernstein and Tanja Lange, particularly pp.6-7, 8-10, 14-17 for further discussion about the NIST parameter choices.


texts: What is the structure of a Server Key Exchange Message structure when using a psk identity hint?

texts: I need to know the structure of a server key exchange message when using a psk identity hint.  I know the general structure but I can't find an example of where the identity hint fits in.  Thanks.


texts: Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?

texts:
While looking at this question I discovered the following here (question 5), and wanted to ask it as a separate question.

  Alice knows that she will want to send a single 128-bit message to Bob
   at some point in the future. To prepare, Alice and Bob first select a
   128-bit key k ∈ {0, 1}128 uniformly at random.
      When the time comes to
   send a message x ∈ {0, 1}128 to Bob, Alice considers two ways of
   doing so. She can use the key as a one time pad, sending Bob k ⊕ x.
   Alternatively, she can use AES to encrypt x. Recall that AES is a
   128-bit block cipher which can use a 128-bit key, so in this case she
   would encrypt x as a single block and send Bob AESk(x).
      Assume Eve
   will see either k ⊕ x or AESk(x), that Eve knows an initial portion of
   x (a standard header), and that she wishes to recover the remaining
   portion of x. If Eve is an all powerful adversary and has time to try
   out every possible key k ∈ {0, 1}128, which scheme would be more
   secure?

And the answer in the document is:

  They would be equally secure. Either way, Eve would not be able to
  learn the unknown portion of x.
  Even after trying every possible key
  (including the actual one), Eve will have no way of recognizing the correct
  plaintext or even narrowing down the possibilities in any way.
      Why is this? Well, since AES is a distinct permutation on {0, 1}128 under each possible key, and the key was selected uniformly at random, given any plaintext, each possible ciphertext is equally likely. So when AES is used for a single block with a random key of the same length, the effect is exactly the same as using a one time pad: the ciphertext reveals no information about the plaintext.

The question mentions a standard header, so I think its fair to assume we know all the plaintext except the very last bit. So my question, is this answer correct?


texts: Why is the discrete logarithm problem assumed to be hard?

texts: This might be a quite stupid question: since a naive brute force algorithm to solve the discrete logarithm problem will only take O(n) time for a group G with order n, why is it assumed to be hard to solve? Doesn't hard mean no polynomial algorithm to solve in the context of cryptography?


texts: Is double encryption really a bad idea? Are meet-in-the-middle attacks practical at all?

texts:
Meet-in-the-middle attacks are used to justify that attacks on ECC and double encryption will have complexity of $O(\sqrt{n})$ for ECC and $O(2^{n+1})$ for double encryption complexity instead of $O(n)$ and $O(2^{2n})$, respectively.

From my understanding (and please correct me if I'm wrong), meet-in-the-middle attacks rely on storing the results in a map. For example, if we double-encrypt with DES, we precompute all possible encryptions with all keys (which is $2^{56}$ possibilities), put them in a sorted map, and then decrypt with all possible keys, and see which of the decryption intermediate cipher-texts match what we have in the map. Given that map searches are $O(\log{n})$, then we have no problem.

I get this is possible for DES, albeit it's super-hard. We'll need around 500 TB of memory to do this. Well, let's say the NSA has that.

But why is the meet-in-the-middle attack taken seriously at all with ECC and AES, when they have 160 or 128 bit at least? If we used all earth's atoms to build SSDs to store all the map information I discussed up there, it probably won't be enough.

My question is basically: Is double-encryption a stupid idea given all these practical limitations when talking about encryption algorithms other than DES that have relatively long keys? And for ECC, is it true that ECC can be broken with $O(\sqrt{n})$ complexity?


texts: Can a zero knowledge proof be faked through http?

texts:
I'm working on a small blockchain project and I came across the idea of using zero knowledge proofs to enforce anonymity. I think I generally understand the idea, but I'm unable to find an explanation of a reliable way to implement this system with a protocol like HTTP.

For example, given the classic sudoku example, where you have found the solution to the puzzle and want to prove to someone that you know the solution, without showing the solution, you can just create a mapping where you shuffle the numbers. Whenever the person asks for a row, you show them the row they asked for, with the valid numbers.

My question is: If you are implementing this in HTTP and one server is trying to prove to the other that it knows the answer, when the verifier asks for a row via HTTP, cant the prover just provide a fake row of the numbers 1-9?  The prover would only need to generate a random combination of the numbers, making sure theyre all only used once, and the prover would deem this as valid.

I must be missing something here, but I fail to see how this could possibly be implemented between two servers. Any help would be tremendously appreciated


texts:
One of the main rules of the OTP is, that a key should never ever be reused.

But if we use some commutative operation (XOR for example) for generating the cipher text, then I don't see any difference between the message and the key, so can we also say that a message should never be reused?
With other words - even if we use different key for every message, could the system be weakened if we sometimes use the same message as before?


texts:
So far, I have been able to research on what it is:

authentication;
authorization;

using resource authd.

I still have not come across a definitive answer or source which explains:

Why do we use authd?
When to use it?
How does authd work?

Can anybody help me answer these questions?


texts: Should we use the new CAESAR competition ciphers?

texts:
At the beginning of this year, the CAESAR competition published the final portfolio for authenticated encryption algorithms.

I'm not a cryptographer and when I look at other applications, almost always AES-GCM or ChaCha20-Poly1305 is used for authenticated encryption.

So, I wonder why that is. Are the new CAESAR algorithms too new, or are there not enough implementations in the different programming languages? Other reasons?

As a programmer: When I design a new system today, should I consider the new CAESAR algorithms? Are there technical advantages/disadvantages?

Also, I heard of the Lightweight Cryptography project organized by NIST. Is not this competition redundant given the category 1: Lightweight applications (resource constrained environments) in the CAESAR competition?


texts: How to determine the signature type of RSA with a hash function?

texts:
I have the following function:

  rsaSha512Sign(arg1, arg2) - arg1 is the private key PEM,
  arg2 is the data to sign using SHA-512 with RSA.
  Returns the signature as a Base64 String.

With no additional documentation or source code available.

I assumed the description above meant to first hash with SHA-512, then apply RSA. However the signature is much longer than the hashed arg2.

How can I determine which algorithm was used?


texts:
I have seen that in MPC multiple models in different dimensions can be envisioned, like asynchronous vs synchronous networks, access to broadcast channels, and so on. However, a particularly interesting dimension is whether point-wise private and authenticated channels are available. In this direction, I have seen papers using the terms plain model, CRS model, or PKI model. I would like to understand what these models actually mean.
My concrete questions are the following:

I understand that the CRS model refers to a setting where a common reference string is provided to all parties. How can this help in computation? (any pointer to a concrete protocol that uses such setup would be welcome).
I assume that the plain model is just the lack of any setup like a CRS. Does this mean that not even secure channels are assumed? I can't think of a protocol for more than 2 parties that works in this setting. Again, pointers would be welcome.
If a public-key infrastructure (PKI) is assumed, what is it used for? Establishing secure channels?


texts: Shamir Secret Sharing - Threshold decryption implementation

texts:
I'm implementing Shamir secret sharing in C using OpenSSL.
I've split up the private key and I'm ready to start decrypting the original message using some of the shares.  I set $n = 5$ (5 shares total) and $t = 3$ (3 shares required to decrypt).
The way my encrypted message is stored is in a ${\rm msg} = (c_1, c_2)$ format, so I don't think I can just follow the example on Wikipedia, though I may be mistaken.  Here is how my book tells me to do it (image).  I've highlighted the particular part I'm stuck on:

"The dealer then sends $\langle i, s_i \rangle$ to authority $i$ in a secure manner.
To collectively decrypt an encrypted ballot $c$, where $c = (c_1=g \bmod p, c_2 = Y^r \times m \bmod p)$, $t$ such election authorities $\{i_1, i_2, \dotsc, i_t\}$, where $1 \le i_j \le n$, for $1 \le j \le t$, perform the following calculations (Desmedt & Frankel, 1990):

Each entity uses its share $s_{i_j}$ to calculate $\alpha_{i_j} = c_1^{i_j} \bmod p$ and broadcasts it.
Each entity calculates $c_{i_j} = \displaystyle \prod_{1 \le k \le t, k \ne j} \frac{i_k}{i_k - i_j} \bmod q$ $\color{red}{(\Leftarrow \text{HERE})}$ and $\mu_1 = \displaystyle \prod_{j=1}^t \alpha_{i_j}^{c_{i_j}} \bmod p$. Note that $\mu_1 = c_1^s \bmod p$.
Each entity calculates $\mu2 = \mu1-1 \bmod p$ and $m' = \mu2 \times c2 \bmod p$, where $m'$ is the recovered ballot."

In this portion, I'm confused by the values $i_k$ and $i_j$.  It seems to indicate that $1 \le i_j\leq n$ (values 1–5).  Then it says $1 \le j \le t$ (values 1–3).  Can someone straighten me out?
Let's say I'm using the following keys, just for reference:

Key #2 | 1234
Key #4 | 4567
Key #5 | 5678

Final question: do I need to $\bmod$ each result, or just the final sum?


texts: Differential addition on Montgomery curve

texts:
Point multiplication using Montgomery ladder technique over Montgomery curves only require x coordinate, which in many situation leads to faster implementation as compared to point multiplication over standard curves. However, to compute point multiplication over Montgomery curves, a differential point addition operation is required https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html instead of typical point addition operation on standard curves.

What does this differential point addition means and how it can be computed?


texts: What's a good security schema for many to many communication?

texts:
Assuming you have a "typical" group chat-room, with n participants connected together by a server (the server handles message routing).

Would be a good security schema which would allow for encrypted communication between all parties assuming the server is not "trustworthy"... or rather, assuming that the server will always do the routing correctly (it's up to the participants to figure out if there is a "Stranger" in the conversation) but it's not trust worthy in the sense that it can try decrypting the contents of the communication ?


texts: Is it safe to publicly announce the prime number in Shamir three-pass protocol

texts:
So say, I want to use a prime number p for anyone that wants to communicate with me using Shamir's Three Pass Protocol.

I will be maintaining my secret keypair (encryption exponent, decryption exponent) and will be expecting other parties to create their own secret keypairs according to the public prime p.

Assuming we have some method of authentication, so we won't be susceptible to man-in-the-middle attacks from that perspective.

But, is it safe to publish the prime number publicly?


texts:
I see many references to KDF2 here, but all links are broken and Wikipedia does not have an entry for KDF2.  Is KDF2 a specific standard for Key Derivation without a password?

Ultimately, I am trying to make sense of why KDF2 is listed as PRNG for Crypto++ on Wikipedia.


texts: Using pairings to verify an extended euclidean relation without leaking the values?

texts:
Let $P_i(x)$ be polynomials $i=1,...,n$, $s$ some value, and $g$ a generator of a group $G$ where the discrete logarithm is hard.

Assume a prover wants to convince a verifier having access to the values $g^{P_i(s)}$ that it knows polynomials $q_i(x)$ such that the following equation holds:

$q_1(s)*P_1(s)+q_2(s)*P_2(s)+\ldots+q_n(s)*P_n(s) = 1.$

The prover thus sends the verifier the values $g^{q_i(s)}$ and
uses bilinear maps to verify the correctness of the answer.

Can the following equation tell me whether it has correctly computed the $q_i(s)$:
$$e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$$
where $e$ is a bilinear map $G\times G\rightarrow G_1$.

So basically I want my bilinear map to verify on the exponents while hiding them. Is the second part of the equation correct? Or should it be 1, or $e(g,g)^{ord(G)}=1$?


texts: What is the difference between Columnar and Grid Transposition?

texts: Can someone explain with examples. Furthermore, is a key required to crack the ciphers?


texts: Can we possible to solve the LPN problem using Arora-Ge algorithm?

texts:
I recently studied how to solve the LWE (learning with errors) using algebraic relations proposed by Arora and Ge (paper : New Algorithms for Learning in Presence of Errors).
As I understood, for LWE instances of the form $\vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~q$ for some integer $q$, adversaries generate algebraic polynomials which has a root $e_i = b_i - <\vec{a}_i,\vec{s}>~mod~q$. If adversaries obtain sufficiently many polynomials, then they can recover the secret vector $\vec{s}$ using linearization technique.
Thus, I think that the Arora-Ge algorithm is also possible to solve LPN (learning parity with noise) problem since the instances are of the form $\vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~2$.
However, I cannot find any references about the result, so I guess that I have some mistakes.
Why can't I use Arora-Ge algorithm to solve the LPN?


texts: Are there any downsides to key stretching an already high quality entropic key?

texts:
For example, if we grab 50 bytes from a high quality source and run them through a key stretching function like Argon2 and have it generate a 32 byte secret for AES.

Is there any downside to this? Do we lose any entropy during this process since it comes from a high quality source already?


texts:
I have my own version of DH. It is basically a product of two DH's. It does provide authentication preventing MITM attacks without signatures but no forward secrecy if the private keys, as well as key exchange transcript between them, are fully compromised. Like this:

Alice has a private Key $s_a$ in Group $G_a$ of order $q_a$ modulo $p_a$ with generator $g_a$ as $P_a=g_a^{s_a}, (G_a,p_a,q_a,g_a,s_a,P_a)$.

In EC cryptosystem it is scalar multiplication. Similarly Bob has $(G_b,p_b,q_b,g_b,s_b,P_b)$.  During communication
Alice generates $x_b$ in $[1..q_b]$ and sends $h_b=[x_b]g_b$  to Bob
Similarly, Bob generates $x_a$ in $[1..q_a]$ and sends $h_a=[x_a]g_a$ to Alice.

Then the shared secret is $[g_a^{(x_a s_a)}]\cdot [g_b ^ {(x_b  s_b)}]$
They each calculate one part using own private key and the received message and the other one using the other side's public key and the generated secret $x (a/b)$. If forward secrecy is ignored, is there any problem with this?

I am surprised, DH is not used in PGP as much. Why?


texts: AES CBC with unique key per message, but fixed IV

texts:
I'm working on a project with a scheme in which c[i] = AES-CBC-Encrypt(msg_key[i], IV, msg[i]), and two distinct plaintexts never have identical keys. IV is a string of nulls.

Random IVs are not an option because fully deterministic behavior is essential in this application. The only available sources of entropy (passphrase, id and msg[i]  below) are used in key derivation, so no derived IV would be independent of the key. The value i is used for notational reasons only and is not available for cryptographic use, e.g. as a counter.

Keys are derived as follows:

passphrase = string chosen by user, constant for all messages

uuid = non-secret UUID, constant for all messages

msg[i] = plaintext of message i

root_key = PBKDF2(passphrase || uuid)

signing_key = HKDF(root_key, 0x01) # HKDF with extraction as in RFC 5869, IKM=root_key, salt=0x01, info="", L=chosen AES key length

text_id[i] = HMAC(signing_key, msg[i])

msg_key[i] = HKDF(root_key, text_id[i] || 0x02)

text_id[i] is known to recipients in another scheme beyond the scope of this question. The reason for deriving variable keys with a fixed non-secret IV instead of variable IVs for a fixed secret key is twofold:

Limit the amount of text encrypted with one key
Require knowledge of text_id[i] to decrypt any block of c[i] in addition to the passphrase. (The motivation for this comes from the system this scheme belongs to.)

It seems to me that this scheme addresses the major concerns I have seen raised regarding fixed IVs:

In order to produce an key collision in a chosen-plaintext attack, the adversary must find two messages that produce a collision in the HMAC function.
Two plaintexts with identical prefixes will not generate ciphertexts with matching or similar prefixes with any greater likelihood than two random plaintexts would.

Someone asked a similar question and got an answer that concerns me a bit:
Why should I use an Initialization Vector (IV) when I have unique keys?

  On the other hand, by not using a random IV, in some setups, one gives the adversary the same plaintext block enciphered with different keys (that would be the case if the first block of each plaintext is a known constant); this reduces the number of trial encryptions for exhaustive key search by a factor (at worse) equal to the number of different keys.

If I'm understanding this right, the concern is that if an attacker possesses N ciphertexts and knows that their plaintexts all start with a common prefix P at least one block in length, then the attacker can encrypt P under various keys until they duplicate the first block of one of the ciphertexts, at which point they will have discovered the key for that ciphertext. It seems like N needs to be quite large to make this practical, particularly for a 256-bit key.

But fixed IVs make me feel bad inside, and so I wanted to ask... what dangers might I be overlooking?


texts: Vigenère cipher: Security when key length and plaintext length are the same

texts:
I have read the Vigenère cipher is secure as long as the key length is the same as the length of the data to be ciphered.

Is this true when the same key is used multiple times?
In such cases, after how many uses would the key be considered insecure?


texts: Achieving 32-bit verification code with 16-bit CRC?

texts:
I am programming an embedded chip that has a hardware 16-bit CRC module. I have to protect some data bytes $d_0,d_1,...,d_{n-1}$ against corruption caused by sudden loss of power; a 32-bit CRC would provide the level of protection that I need, but the chip doesn't have that capability.

Unfortunately the CRC module uses a hard-coded polynomial that can't be changed. And I need the computation to be as fast as possible. Perhaps a table-based CRC algorithm would be fast enough, but the table would occupy 1 kilobyte of ROM, which I want to avoid if I can.

So my question is this: Can I somehow use this hardware CRC-16 module to reach the level of security that I need?

My current idea is to compute $CRC_{\mathrm{forward}}$, the CRC-16 of the data bytes $d_0,d_1,...,d_{n-1}$, and $CRC_{\mathrm{backward}}$, the CRC-16 of the data bytes $d_{n-1},d_{n-2},...,d_0$, and simply concatenate these two 16-bit CRCs to create a 32-bit EDC. Is this sufficient? Or are these two CRCs in some sense dependent?

More precisely: Suppose $D$ is the data, and $E$ is a corrupted version with $E \ne D$. Then I want the probability that $CRC_{\mathrm{forward}}(E) = CRC_{\mathrm{forward}}(D)$ to be independent of the probability that $CRC_{\mathrm{backward}}(E) = CRC_{\mathrm{backward}}(D)$. Is this the case here, or have I missed something?

Edited to add: If the discrepancy $E \oplus D$ is palindromic, and $CRC_{\mathrm{forward}}(E) = CRC_{\mathrm{forward}}(D)$, then $CRC_{\mathrm{backward}}(E) = CRC_{\mathrm{backward}}(D)$. So this idea doesn't work. Does anybody have a better idea?


texts: How can we deploy information-theoretic private information retrieval in practice?

texts:
I recently came to know that there is a notion called "information-theoretic private information retrieval".

The assumption is that multiple non-colluding servers have same data set and a client wants to retrieve a specific element (or multiple elements) in the data set by taking location(s) or keyword(s) as input without revealing the client's query to the servers.

I have some questions about this type of setting.

Who does guarantee that those multiple servers have same data set at a time?
Is this setting practically used by some companies?


texts: Voting protocol - How many dishonest tallying centres can the protocol cope with?

texts:
We have the voting protocol that is described here.

I am looking at the following exercise:

Determine how many dishonest tallying centres the protocol can cope with before the following properties no longer hold.

Only authorized voters will be able to vote.
No one will be able to vote more than once.
No stakeholder will be able to determine how someone else has voted.
No one can duplicate someone else's vote.
The final result will be correctly computed.
All stakeholders will be able to verify that the result was computed correctly.
The protocal will work even in the presence of some bad parties.

Could you give me some hints how we can determine that??


texts: Importance of supersingularity of elliptic curves

texts:
I'm struggling to understand the high-level idea of "Verifiable Delay Functions from Supersingular Isogenies and Pairings" (https://eprint.iacr.org/2019/166.pdf) by De Feo et al.
I will shortly outline the construction (p.12):
setup:

(choose appropriate parameters)
Select a supersingular elliptic curve $E/\mathbb{F}_p$.
Choose a direction on the horizontal l-isogeny graph and compute a cyclic isogeny $\phi : E \rightarrow E'$ of degree $l^T$ and its dual.
Choose a generator P of X1 = $v^{-1}$($\tilde{E}[N] \cap \tilde{E}(\mathbb{F}_p)$) and compute $\phi(P)$.

eval:

Compute $\hat{\phi}(Q).$

verify:

Verify the condition ($e_N(P, \hat{\phi}(Q)) = e_N(\phi(P), Q)$) for the pairing $e_N$.

For step 2, I wonder: Why does the curve need to be supersingular? I think that it has a certain implication on the structure of the isogeny graph from $E$, but that is only my guess.
For step 3: I assume that we do a random walk on the isogeny graph. I think that means: for any elliptic curve $E_0$, we construct an isogeny, compute it, jump to the new curve $E_1$ and repeat this process. I wonder: Isogenies project points between curves, but their result isn't really a new curve. So how can we compute an isogeny from $E_1$ without really knowing it? Why is it important that the isogeny graph is "horizontal"?
How can we prove that the isogeny actually takes T steps (.. which is necessary for the delay property of VDFs)? Or do we just publish all T intermediate isogenies? Why can we assume that all of them have order l?
The idea in step 5 and 6 looks clear to me: The condition (which is quick to evaluate) only holds for correctly computed isogenies, which can only be calculated with delay T.
Concerning P: $v : E \rightarrow \tilde{E}$ is defined as $(x,y) \rightarrow (u^2 x, u^3 y)$, $\tilde{E}$ is the quadratic twist of E. I understand that $E$ and $\tilde{E}$ are isomorphic, but I don't see why X1 is constructed in such a complicated way. Why can't we use the points on E as X1?
If my questions are too specific, I'd be more than happy for the explanation of supersingularity in this case! Would the construction also work for ordinary elliptic curves?


texts: Is this DH variant a workable zero knowledge proof?

texts:
I encountered the use the following protocol as a zero-knowledge proof (argument?) of knowledge of x given y=g^x for a typical DL group:

Verifier chooses c and sends g^c
Prover responds with g^(cx)

It is simpler and more efficient than Schnorr. Intuitively it seems satisfactory. It is zero-knowledge (can be simulated) and I cannot come up with a strategy for responding without knowing either x or c in advance.

That said, I cannot write an extractor for it (and if one did exist, it seems it would break DH key exchange). So it is not provably sound but let's pretend this fact isn't enough to scare me away. I am wondering if anyone can shed more light on why it might be problematic to do this in practice.


texts:
I am hoping to employ a signed set membership system which is valid iff each signer's contribution to the set is present.  The system should allow for two or more mutually exclusive signed sets to be merged into a new signed set without requiring new signatures.  Also, unless the set has a single signer, it should be intractable with the signed set alone to discover which elements of the set were signed by which signer.   The following describes the system:

EdDSA signatures are of the form:  $S = (r + H(M,R,A)*a)$ $mod$ $l$.

Consider the modified form: $S = (a + H(M, R)*r)$ $mod$ $l$, where we omit the public signing key A from the hash function and swap the private signing key $a$ with the private session key $r$.

Now, suppose we have two signers, $A_1$ and $A_2$, having signed a set of three elements, $(M_1,R_1)$, $(M_2,R_2)$ and $(M_3,R_3)$.  The signature is then:

$S_{set} = (a_1 + a_2 + H(M_1,R_1)*r_1 + H(M_2,R_2)*r_2 + H(M_3,R_3)*r_3)$ $mod$ $l$

and is verified iff:

$S_{set}*B = A_1 + A_2 +H(M_1,R_1)*R_1 + H(M_2,R_2)*R_2 + H(M_3,R_3)*R_3)$ $mod$ $l$

So, does this system seem to accomplish the stated goals while maintaining the security of the unmodified EdDSA algorithm?


texts: Finding the relationship given by the generating elements of a non-abelian group (for a maximum case) where they correspond to finding cycles

texts:
Let $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$, where $p$ and $q$ are odd distinct primes. Let $G$ be generated by the elements $s=(g_1,e_q)$ and $t=(e_p,g_3)$,

$g_1,e_p \in \mathbb{Z}_p \times \mathbb{Z}_p$,

$g_3,e_q \in \mathbb{Z}_q$,

$e_p,e_q$ are identity elements. $|s|=p, |t|=q$.

$\phi:\mathbb{Z}_q \rightarrow Aut(\mathbb{Z}_p \times \mathbb{Z}_p)$

$e_q \rightarrow \phi_{e_q}$

$0 \rightarrow \phi_{0}$

$1 \rightarrow \phi_{1}$

.

.

.

$q-1 \rightarrow \phi_{q-1}$

So for any $\phi_k, 0 \geq k \geq q-1$, we can determine $\phi_k(g_1)=g$, where $g \in \mathbb{Z}_p \times \mathbb{Z}_p$ ($g$ is some element and it will change according to $\phi_k$).

Let $\mathbb{Z}_p \times \mathbb{Z}_p$ be generated by $g_1$ and $g_2$. Let $|g_1|=|g_2|=p$. Then any $g \in \mathbb{Z}_p \times \mathbb{Z}_p$ can be expressed in terms of $g_1$ and $g_2$.

For, $\phi_k(g_1)=g$ let, $\phi_k(g_1)=g=g_1^{m_1} g_2^{m_2} \rightarrow (1)$

For a product of elements, say $sts$,

$(g_1,e_q)(e_p,g_3)(g_1,e_q)$ we can simplify as,

$(g_1 \phi_{e_q}(e_p), e_q g_3)(g_1,e_q)$

$(g_1 \phi_{e_q}(e_p) \phi_{g_3}(g_1),  g_3 e_q)$

$(g_1 \phi_{e_q}(e_p) \phi_{g_3}(g_1),  g_3) \rightarrow (2)$

Now as mentioned by (1), $\phi_{g_3}(g_1)$ also can be written in terms of $g_1, g_2$ and $\phi_{e_q}(e_p)=e_p$. Therefore, the first coordinate of the above ordered pair in (2) will simplify as some power of $g_1$ and $g_2$. Let it be as,

$(g_1^{m_3}g_2^{m_4}, g_3)$

Now suppose the group elements satisfies relationships such as,

$stst^{-1}s=e \rightarrow (3)$ (No. of elements in L.H.S. =5)

$ssts^{-1}t^{-1}st=e \rightarrow (4)$ (No. of elements in L.H.S. =7)

.

.

.

$sts^{-1}ts...ts=e \rightarrow (5)$ (No. of elements in L.H.S. =$p^2q$)

(These relationships correspond to finding cycles in Cayley graphs if we draw the Cayley graph of the group $G$ with repect to $s,t$.)

Having $p^2q$ no. of elements in the L.H.S. is the maximum possible no. of elements that can be present such that the product is equal to the identity $e$, where $e=(e_p,e_q) \in (\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$.

In (3)-(5) also if we simplify in the way we obtained (2), we will get something similar.

Suppose we get as,

$(g_1^{m_5}g_2^{m_6}, g_3^{m_7})=(e_p,e_q)$ for (5). Can we solve for $m_5 , m_6 , m_7$ values if we know $p,q,g_1,g_2,g_3, \phi$? (May be using the data that (5) gives the maximum case?)

What is the method of obtaining the solutions? Can we solve for $m_5 , m_6 , m_7$ by a system of linear congruence relations?

Thanks a lot in advance.

Note: we don't know (5) but only knows that (5) gives maximum case and $p,q,g_1,g_2,g_3, \phi$ values. That's why I'm asking for a way of solving algebraically.

Even and idea or guidance regarding this is great. Many thanks again.


texts: Is there an algorithm that allows verification that 2 encrypted or hashed bits of data are the same, given that I may only know half of the key/ salt?

texts:
We have an interesting problem.

Currently, we store a salted hash of some secret key known only to the clients of our clients to allow us (and our clients) to find other records that were generated by the client's clients, without either us or our clients being able to identify the client's client or know their secret key. We know the salt.

We now have a requirement to change the salt every 12 months, but we still need to be able to match the last year's records.

The only way I can see to do this is by keeping the current salt and the previous salt, and storing every record with both hashes, then when we want to find other records, look for either of the two stored hashes in either of the two stored hashes on the other records, which is double the  computation on storage, double the storage and up to 4 times the search time.

I think we need something like a 2-part key, so every 6 months we can generate a new half-key, and delete the oldest half key, so if the key is $k_1k_2$, in 6 months I can throw away $k_1$ and generate $k_3$, so the new full key is $k_2k_3$.

So what I'm looking for is a function where the client's client passes in their key, $s$, and we pass in a 2 part key, $k_n$ and $k_{n+1}$, and receive a digest, such that there is another function where we can pass in two digests and the current $k_nk_{n+1}$ and get true if the two digests were generated with the same $s$ and share at least one of $k_n$ and $k_{n+1}$, without us ever being able to tell what $s$ is.

If it's not possible, then we will have to go with the double hash storage, but what I'm describing sounds like something that is possible with commutative operations...


texts: Encrypting AES cipher text with fully homomorphic encryption

texts:
Suppose I run a fully homomorphic encryption scheme (FHE) on a cipher text c, generated by running AES on plain text m and get c' as the output.

What would the output be if decryption of AES is run on c'? Would the decryption of c' using AES key result in a cipher text that decrypts to m if the decryption function of the FHE was applied?


texts: Composing and Inverting Symmetric Encryption Keys

texts:
Using a symmetric encryption algorithm $E$ on a message $M$, users usually send $E(M)$ to the recipient and then the recipient will compute $E^{-1}(E(M))=M$ to retrieve the message. For what symmetric encryption algorithms would it be equally secure to instead send $E^{-1}(M)$ and have the recipient compute $E(E^{-1}(M))=M$?

Suppose we have two symmetric keys $K$ and $L$ to encrypt $M$. We could compute $K(L(M))=M'$. Is there any secure encryption algorithms such that from $K$ and $L$, we can compute a new key $KL$ where $KL(M)=K(L(M))$?

I know XOR has both of the above properties if used on just one block. But my question is: does there exist any secure symmetric algorithms that have both properties and can be used for multiple blocks?


texts: A single password manager vs password generator/hash

texts:
I have been wondering about the options available for managing passwords. However, they all seem to fail if the master password is compromised (which isn't a big surprise).

On one hand you have system's like LastPass which store all your passwords using a master password to encrypt them.

  In other words, your computer encrypts your passwords with your email and master password and sends that data to Lastpass. When you authenticate with your master password at Lastpass.com, Lastpass.com returns all your encrypted passwords, which are decrypted locally on your computer with your email and master password.

On the other hand you have systems which take a master password and then can generate a unique (but always the same) password by adding the domain or other identifier. This is perhaps more safe in one way since nothing is ever stored or transmitted anywhere. However, it's less safe in another way since you can never change an individual site's password if it is ever compromised.

In both cases it seems that knowing the master password either gives you the other passwords, or allows you to generate them. Are their any other options? Am I missing any other large security problems these password managers create?


texts: What signature schemes allow recovering the public key from a signature?

texts:
It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone.

This seems like an interesting property; as far as I know, RSA doesn't share it.

Depending on the application, this can both be an advantage (shorter messages, as the public key or a key id doesn't have to be attached) and a disadvantage (if confidentiality is required, the signature has to be encrypted).

Which other cryptographic signature schemes have that property? I'm especially interested in RSA, Ed25519 and (non-elliptic) DSA.


texts: Is there a recent and comprehensive survey on zero knowledge proofs? I'm trying to find one which provide more details than the two chapters (19/20) in Boneh and Shoup's book (a grad course in applied cryptography)


texts: Multi Key Encryption but read only part of data

texts: Is there a way to encrypt data/document with multiple keys, but every key is only allowed to read/decrypt only a certain part of the document and not the whole document? The document cannot be sub divided into multiple smaller documents for various users.


texts: AES-CBC Padding: Why always attach 16x 0x10 pad?

texts: Why do we have to always attach a 16x 0x10 pad even though the last block is already at block-length?


texts: Threshold lower than $\dfrac{n}{2}$ in distributed key generation

texts:
While I was studying protocols for distributed key generation with malicious adversaries, Gennaro et al.$^{[1]}$ pointed out that the protocols that provide both secrecy and robustness should have a threshold lower than $\dfrac{n}{2}$. However, I do not see how the robustness of the scheme can compromise the secrecy of the protocol in the case of a threshold higher than $\dfrac{n}{2}$.
Does someone have an explanation for this?

[1] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin, “Secure distributed key
generation for discrete-log based cryptosystems,” in International Conference on the Theory and Applications of Cryptographic Techniques, pp. 295–
310, Springer, 1999.


texts:
Trying to get my head around digital signatures and hit a slight block. The book I am using gives the following information

Device A hashes a message to create a message digest
Device A encrypts the digest with device A's private key to create a signature
Device A adds the signature to the message Device A encrypts the whole message (including the signature) using device B's public key
Device A sends the message to device B

Device B decrypts the message with device B's private key
Device B splits the signature off of the message
Device B decrypts the signature using device A's public key to get the message digest
Device B hashes the message to get a message digest
If the message digest device B created is the same as the one decrpyted, the message has not been tampered with

All fine, but how does device B know what hashing algorithm was used to create the message digest?


texts: How to show that a one-way function proves that P ≠ NP?

texts:
According to this, the existence of a one-way function proves P ≠ NP. What is the proof of this?

One way to show this is that if P = NP, then any function is easy to invert. P and NP are about decision problems though, not computation problems.

(Basically, my question is about how statements about decision problems relate to computational problems.)


texts: how to get top 10 numbers after using Pallier cryptosystem

texts:
Assume I encrypted 1000 Integers using the pallier cryptosystem.

Since each time I encrypt a number using pallier I'm using a random r element from Z* then the encrypted numbers aren't in order anymore i,e: we have 2<3 but Enc(2) with pallier doesn't necessarily mean it is < then Enc(3) with pallier.

So how would it be possible to get the top 10 biggest Integers out of those 1000 Integers  when the numbers are encrypted?


texts: Single-purpose symmetric encryption scheme for single files

texts:
I'm writing a simple password manager program that will encrypt/decrypt a single file (it's size will most likely stay under a few K). This is my initial file format design:

1. hmac                        plaintext
2. hmacSalt                    plaintext
3. keySalt                     plaintext
4. iv                          plaintext
5. [file header/metadata]      ciphertext
6. [file content]              ciphertext

Encryption scheme:

$hmacSalt, keySalt, iv := CSPRNG(...)$ where each value is separately assigned
$derivedKey := scrypt(key, keySalt)$ where $key$ resembles the master keyphrase, provided by the user
$C := E(derivedKey, iv, 5 || 6)$ where $5$ and $6$ refer to the lines denoted in my file format design
$hmac := hmac(scrypt(key, hmacSalt), 2 || 3 || 4 || C)$

Decryption scheme:

$derivedKey := scrypt(key, keySalt)$
$compare(hmac, hmac(scrypt(key, hmacSalt), C))$ where $C$ refers to complete file content, with the HMAC's size as offset
$P := D(derivedKey, iv, C)$ where $C$ is the ciphertext (which is composed of $5$ and $6$)
Parse file header and content

The encryption cipher is AES-256 and HMAC's underlying hash is SHA2.

My questions:

As you can make up from this encryption scheme, I'm using the encrypt-then-authenticate approach to enforce ciphertext integrity. In step 2 of the decryption process I perform this authentication step. If the calculated HMAC turns out to be equal to the HMAC in the file, does this mean, apart from the implied ciphertext integrity, that the supplied passphrase is certainly the same as the original passphrase used for the encryption, resulting in this ciphertext? Or should I perhaps use an additional plaintext HMAC, stored in the encrypted file header, to ensure passphrase validity.
I'm unsure which cipher mode of operation would be most suitable for this kind of encryption. I couldn't find much information about this, as most recommendations are based on network-based cryptography. CBC and CTR both seem good options, and I believe the security difference are negligible, as long as the implementation is done correctly. In Cryptography Engineering, the authors used to recommended CTR, but now prefer CBC as it's easier to "get right". CTR seems more susceptible to a poorly generated IV, as it's essentially a stream cipher. Which one would you recommend?
This question partially depends on my choice of cipher mode (question 2). Does generating a new salt and IV for each file mutation really offer a noticeable security benefit? This may sound like a stupid question, but file mutations only take place sporadically, and thus a sufficiently large IV should deter any ciphertext attacks?
According to the Horton Principle, the MAC should "Authenticate what is being meant, not what is being said". I understand this includes the structure of the file etc., but would including salts and IV be wise as well?
In my design I'm using the same underlying key as input for the encryption and HMAC function. Does the use of two separate salts offer any security benefit, or is reusing the same key inherently insecure anyway?

PS: I couldn't decide if this question would be more suited for security.stackexchange.com or not, so please forgive me if that's the case.


texts: Showing the non-pseudorandomness of a generator

texts:
I'm sorry if this question is too novice. It comes from a practice midterm in a cryptography course which I'm taking, and my confusion here is really that I don't know the "tools" that one uses in practice for this sort of question. The notation (and class) is Katz's.

I've been given a PRG $G(s)$; I'm trying to show explicitly that $s\mathbin\|G(s)$ is not a PRG. Intuitively, I'd expect both components to be random-seeming, so there's nothing obvious that sticks out to me to XOR or manipulate.


texts: How to understand why an algorithm uses additive or multiplicative homomorphic

texts: If we take the example of LWE (Learning With Errors) how does one know if it's homomorphic by addition or multiplication?


texts: Encrypt using ECDH with two different EC public keys, minimizing payload size

texts:
Let's say Alice has the private EC keys $a$ and $b$, with a base point of prime order $G$. Alice computes the corresponding public keys $A = aG$ and $B = bG$, and sends them to Bob.

Bob now wants to encrypt asymmetrically a message $m$, so that only Alice can decrypt it. Furthermore, Bob wants the encryption to be "maximally" protected by both secrets ($a$ and $b$). He will use ECDHE to derive one or more shared secrets, and encrypt the message with AES, XOR, or some such.

The thing is, we want the payload (ciphertext and metadata) to be as small as possible.

Ideas:

Bob could create two different ephemeral private keys ($e_1$ and $e_2$), derive two different shared secrets ($s_1 = e_1A$ and $s_2 = e_2B$), and cascade encrypt the message with these two secrets: $x = Enc_{s_1}(Enc_{s_2}(m))$.
Derive $s_1$ and $s_2$ in the same way as in (1), but instead of using cascade encryption, generate a single secret, for example by doing $s = s_1 \oplus s_2$. Then $x = Enc_s(m)$.
Do the same thing as in (2), but re-using the ephemeral private key, ie. $e_1 = e_2$.
Do just a regular ECDHE to compute a single shared secret using the public key $C = A + B = aG + bG = (a + b)G$. To recover the shared secret, Alice will have to use the private key $c = a + b$.

Observations:

We want to minimize the ciphertext payload and thus, the metadata. In both (1) and (2), two ephemeral public keys have to be transmitted to Alice in order for her to decrypt the ciphertext. In both (3) and (4) only one ephemeral keypair is used, so they are preferred from the point of view of message compactness.

Questions:

Is (2) at least as secure as (1)?
Would it be better to use a KDF for combining the shared secrets in (2)?
Is it safe in (3) to re-use the ephemeral key?
Is it secure to use the construction in (4)?
What are the trade-offs between (2) and (4)?

Thanks!


texts:
I have been reading up on RSA attacks and came across one that could be called a least-significant-bit (LSB) oracle attack.

For the sake of clarity lets define RSA primes $(p, q)$, private key $d$ and the public key $(e, N)$ where $N$ is the modulus.

Now assume an oracle exists that will decrypt a given ciphertext $C$ using the private key $d$ and checks the parity of the decrypted cipher. i.e. it will return true or false if the decrypted cipher was even or odd respectively.

If an attacker intercepts an encrypted plaintext $C = P^e \mod N$ he could multiply it by $2^e\mod N$ (essentially doubling the original plaintext) and send it to the oracle. The oracle will decrypt and find $2P\mod N$. Now if $2P>N$ then the remainer will be odd, since $N$ is odd. If $2P<N$ then the remainder will be guaranteed to be even. The attacker will now know that either $P<N/2$ (oracle returned even) or $P>N/2$ (oracle returned odd).

This is the part where I am stuck, because apparantly you can somehow iteratively apply this principle and by iteratively shrinking the bounds of $P$ completely recover $P$ in $\log_{2}N$ iterations. I am having trouble seeing how the iteration would work.

If possible I would prefer a hint over a fully written out solution as I will learn more from doing it myself. I just need a little nudge in the right direction. Much appreciated.


texts: Extracting secret image from cover image

texts:
I want to develop a steganography project with using exploiting modification direction method. I started to try and understand how the method works, but I have some questions about decryption.

I hid the secret image in a cover image larger than the secret image by 9 times. So when it comes to decryption I'm not going to use all of the pixels of the cover image: I only need to use those pixels used during encryption. But if the pixel count isn't provided before then how can I know how many pixels should be used to extract the secret image?

If I use all pixels of the cover image the resulting image's size doesn't match the original one and it is quite likely there will be flaws in the image.