texts:
I have a question about how I need to solve the following:

A sentence has been changed to ASCII and then encrypted with the formula $E(x) = ax + b \bmod 256256$. All I know is that the first 4 letters are: W I S K

This is the encrypted message:

 064066 158368 092525 143358 099354 141643 110102 051667 024006 190286 133343

How do I go about solving this? I first tried to program a brute force but I actually want to understand how to solve it. I tried working with the extended euclidean algorithm as well, but didn't get far.


texts:
Just started reading Oblivious Transfer. I am searching for a proof of security based on RSA implementation but I can't find anything simple to understand. Can someone direct/show me to an easy to understand proof of it's security?

Many thanks


texts: Could the multisignature scheme in bitcoin alternatively also be implemented by means of a Shamir Secret Sharing Scheme?

texts:
When I first came across the Bitcoin multisignature scheme, I wondered that it remarkably looked similar to what Shamir Secret Sharing does (SSS), but then by using facilities in the bitcoin scripting language instead. I recently read that the Monero cryptocurrency are also looking at implementing a multisig scheme.

I wonder, would it be possible to implement a multisign scheme completely separate from the cryptocurrency's blockchain just by using SSS?

Edit: To avoid confusion, I have now used the symbols $\oplus$ and $\odot$ for elliptic sum and multiplication, while using $+$ for undistorted arithmetic (for use in SSS).

Say that we have 3 parties, Alice, Bob, and Charlie, and that they want to set up a 2-of-3 signature scheme. If $s$ stands for secret (private key) and $p$ stands for public key, and $G$ stands for the generator, and if we carry out all multiplications in the associated modular field, we have:

Alice:   $s_1$ and $p_1=G \odot s_1$
Bob:     $s_2$ and $p_2=G \odot s_2$
Charlie: $s_3$ and $p_3=G \odot s_3$

We could create a composed key $(s_0,p_0)$ with these individual keys, just by adding them up:

$s_0 = s_1 \oplus s_2 \oplus s_3$
$p_0 = p_1 \oplus p_2 \oplus p_3$

Alice, Bob, and Charlie would disclose $p_1$, $p_2$, and $p_3$ to each other, and hence have knowledge of $p_0$, but would not know the combined secret $s_0$ that would control funds parked in $p_0$.

Alice now needs to split her secret over Bob and Charlie.

Say that Alice pick an arbitrary number $a_1$, and constructs a line  $y=s_1+a_1x$, in which her secret $s_1$ is the intercept. In accordance with the SSS, she can arbitrarily pick two points $(x,y)$ on that line. The point $(x_{AB},y_{AB}=s_1+a_1x_{AB})$ will go to Bob and the point $(x_{AC},y_{AC}=s_1+a_1x_{AC})$ will go to Charlie.

Of course, Alice could be lying, and just share whatever numbers to Bob and Charlie. Therefore, in a elliptic twist to the Feldman scheme, to keep Alice honest, she also supplies the numbers $G \odot s_1$ and $G \odot a_1$. This should allow Bob and Charlie to verify that their shares in $s_1$ are valid, while Alice would also not reveal the secrets $s_1$ and $a_1$. For example, Bob could verify his share in Alice's secret by checking that the following holds:
$$G \odot y_{AB}
= G \odot (s_1 + a_1 x_{AB})
= G \odot s_1 + (G \odot a_1) x_{AB} $$

All players send their shares as following:

from/to     Alice   Bob     Charlie
Alice               AB      AC
Bob         BA              BC
Charlie     CA      CB

Where each share is defined as the following tuples:

$AB = (x_{AB},y_{AB},G \odot s_1,G \odot a_1)$
$AC = (x_{AC},y_{AC},G \odot s_1,G \odot a_1)$
$BA = (x_{BA},y_{BA},G \odot s_2,G \odot a_2)$
$BC = (x_{BC},y_{BC},G \odot s_2,G \odot a_2)$
$CA = (x_{CA},y_{CA},G \odot s_3,G \odot a_3)$
$CB = (x_{CB},y_{CB},G \odot s_3,G \odot a_3)$

Not one party has full knowledge of $s_0$. However, any two parties have enough knowledge to reconstruct $s_0$.

Charlie now deposits the amount to escrow in the 2-of-3 signature scheme on public key $p_0$.

If Alice wants to assist Bob to gain control over $p_0$:

Alice discloses to Bob: $s_1$ and $(x_{CA},y_{CA})$
Bob reconstructs $s_3$ from $(x_{CA},y_{CA})$ and $(x_{CB},y_{CB})$
Bob reconstructs $s_0$ from $s_1$,$s_2$ and $s_3$ and now has control over the funds in $p_0$.

I wonder, is there a reason why this would not work as an alternative to the existing Bitcoin multisignature scheme?


texts: Effective period of Mersenne Twister generator output

texts:
Mersenne Twister generator has a period of (2^19937)-1, but it is period of internal states.

Any idea what is the effective period of MT 32 bit output - period over which 32 bit output does not repeat. It has to be smaller than (2^31)-1 but I couldn't find definite answer.

Thanks


texts: When was the RSA 64-bit key introduced into internet encryption?

texts:
When (if ever) was a key length of 64 bits used in "internet encryption" and when was that "cryptographic standard" first introduced?

Following up, when did "internet encryption" key lengths change to 128-bits, then to 256-bits, 512-bits and so on up to 2048-bits? Was the same "cryptographic standard" used?


texts: Determining the primitive root $g$ of $p$, given $B=g^b \pmod p$

texts:
This is related to Diffie-Hellman key exchange.

Suppose you're given a prime $p, b \in \{0,1,...,p-2\}$, and $B$, such that
$$
B= g^b \pmod p.
$$

Assuming that $$\gcd(b, p-1)=1$$ How could you determine the primitive root $g$?


texts: How are points on an elliptic curve discretized?

texts:
I'm a working programmer (read: a person without a maths degree) trying to get a better grasp on elliptic curves specifically in the context of elliptic curve cryptography (though to be clear, this is for personal development — I'm in no way trying to roll my own crypto).
One concept that's difficult to grasp for me is that curve points in the ECC context are often discretized over a finite field — specifically, a finite field having cardinality of the form $P^n$ for some large prime $P$. This gives points on elliptic curves a congruent behaviour under modular arithmetic whose value I can understand in this setting.
My question here is, how is the set of discrete points on elliptic curves determined for ECC applications? I'm entirely willing to do the legwork in terms of getting more math context, but I think I've got a lack of mathematical vocabulary which has made searching for papers explaining this difficult.


texts: Proof of correctness of Exponential ElGamal

texts:
I have an assignment for proving the correctness of both ElGamal and exponential ElGamal homomorphic features (multiplicative and additive respectively). I have managed to prove the former but am struggling on proving the latter. I have reached the point where adding two ciphertexts $c_1$ and $c_2$ to obtain $c_3$, where:

$$c_3 = (a^{r_1} + a^{r_2}, m_1+m_2(b^{r_1} + b^{r_2}))$$

Have I gone completely wrong?


texts: Signing and verifying message consisting of several parts

texts:
Given a message $m$ that consists of several parts. we want to be able to verify individual parts or a combination thereof.

The simplest solution is independently signing each part. But since asymmetric signatures are relatively expensive to compute and verify, that might not be the most efficient approach.

Is there an efficient and faster alternative approach for this problem?


texts: Why does consecutive permutations or consecutive substitutions not enhance security?

texts: My professor stated that permutations which are done repeatedly does not further enhance security than just one permutation. He also stated that fact this applies to consecutive substitutions as well. Algorithms such as AES which intertwine permutation and substitution in each round does in fact increase security. I understand this is because if they are intertwined, then the substitution effect will be diffused by the following permutation. However, if he were to ask this question in a test: why does repeated permutations or substitutions not enhance security? I won't be able to think of a good answer.


texts: Can binomial distribution be used to sample noise for Ring-LWE-based homomorphic encryption?

texts:
Homomorphic encryption schemes based on Ring-LWE need to sample the noise terms from a discrete probability distribution $\chi$ over the integers with support $[-B,B]$. For example, the Fan-Vercauteren encryption scheme uses the discrete Gaussian distribution.

Several Ring-LWE-based public key encryption and key encapsulation schemes, e.g., NewHope, Kyber, etc, use binomial distributions instead of discrete Gaussians since they are easier to sample from. Can a similar optimization be made for homomorphic encryption schemes?


texts: Are there any practical ways to transfer random data securely?

texts:
The owner of the random.org service recommends that you do not use randomly generated numbers from their website in cryptographic keys. This makes sense, but it got me wondering. Is it possible to securely transfer random values in such a way that they are still viable for use in cryptography?

They can be trivially transferred with a physical cable, but what about when such an instance is impossible? For instance, when a true random number generator is physically separated from the client which needs random numbers, and both machines are in control by the same person.

Is this practical to do securely?


texts:
16 byte key where each byte is in range 0-255, generated using cryptograhic PRNG will be believed to have 128 bit strength.
What would be a bit strength of a key generated using same quality PRNG, also of 16 byte length, if each byte instead of being one of 256 random values, would be one of 16 hexadecimal characters?
Would that be calculated as (128 x 16) / 256 = 8 bit?


texts: Tracking Spread of CoV-19 along Social Graph while Protecting Privacy and Anonymity

texts:
In several countries there are currently ideas to track the spread of HCoV-19 by use of mobile location data. A good knowledge of the virus' spread throughout communities and countries will certainly be a huge benefit to everyone, as it provides data that allows fast and decisive, but ultimately localized, action. However, gathering health and location data is a huge invasion of privacy and we should not be too keen about simply handing this information to the government or any third-party app.

Here is a rough idea that I think could allow to track infections in a way that respects privacy and (in parts) anonymity.

When Alice and Bob meet, they exchange IDs and keys. They also save the date of their encounter.
Alice and Bob publish their health status as ciphertext (using the ID and keys from earlier) on a centralized server.
When Alice falls ill and is tested positively she updates her status.
Bob regularly checks the list for updates under Alice's ID, he can decipher Alice's status and will be warned that he was in contact with Alice during a time she was not showing symptoms, but might have been infectious. He can now choose to self-isolate or implement stronger social distancing measures in order to reduce the number of people he infects.
At the same time Charlie does not have access to Alice's or Bob's health status, nor should he be able to guess from the ID who the person is.

This procedure can certainly be generalized/modified in several ways.
One could, e.g., also associate an ID to meetings, gyms, grocery stores such that it's not necessary to exchange IDs and keys for every person. They would be assigned a virtual health status, depending on wether one of the attendees might have been infectous.

Another idea: instead of only publishing "healthy/ill", one could publish one's degree of seperation to the next ill person (so a value of 2 would mean that one of my friends was in contact with someone who has been tested positive and whom I met subsequently at a time when he might have been infectious but has not yet shown symptoms. This will then signal to me that I should skip large meetings and reduce contact to at-risk persons in the next 2 weeks)

My questions are:

Are there glaring privacy and anonymity flaws in the procedure outlined above?
Is there a way to further anonymize everything? Eg. such that Bob can't reveal Alice's ID to Charlie. Or such that checking the published list only reveals that one of my recent contacts has been tested positive, but it's not possible to deduce which one.
Is there a protocol that already implements the cryptographic requirements of this procedure? I imagine standard end-to-end encryption will not scale well. Also, since Alice would need to encrypt and publish her status once for every person she had contact to in the last few weeks, it might be possible to reverse-engineer parts of the social graph, which might compromise anonymity.


texts: What are the consequences of removing a single byte from a sha256 hash?

texts:
I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash.

Sha256 would meet this criteria since it outputs 32 bytes.

However, I'd also like to include a "version" byte in case I need to change the hash algorithm in the future. This would require 33 bytes.

One simple solution is to simply chop off the last byte and only use the first 31 bytes for the lookup.

Does this bias the hash in any way?
My assumption is this would decrease the computational power needed to reverse the hash by 1/256th. Is that correct?
My assumption is this would increase the likelyhood of a hash collision by 25600%. Is that correct?


texts: Enigma ring settings - is the relative location of the turnover all that matters?

texts:
I understand that the ring setting of an Enigma rotor changes the alignment between the internal wiring and the letters on the ring. For example, in the diagram below, rotor I has ring setting 2 (B), which causes current entering at position A (the center) to flow through the wiring from Z to J (internal positions) which corresponds to A -> K based on the visible indices on the rotor.
However, we could achieve the same result with ring setting 1 by using Z as the top character, which would cause current to flow from Z->J (internal positions) corresponding to Z->J on the visible indices.
This leads me to believe that the only real impact the ring setting has on the encryption is that it changes the location of the notch (that steps the next rotor) relative to the internal wiring. For plain texts that are long enough to step at least one rotor this will result in a substitution that cannot be recovered by permuting the rotor starting positions alone.
Is there anything else I'm missing?


texts: Why is TLS SRP verifier based on user name?

texts:
I don't understand why TLS SRP (or SRP in general) includes the user name in verifier calculation, given that user name is basically public.

From spec RFC 5054 $x$, which is then used to calculate verifier, is calculated as follows:

x = SHA1(s | SHA1(I | ":" | P))

I thought about removing 'I' to facilitate changing of user names(verifier won't have to be recalculated). Then $x$ will be:

x = SHA1(s | SHA1(P))

However I'm not sure if it will have any negative impact on the protocol. Will that change decrease security?


texts: In the RSA DES challenges, how did the contestants know they had found the right key considering they weren't given any plaintext?

texts:
If the contestants were given both the plaintext and ciphertext, it's straightforward. Just bruteforce all 56-bit keys until you find one that maps the given plaintext to the given ciphertext.

But from what I understand, the contestants were given only the ciphertext and the initialization vector. I'm confused as to how they cracked the challenge without any plaintext.

What I imagine they did was:

Ok, we know the plaintext is less than or equal to the size of the ciphertext.
Calculate all possible plaintext from 1 bit up to the bit size of the ciphertext.
Calculate all possible 56-bit keys.
Run each plaintext through all 56-bit keys until they found a mapping.

But this doesn't make sense given the sheer size of the possibilities.

So since they weren't given any plaintext, how did they know they'd found the right plaintext/key combination?


texts:
question is here. determine true or false

I think that in the RSA cryptosystem, one should use large private key because of the low exponent attack.

Also, In RSA cryptosystem, one should use large public key because of the low exponent attack.

Is my thinking right?
How much long or big do these key need to be?


texts: Password Hashing Security Using Scrypt & Argon2

texts:
I am developing an app where the following cryptographic system will be in place:

Elliptic Curve key exchange (curve: secp521r1)
Double Scrypt the shared secret with different salts
Pass this result through Argon2 with another salt
Encrypt the data using AES 256 and the key from Argon2 (and an IV)

I was wondering whether at the password hashing and KDF stage there was any weaknesses of using double Scrypt then Argon2?? If so, what would be the solution to improve the security of the hashing?? Thanks


texts: how to verify the digital signature in a zero knowledge proof

texts:
I know that the zero knowledge proof is able to prove to the verifier that the holder does in fact posess the digital signature issued from an issuing 3rd party but...
How does the verifier validate that the signature (which is hidden to the verifier) that the holder possesses is valid?


texts: Is the hash function defined in this exercise collision-resistant?

texts:
I have this problem:

  "Let ${\rm Enc}_k(m)$ a safe block encryption system. We define a hash function $H(m)$ as follows:

  $m$ will be concatenated with $0$ until $|m|$ is a multiple of len(block);
  we break the sequence $m$ into $n$ blocks like $m = m_0 \mathop\| m_1 \mathop\| m_2 \mathop\| \dots \mathop\| m_{n-1}$;
  we apply this algorithm:

c ← Encm0(m0)
for i = 1 to n-1 do
  d ← Encm0(mi)
  c ← c NOR d
end for
H(m) ← c

Where c NOR d denotes the bitwise operation NOT (c OR d), i.e. (for single bits) 1 NOR 0 = NOT (1 OR 0) = NOT 1 = 0.

Is this $H$ resistant to collisions?


texts:
During the TLS handshake, there are random bytes sent from the server to the client and random bytes sent from the client to the server.

Since these bytes are sent in clear text, what is the relevance of them being random? I thought randomness was mostly about lowering the likelihood that these numbers could be guessed. If they are passed around in clear text; whats the importance of the randomness?

Also, what exactly are these random bytes used for?


texts: human readable unpredictable & no collision uid based on time

texts:
I need to create an unpredictable uid based on time.
I plan to allow it to work during a time frame of 100,000,000 seconds.
So the seconds will go from 00000000 to 99999999.

I need an algorithm that will "convert" the seconds to another 8 digit number. 8 digits in, 8 digits out.
Example :

algorithm(00000001) returns 87981278
algorithm(00000002) returns 57941047

The returned number must be unpredictable and there musn't be collisions

If we run the algorithm with the 100,000,000 possible number, we will get 100,000,000 different results (sort of randomization of the 100,000,000 possibilities)

The security does not need to be bulletproof. I just want to avoid id's being in sequence ...

It has to be human readable ... people will need to manually type this id, so big hashes aren't an option.

Any direction you can point me to ?

Thx !


texts: Is semantic security important in a hybrid cryptosystem?

texts:
RSA doesn't provide semantic security when used unmodified, and neither does the commonly used PKCS#1 v.1.5 padding scheme for encryption.

Is this a problem for hybrid cryptosystems at all?

My suspicion is that it isn't, since the plaintext message of the RSA encryption should be a random string used as an encryption key for the symmetric cipher used to encrypt the actual message, which would make the advantage an attacker could gain by the lack of semantic security pretty neglegible.

I guess that it's still a bad idea to rely on the randomness of the ciphertext in that way, but then again, as far as I understand, more secure padding schemes like OAEP also need a random input to guarantee semantic security, so by encrypting messages without a good entropy source seems to be equally bad in both cases.

To sum up my question:

Is semantic security necessary if the plaintext is guaranteed to be random for all messages encrypted by an asymmetric encryption scheme?
When the plaintext turn out to be not as random as expected (e.g. due to a broken RNG), is that worse than the RNG input for a semantically secure padding scheme being predictable?

Additionally, if it is, can anybody explain why PKCS#1 v.1.5 is still commonly used? As far as I know, GnuPG uses it exclusively for RSA encryption, and TLS does so as well for its RSA key exchange in many of its cipher suites.


texts: Best/average/worst-case complexity for cryptography

texts:
I understand that the complexity of a problem can be measured by it's best-case, average-case, or worst-case complexity. Am I correct in thinking that, for cryptographic purposes, each of these is of interest?:

Best-case: If we can find a problem whose best-case complexity is high, then it will be high for all instances of that problem, so this problem would be great to base a cryptosystem on.

Worst-case: If a problem has high complexity in the worst case, we could look for a large set of instances for which the problem has worst-case complexity, and randomly select keys from this set.

Average-case: Wikipedia says that average-case complexity analysis can be used to generate hard instances of a problem.

There does seem to be some conflicting opinions between the best measure of complexity. For example, I have read that NP-complete problems (using worst-case) are desirable for the reason above, but I have also read that they are undesirable because we want the problem to be hard over random inputs.


texts: Public and Private key encryption in simple math

texts:
Can anybody show me (or point me to resource) how to generate public key and private key with simple math? Steps which can be reproduced in a simple calculator – so the message, keys  all can be numbers for test. The values can be simple; it’s fine if it’s hackable. And how will you go about encrypting and decrypting the message with keys?

Let me know if you don't understand my question.


texts: Tackling encryption problems with "Zipf's law"?

texts:
I am new to cryptography and was wondering if it would be possible to semi-reliably "decrypt" an encrypted message by using the statistical distribution of symbols (/letters/numbers) in the encrypted message in accordance with Zipf distribution.

https://en.wikipedia.org/wiki/Zipf%27s_law?

If "symbols" were "recycled" (for example, if x = 102023 , then a = 102023 later)  then this would not be possible, right? If "symbols" are not "recycled", is the code very weak?


texts: How can we encrypt a file to be just readable (and not writable) after decryption?

texts:
Is it possible to encrypt a file (e.g., a text document) such that when a user decrypts it, he/she be able to just read the file and not be able to change the content of the file?

I mean, the result of decryption be a read-only file. I think any modification can be detected using message authentication code. I am looking for a method to prevent the user from modifying the decrypted file.


texts: Which is the best AES mode of operation?

texts: Is there any reason to choose, say ECB over CBC? Or GCM over AEX? Or CTR over CFB? Is there a best AES mode of operation? And, when required, which is the best padding to use?


texts: Will a SHAKE128 stream cipher be vulnerable to related key attacks?

texts:
Suppose that SHAKE is seeded with key concatenated to an IV, will the 'key' stream produced by SHAKE128 vulnerable to related key attacks like RC4 is?

My guess is no because seed is already "absorbed" before the key stream is "squeezed" out.


texts:
I have software that generates user login keys randomly, we store the argon2 hash on our server. The generated keys are very strong, 64 pRNG hex characters. Right now we just use an empty string as the salting parameter in argon2 since we figure salt is not even needed since our passwords themselves are not prone to a dictionary attack.
I don't know much about the internals of how argon2 works though... is there some internal reason to generate a random salt in which argon2 becomes insecure without it... or is it just an optional parameter provided for protecting against common strings being hashed, but can be ignored if none of your strings will be common?


texts: Building a pad for OTP on-the-fly with Diffie-Hellman

texts: Through repeated DH attempts, could Alice and Bob build a large random key for use as a one-time pad? My intuition is that this protocol would be as hard as breaking DH (discrete logarithm).


texts: When did Kerckhoffs's principle become fully accepted in design and practice of modern ciphers?

texts:
Kerckhoffs's principle is named after a publication over 130 years old. Yet it is still something that is commonly misunderstood and challenged by newcomers to cryptography. This question from Open Source Stack Exchange seems typical, and one answer to it implies that at some point, cryptographers in general "got it" and it has become a cornerstone of modern cipher design.

This seemed interesting to me - was the principle for Kerckhoffs's original paper (originally design principle 2 from a list of 6 according to Wikipedia) broadly accepted from the moment of publishing, or has it taken time, specific events and/or the failure of many electronic designs before attaining its current importance?

I searched for "violations of Kerckhoffs's principle" and found a few modern examples (e.g. MiFare being hacked), where essentially the cipher was weak - and easily understood to be weak at the time it was made - but kept secret in the vain hope that reverse-engineering it would be too much of a challenge. However, I didn't find anything I could relate to history such as a series of "secret" ciphers failing badly in the 1990s for instance. So I'm starting to think the principle really has been well-understood ever since it was published, just not followed in practice by some institutions that should have known better had they asked any cryptanalyst. Therefore one way re-framing my question might be "Has there ever been a time in modern (computer-based) cryptographic practice where Kerckhoffs's principle was not considered as important as it is today?"

I tried to use Google ngrams to get a sense of when terms may have become popular, and didn't notice any spiking, but a steady rise in term frequency for e.g. "security through obscurity" from 1970's to present day. Does that point to use of Kerckhoff's principle as a norm (or even just as a label), due to increased academic study of cryptography? This has been suggested in comments. Is there better evidence for that than my ad-hoc searching?


texts: Key, plaintext block and ciphertext block permutations question

texts:
Question: If a cipher’s key size is $k$ bits and its block size is $b$ bits, how many possible keys are there, how many possible plaintext blocks are there, and how many possible ciphertext blocks are there?

Studying for an exam and this popped up in a past paper without an answer, is the solution e.g. for key size $2^k$ bits? and similarly for the others will be $2^b$ bits? My friend thinks its $b^k$ so were unsure and clearly don't understand the logic behind it.


texts:
A friend just showed me how to combine padlocks to achieve a lock that opens when k out of n people turn their keys.

I was wondering if there was something similar for encryption; using n or fewer public keys encrypt a piece of data so it can only be unlocked if at least k out of n specific private keys are applied.

I've tried ideas of stacking normal public key encryption, but without luck. I'm sure somebody must have done research on the topic, but I have no idea what such a thing is called. Maybe it's even widely accessible through standard encryption libraries?


texts: Differential Privacy of the Laplace mechanism with non-deterministic function

texts:
This question is about the proof of the differential privacy of the laplace mechanism.

All more detailled explanations I found of the proof, that the laplace mechanism is $\epsilon$-differentially private, use deterministic functions as the query f that is made on the database (e.g. counting queries).

But is the statement actually only valid for deterministic f?

Seems to me, that adding Laplace noise is a popular easy way to make any kind of query differentially private. Imagine having a random query, but its randomness is weird and you just say: Eh, skip finding out, if the mechanism is private on its own. Just add additional noise (in this case laplace noise) and it will be fine. Judging from the idea behind adding noise to improve privacy this should be possible - I thought.

If the laplace mechanism works for non-deterministic functions as well - where in the proof of the differential privacy is the influence of the function's randomness taken into account?
If the standard proof as shown below (from "The algorithmic foundations of differential privacy" by Dwork/Roth) doesn't work for random f - is there a way to prove it in another way? How?

Thank you in advance for any help.


texts: How is the quality of a password calculated and what does it mean?

texts:
While using Keepass and using it to generate random passwords, I always have noticed the "quality" section but truthfully have never known what it actually means.

So my questions are;

How much entropy is enough?
How much is overkill?
How does entropy actually apply to the length of time it may take for an attacker to guess a password?
How is entropy calculated and how may my addition of a new character affect the number of bits?
What is the theoretical max?

Thanks!


texts:
After reading a bunch of past stack exchange posts like this one and RFCs 5869, 2104, and 4868 I felt comfortable that a 32-byte key was sufficient for HMAC-SHA256.  However, I am implementing my code in C# and someone pointed out to me that the Microsoft HMAC-SHA256 documentation recommends a 64-byte key:

  The key can be any length. However, the recommended size is 64 bytes.

Is there any good reason to use a 64-byte key instead of a 32-byte key?


texts: How were shift amount constants in MD5 found?

texts:
The md5 specification gives a series of 4 rounds to execute over a 16-word block.

Each round has a repeating sequence of 4 shift amounts (s in [abcd k s i]) :

7, 12, 17 and 22 for the round 1
5, 9, 14 and 20 for the round 2
4, 11, 16 and 23 for the round 3
6, 10, 15 and 21 for the round 4

The specification only says:

  The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

How did they find these shift amounts? Is it a sequence like $u_n = (u_{n-1} + j) \; mod \; k$ ? What guarantees the "avalanche effect"?


texts: How was the complexity of the Biclique Attack calculated?

texts:
The abstract of the Biclique Attack paper claims:

  The first key recovery attack on the full AES-128 with computational complexity $2^{126.1}$.

What does $2^{126.1}$ mean in this context? And where does this value come from?


texts:
In the book titled "Secure Multiparty Computation and Secret Sharing" stated that MPC protocol is not secure when the adversary $t>n/2$. This was proved by using a 2 party protocol, but I can't understand why the same applies when $n<2$.

For example, when $n=6$ and $t=3$, the adversary might know the multiplication of the output for the 3 honest players, but as long as their individual inputs are not known, doesn't that consider as secure?
Could someone please help me with this problem?


texts:
Does google's Crypto.JS AES encryption use PBKDF2 as default?

Some references, but I can't figure out the answer myself:

https://code.google.com/p/crypto-js/#The_Cipher_Algorithms

https://code.google.com/p/crypto-js/source/browse/tags/3.1.2/src/aes.js


texts:
Is there any easy way to crack a Beaufort cipher?

We have a Vigenère table, and are trying to guess the keyword.

Any easier way?


texts:
What is the risk of storing an MD5 (or similar) hash of a decrypted file alongside the encrypted version of the same file.

Obviously if someone were to attempt a brute force attack against the file having the hash would provide an end condition for the attack.  Does providing the hash make reversing the encryption easier in some other way?


texts: Possible to split a secret to generate a re-encryption key (PRE)?

texts:
I am wondering, if it is possible to split a secret (s.th. like shamir's secret sharing) which can be used to generate a re-encryption key in proxy re-encryption and only serve the splitted portions for the sake of generating a re-encryption key which can only be used for a specific public key?

So something like:

sec = secret to decrypt message
sec1 = portion of sec
sec2 = portion of sec

pkr = public key of receiver of the message
pkm = public key of bad actor who wants to re-encrypt for him
sec1_pkr = getKey(sec1, pkr)
sec2_pkr = getKey(sec2, pkr)

reKeyPkr = getReKey(sec1_pkr, sec2_pkr, [secn_pkr...], pkr) = re-encryption key for receiver pkr
reKeyPkm != getReKey(sec1_pkr, sec2_pkr, [secn_pkr...], pkm) = re-encryption key for receiver pkm
...


texts: Can I build a secure tweakable block cipher from a normal one by adding key and tweak?

texts:
Let (E,D) be a secure block cipher.

Consider the following tweakable block cipher:

E'(k,t,x) = E( (k+t) mod |K|, x)
D'(k,t,c) = D( (k+t) mod |K|, c)

Is (E',D') secure?


texts:
I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical (pag. 10 and 11) and here say

  The most direct way to construct a TCR hash function is to key a function like MD5 or SHA-1.
  ...

  A safer approach might be to incorporate key bits throughout the
  message being hashed. For example, with $|K| = 128$ one might
  intertwine $128$ bits of key and the next 384 bits of message into
  every 512-bit block. (For example, every fourth byte might consist of
  key.) Now the cryptanalyst's job amounts to finding a collision
  $M,M'$ in MD5 where we have pre-specified a large number of (random)
  values to be sprinkled in particular places throughout $M$ and $M'$ .
  This would seem to be very hard.

... But if I add keys bits throughout the message being hashed; for me, nothing prevents fall in the MD5 again (MD5 is broken), then my question is Why that approach is safer?


texts: I know that the ChaCha20 core (without the initial constant) is not an ideal PRP and must not be used as such.  I also know that $\text{ChaChaCore}(0) = 0$.  Are there any other differences?


texts: We shall say that an obfuscator $\mathcal{O}$ is a reversible black box obfuscator if for each reversible program $P$ the obfuscated program $\mathcal{O}(P)$ is still reversible but does not reveal any more information than an oracle that computes $x\mapsto P(x)$ along with an oracle that computes $x\mapsto P^{-1}(x)$. It is well-known that black box obfuscators do not exist. Do reversible black box obfuscators exist?


texts: To understand a fact related to padding in MD5

texts:
I'm trying to understand the padding process of MD5
from this link.
In that paper in Section 3.1, I found the following description of padding:

The message is "padded" (extended) so that its length (in bits) is
congruent to $448$, modulo $512$. That is, the message is extended so
that it is just $64$ bits shy of being a multiple of $512$ bits long.
Padding is always performed, even if the length of the message is
already congruent to $448$, modulo $512$.

I have tried to understand the sentence "That is, the message is extended so that it is just $64$ bits shy of being a multiple of $512$ bits long." with my utmost effort. But I've failed.
Could anyone clarify that sentence?


texts: Questions about the Curve25519-donna implementation

texts:
I'm trying to understand the implementation of the following function:
Please note questions in comments.

int curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
limb bp[5], x[5], z[5], zmone[5]; // why 5 elements in each?
uint8_t e[32];
int i;
for (i = 0;i < 32;++i) e[i] = secret[i];
e[0] &= 248;
e[31] &= 127;
e[31] |= 64;
fexpand(bp, basepoint);
cmult(x, z, e, bp);
crecip(zmone, z);
fmul(z, x, zmone);
fcontract(mypublic, z);
return 0;

}

Why do all the functions work on a polynomial form of a number? and thus require fexpand function? as I understand fcontract does the opposite.
e[0] &= 248;  e[31] &= 127; e[31] |= 64;  - I've found this suggested in the whitepaper, is there any particular reason behind doing this?
Why is cmult performed twice? what does crecip function achieve?

From what I read on curves in the Weierstrass form, in order to get a public key H, one needs to compute H = dG    (where G is the base point of the subgroup).
Then the situation is entirely different in case of Ed25519 (I know Montgomery Curve25519  is birationally equivalent to a twisted Edwards curve  Ed25519), where generation of the public key involves hashing and results in a non-linear key-space.

In contrast with Ed25519, Can private/public keys in Curve25519 be said to form a linear space? I was wondering whether it would be possible to generate public keys independently to the corresponding private keys using a common index in case of Curve25519.

Update: besides the excellent answer provided by Lery; those of you not familiar with projective coordinates might find this useful.


texts:
let's say I have a protocol to send a file $F$. I am intending to employ AES in CBC mode for encrypting $F$ where the $IV$ is
randomly chosen. For authenticity, I am employing $HMAC$ to compute
a Message Authentication Code ($MAC$). Both the encrypted version of $F$ and the $MAC$ are sent to the receiver.

Is there any flaw in this design?


texts:
In the Diffie-Hellman protocol, each participant selects a secret number $x$ and sends the other participant $α^x\bmod q$ for some public number $α$.

What would happen if the participants sent each other $x\,α\bmod q$ for some public number $α$ instead?

Give at least one method Alice and Bob could use to agree on a key. Can Eve break your system without finding the secret numbers? Can Eve find the secret numbers?

I figure out that it is vulnerable to use $x$ instead of $α$ because Eve can find $x$ by using Fermat theorem. But I can't find system in which both will agree. Please indicate the system that they might use here.


texts: Difference Between an Authentication Token and an OTP (One Time Password)

texts:
I would like to better understand why some people use the term One Time Password and other Authentication Token.
I have noticed that in academic circles, there is a differentiation between authenticated tokens (say a nonce and the signature of the nonce) vs. OTP's, which I always saw as a family of such tokens, one that is either hardware or software aided, using some shared secret or seed and not a certificate itself.
In industry, I hear more and more people calling authenticated tokens OTP's.. I actually start doubting myself, and could not find much material online that compares or even defines both. So I wonder the following:
What is the difference if any, in between these 2 concepts?
Can I use the terms interchangeably?
Are there standards that define what an OTP is and how it should look like?


texts: CBC-MAC: is it secure to authenticate a fixed length ciphertext?

texts:
Suppose I have a fixed-length arbitrary ciphertext.

To authenticate such ciphertext:

I generate a random AES Key $K_{auth}$.
Then I compute the CBC-MAC Tag of the ciphertext with $K_{auth}$.
Finally, I store the ciphertext and the associated Tag in my database.

For decryption process:

I get the ciphertext and the associated tag from my database.
Then I check the ciphertext length and if it match as expected, compute the tag with $K_{auth}$.
Finally, if tags matches, I process the cipertext.

In my case the database should be considered untrusted, as an adversary may edit both ciphertext and tag. However, as keys remain private, is such Encrypt-then-Mac approach secure (even if the tag is not itself encrypted) ?


texts: Are there standards for transport layer security using only symmetric keys?

texts:
I have an embedded system with AES-128 implemented in hardware. There is very little flash/RAM and the (8-bit) CPU runs relatively slowly. Public key crypto isn't a viable option. This system is connected to the Internet and can have one or more unique AES keys programmed at manufacture.

Are there any standard protocols for securing a TCP socket using pre-shared symmetric keys?

Is it enough to just use a pre-shared key for AES-CBC over TCP?
Is there a benefit to exchanging a unique session key (eg. AKEP2/Needham-Schroeder)

Thanks.


texts: Why is it better to add and double points on an elliptic curve using projective space?

texts:
I have been given a textbook which defines the addition of two points on an elliptic curve and the doubling of a point on an elliptic curve. This textbook explains elliptic curves in projective space where $z=1$ and it expresses the points on the curve as affine points of the form $[x,y,1]$ but it never really explains why we want to do this.

I have looked over many solutions of which only explain the addition of two points $P$ and $Q$ as the following:

We find the line between the points, find the point of intersection on the curve and finally reflect it over the x axis.

The textbook I have been given says that for adding two points P and Q we use the group operation $P\bigoplus Q=O*(P*Q)$ where $O$ is a "point at infinity" $[0,1,0].$ We first find the slope of the line between the points and then we plug it in to the following equations:

$x^3=m^2-x_1-x_2$

$y^3=-m(x_3-x_1)-y_1$

and the point should be denoted as $[x,y,1]$.

This textbook has confused me beyond belief.

To my understanding, a projective plane essentially is a plane that is parallel to another plane that lies flat on the x,y axis. This plane is perpendicular to the z axis (points satisfy $z=1$), it contains affine points of the original plane and the point at infinity $O$. If one were to construct a 3 dimensional line crossing the origin it would eventually pass through the coordinates $[x_z,y_z,z]$, so the point $(1,2)$ would be found on the projective curve as $[1,2,1]$.

Is there any specific reason why we want to express points of the elliptic curve in projective space? Does it make adding two points or doubling a point easier?How might I explain to someone why I chose to represent it using projective space if they were to ask me why not just use the algorithm shown in the picture?


texts: Password-based encryption with small typos allowed

texts:
I'm trying to write some software to encrypt and decrypt some messages with a password.  I am trying to implement it using this post:  How can I securely convert a "string" password to a key used in AES?

Now, I also want to devise a scheme to allow the user to make small typos when typing in the password, but still be able to decrypt the message even with that small typo.

Is there a way to do this without sacrificing the security of the encryption scheme?


texts: Blind quantum computing and fully homomorphic encryption

texts:
I am somewhat familiar with current research on fully homomorphic enryption schemes and their possible application to Cloud computing.

I've just noticed (somewhat late) that a marketing-savvy group of Physicists working on quantum information is approaching the same possible application: they call their approach blind quantum computing.

Is this a serious contender with respect to the claimed application (the group's reputation in Physics is not in doubt) and are there any significant similarities between the two approaches on a fundamental level?


texts: What is the purpose of an Authentication Tag in AEAD encryption schemes?

texts: AEAD encryption schemes produce something referred to as an "authentication tag." What does this tag consist of, what is its purpose, and is the tag itself human-readable data such as a plaintext string or is it cipher text?


texts: Tonelli-Shank vales are incorrect when trying to get back to c value for Rabin


texts:
Im trying to understand the proof in "The Discrete Logarithm Modulo a Composite Hides O(n) Bits" by Håstad et al, where he shows that the order of a random element in RSA group is big.
I got the most part but there is one transition that I just cannot see (in Proof of Lemma 1.2):

Any suggestions on how I could approach it?
Edit: F is defined as:


texts:
I am trying to wrap my head around encryption in .NET. I am trying to implement a simple solution in ASP.NET Core to encrypt a cookie containing some non-meaningful numbers to outsiders. I need to be able to read the cookie content again.

This example (http://www.saipanyam.net/2010/03/encrypt-query-strings.html) uses Rfc2898DeriveBytes and RijndaelManaged but I don't understand if Rfc2898DeriveBytes is producing a random key tied to e.g. machine key or something else.

I need to be able to move software to a new server without managing machine keys, Redis or similar (just looking for something very simple to encrypt data).

// is this random? And if so, will I be able to read cookie contents in potentially 2 years of time?
keyGenerator = new Rfc2898DeriveBytes(ENCRYPTION_KEY, SALT);
key = keyGenerator.GetBytes(32);

// entire code from link above (clean up)

public static class MyHelper
{
    private const string ENCRYPTION_KEY = "some-secret-key";

    /// The salt value used to strengthen the encryption.
    private readonly static byte[] SALT = Encoding.ASCII.GetBytes(ENCRYPTION_KEY);
    private readonly static byte[] key;
    private readonly static byte[] iv;
    private static readonly Rfc2898DeriveBytes keyGenerator;

    static MyHelper()
    {
        keyGenerator = new Rfc2898DeriveBytes(ENCRYPTION_KEY, SALT);
        key = keyGenerator.GetBytes(32);
        iv = keyGenerator.GetBytes(16);
    }

    /// Encrypts any string using the Rijndael algorithm.
    /// A Base64 encrypted string.
    public static string Encrypt(string inputText)
    {
        //Create a new RijndaelManaged cipher for the symmetric algorithm from the key and iv
        RijndaelManaged rijndaelCipher = new RijndaelManaged { Key = key, IV = iv };

        byte[] plainText = Encoding.Unicode.GetBytes(inputText);

        using (ICryptoTransform encryptor = rijndaelCipher.CreateEncryptor())
        {
            using (MemoryStream memoryStream = new MemoryStream())
            {
                using (CryptoStream cryptoStream = new CryptoStream(memoryStream, encryptor, CryptoStreamMode.Write))
                {
                    cryptoStream.Write(plainText, 0, plainText.Length);
                    cryptoStream.FlushFinalBlock();
                    return Convert.ToBase64String(memoryStream.ToArray());
                }
            }
        }
    }

    /// Decrypts a previously encrypted string.
    /// The encrypted string to decrypt.
    public static string Decrypt(string inputText)
    {
        RijndaelManaged rijndaelCipher = new RijndaelManaged();
        byte[] encryptedData = Convert.FromBase64String(inputText);

        using (ICryptoTransform decryptor = rijndaelCipher.CreateDecryptor(key, iv))
        {
            using (MemoryStream memoryStream = new MemoryStream(encryptedData))
            {
                using (CryptoStream cryptoStream = new CryptoStream(memoryStream, decryptor, CryptoStreamMode.Read))
                {
                    byte[] plainText = new byte[encryptedData.Length];
                    int decryptedCount = cryptoStream.Read(plainText, 0, plainText.Length);
                    return Encoding.Unicode.GetString(plainText, 0, decryptedCount);
                }
            }
        }
    }
}


texts:
I think we're all aware of the Logjam attack.

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

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

Now in my mind this question arose:

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

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


texts:
So I'm trying to figure out the feasibility of using a Smart Card to decrypt files in an offline scenario.

I wish to sync encrypted files to a mobile phone with a Smart Card reader case. The files should only be readable when the Smart Card is in the card slot. If the user looses the phone the files will be stored in a encrypted format on disk only.

Assume that I will not be able to write any actual Smart Card apps myself and that the Smart Card is a US CAC or equivalent.

My thinking goes something like this:

Send the Smart Card certificate (containing the Public Key) to backend server
Backend server generates files and encrypts those by using the client Public key and Signs the file with backend private key
Client receives files, verifies backend signature and then decrypts the file with the Smart Card private key

For number 3 I wonder if this is available and would it be performant for text only files?

If it is available, how does it work. Will the Smart Card take a stream of encrypted bytes and then spit out a stream of unencrypted bytes?

Any references to similar examples, code etc appreciated.

Edit: By performant I mean decryption measures with bytes/s. I saw in a talks that the cards have accelerated encryption chips but I don't really know what that implies.

Also, found some sample code from a course homepage at Radboud University. So it is possible to achieve with a custom Java Applet. I'm still wondering if there are any "standard" ways of doing this, either as a part of APDU or GlobalPlatform commands.

Crypto Applet
https://www.cs.ru.nl/E.Poll/hw/samples/CryptoApplet.java

Usage from Java
https://www.cs.ru.nl/E.Poll/hw/samples/CryptoTerminalSmartCardIO.java

Edit 2: So I figured out that the card supports PKCS#11 and that is probably what I should use.

I've downloaded the pkcs11-tool which works well for browsing/viewing things. I can list certificates etc. But when I try to sign something I get that the operation is unsupported (PKCS11 function C_SignFinal failed: rv = CKR_FUNCTION_NOT_SUPPORTED (0x54)).

The documentation I've found on this tool is not very good (no examples just man page) so if anyone knows how to do this properly please tell:

pkcs11-tool --module $OPENSC_LIB --sign --slot 0x2 --input-file message.txt --login --pin XXXXXX --mechanism SHA1-RSA-PKCS

By the looks of it I would also be able to use PKCS#11 to decrypt a message. Didn't get that far yet.


texts: Homomorphic encryption or double symmetric encryption?

texts:
I am new to Homomorphic Encryption.

The scenario is that the encrypted data will be sent from Alice to a trusted cloud machine for computing operations and then sent to Bob. Can HE (e.g. NTRU) be faster than using symmetric encryption and having to decrypt the data from Alice, do operations, and encrypt again to sent to Bob (e.g. AES)?


texts: Implementing AES encryption for firmware distribution system

texts:
I need to implement an AES encryption for firmware distribution system.
I have a bootloader that can decrypt various AES variants (ECB,CBC,CTR).

When I approached this I found few issues that aren't clear to me.

First, there's the IV vector, which is strange to me.
This vector has to be known to the encryptor and also the decryptor, does it makes sense?
On the decryptor side (source code) I need to input the IV vector, however, on the encryptor side (software encryptor) I can't choose IV vector. (NCrypt, AES Crypter lite, Kryptel). I know that ECB doesn't need one, but how can the software encryptor do CBC or CTR without it, is it randomly generated?  If so, how the decryptor will know it?
Another question is regarding the actual size of the encrypted file. It must be divisible by the block size, right?  So if my block size is 128, why the output of AES Crypter lite for instance produces a file size which is not divisible by 128?


texts:
One can have a NIZK proof for DLOG by applying Fiat-Shamir heuristic to Sigma protocol, such that one can prove non-interactively that $x$ is discrete logarithm of $X = g^x$. Then, in simulation based proofs, the simulator can extract the witness $x$.

What interest me is whether a party $P_2$ given $X = g^x$ and DLOG proof $\pi \gets (\{ \exists x' \mid X = g^{x'} \}, x)$ from a party $P_1$, can give another proof for the randomization of $X$. More precisely, $P_2$ samples a random $r$, calculates $X' = X^r$, and then gives a proof like $\pi' \gets (\{ \exists r' \mid X' = X^{r'} \}, r)$ or any other proof, such that the simulator simulating $P_1$ can later extract the randomized witness $x \cdot r$ either from the proof $\pi'$ received from $P_2$ or from the combination of both proofs $\pi$ and $\pi'$?

Please note that when I talk about proofs here I mean always non-interactive version.

NOTE: I know that Sigma protocol cannot be re-rerandomized. But, is there any other type of proof that will let you to prove this re-rerandomization and extract the witness?


texts: Is PGP's way of maintaining email security optimal?

texts:
I read a book called "computer networking: A top-down approach". It talked about how PGP creates an email message between Alice and Bob to maintain confidentiality, integrity, and authenticity. Let me define some terminology and the procedure at the very high level:

m :              email message
H() :            cryptographic hash function
Ka_priv_sign() : signing using Alice's private key
|| :             contacternation
Ks :             session key
Ks_enc():        encryption using session key
Kb_pub_enc():    encryption using bob's public key
blob :           The final data blob Alice sends to Bob.

To send an email to Bob, Alice first signs the message with her private key:

m || Ka_priv_sign(H(m))

Alice then encrypt the message and signature

blob = Kb_pub_enc(Ks) || Ks_enc(m || Ka_priv_sign(H(m)))

Alice will send this final blob to Bob.

The cryptography seems to have a problem here since digital signature is applied before encryption and encryption does not provide data integrity.
I think the right order of operation should be:

Alice first encrypts the message with the session key and encrypt the session key with Bob's public key:

Kb_pub_enc(Ks) || Ks_enc(m)

Alice then signs the encryption results after hashing them:

blob' = Kb_pub_enc(Ks) || Ks_enc(m) || Ka_priv_sign(H(Kb_pub_enc(Ks) || Ks_enc(m))))

Questions:

Is PGP still using the way that the textbook describes today? Do you think my construction is better?


texts: Existence of PRF $\implies$ existence of PRG

texts:
Let $F:\{0,1\}^n\times \{0,1\}^m \to \{0,1\}^l$ be a PRF.
  I want to show that $G(-)=F(-,x_0)$ is a PRG for every $x_0\in \{0,1\}^m$.

Proof attempt:

Let $D$ be an efficient distinguisher against $G$ in the PRG experiment (see below). We aim to show that $D$ has negligible advantage.

Consider the following efficient distinguisher $D'$ in the PRF experiment. Given access to a function $\mathcal O$ which is either a random function $\{0,1\}^m\to \{0,1\}^l$ or $F_k$, then $D'$ outputs precisely the accept/reject choice of $D$ on the string $\mathcal O(x_0)$.

By construction $D'$ wins if and only if $D$ accepts. By assumptions, since $F$ is a PRF, the former event has probability bounded above by $\frac{1}{2} + \text{negl}(n)$ for some negligible $\text{negl}$, and hence the same is true for the latter event.

My questions:

Is the proof correct?
Is the level of rigor sufficient?

Additional information:
Here are the two experiments I was referring to (taken from Katz/Lindell).


texts: Is sharing the modulus for multiple RSA key pairs secure?

texts:
In the public-key system RSA scheme, each user holds beyond a public modulus $m$ a public exponent, $e$, and a private exponent, $d$.

Suppose that Bob's private exponent is learned by other users. Rather than generating a new modulus, Bob decides to generate just a new public and a new private exponent $e'$ and $d'$.

Is this safe for Bob?


texts: Can a stream cipher with a big S-box create ASIC-resistance?

texts:
For a proof of work system a hash algorithm generates one pseudorandom index each round, in the same manner as RC4 and Spritz do. And it uses a bigger S-box, e.g. 2^20 numbers. The actual hash would be the first 32 output bytes of the stream cipher after dropping a certain number of rounds.

Would this be sufficient to get ASIC-resistance in a cryptocurrency?


texts: Determining order of the group for an elliptic curve defined over a finite field

texts:
I need to find out the order of the group for an elliptic curve. See the image for the question.

The inequality condition after simplification leads to $-2 \sqrt{p} \leq m \leq2 \sqrt{p}.$ Also, the order of the group will be a factor of $m$ (Lagrange theorem).

I found a research article on https://link.springer.com/content/pdf/10.1134/S2070046611020075.pdf

I could still not figure out the exact answer.


texts: Generate an insecure public / private key pair

texts:
I am looking for a way to generate an "insecure" public key pair. and by insecure I actually mean a pair that is breakable using brute-force (or other encryption) methods.

As far as I know PGP started with 128bit-keys. and at this point I can only find tools to generate keys using 1024bit or more.

Is there a way to generate a key pair with lets say 56bit (or even less) that will still generate a valid Certificate than can be used in PGP messages?


texts:
Suppose I have an arbitrary 256 bit number $m$ another secret number $k$ of the same bit length, and then I multiply them both modulo a 256 bit prime number $p$ to get $c$ as follows:
$$
c = (m\cdot k) \mod p
$$
Is there any way to get $m$ back without knowing $k$?

Can anyone please clarify a bit more on that, and also please explain to me why my example can be broken by an attacker?


texts: Given a list of ciphertexts, how to identify the ones that used the same key for encryption

texts:
I'll start off by saying I am not looking for solutions here, just suggestions on how to proceed. I am given a short list of ciphertexts (20something) and I know that one of the ciphertexts has been encrypted with the same key.

I know that once I identify the ciphertext, I will do a crib drag attack, but my issue is with finding the ciphertext in the first place. Are there any suggestions as to how to approach this issue? All similar questions I could find online dealt with a list of ciphertexts that were all encrypted with the same key, which is much simpler to tackle.

The only thing I know about the plaintexts is that they are all in English. I could do all the possible XOR combinations and crib drag every single one of them but that seems terribly inefficient and not the correct way to go about it. Any suggestions are appreciated.

Update:
Unless I've misunderstood what Meir Maor meant (I couldn't find anything on "char level histogram"). I don't see how a frequency chart would help in this case, considering that only the key is the same between the 2 messages in a list of over 20.


texts:
I read, here, that ECDSA signature is EUF-CMA but not SUF-CMA, aka sEUF-CMA (for strong existential unforgeability under adaptively chosen message attacks; see terminology there).

Specifically, the assertion is that given an ECDSA signature for a message, it is possible to transform it into a different signature that pass verification for that same message.

Is there such issue, and where exactly does it lie?

mathematical definition
standardized definition of signature in some edition of ANS X9.62 (paywalled), SEC-1, or FIPS 186
some implementations


texts: Model a dishonest majority controlled by several adversaries in a voting protocol?

texts:
In the context of secure multi-party computation protocols, when a dishonest majority is considered, it is assumed the worst case scenario, i.e., all the corrupted parties are controlled by the same adversary.

Having all the corrupted parties controlled by the same adversary is the worst case scenario since it means that the corrupted parties can be forced to cooperate so as to achieve a result that is desiderable for the adversary.
This makes sense since proving security in this context implies the protocol to be secure for any number of adversaries.

However, in the context of a majority voting protocol it is crucial if the parties can cooperate or not.
Indeed, a cooperating majority of corrupted parties may influence arbitrarily the output of the protocol.
On the other hand, a non-cooperating or partially cooperating majority of corrupted parties can hardly influence the output of the protocol (since it is unlikely they all vote in the same way).

Are these cases already treated somewhere in literature?


texts: Any way to prove possession of a RSA 2048 private key using 256 bit?

texts:
Alice has a RSA 2048 private key and Bob has corresponding public key.
They have a secure connection, but Alice can transmit only 256bit to Bob (Bob can transmit any amount of data to Alice).
Is there a way how Alice can proof to Bob that she is in possession of the private key?


texts:
I would like to encrypt some data using a combination of multiple keys. There would be two keys: a client keys that would be generated for each client and a single server/application key used by everyone. The idea is to be able to encrypt/decrypt the data only if we are in possession of both keys. So neither the server nor the client could decrypt the data alone.

I know that I could simply encrypt the data using the client key and then encrypt the data using the server keys, but I was wondering if it was possible to just combine the keys in order to create the common decryption key as I am not fond of multiple encryption... I have looked into Secret Sharing, but from what I experimented with the crypto++ library, I can only generate n keys from a message (the message would be the merged key in my case). I would rather want to generate a client key, then merge this client key with a fixed server key to generate the final key used for encryption.

Is XORing the keys together a good solution ? (I believe if both of them have the same character at the same location, it would reduce the encryption strength of the final key...)

Also, can I only use a single IV for both keys in this context ? The IV would of course be randomly generated for every client.


texts: What is the role played by cache misses in memory-hard password hashing?

texts:
I experiment with argon2 and build a web application. In browser, I use one threaded hashing with not too much memory. I want to protect my short length input data from parallel brute-force attack.

I understand, using large memory (1GB or greater) prevent parallelism, because of the cost. I would like to support mobile and older browsers, so I use 16MB or 32MB memory maximum.

I thought argon2 indexing function generate large amount of cache miss, while randomly access the shared memory and a cores waiting a lot. Consequently parallelism increase the cache miss count and slowing down the hashing. I was benchmarked in parallel, but it is not affected, parallelism worked.

Is it because my benchmarks wrong or is not generate a lot cache misses I thought or cache misses not affects like the processing?

Cache misses wrong for memory-hardness, because the waiting cores might compute a missing memory faster then the waiting time, aka time-memory tradeoff?

edit1
What is the relationship between used memory and memory bandwidth and speed?


texts: Diffie-Hellman in Https: How are prime numbers picked?

texts:
I am trying to understand https, as I understand https uses the Diffie–Hellman method for keys exchange and then AES for encryption.

But Diffie–Hellman needs two prime numbers, where do these come from?


texts: What is the "successive-configuration relation"?

texts: This term is used in the book Foundations of Cryptography on pg 20 with regard to defining deterministic oracles, but is not previously defined and I can't seem to find a definition online easily.


texts: Are really, really long passwords any more secure than short ones?

texts:
Just for fun, I want to encrypt a message that will take about 10 or so years to decrypt. My idea is to encrypt a message with AES-512 with a password one million decimal digits long.

Knowing not much about cryptography, is this any more difficult to decrypt than a shorter password? (I'm trying to prevent brute-forcing, until computing power becomes so high that it is irrelevant).


texts: How are trapdoor functions developed/found and where can I find existing ones?

texts:
Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is

Prime Factorization, used in cryptosystems such as RSA

How are these trapdoor functions found?


texts: Distribution of the Difference of Uniformly Random Elements

texts:
In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (finite) field is again uniformly random (Lemma 5.9). This is again used in the reductions of 'Worst-case to Average-case Reductions for Module Lattices', for Module Learning with Errors.

Firstly, why is this true?
Secondly, what happens when you relax the algebraic conditions on the sample space? For example, in an integral domain, one might not have inverses at all; is there a different sufficient and necessary condition for the difference of distinct, uniformly random elements in an integral domain to be again uniformly random? What about simple modules? Euclidean domains?


texts:
What are the minimal components to build a security model proof for a protocol?

This question might seem trivial, but having read many papers-- from the IEEE, ACM, etc., that talk about a KMP-- I still don't know where to start. For example, should I use the adversary model or a random oracle?


texts:
Rivest and Shuldt proposed a new sponge like cipher algorithm called Spritz:

http://people.csail.mit.edu/rivest/pubs/RS14.pdf

In this paper they say that the strength of the cipher is related to the bit-capacity of its sponge-like internal function. They calculate this as 936 bits from 5 8-bit registers and 112 bytes of an internal state space. That gives (112+5)*8 = 936 bits.

However the 112 bytes of the internal state space are all different, thus they represent one of (256!)/((256-112)!) permutations. This number of permutations can be represented in 855 bits which with the 5 registers makes for 895 bits which is 81 bits less than claimed.

My question is, is the effective strength of the sponge function 936 bits as stated by Rivest and Shuldt, or, given it can be entirely represented in only 895 bits, "just" 895?


texts: Is it possible to determine or estimate the period for Blum-Micali PRG?

texts:
The Blum-Micali is a cryptographically secure pseudorandom number generator.

The construction (from wikipedia):

Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ \bmod{\ p}$.
The $i$-th output of the algorithm is 1 if
$x_i < \frac{p-1}{2}$. Otherwise the output is 0.

I have toyed with small values of $p$ and have noticed that cycles occur if there's a fixed point, that is $x_{i+1} = x_i = g^{x_i}$.

For example when $g=3$ and $p=7$ (from wikipedia primitive root example), there are two fixed points where $3^4 = 4 \bmod 7$ and $3^5 = 5 \bmod 7$. This would be problematic for Blum-Micali generator since it would cycle and repeatedly output the same bit.

Is there a relationship with the size of $p$ and the period which is based on the likelihood of a fixed point?


texts: Secure blinding factor switching at malicious server-side (Switching in One Time pad)

texts:
Suppose all the values and operations are defined over a finite field $\mathbb{F}_p$ where $p$ is a large prime number. Assume all values are non-zero. Here $(z)^{-1}$ denotes multiplicative inverse of value $z$.
We give away the values $v_1$ and $v_2$ to an adversary and ask him to compute their product:

$v_1=a\cdot z_1$
$v_2=b \cdot z_2 \cdot (z_1)^{-1}$

So, the adversary computes $v_3= v_1\cdot v_2=a\cdot b \cdot z_2$.
The values $z_i$ are picked uniformly at random from the field. But $a$ and $b$ are fixed values of the field.
Questions:

Given the three values $v_3, v_1$ and $v_2$ can the adversary learn anything about the fixed values $a$ and $b$ (and the $z_i$ values)? If yes/no Why?
In other worlds, given the above three values, can the adversary infer anything about $a$ and $b$?

Let $v_1=a\cdot z_1$ and $v_2=(z_1)^{-1}\cdot z_2$.
If we give $v_1$ and $v_2$ to the adversary and ask him to compute their product:  $v_3=v_1\cdot v_2=a\cdot z_2$ would it learn the secret value $a$ (and $z_i$ values)?


texts: Is there a method to combine encryption and ring signing?

texts: There's the well-known question on whether to sign or encrypt first. However, if instead a message is to be ring-signed such that either recipient could be the actual signer, is there any scheme that combines signing and encrypting in one "atomic" step?


texts: Variants of universal composability in security proofs

texts: Universal composability (UC) framework seems to be a powerful framework for proving security of protocols, which guarantees security even in the presence of concurrent composition. Though, I see there are multiple variants of the original UC framework, such as simplified UC (SUC), joint state UC (JUC), global setup UC (GUC). I was wondering how all these different variants fit together. For example, assume there is an ideal functionality $\mathcal{F}$, which is defined in $(\mathcal{F}_1,\mathcal{F}_2, \mathcal{F}_3)$-hybrid model, where $\mathcal{F}_1$ is in the original UC framework, $\mathcal{F}_2$ is an ideal functionality such as a global setup or blockchain that should be available to all the other protocols, so we assume that it is in GUC, and $\mathcal{F}_3$ is something like a key generation functionality that is defined in such a way that should have multi instances, so let's assume it is in JUC. So, now when proving the security of $\mathcal{F}$, how should one prove it? Can one just prove it in normal UC? Or do one needs to do the proof in GUC or JUC, since $\mathcal{F}_2$ and $\mathcal{F}_3$ are assumed to be defined in those frameworks, respectively?


texts:
Studying for CISSP these choices seemed limited:

  What is the advantage of digital signatures over message authentication codes?

  Digital Signature provides integrity verification while message authentication code does not
  Digital Signature provides confidentiality while message authentication code does not
  Digital Signatures provide authenticity while message authentication code does not
  Digital Signatures works faster than message authentication codes

Using the following chart as a reference, I'm leaning towards #2, but none of the choices really fit properly…

Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Hopefully an expert here can clarify.


texts: Is it possible to perform an MPC protocol to compute a product in a polynomial ring?

texts:
I hope not to be asking much, but I have N parties, each one holding a polynomial in with 0-1 coefficients and fixed degree $n-1$. I was wandering if it is possible (I mean feasible) to compute the product of all of these polynomials with an MPC protocol.

Actually, for security I would need the result modulo $X^n+1$, so my actual request is the following : Given $N$ polynomials $P_1,P_2,\dots,P_N$ with $0-1$ coefficients and degree $n-1$, compute $(\prod P_i)\mod(X^n+1)$ with a multiparty computation protocol where each party holds a $P_i$.

My question regards the complexity of such a product ($O(n \log n\log N)$ integer multiplications if an FFT algorithm is used ?)

It is my first question here, so please attach a welcome message to you answer :-)


texts: How many p and q pairs are there in a 1024 bit modulus?

texts:
I was reading:
Is sharing the modulus for multiple RSA key pairs secure?.

My question is: Given a 1024 bit modulus, how many pairs of 512 bit p's  and q's are there that would be able to be combined to create a 1024 bit modulus for use in RSA?

Since a 1024 bit modulus has not been factored, I am guessing we don't know, but I wonder if there is an equation?

I thought it would only be one set honestly: one p and one q multiplied together to get n. (Mainly because they only show 1 set in the wikipedia article: https://en.wikipedia.org/wiki/RSA_numbers#RSA-768)

Maybe I don't understand but the side question would be: Given a 1024-bit modulus, how many pairs of e and d could one come up with?


texts: Distinguishing advantage in terms of $\Omega(\omega)$

texts:
I was going through this paper ("Fully Homomophic Encryption over the Integers Revisited") and the statement written in the first paragraph on page 5 stating $\DeclareMathOperator{\agcd}{AGCD}$

  We say that an algorithm $\mathcal{A}$ is an $(\epsilon_1,\epsilon_2)$-distinguisher for $\agcd_{X,\phi}(\mathcal{D})$ if, with probability $\ge \epsilon_2$ over the randomness of $p \leftarrow \mathcal{D}$, its distinguishing advantage between $A^{\agcd}_{X,\phi}(p)$ and $U(\mathbb{Z} \cap [0, X))$ is $\ge \epsilon_1$.

and the paragraph just before Theorem 1 on page 5 stating -

  In [4], Applebaum et al gave an LWE self-reduction from secret distribution $U((\mathbb{Z} \cup [0, p))^n)$ to secret distribution $D_{\mathbb{Z}^n, O(\alpha p)}$ which reduces the distinguishing advantage from $\epsilon$ to $\Omega(\epsilon)$, if $\alpha \ge \Omega( \sqrt{\ln(n / \epsilon)} \, / \, p )$.

Based on what I understand, shouldn't the distinguishing advantage increase from $\epsilon$ to $\Omega(\epsilon)$ ? Since $\Omega(\epsilon)$ is a function $f(\epsilon)$ such that $f(\epsilon) \geq cg(\epsilon)$ for some $\epsilon > 1$, shouldn't the distinguishing advantage increase because $f(\epsilon)$ is asymptotically $ \geq \epsilon$.

Any help is appreciated.


texts: In practice, how many algorithms depend on the totient function?

texts:
I am somewhat familiar with the RSA algorithm, and I know that the security comes from the fact that the totient $\phi(m)$ is difficult to compute when $m$ is large and of unknown factorisation. I have more or less assumed that something like this lies at the base for most modern public-key encryption, but how widespread in the real world are public key encryption schemes (including RSA) for which "finding $\phi(m)$ from $m$" is the main bottleneck for a brute-force attack?

I'm not asking how many such schemes there are out there that people have invented (although I actually only know of RSA, so if someone were to, say, drop the names of one or three others, that would be cool), but rather, in a sense, what qualification can I use when I say "_____ of modern public key encryption hinges on the fact that $\phi(m)$ is hard to compute" to laypeople, for instance in a high school math class where we take a day off from the usual curriculum. Can I say "Almost all of modern encryption", or "Most" or do I have to moderate it to "A lot", or even just "Some"?


texts: Does a hash function have a Upper bound on input length?

texts:
I came across this Answer stating (just a line from the answer):-

  The input space is "infinite" and thus it has an infinite amount of values that will collide into a single hash

And in the comments of this answer, there exists a comment of @poncho stating:-

  Technically, the input space for the SHA-1 and SHA-2 hash functions is not "infinite"; SHA-1 and SHA-256 inputs are limited to $2^{64}−1$ bits; SHA-512 is limited to $2^{128}−1$ bits

In reply to the above comment, the answer'er does accept the above fact. But, I can't seem to understand why?

As there exists a large number of answers, like this who loosely use the term infinite with the input space of hash functions. I tried to resolve the ambiguity via Wikipedia page of MD5 and SHA1, this is the definition of both:-

  In cryptography, SHA-1 is a cryptographic hash function which takes an input and produces a 160-bit hash

  The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value

In both the definition, there exists no mention of input size (in bits) of the algorithms.

QUESTION:-
Does hashing algorithms have an upper bound in the input space?

P.S.:- If the upper bound does exists, then can anyone tell me why isn't the hashing algorithm able to work on input size above the upper bound?


texts: How does the "biased-$k$ attack" on (EC)DSA work?

texts:
I recently stumbled across Thomas Pornin's old answer about deterministic (EC)DSA again. There he states the following:

  Note that $k$ must be generated uniformly in the $[1, q-1]$ range
  (where $q$ is the subgroup order). Any information on $k$, even
  partial (such as: values between $1$ and $2^{160}-q$ are twice as
  probable than values between $2^{160}-q$ and $q$), can be exploited by
  the attacker.

When asked for clarification on this, he responded with a link to "The Security of DSA and ECDSA Bypassing the Standard Elliptic Curve Certification Scheme" by Vaudenay (PS) which mentions that Bleichenbacher discovered the attack and mentioned it in private communication with the author.

Now the paper has a short paragraph (section 2.2), which basically states an approximate equation for the bias and says that

  Bleichenbacher actually used it in order to approximate the secret key more
  and more precisely with signatures.

Now my question:
How does this attack work in a more detailed description? or formulated differently: How does one exploit this tiny bias to recover the secret key and how many signatures (ie oracle queries) are required for this along with what approximate computational effort (if it is non-negligible)?

The relevant section from the paper is (for your convenience):

  The initial standard pseudorandom generator in DSA for $k$ was simply
  a 160-bit pseudorandom number reduced modulo $q$. Bleichenbacher
  observed that the probability of $k$ in the $[0, 2^{160} − q]$ range
  have probability which is twice of the others. This leads to a bias

  $$E\left(e^{\frac{2i\pi k}q}\right)\approx \frac{q
 e^{i\pi\frac{N-1}q}}{\pi N} \times \sin\left(\frac{\pi N}q\right)$$

  where $N=2^{160}$. Since $q \approx N$, this may be large depending on
  the $\frac{\pi N}q$ angle. Bleichenbacher actually used it in order to
  approximate the secret key moreand more precisely with signatures.


texts: Secure Key exchange using javacard applet

texts:
I am working on a javacard applet project where i need...

Secure communication between two applets let say there is applet A
and applet B. Let say both applet has their own RSA key pairs.
Now I want to perform Diffie-Hellman key exchange between these applet.So
that both applet can talk securely.

How to perform above mentioned functionality if anyone can also suggest other than this where two applets can communicate by using asymmetric crypto.

Any help on this topic will be highly appreciated.


texts: Reasonable Password Entropy given a certain Set of argon2 Parameters

texts:
I followed the recommendation of choosing threads, memory consumption and the number of iterations (in that order) on my machine. But now I wonder which passwords (by means of entropy) are actually secured by this set of parameters.
Clearly, a single letter is not secure, regardless of the parameters; but on the other hand, using a 256-bit entropy password renders the usage of argon2 pointless. So the security of my hash certainly depends on the relation between password strength and argon2 parameters. Since I am using old and not powerful hardware I am concerned, that the time it takes for me to calculate the hash is negligible for a large scale attacker. (This might be even worse for hashing on mobile phones or embedded devices.)
So the question is: Given a certain set of argon2 parameters, what is the minimal entropy a password should have so that the hash can be assumed to be secure?
Alternatively: Given a certain set of argon2 parameters, how many passwords can the fastest supercomputer available today (in 10/20/50 year) check in a second?
Edit: I am using a strong (>= 128-bit) password for locking my password manager, but entering this several times is tedious. So I thought using a key file that is protected by a simpler password. Since I am syncing stuff to the cloud, the hash of the simpler password can not be considered a secret. In order too choose a simpler password that is still considered secure, I need to be able to estimate the protection gain from using a strong KDF (e.g. argon2).
Edit 2: This question and answer tackle my question in a general context (not Argon2 specific) very well.


texts: How to detect if a protocol is vulnerable to a replay attack trying to impersonate?

texts:
I'm having a hard to finding out how I can detect if protocols are vulnerable to impersonation of Alice/Bob by Eves' replay attack! I have an example here:
$$\begin{array}{lclcl}
\mathsf A & \to & \mathsf B & : & \mathtt{Hello}  \\
\mathsf B & \to & \mathsf A & : & B, K_{ab}\{B\}  \\
\mathsf A & \to & \mathsf B & : & A, K_{ab}\{A\}  \\
\end{array}$$
I would think that this is vulnerable to Eve impersonating Bob by adding these steps:
$$\begin{array}{lclcl}
\mathsf A & \to & \mathsf B            & : & \mathtt{Hello}  \\
\mathsf B & \to & \mathsf E(\mathsf A) & : & B, K_{ab}\{B\}  \\
\end{array}$$
Now that Eve has the plaintext of $B$ and the ciphertext of $B$ ($K_{ab}\{B\}$ ), depending on which cipher used she now has $K_{ab}$ with which she can impersonate as Bob to Alice.
$$\begin{array}{lclcl}
\mathsf E(\mathsf B) & \to & \mathsf A & : & A, K_{ab}\{A\}  \\
\end{array}$$

But when I look at protocols such as:
$$\begin{array}{lclcl}
\mathsf A & \to & \mathsf B & : & A, K_{ab}\{N_a\}                    \\
\mathsf B & \to & \mathsf A & : & B, N_a, K_{ab}\{N_b\}               \\
\mathsf A & \to & \mathsf B & : & A, B, N_a, N_b, K_{ab}\{N_a, N_b\}  \\
\end{array}$$
I'm totally lost. Is there some sort of characteristic vulnerability in protocols to which Eve could take advantage which I'm not seeing? I'm sorry if this is a stupid question but I'm new to this.

Notes of the editor:

$\mathsf A$ (resp. $\mathsf B$) is entity Alice (resp. Bob), $A$ and $B$ are their respective identity.
$\mathsf E(\mathsf A)$ means entity Eve impersonating Alice.
$K_{ab}\{A\}$ means encryption of $A$ with a symmetric cipher under key $K_{ab}$ shared by Alice and Bob but initially unknown to Eve.
$N_a$ means a nonce chosen by Alice.
$X, Y\dots$ denotes a reversible concatenation of two or more messages; perhaps plain concatenation if the length of messages is fixed, or concatenation with , as separator after replacing every \ by \\ then every , by \, in the messages concatenated.


texts: What is the difference between HMAC-SHA256 and SHA256? how do i know which one is better?

texts: What is the difference between HMAC-SHA256 and SHA256 in terms of speed, length, and size of data.


texts: Efficiency of computing $e(P,Q)$ Vs $g^a \pmod{p}$?

texts:
The definition of $e$ can be seen here. I want to know the accurate comparison of efficiency between $e(\cdot,\cdot)$ and $g^a \pmod{p}$. If  computing $e(P,Q)$ is less efficient than computing $g^a \pmod{p}$, should we prefer $g^a \pmod{p}$ to $e(P,Q)$ when designing protocols?

Also, what is the reason for defining the pairings on an elliptic curve? Is it to solve the multiplication of points over the elliptic curve?

p.s. Sorry to have a lot of questions, I'm new to elliptic curve cryptography..


texts:
I'm new to SSL/TLS and I'm staring as a new security researcher. It appears to me that SSL/TLS protocol is needlessly complex for arriving at a shared secret. The complexity results in so many bugs (e.g., downgrade attacks, implementation bugs) What is the reason?

If I come up with a simple key-exchange protocol (without all the fancy features and no backwards compatibility), but is proven to be secure (both protocol and implementation via formal verification), would organizations, browsers start adopting it?


texts: Lower bound for the length of a one-way function's value?

texts:
Let $f\colon \{0,1\}^n \to \{0,1\}^n$ be a length-preserving (i.e., $|f(x)| = |x|$) one-way function. Then, for $k \in \mathbb{N}$ and $m = n^k$, the function $g\colon \{ 0,1\}^m \to \{0,1\}^n$ with
$$g(x_1, \ldots, x_m) = f(x_1)$$
is also one-way. Otherwise, being given $f(x)$ and $1^n$ as well as the description of a PPT $A$ which inverts $g$, one could run $A(f(x), 1^m)$ to obtain a preimage $x'$ for $f(x)$. This procedure can be realized in polynomial time since $m = n^k$ is polynomial in $n$.

The above gives a one-way function $g$ for which $|g(x)| = |x|^{\frac{1}{k}}$ for constant $k$. My question is: Does there exist one-way functions whose value is even shorter than this? For example, is there a one-way $g$ for which $|g(x)| = \log |x|$?

Clearly, $|g(x)| \in O(1)$ is not possible since producing preimages for $g$ would then be possible with only constant information; hence my question about this apparent "gap" between $O(1)$ and $O(n^{\frac{1}{k}})$.


texts: Why does Birthday attack work only with random messages and not with chosen messages?

texts: Considering unkeyed hashing functions, I studied that the birthday attack can only work generating random messages and not with messages chosen from the attacker, but I didn't understand why. For example if there is a trade contract between two parties A and B where A states to sell a warehouse to B for 10.000 dollars, and the attacker (e.g. A) wants to modify this document and insert 100.000 instead of 10.000 dollars (I denote this document with D), why can A not generate a huge number of possible modified documents (for instance modifying space, dots, commas, etc. of D) and trying to find a collision between all possible modified documents and the original document?


texts:
Can the keystream generated by CTR mode be considered a pseudo-random function?

I give more information. Assume $f$ is a PRF. We define a function which takes 2 inputs, the desired length, and an arbirtrary value:

$F_l(r):=f(r\cdot l \cdot 1) \cdot f(r \cdot l \cdot 2) \cdot \cdots\cdot f(r\cdot l\cdot l-1)\cdot f(r \cdot l \cdot l)$ where $\cdot$ denotes the concatenate operation.

Is $F_l$ a PRF ?


texts: How does mutlivariate crypto schemes work?

texts:
I have been studying multivariate cryptography for post-quantum cryptography lately, but I have a hard time in understanding how these signature schemes work. As long as I see there there is UOV scheme, then Rainbow which is kind of a generalization of UOV scheme, and also there is something called HFEv-.

But how does these signature schemes work? I mean we use some multivariate polynomials, and most of the time the polynomials are quadratic. But how do we actually sign and verify messages (let's say a toy message such as 011101101)? Is there any place where I can find step by step how the algorithms work, and their application to toy examples so as to see how they work?


texts: Difficulty to find the pre-images of a pair of hash result such that given $a,b$, $H(x_1)=aH(x_2)+b$?

texts: Suppose given fix values $a,b$, how difficult to find a pair of sha256 pre-images $x_1,x_2$ such that $H(x_2)=aH(x_1)+b$? How difficult to find 4 hash pre-images $x_1,x_2,x_3,x_4$ such that $\dfrac{H(x_2)-a}{H(x_1)+b}=\dfrac{H(x_3)-a}{H(x_4)+b}$?


texts: Is TEA suitable for encrypting/authenticating many short messages?

texts:
I know that TEA has its weaknesses, but is easy to implement. My question is whether it would be suitable for my use case: The main reason for using encryption is not so much secrecy, but authentication and protection against interference.

I have a number (max 20-30) of GPS trackers, which send their location by radio in intervals to a base station.
Each message consists of a tracker ID, a timestamp, the location, and a checksum, so max 16 bytes, but in a fixed format.
Each message will be similar to the previous one, as the time increment will be constant, and the location will not change very much between two subsequent messages.
The time frame is about three hours, with probably about 800 messages sent per device during that period. So roughly 20k messages in total.
the code of the system will probably be public (so security through obscurity will definitely not work)

What I want to avoid from happening is anyone sending fake messages that are mistaken for real positions; decoding the message content is not a problem, as anyone can observe the trackers moving around anyway if they wanted to. So if it takes more than three hours to crack the key and enable sending fake messages, that would not be an issue, as that means the window in which a single key is used would be over.
I guess what I really need to know is:

Is TEA (or XTEA, or XXTEA) at all suitable for this use case? And if so, vanilla or X/XX? Or is there another algorithm that would be better suited? For example, just a hash checksum?
Are there any other ways I could improve security (eg use a different key for each tracker, randomly vary the format of the message (location first vs timestamp first), compress the message (only store difference to previous location, eg, to remove some redundancy))

My main design goals are reasonable security (it's competitive sports, not secret missile plans), simplicity of use and implementation (I am a developer, not a cryptography expert), and low computational overhead (this will run on an ESP32 micro-controller).
I have some basic thoughts on this, but would appreciate some expert advice!
UPDATE: Since this was asked in one of the answers: the trackers will be initialised in close proximity on power-up, and the base station can transmit a 'secret' key via Bluetooth Low Energy to each tracker. I do realise that Bluetooth is not really secure, but given the proximity this is in my view a negligible risk.


texts:
I have difficulty finding information about key space calculation of RSA. I think there is a gap in my math knowledge that prevents me from understanding the problem.

I know that symmetric ciphers such as AES 256 have key space equal to 2^256, but that can't be the same with RSA of key length 4096 that uses the product of prime numbers, can it?


texts: Understanding ransomware – What makes plain-text-attacks or brute-forcing so hard?

texts:
Say I have four files. Two are completely unencrypted, while the other two are the exact same files other than that they have been encrypted with (apparently) the same public key (via a ransomware virus). Is it possible to deduce the key from these files, so I can apply it to other files also encrypted with the same key?

Edit

Sorry, after searching through the questions related to my tags, I see the simple answer is no, because although the public key is easily discovered, it's probably a private key I'm looking for, which would be hosted elsewhere.

But to modify the question:

Does the length of the public key imply the length of the private key, or can they be unrelated?
Also, wouldn't more plaintext information provide a brute-force program a starting point to speed the process?

I don't understand why, given that all the files would be decrypted using the same key, we can't deduce said key by comparing encrypted files to unencrypted ones.


texts: Encrypted database: how to deal with general queries?

texts:
My question is quite related to the concept of homomorphic encryption, which is not practical at all nowadays.

In short, I would like to know how to query encrypted databases. Simple queries which test the equivalence of the entries can be easily implemented. Fine.

How about queries like: "select all employees with salary greater than 10000"?

The naive approach would be to select all employee id's along with their corresponding salary, decrypt everything and then check which ones match the aforementioned condition. Obviously this is far from being efficient.

Is there a more efficient way to handle such queries into encrypted data? Maybe some partially homomorphic algorithm?

My background: I have been in the academia for a while, so I know quite a lot about the concepts, but have no idea how these concepts have been employed by the industry so far.


texts: Encryption / Decryption using AES-256 GCM

texts:
I am new in cryptography and I am facing some complications in encryption-decryption. I am trying to use AES-GCM with a 256-bit AES key and a 96-bit nonce. I use an open source project (Vault) to create the encryption keys. Vault can encrypt/decrypt using the generated key.

The question is what should I have to encrypt data in a different application using the key generated by Vault (so Vault can decrypt afterward)? Is having only the encryption key enough, or should I export more data from Vault such as IV?

Thanks in advance if you have some advice and hope my question is clear


texts: Encrypting any text without key after padding oracle attack in CBC mode

texts:
Suppose the decryption program is already built. Now I want to encrypt an arbitrary plain text given the IV and the decryption program (no key). From the formulas, we have $$Dec(C_i)\oplus C_{i-1}=P_i$$ $$Dec(C_1)\oplus IV=P_1$$. However, given these information, I can only figure out $Dec(C_1)$. I have read this question, but it assumes all $Dec(C_i)$ are known, which is not correct for my case. My question is how can I find out all $C_i$? (Please note there isn't a database of $P_i$, $Dec(C_i)$ pairs to look up collisions).

I thought about using the decryption program to brute force each possibility, but it will take too long time. I also tried applying similar technique for decryption algorithm(tried to reverse the process), but still can't get a result. Any hints would be appreciated.


texts:
I am trying to understand better the hard-core bit property from the RSA assumption. The paper by Håstad and Nåslund shows that every single bit is hard-core. By the result itself, two or more bits can be correlated, but marginally a single bit is pseudorandom.
Is it possible to extend the result to the parity of an arbitrary non-empty subset of bits? That is, for every non-empty subset $S$, is the parity of $x_S$ hard-core given $(e,N,x^e\mod N)$? If not, then what property $S$ has to hold to conclude the parity of $x_S$ is pseudorandom?


texts: What are the well known protocols that offer perfect forward secrecy?

texts:
As far as I know these are the well known protocols that offer PFS

TLS/SSL (with DHE-RSA, DHE-DSS, ECDHE-RSA or ECDHE-ECDSA)
SSH (RFC4253)
OTR (Protocol Version 3 Spec)
IPsec (with IKEv1 and IKEv2) (RFC 2412)

Are there any other well known protocols? Have any of these been shown to be insecure?


texts: The protocol of provisioning shared key to multiple devices?

texts:
I have a bunch of IoT devices which can do ECDH/ECDSA and AES. They all are connected to some server and know its public key. In turn, server knows each public key of the corresponding device. Devices do not know about each other, only their master-server and its public key.

What I want is to get rid of ECDH for most of the time and to let all the devices to securely know about some common key that can be used to broadcast messages using AES and which (optionally) could be switched to a new one after some time.

So, the naive idea is for devices to securely "ask" server for a new AES key and its expiration date every time they get online. Or re-ask if they get decryption error.

Does it sound sane? Or should I consider some other group key establishment protocol?

By securely "ask" I mean some proper way of communicating like noiseprotocol/TLS


texts: As a cryptographic primitive, what does a nonce provide? It seems like, at least in my understanding of it, a nonce by itself would not provide any sort of cryptographic usefulness, compared with primitives such as digital signatures or symmetric key crypto.


texts: GCM mode and the order of AAD and plaintext

texts:
In GCM mode of encryption, what are the limitations on the mixing of plaintext and AAD (additional authenticated data)?

Must the AAD come before the plaintext? Or could it be after the plaintext instead?
Could there be both a block of AAD before the plaintext, and another block of AAD after the plaintext?
Is it possible for AAD and plaintext to be interleaved in some more complicated way?


texts: Trapdoor committement using ring lattices involving three parties

texts:
Assume there are three parties say A, B, C.

A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B.
B has to prove to C that he possesses commitment $c(m)$. There is no interaction between A and C. But B should not cheat by sending commitment to some other message $m^\prime$.

I guess for this we need A to generate $c(m)$ using his own trapdoor and later C can verify it is generated by A itself. Is it possible to achieve this using lattice based hard problems like $RSIS$ or $RLWE$.
Or is there any other way to achieve this using $RSIS$ or $RLWE$. ?


texts: Can NORX be used as a general purpose hash function?

texts:
In general terms, NORX works combining a cryptographic hash function and an stream cipher. At the end of an encryption operation you end with a ciphered message plus its authenticated hash. If you call AEADEnc() whith a zero length secret and postfix message, you basically get a hash function for each $(key, nonce)$ pair.

My question is, given a fixed and public $(key, nonce)$ pair, can NORX AEADEnc() work as a secure cryptographic hash function?