texts: Is multiple hashings of a cryptographic hash function an acceptable way to increase complexity?

texts:
Is nesting/re-hashing a viable way of slowing down a fast cryptographic hash function (such as SHA-256) to slow down brute-forcing attacks on shorter passwords? The use of longer passwords would of course be ideal, since it would lead to an exponential growth in brute-force difficulty, but is the use of multiple rounds an acceptable way of achieving linear growth in computational cost?

suppose an example: SHA256(SHA256(password)) would be twice as computationally expensive as SHA256(password), and so, a function with a difficulty parameter could be defined as:

function hash(String password, int difficulty)
{
String result = password;
while(difficulty >0)
{
result = SHA256(result);
difficulty--;
}
return result;
}

Are there any security risks/weaknesses with this approach? thanks.


texts: A secure function evaluation problem and an alternative of 1 out of n oblivious transfer?

texts:
I am considering a "secure function evaluation" problem:

Consider two parties: A and B. A has a one-to-one mapping function $f(x)=k$. Basically, the function $f(x)$ can be regarded as a table of two columns. The first column is the domain of $x$ denoted as $D$. The second column is the range $K$.
The party B has a secret input $x_i\in D$. B sends its input $x_i$ to A  and A will return the corresponding $k_i$ to B.

The requirement is that A will learn nothing about the input $x_i$  and the output $k_i$. B will learn nothing about the function $f(x)$.

For the above problem, a possible solution is the 1-out-of-n oblivious transfer. However, when the size of the domain (or the table) is large. Using oblivious transfer will introduce both heavy computational and communication overhead.
Another possible solution I can think about is to model the function as a circuit. And then some techniques such as Garbled circuit may be utilized.

I think the above problem as been considered for a long time in the cryptography community. Any related works or thoughts on this problem will be helpful.
Especially, is there an alternative of the 1-out-of n oblivious transfer to increase its efficiency?


texts: Why we need to use a modulus in public cryptography?

texts:
I know that in public cryptography we use asymmetric keys (public and private) for encryption and decryption. But we also use a modulus which fixes the ciphertext length. Isn't that a disadvantage?
Please, can you explain why we use the modulus?


texts: Formatting first/last byte of curve25519 private key?

texts:
Can anyone dumb it down for me on why you would need to format the first and last byte of a random number to properly generate a curve25519 private key as noted in 'Computing secret keys' section of http://cr.yp.to/ecdh.html#curve25519-paper.

Computing secret keys. Inside your program, to generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from
a cryptographically safe source: mysecret[0], mysecret1, ...,
mysecret[31]. Then do
 mysecret[0] &= 248;
 mysecret[31] &= 127;
 mysecret[31] |= 64;

mysecret[0] &= 248 = 0b1111 1000...setting three lsb's to 0 to ensure multiple of 8?
mysecret[31] &= 127 = 0b0111 1111...setting the msb to 0 for?
mysecret[31] |= 64 = 0b0100 0000...setting the second msb to 1 for?
I must be missing some important note on this in RFC7748?


texts:
What is the ChainOfFools/CurveBall Attack on ECDSA on Windows 10 CryptoAPI (Crypt32.dll)
Could someone provide details?


texts:
Assume $M_1$ is $\operatorname{OAEP}$ padded and encrypted and the ciphertext is 1024 bytes as an example. If an adversary somehow gets around the encryption and manages to get half of the bits of $\operatorname{OAEP}(M_1)$, and although infeasible, assume that it was somehow possible to loop through all combinations of the missing 512 bytes. At some point the $\operatorname{OAEP}$ decode will succeed and give $M_1$.

Will the decode operation succeed more than once to give other plaintexts, and if so, how many times?


texts: When a bit error happens in an IV, what would the result of decrypting a cipher-text be in the different encryption modes like ECB, CBC, CFB, OFB, and CTR?


texts: Slow hash algorithm that does not require salt?

texts:
I usually choose bcrypt when hashing as I can set the work factor to slow down the calculations of the hash. However, I have to keep a copy of the hash in order to verify it (since it includes the salt) when the same input comes around again.

Are their any A) common and B) slow hashing algorithms that do not require a salt? In other words, I don't need to preserve the output state in order to calculate the exact same hash again?

I am not looking for a more secure/unbreakable hash - just one that takes a long, long time to work out.

At this point it seems that multiple rounds of SHA-256 is my current best option.


texts: Security implications of using the low-order bits for Merkle–Damgård message length

texts:
According to RFC 1321 § 3.2 (MD5), the length of the message ($b$) is encoded as $b \bmod 2^{64}$:
A 64-bit representation of b (the length of the message before the
padding bits were added) is appended to the result of the previous
step. In the unlikely event that b is greater than 2^64, then only
the low-order 64 bits of b are used. (These bits are appended as two
32-bit words and appended low-order word first in accordance with the
previous conventions.)

This is contrasted with other Merkle–Damgård functions like SHA-1 which, despite also using a 64-bit representation of message length, are simply undefined for messages larger than that. Obviously this is a massive amount of data and there is no reason anyone would ever hash a message of that size, but I am still curious about the theoretical implications of this old design decision.
This question was inspired by Does a hash function necessarily need to allow arbitrary length input?.


texts: Append data to authenticated ciphertext encrypted using a stream cipher

texts:
Say we have xSalsa20 authenticated using Poly1305. If $ X $ is the ciphertext, $N$ is the nonce value, and $H$ is the authentication tag such that the final ciphertext is $ N || X || H $, then given the key $K$, is it possible to extend $ X $ with more data, without decrypting it, updating $N$ and $Y$ as needed? (I'm not sure if $N$ would need to be changed.)

To be clearer, say $ X_m $ is the original authenticated ciphertext. I want to append plaintext data $ A $ to it. I'm looking for a scheme to implement $ X_n = Append(X_m, A, K) $ such that $ Decrypt(X_n, K) = Decrypt(X_m, K) \| A $.

Salsa20 is a stream cipher so it produces a CSPR key-stream, $ S $, and then then ciphertext becomes $ X = S \oplus P $, where $P$ is the plaintext. So I intuitively feel as though this should be a lot easier to do than with a block cipher. Perhaps by generating the same key-stream up until the size of the ciphertext and encrypting the new data with the part of the key-stream past that point. If the authentication tag is generated from the ciphertext then decryption wouldn't be necessary for that either. Also the nonce would not really be reused in a scheme like this as far as I can see.

How well would this translate to other stream ciphers like XChaCha20-Poly1305?


texts: How does a company like Apple keep its keys safe?

texts:
Whatever key is used to sign new iOS updates (for example) must be incredibly well-protected. How does a huge corporation like Apple keep those 4096 bits safe?!

Same goes for SSL keys for websites like Facebook or Google -- a compromised key means trouble for millions of users, but at some point the key must be decrypted and used for a signature.


texts: How can I generate a good password from a SHA512 hash?

texts:
I have to change local administrator passwords on machines. I don't want to store password in a database. I have to generate a password that I can find later to connect to the machine again. So I periodically generate a secret random string (stored in a database) and make a hash of it with the machine  name. At this point I want to know how to generate a password from this hash (following current good practices) and I want to find the most secure way to do it.

So… I have to generate a password (in Python and following current good practices) from SHA-512. How can I do that? And what about security aspects concerning the password generation and the generated password?


texts: Using XL Algorithm to solve overdetermined systems, simple example required

texts:
Can someone give an example of how the XL algorithm is used to solve an overdetermined system as apposed to just a general case?

I have a fairly good understanding of how steps of the algorithm work, extending the system, then linearizing the system in the hopes of obtaining a univariate polynomial which is then solved. A small example with numbers and variables over a finite field would help me to see what's going on and understand the algorithm more.


texts: Is 2 a safe generator for elgamal encryption

texts: From what I understand here https://en.wikipedia.org/wiki/ElGamal_encryption and here: https://ritter.vg/security_adventures_elgamal.html, any number can be used as a generator. Is there something wrong with using 2 as the generator? Are there other constraints?


texts: Mapping integers to Ed25519 and back again?

texts:
I would like to map integer values to points on Ed25519, and then back again.

Is there a technique that takes advantage of the specific structure of Ed25519?


texts: Does a key need to be signed if it is being used to decrypt a message that is already signed?

texts:
I am trying to better understand authentication. Lets say I have posted my 128-bit AES symmetric key on some forum, encrypted asymmetrically to my friend using 256-bit ECC (25519). The forum isn't controlled by us so this key message could potentially be tampered with.

I then post a bunch of actual communication messages onto the forum that are encrypted with that AES key, and I sign them using a ECC 25519 signing key that my friend can safely use to verify the messages have not been tampered with.

Did I also need to sign my AES key message, or is it an adequate authentication check that the key decrypts my signed message correctly? If the key was tampered with it would fail to decrypt my message to something meaningful?


texts: Finding IV for forgery of AES CBC-MAC with non-fixed IV

texts:
As CBC mode might do several rounds, how it could be possible to find another IV for forgery attack?
This is an example from my course:
Assume you receive a pair with the plaintext $P_1$ and its MAC using an original $IV_1$. If you want to change $P_1$ to another plaintext $P_2$, how to find the $IV_2$?
As said in explanation, the process could be:
$MAC = E(P_1 \oplus IV_1)$
$MAC = E(P_2 \oplus IV_2)$
so,
$IV_2 = P_1\oplus IV_1 \oplus  P_2$
Why it is possible?
I test it with cryptool2 but it doesn't work...


texts: Does TLS have to provide both confidentiality and authenticity?

texts: I'm working on a project that uses OAuth. In the OAuth RFC it says many times that communication between the authentication server and the client should be with the use of TLS. However, in the project I'm looking at that uses OAuth, they say that the channels they use are only authenticated, not confidential. When looking at the TLS tag here, it says that TLS is both confidential and authenticated. But when looking at wiki, it looks like it can be either or? Can someone maybe clear up whether TLS can provide authenticity without providing confidentiality?


texts: Attacking a variation of the Vigenere with very long key length

texts:
I am to decrypt the ciphertext YVBCXGJRYHHRCJIUL into its plaintext message. The information that I am given is that the key used in the cipher is very long (equivalent to the length of an entire book) and that the key is certainly longer than the message being encrypted. The only other information I know is that the message encrypted is 2 days of the week, such as "SATURDAYWEDNESDAY."
There is no way to do any statistical analysis to discover key length. I am completely lost as to how I am to accurately decrypt the ciphertext into the correct message.
EDIT: It is known that the days of the week are "in order" and so based on the length of the ciphertext I can determine that it must be WEDNESDAYTHURSDAY or WEDNESDAYSATURDAY. This will reveal to me the first 9 characters of the key, but if the key is never repeated then I cannot use this to decrypt the second half of the ciphertext.


texts: When using AES-CBC-128, what attacks become feasible as you decrease the entropy of the IV?

texts: 16 bytes is the recommended entropy for the IV, AFAICT. Is 12 bytes of randomness with 4 fixed (across invocations of this encrypt function) bytes at the end, significantly worse? How so? What about 8 random bytes followed by 8 fixed bytes?


texts: After spending a good hour searching I came across an article that explained that you can't reverse a hash value. How true is this? I need to reverse a base64 encoded Sha-1 email address but I can't seem to find a way without knowing what function was used to hash. Or is there an easier way of going about this?


texts: How can an encryption scheme be indistinguishable with multiple messages but vulnerable to an adaptive chosen-plaintext attack?

texts: In order to be indistinguishable with respect to multiple messages, wouldn't the scheme need to be nondeterministic? How would this then possibly be vulnerable to an adaptive CPA?


texts: How to interpret the article claiming NIST P-256 curve to be unsafe?

texts:
Here: http://safecurves.cr.yp.to/ , I read that the NIST P-256 elliptic-curve is not safe.

The article lists several aspects (off-curve point, side-channel, etc.) where implementing P256 can fail the security, how should we understand these?

I think this is valid for encrypting, but are these also valid for signing?


texts:
My LCG has the form:

$$S_0 = k$$
$$S_{n+1} = S_n \times a + 1 \pmod m$$

Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this case we say the two sequences are equivalent. This equivalence partitions the generator outputs into disjoint subsets, or cycle sets.

How many cycle sets are there for a given $a$ and $m$, and how many elements are in each one? Can I also find a representative element for each set? It does not seem practical to find the answer for large $m$ by a brute force search.


texts: Is this an acceptable authenticated encryption?

texts:
After much deliberation, I've decided to use a normal Encrypt-then-MAC scheme instead of an authenticated encryption mode such as GCM as authenticated encryption primitive. This is due to the lack of good, clean and reliable implementation across all the platforms I intend to support.

Background

This is for a multiplayer [strategy] game over TCP/IP. In particular, a player will log in and play every day (or every other day) for about 1-2 months (the typical playing time).

The reason why we use encryption at all, is to:

prevent sabotage (replay another player's login + actions to make him waste his daily turns, modify actions in flight)
prevent eavesdropping (stealing login credentials, monitoring actions, stealing in-app purchases)

Proposed Authenticated Encryption Primitive

At a new connection derive the IV, encryption key and signing key using HMAC-SHA512, using a secret (lifetime - max 24 hours, randomly generated) and public client + server nonces and two salts (one for each direction). We simply split the resulting 64 bytes to form 16 byte IV, 16 byte key and 32 byte signing key.
We set up two AES-CTR ciphers (one in each direction) using the IVs and the encryption keys derived in step 1.
For each packet to encrypt, we perform the following steps:

Encrypt the packet with the next [plaintext number of] bytes of AES-CTR.
Calculate HMAC-SHA256(signing key, 4 byte message number || 4 byte message length || ciphertext)
Increase message number by 1.
Send ciphertext || first 8 bytes of HMAC

On decryption, checking HMAC is made so that successful matching the HMAC and failing to match the HMAC should execute equally fast.

Example code:

int hmacFail = 0;
int hmacSuccess = 0;
while (hmacPtr < hmacEnd) {
    if (*(hmacPtr++) != *(hmacOurPtr++)) {
        hmacFail++;
    } else {
        hmacSuccess++;
    }
}
if (hmacFail > 0) -> Raise HMAC invalid error

On failed packet authentication, the connection is dropped. On the consequent reconnect a new server and client nonce will be used, so IV and keys will not be reused. Typically a connection lives for about 5 minutes, but may stretch into 1-2 hours.

Messages are typically small (less than 100 bytes) and infrequent (usually no more than a few messages a second)

Questions

Is something missing from the MAC?
I'm fairly confident that reducing the HMAC to 8 bytes should be ok, as the behaviour of dropping a connection (and thus forcing a new signing key). It might be quite ok to reduce it further.
As far as I can tell from some initial benchmarking, the dominating cost is in calculating the hash. What are my options if I want to reduce this cost while using readily available hash primitives? Going to SHA1 or even MD5 would make it faster (in my particular test, SHA1 was around 50% faster, MD5 100% faster). Any tips and tricks given the circumstances?
Anything else I've forgotten to take into account?


texts: Construct block cipher from a smaller one with mixing function

texts:
I read about the AEZ encryption scheme as presented at the CAESAR competition. To me it seems like a construction of an arbitrary length block cipher from a smaller one. The key component is the mixing function. (See the figure… Left: without cipher text stealing, Right: with cipher text stealing.)

Image source: http://www.cs.ucdavis.edu/~rogaway/aez/aez.pdf

In my opinion the properties of a mixing function would be:

keyable with good avalanche effect
no need to be cryptographically secure
arbitrary length
reversible
fast (at least faster than encryption cipher)

AEZ uses reduced round AES as the core of its mixing function. Overall operation time is about 1.8 AES (as mentioned in the document). This algorithm will be bound to the AES cipher.

I wonder, is there an alternative mix function with these properties floating around?


texts: Can a shift cipher attain perfect secrecy?

texts:
On a practice question for my intro cryptography exam, it asks the following:

Assuming that keys are chosen with equal likelihood, the shift cipher provides:
   A) computational security
   B) perfect secrecy
   C) semantic security
   D) none of the above

I chose "none of the above", though I wasn't too sure. But I was certain it was not "perfect secrecy". However, when I review the exam solution key, it says "perfect secrecy" is, in fact, the answer.
Given that the message space of a shift cipher is huge, and the key space's cardinality is only 26, how can it possibly provide perfect secrecy under any circumstances?


texts: Understanding forking lemma and oracle replay attack

texts:
Many signature schemes use forking lemma to prove security, like scheme in here.In short, that goes through a reduction technique which called oracle-replay attack to solve the difficult algorithmic problem, requiring two rounds of simulation for $\mathcal{F}$ to obtain two valid signature pairs $(m,r,e,s)$ and $(m,r,e',s')$,where $r$ is a "commitment", $e = H(m||r)$,$s$ and $s'$ is related to $m$, $r$ and $e$. But how to ensure the forger $\mathcal{F}$ will output the same message $m$ and $r$ ,since they may select randomly in each simulation?

see also
[PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.


texts:
I'm not familiar with algorithm complexity so I'm asking here.
I need help determining degital signature complexity, I did some research and all I found is complexity for the D.S.A only:
( ) =(2 ).
( Verification) = (3 ).
I'm using RSA Signature and SHA-2 hush function.


texts: Why are there limitations on using encryption with keys beyond certain length?

texts:
I am writing a java program to encrypt a message using 256-bit AES encryption, but I am getting illegal key size error, I have read that I have to use some JCE Unlimited Strength Jurisdiction Policy Files to encrypt/decrypt message with key of 256-bit or longer, but I do not understand why there is a limit on using a key size? Why using 256-bit encryption is disabled in Java by default?

Is it a crime to encrypt/decrypt files using 256-bit keys?


texts:
Universal reencryption is an interesting encryption primitive.  Attempts to build signatures schemes or protocols with authentication incorporating it have frequently failed though.

A plausible application of a signature scheme employing universal reencryption might be:

Alice's software obtains a blind signed credential from a signing authority, perhaps stating her age.  Alice wishes to use this credential with multiple websites, but obviously using the same signature on multiple websites violates the browser's cross origin policy because a typical signature depends upon a nonce that could be used to track Alice.  A signature scheme based upon reencryption might allow Alice to mutate the nonce embedded in the signature.

There is an easy solution to this problem if the signing authority simply gives Alice thousands of single use blind singed tokens and keeps her stocked up, but that entails some logistical complications.

It'd be lovely if Alice could just use the same signature over and over, mutating it each time through universal reencryption or similar.  Are there any signature schemes that support anonymizing the signature like this?


texts: Time complexity to solve Discrete log problem

texts:
What is the time to complexity to solve
Discrete log  problem now in $Z_p$?

Initially for $n$ bit prime $p$, it was $Exp(n^{1/3})$.


texts: Can Elgamal be secure in $\bmod {n^2}$? Meaning instead of using a prime order group to use a group where DCR assumption holds?


texts: RSA: large private exponent often yields large public exponent

texts:
In this answer to a question about choosing RSA's exponent (whether it is better to choose the private or the public exponent), user @Jus12 stated:

When choosing $d$ first: [...] guarantees with high probability that $e$ will be large, making encryption slow.
When choosing $e$ first: can choose very small or pre-determined value of $e$; [...] guarantees with high-probability that $d$ is large so various attacks still don't work.

I easily understand that a small value for $e$ leads to a large value for $d$, as $e\cdot d\geq k\varphi(N)+1$ with $k\in\mathbb Z$ and $N=pq$ being the RSA modulus.
However, I do not see why a large $d$ will probably also result in a large value for $e$. I just see no obvious reason why a large $e$ is more probable than a small one.
I did a quick test for $p=5$ and $q=11$. Considering every $d>\max(p,q)$ as "large" I get the following results:
 d   e
------
13  37
17  33
19  19
21  21
29  29
31  31
33  17
37  13
39  39
------
23   7
27   3

In this case, large $e$'s are more than four times more frequent than small ones. But why is this?


texts: Secure Cipher Suites supported by JDK versions

texts:
I'm a n00b to cryptography.  I've been searching through oracle's java docs, ssl labs, googling and more googling attempting to find an up to date list of cipher suites considered secure for the latest updates of Java SE 6 (I know its old), Java SE 7 and Java SE 8. I've found plenty of outdated info which is not useful to me.

I understand the basic concepts and ciphers that together make a cipher suite- key exchange, bulk encryption and MAC. I also have a high level understanding of the TLS protocols.

If someone can point me to an up to date resource(s) I'd really appreciate it. Deadlines are looming.

To clarify- This isn't a programming question. It is strictly focusing on secure cipher suites. I'm not implementing any of this in code. It is simply a list of secure ciphers related to Java that I'm compiling.


texts:
Please give help! how can I calculate the probability of collision? I need a mathematical equation for my studying.

Assume, I am using SHA256 to hash 100-bits. Thus:

SHA256 {100} = 256-bits (hash values) I would like to know the probability of collision.

This website:
https://preshing.com/20110504/hash-collision-probabilities/

Gave an equation: $K^2 / 2N$

But I could not know what is $K$ and $N$? Is K is the output which is (256-bits) and $N$ is the input which is (100-bits)

Please Help and Thanks in advance...


texts: Secret sharing - no dealer, modifiable, verifiable

texts:
I need to find a secret sharing scheme with these properties:

The scheme is set up by all participants, ie no single entity called the dealer

The parameters of secret sharing need to be modifiable, eg enrollment, disenrollment, change of access structure, ...

Need to be verifiable, ie participants could check whether their shares are consistent with others.

Is this scheme could be available at all !?
A brief description is helpful.


texts: Entropy after shuffling result of /dev/urandom

texts:
first of all: Im pretty paranoid.
I am creating a seed on my linux server using the following command:

cat /dev/urandom |tr -dc A-Z9|head -c${1:-81}

Since I don´t have any local linux systems, I connect to my external server via SSH.

Now, I got this (probally unjustified) fear, that my seed, although being transferred via SSH, might be compromised. So I considered shuffling the seed on my local computer. For example taking parts of it (5-10 digits) and pasting them at a differnt location.

I guess that this might decrease the security/entropy of the seed. My questions is: how much? Should I either trust that my seed has been transmitted safely or shuffle it around a bit?

Of course I know the easiest solution would be using a local Linux system to generate it. But let´s talk about the other solutions.


texts: For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = H(A_2) = .....  = H(A_n)$).


texts: Exactly how bad is using 'mod' to clamp reduce numbers to a given range?

texts:
Let's say I'm naive and want to generate a random integer in the range [0, m), so I do the following:

k = cryptographically_secure_rng() % m

where cryptographically_secure_rng returns a random integer in the range [0,n).
Obviously, assume m <= n.
Now in general k isn't distributed uniformly anymore.

It seems to me that for any reasonably nontrivial value of m and n, this can't possibly cut the attacker's time by more than half -- and in general, it would seem to cut it by a much smaller fraction.
Yet my impression from security/crypto is that such a naive RNG would be catastrophic for the security of the system.

So my question is:
How bad is this from the standpoint of an attacker trying to attack a system by exploiting this function?

Could such a bias be abused and amplified (e.g. exponentially) to attack a system?
If so, in what kind of a system might this occur, and how?
If not, then is the problem worth worrying about, and why?


texts: I'm trying to protect a key using a PIN code. However, if the user somehow loses the PIN code, I'd like to be able to allow recovery using a PUK (similar behaviour as for instance your SIM card on your phone). How would I go about implementing this, whilst storing as little private data as possible? Are there crypto schemes that describe this functionality?


texts: Signing many small messages with minimal overhead

texts:
I have a distributed system where each client writes many small messages, roughly the size of messages in a chat system, e.g. ~100-200 bytes each. I want each message to be signed so that we know for sure who sent each message, but the overhead of an RSA signature on each message is huge, so I need another approach.

One idea would be to sign the first message like normal, and include a hash of a random value. Then, in the next message, include that random value and a new hash of another random value. Each message "unlocks" the previous message's hash, showing that they were authored by the same client. Using a bcrypt/scrypt/argon2 hash with a work factor to meet about 10ms would mean that the random value could be kept small, say 64bit. Each message also has a unique id, which would be used as a salt. This is a huge improvement in overhead, but I have no real idea how secure such a system would be. Also, messages store ordering information, so once a message has been "unlocked", that random value cannot be used to "sign" a second message.

Some messages would contain encrypted fields, using some form of hybrid encryption. The servers only need signed metadata, not the actual messages.

I'd say this is a great example of where "don't roll your own 1. distributed system 2. crypto" applies. I've got the distributed system part, but I need your help with the crypto.

How can I sign many small messages (tens of thousands) with as little size overhead as possible, while still being secure? I've got 50MB of RAM and about 10ms of cpu time for decryption of each message. The client must be able to sign, encrypt and send messages without getting a response from the recipient(s).


texts:
Bob uses RSA with $p=83$ and $q=103$. His public key is $e=445$.  Alice claims that she can calculate Bob's private key without using the definition $d=e^{−1}\bmod φ(n)$?
But how?


texts: How to convert random bytes into blocks of numbers without weakening entropy?

texts:
Let's say you have a, or several random byte(s) 0-255 and would like to derive numbers 0-9 for a One Time Pad (OTP) of them.
What would be a non-naïve approach to represent 256 possible values onto 10 possible values without weakening the underlying security? I am not sure that I simply can discard 6 states of the 256 values to achieve division by 10 without a fraction as result and not weaken security at the same time.
Is there a simple, yet convincing mathematical approach that I could port myself to a programming language to map bytes into blocks of numbers ranging from 0-9 safely?


texts: TLS Key Block calculation - What is a PRF?

texts:
In Section 6.3 of the RFC for TLS 1.2, it is written that the key_block is derived from the following formula:

  key_block = PRF(SecurityParameters.master_secret,
                  "key expansion",
                  SecurityParameters.server_random +
                  SecurityParameters.client_random);

An arbitrary amount of "key_block" formulas are run until enough keying material exists to populate keys for the following six session keys:

  client_write_MAC_key[SecurityParameters.mac_key_length]
  server_write_MAC_key[SecurityParameters.mac_key_length]
  client_write_key[SecurityParameters.enc_key_length]
  server_write_key[SecurityParameters.enc_key_length]
  client_write_IV[SecurityParameters.fixed_iv_length]
  server_write_IV[SecurityParameters.fixed_iv_length]

Unless I'm missing something, since values fed into the Key_block calculation are identical and don't change, the result of each calculation is the exact same string.  Given that, why would the RFC indicate to recalculate the PRF when we could just repeat the same string as necessary to populate the six session keys?

After writing that out, I realized that I'm taking PRF to effectively mean "Hash of the following values".  If I've misinterpreting PRF, then maybe the more appropriate questions would be:
Does each iteration through the Key Block calculation produce different results by nature of what a PRF is?
If so, how does the opposite end of the negotiation come to the same session keys?


texts: Programming language for modular arithmetic over large numbers

texts: I'am trying to implement algorithms on integer factorization.This involves dealing with integers of 200-500 digits and doing modular arithmetic over them.Which programming language has inbuilt support for large numbers?Does C++ support large number arithmetic?


texts:
I hope someone can help me with the sequence of games security proof for protocols. Here are my questions:

What is the aim of each individual game? i.e. why can't we do this in one indistinguishable game ?

How can we link each game with the previous one? i.e. I am not understanding the difference lemma which states:

Lemma 1 (Difference Lemma). Let A, B, F be events defined in some probability distribution, and suppose that A ∧ ¬F ⇐⇒ B ∧ ¬F. Then |Pr[A] − Pr[B]| ≤ Pr[F].


texts: How to encrypt/decrypt data in an SPI BIOS FLASH

texts:
I need some info/suggestions about the cryptographic algorithm that make me sure that the executed bios by the CPU is an authenticated bios. The check has to be performed by a FPGA.

I have SPI Flash that contains the bios code ( assembler code ), CPU and  FPGA between CPU and SPI Flash.

The first idea was to authenticate the bios performing a HMAC authentication of the data stream between CPU and flash, but I saw that the stream is always different so impossible to authenticate ( the bios/CPU waits the wake up of the peripheral so perform each time different operations ).

The second idea is to encrypt the whole SPI flash and decrypt on fly with FPGA when the CPU request the data. I actually don't know if FPGA is enough fast to do this, but I'm sure I can't use an AES 128 because the FPGA isn't so fast to fetch 128 bit to decrypt only 32 bit ( during the bios execution there are a lot of memory jump and usually the fetched data are 32 bit for each CPU operation ).


texts:
I've read "A Parallelizable Enciphering Mode" by Halevi and Rogaway about the encrypt-mix-encrypt mode for ciphers and was asking myself if this mode provides "full" diffusion.

So if an attacker alters one bit of the ciphertext, how many bits (all?) get scrambled on decryption? (if using AES and blocks of size 4096 bits (drive sector size))

Or in other words: Does this mode turns a "narrow" block cipher into a "wide"
cipher and hence would be a perfect choice for  full-disk encryption (FDE)?


texts: What informal indicators exist for estimating the computational infeasibility of cryptographic problems?

texts:
When assuming a block cipher primitive is secure, or a number theoretic problem is hard, this assumption is usually based on how far we are from breaking the primitive or solving the problem using known techniques - using known algorithms and hardware.

But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware? I am not asking for opinions on the matter (or for arguments that fix the algorithms and prove that the necessary hardware would be physically impossible) but for justifications based on e.g. the sociology of cryptography or economics of cryptography, using scientific (justified and repeatable) methods and based on the premise that all research is done in the context of pre-existing research.

How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?
Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?
If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?
What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?


texts: Blowfish: hex digits of pi used for s-boxes?

texts:
Preface: here is the official site for the Blowfish algorithm:

http://www.schneier.com/blowfish.html

The Blowfish algorithm uses an s-box, which consists of hex digits of pi (found here: http://www.schneier.com/code/constants.txt). I'm guessing that this s-box serves a very similar purpose to the s-box in AES (right?)

However, at the bottom of that file, there is a smaller box called p_array or parray or something. I have no idea what it does! Also, is there some sort of significance to why the hex digits for pi are used, and not some random values?


texts: Verification of data on an untrusted remote storage server

texts:
I was looking at tahoe-lafs which accepts a file, encrypts it, does erasure coding on it which generates n shares and then distributes it over the storage servers. The distribution is Share 1 = Server A, Share 2 = Server B and Share 3 = Server C.

Now If I want to make sure that the Server B  has that data, how do I go about doing that?

I could request the share, hash it and verify it by building a merkel tree but that would consume lot of storage server bandwidth if the share size is big. We can't ask the storage server to send us the hash by computing it since it might have the precomputed hash and might not generate the hash at all.

So how do I go about doing this? I looked at Provable data possession but couldn't understand much. Can someone point me in the right direction or help me understand it?


texts: How to construct Hash function of type $H:\{0,1\}^x \times G \mapsto Z_p^*$?

texts:
In many cryptographic protocols design, I have seen the statement
'Choose a Hash function $H:\{0,1\}^x \times G \mapsto Z_p^*$ i.e a hash function which takes as input a binary string of finite length and a random element of some group and outputs an element of multiplicative group of prime field. How could I construct such a hash function?


texts:
I am starting to learn more about cryptography and I just read more about how asymmetric keys can make a digital certificate, and I would like if someone could explain me why the following case can't be applied:

Since asymmetric keys rely on a pair of keys, and you use the private key to encrypt the hash of the document you want to sign so someone later can read the encrypted hash using your public key, to look for a match with the document's hash...why can't someone generate another private key that will match your public key and fool the whole process?

Usually every text about asymmetric cryptography focus on how difficult it is to find the original private key or to break the cypher-text, but my point is, in order to make someone believe your document/code/website is legit and certificated, you don't need to find the original private key, any new "malicious" private key that matches the well known public key of the CA (certification Authority) will be able to sign everything you want with this new key, so the public key will match and decrypt it.

I don't know very well the asymmetry keys math, so there might be "something" there that also prevents this, but so far I haven't seen any information, like how unique is the connection between the keys and how difficult it is to generate a key ('A') that will match a previously given key ('B').


texts: How hard is it to generate a partial RSA fingerprint collision?

texts:
When I  use SSH to log into a new system, I get asked to verify that the fingerprint (a 32 hex digits string) of the hosts's RSA key is correct. How much if it must I actually compare (by hand/eye) to make it unfeasible for someone to man-in-the-middle me? Assume the adversary has a budget of a few thousand dollars.

Clarification: I'm assuming that a human will never hand verify that the fingerprint printed by there SSH client is in fact exactly the same as the key on there server, but rather (assuming they are more diligent than the average human) will read a limited prefix and/or suffix. If we assume they will read the first and last 4 digits then you should be able to create a collision of just those digest in $2^{(4+4)4}=2^{32}$ guesses.

The question then becomes; how many digits can an attacker expect to match with the budget described above?


texts: How to compute the attacker's probability?

texts:
Given a random bit string $R=r_1r_2\cdots r_n$, let us encrypt each bit $c_i=E(r_i,k_i)$ where $k_i$ is taken from the stream of encryption keys. Suppose that an attacker can guess the correct $r_i$ from $c_i$ with probability $p>1/2$. Then, the probability that the attacker can recover correct $R$ from $C=(c_1,\cdots,c_n)$ is $p^n$.

Now, suppose that we use the following encryption diagram (given below).  Is the attacker's probability of recovering the correct $R$ from $C'=(c'_1,\cdots,c'_n)$ still $p^n$?

Let $r'_i=r_1\oplus r_2\oplus\cdots\oplus r_{i-1}\oplus r_i$.
Let $c'_i=E(r'_i,k_i)$.


texts: NP complete problems related to permutations of binary vectors or block ciphers

texts:
Recently, T.Gowers wrote a blog entry called "How not to prove that P is not equal to NP" about the Razborov/Rudich Natural Proofs paper. He has a construction where he talks about compositions of 3-bit scramblers along with a paper on the subject. Boaz Barak replied to that post with the following comment:

  Some other intuition that these scramblers might be hard to distinguish from random is that they seem somewhat related to the designs of block ciphers, and these are actually conjectured by cryptographers to be indistinguishable from random. (And cryptanalysts spend significant time trying to attack these conjectures.)

I'm wondering:

  Are there any NP complete problems related to permuting bit vectors or block cipher constructions?


texts:
I am trying to perform Cryptanalysis on Affine cipher . Given Plain Text "GO" and cipher text "TH"

We know , $G =6 , O=14 , T=19 , H= 7$

By brute force method

I'm getting key $(a,b)$ as $(5,15 )$

But by known plain text attack method

$6a + b = 19 \\
14a +b = 7$

on solving the equations . im getting

$-8 a + 0  =  12  $

taking addictive inverse of $-8 = 18$

We get , $18a +0 =12$ , Now

$a= 12*$ multiplicative inverse of $(18)$

Multiplicative inverse of 18 doesnt exist then how to proceed ? Is my approach correct ?


texts: Session based AES with random key and static salt

texts:
I'm currently using aes to encrypt/decrypt messages to and from a web service.

When the user establishes a session he sends a random  generated secret via rsa public key.

This secret is used to establish a secure channel using AES (CBC).

I'm using Rfc2898 to derive a key with a static salt (the salt is hardcoded and never changes). The IV is randomly generated for each message and prepended in cleartext.

Is it ok to use a static salt (Since I'm using a random generated secret for each session)?


texts: What makes an open source encryption algorithm safe?

texts:
Take for example the popular AES algorithm where we have a combination of substitution, shift row, mix column, and add key steps involved in encrypting plain test.

All of the mathematical operations within the s-boxes, shift row, and mix column should be known to the attacker, correct? I understand they could be hard to calculate but aren't they static operations for the most part? Since they can literally see the implementation of the calculations in the code to see how all the bits were changed around. The only step that is therefore hard to break is the add key stage, where we XOR our key with blocks of bytes.

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key? Since the implementation details are known of how the substitution, shift row, and mix column steps work, whats the point of using them in the encryption scheme?


texts: Simplifying the description of the Keccak padding rules

texts:
I would like to check if my following understanding of Keccak padding has any flaws and if there are, please feel free to point them out and correct them.

The Keccak version I am interested is the original Keccak with 256 bits output (not the SHA3 from NIST).

It has a bitrate of 1088 bits and a 256 output bits.

Assuming that a Keccak function operation has a absorbing phase followed by a squeezing phase, Keccak-256 would require 136 bytes (1088 bits) of memory space to compute on for every absorbing phase.

During the absorbing phase, a part of the input message of 136 bytes of length would be copied into the computation states (blocks/lanes ..etc..). If the copied message into the states are insufficient, a padding has to be applied otherwise if the message states are sufficient (exactly 136 bytes), nothing has to be done.

When padding occurs on the bit level, it will begin with bit 1 followed by a string of 0 until finally the last bit is also a 1 for the original Keccak-256.

I would like to know the flaws of my above description and what are the correct description in a very simply and easy to understand manner I should approach it from.


texts: Why restrict nonce/IV and counter to specific sizes?

texts:
When setting up a nonce/IV and counter (e.g. for AES-GCM-128), why are the nonce/IV and counter restricted to specific sections (e.g. random nonce/IV in first 8 bytes and counter in last 8 bytes)? This results in the last 8 bytes always starting off at a predictable value (0), reduces uniqueness (only 8 bytes of random data), and requires more frequent re-keying due to counter wrapping.

Is there a reason the entire 16 bytes cannot be initialized to random data, start the counter from there, and allow the counter to use the entire 16 bytes?


texts:
I need a bit of clarification about the definition of transcript of a simulator in Zero-Knowledge Proofs.

Basically, the way I understood it, the simulator is given access to the (potentially malicious) Verifier as a sub-routine, and the goal of the simulator is produce a transcript that's computationally indistinguishable from the transcript produced between the Prover and the (potentially malicious) Verifier.

My question is: Does the transcript of the simulator include the final Accept/Reject output of the verifier or not? In other words, if the verifier accepts in an interaction with the real Prover, should the simulator also be able to produce a transcript, that will be accepted by the verifier, or can the simulator just leave the verifier's output out.

If it leaves the verifier output, then the definition doesn't seem to make sense to me, because I can always generate a random transcript that looks like the interaction between prover and verifier. However, in most lectures, I don't see people requiring the result of verifier in the transcript, which is what's confusing me.


texts: Why does HOTP use such a complex truncate function?

texts:
In the HOTP protocol after calculating a 20 byte hash it is truncated to 4 bytes.

For this first an offset is calculated (low-order 4 bits of the last byte) which determines the four bytes to be selected:

DT(String) // String = String[0]...String[19]
 Let OffsetBits be the low-order 4 bits of String[19]
 Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
 Let P = String[OffSet]...String[OffSet+3]
 Return the Last 31 bits of P

Why is this more 'secure' than simply always taking the first four bytes of the hash?


texts: Can you point me to an MDS table reference for the Kalyna cipher?

texts:
I'm working with cipher Kalyna.

Kalyna — like AES — has MDS tables in its MixColumns step. But Kalyna's documentation doesn't list these MDS tables.

Could you give me a hint where to find proper documentation or the particular MDS tables?


texts: How is the number $2^{130}-5$ used in Poly1305? It operates on blocks that are 128 bits long, but the number has 130 bits. I don't understand how it is used. This comment makes me think it uses integer arithmetic.


texts: We can obtain "absolutely perfect CONFIDENTIALITY" using the one-time pad. Is there such a thing as "absolutely perfect INTEGRITY"?

texts:
The OTP (one-time pad) gives us perfect secrecy. This is the very best confidentiality available in this universe. (Although it does require large keys, which is beside the point of this question).

The problem is such encryption does not attain integrity. So my question is, is there such a thing as perfect integrity?


texts: what are the plaintext's for the RC4 stream cipher test vectors in RFC6229?

texts:
https://tools.ietf.org/html/rfc6229 has stuff like this:

Key length: 40 bits.
 key: 0x0102030405

 DEC    0 HEX    0:  b2 39 63 05  f0 3d c0 27   cc c3 52 4a  0a 11 18 a8
 DEC   16 HEX   10:  69 82 94 4f  18 fc 82 d5   89 c4 03 a4  7a 0d 09 19
 DEC  240 HEX   f0:  28 cb 11 32  c9 6c e2 86   42 1d ca ad  b8 b6 9e ae
 DEC  256 HEX  100:  1c fc f6 2b  03 ed db 64   1d 77 df cf  7f 8d 8c 93
 DEC  496 HEX  1f0:  42 b7 d0 cd  d9 18 a8 a3   3d d5 17 81  c8 1f 40 41
 DEC  512 HEX  200:  64 59 84 44  32 a7 da 92   3c fb 3e b4  98 06 61 f6
 DEC  752 HEX  2f0:  ec 10 32 7b  de 2b ee fd   18 f9 27 76  80 45 7e 22
 DEC  768 HEX  300:  eb 62 63 8d  4f 0b a1 fe   9f ca 20 e0  5b f8 ff 2b
 DEC 1008 HEX  3f0:  45 12 90 48  e6 a0 ed 0b   56 b4 90 33  8f 07 8d a5
 DEC 1024 HEX  400:  30 ab bc c7  c2 0b 01 60   9f 23 ee 2d  5f 6b b7 df
 DEC 1520 HEX  5f0:  32 94 f7 44  d8 f9 79 05   07 e7 0f 62  e5 bb ce ea
 DEC 1536 HEX  600:  d8 72 9d b4  18 82 25 9b   ee 4f 82 53  25 f5 a1 30
 DEC 2032 HEX  7f0:  1e b1 4a 0c  13 b3 bf 47   fa 2a 0b a9  3a d4 5b 8b
 DEC 2048 HEX  800:  cc 58 2f 8b  a9 f2 65 e2   b1 be 91 12  e9 75 d2 d7
 DEC 3056 HEX  bf0:  f2 e3 0f 9b  d1 02 ec bf   75 aa ad e9  bc 35 c4 3c
 DEC 3072 HEX  c00:  ec 0e 11 c4  79 dc 32 9d   c8 da 79 68  fe 96 56 81
 DEC 4080 HEX  ff0:  06 83 26 a2  11 84 16 d2   1f 9d 04 b2  cd 1c a0 50
 DEC 4096 HEX 1000:  ff 25 b5 89  95 99 67 07   e5 1f bd f0  8b 34 d8 75

So it's pretty obvious what the key is but what is the plaintext supposed to be? I assume each the DEC part of each line corresponds to the offset?


texts: Is recursive secret sharing of practical value?

texts:
This paper describes recursive secret sharing.  In one of their illustrations, a binary secret of length L, along with 3 other binary secrets of lengths shorter than L, are split into ternary shares of length L.

Any two shares can reconstruct all 4 secrets.

It seems to me there is no advantage in hiding multiple binary secrets in ternary shares, which could not have been gained by concatenating the ternary version of those same secrets and then splitting the resulting, single secret into ternary shares.

Is this correct?  Why or why not?


texts: How to sell a piece of data through blockchain?

texts: User A attempts to sell a piece of data D (byte level) to user B at price C through the blockchain. A and B do not trust each other. A worry: After the data D is delivered, B does not complete the transfer; B worry: After completing the transfer, A does not send data D, or sends invalid data D. How to design a reasonable mechanism to protect the interests of both parties?


texts:
There was this one time I came up with a small permutation that had a block size of 16 bits. This was small enough to compute every mapping. I then iterated the mapping starting with zero to see how many iterations it would take to return to zero. The number was less than half of $2^{16}$.

For whatever reason, let's say a person needs a pseudorandom permutation that has only one cycle. Perhaps they need to make a single-cycle S-box or they want to use the permutation to create a non-linear tweak to the plaintext input of a block cipher (each block's tweak is the result of successive iterations instead of increments of one). First thing that comes to my mind is a full-period LCG, but when I tried this for making an S-box ($f(x) = (37 \cdot x + 11) \mbox{ mod } 256$), the results seemed rather orderly. This wouldn't matter for a tweak for plaintext blocks, but it seems desirable to simply not have that property of orderliness. So, what are some way of generating/constructing single-cycle permutations?


texts: Are there low-bit hashing or encryption functions for teaching cryptographical concepts?

texts:
I understand how hashing and encryption/decryption work at a very high level, where the functions work as a black box. Hashing scrambles the input in a non-uniquely reversible way, whereas encryption uses a key to scramble the input in a reversible way where it's highly unlikely that any other key could produce the same output. Salts can be added to prevent rainbow attacks by randomising the output more.

Over time, collisions are detected in hashing functions, and encryption/decryption functions are cracked, leading to stronger functions being developed usually with more bits.

However, I would be interested in studying low-bit concrete hashing/encryption functions in order to understand how it can be mathematically proven to be uncrackable except by brute force (if that is indeed possible).

Are there any such low-bit functions that can be followed through step by step and analysed mathematically without the maths getting too complex? Ones that would be considered cryptographically secure except for their length?


texts: Cipher Text generated is different if nonce is greater than 12 bytes

texts:
I wrote a library which uses AES-GCM-128 to perform encrypt and decrypt operations. This library uses EVP functions that provide a high level interface to OpenSSL cryptographic functions.
To verify my library implementation is correct or not, I did the below test.
I took already known nonce, key, aad, plain text which I feed into my library and got a cipher text.
Now I feed the same into an online website which gave me a different output.
The cipher text generated by the website is 56d86b2c9932554f473950900f40250f and the cipher text generated by my local implementation is 6ceedef0a0f24a0fcb8f8730288f757d
The interesting thing is that if the IV is of 12 bytes, then I get the same cipher text from online website as well as my implementation. However, if I change the IV to 16 bytes, then I get different cipher text from online website as well as implementation.
I know that Using the IV longer than 96 bits causes an additional GHASH call to convert into 96 bits.
Also, the tag generated by my local implementation is always different from the one generated online even though nonce, key, aad, plain text remains same.
Can some one please help me in understanding this behavior?


texts: Are these two methods of differential cryptanalysis different?

texts: I'm trying to understand how differential analysis works. I'm reading this and this tutorials, but it looks like they do different things. In the first paper author tells us to bruteforce last round using every possible keybits for active sboxes and traces differential up to r-1 round. In second work differential goes to the end and bruteforce goes only for a number of keys and author finds k0 and k1 at the same time. Which method is a basic to find round keys?


texts: I have a basic question. Is there a way to define an Elliptic Curve over (binary) Finite Field of order $q=2^m$ such that by taking the points from $(0, Y_0)$ and $(1, Y_1)$ then maps them to $(q - 1, Y_{q - 1})$?


texts: Practical OWP of the set of $k$-bit bitstrings for low $k$

texts:
Down to what $k$ and how can we devise a practical, public, efficiently computable One Way Permutation $P$ of the set $\{0,1\}^k$ of $k$-bit bitstrings, if possible without involving a trusted party for parameter setup ? Note: I want $P$ to be a permutation in the mathematical sense, and computationally hard to invert for some definition of that.

For values of $k$ starting at bout $2000$, we can use the assumed hardness of the Discrete Logarithm Problem (RSA also works if we trust a party to generate and publish an appropriate public key, and destroy any clue that could lead to factorization of the modulus).

For example, with the DLP, we find the smallest prime $p$ at least $\sqrt[3]{9}\,2^k$ such that $q=(p-1)/2$ is also prime, find the smallest $g$ at least $p/\pi$ such that $g^q\bmod p=1$, and define function $F$ over the set $\{1,2\dots q\}$ as $F(x)=\min\big(g^x\bmod p,p-(g^x\bmod p)\big)$. As far as we know, $F$ is an OWP over that set. We then use cycling to reduce $F$ to a permutation $P$ of $\{0,1\}^k$: we convert the input bitsring to integer, add one, apply $F$ and iterate (on average $\sqrt[3]{9}/2\approx1.04$ times) until the result is at most $2^k$, subtract one, convert back to bitstring.

Addition: I'll cowardly let the answer state its security claim. Informally, I'd be happy with a vague argument that more than $\min(2^n,2^{128})$ cycles of classical CPU are required for anything that should require more than $2^n$ evaluations in the forward direction, like finding a bitstring $x$ with the first $n$ bits of $P(x)$ all-zero (or other arbitrary $n$-bit value defined independently of the definition of $P$).

Motivation: I read that OWPs are more useful than OWFs. I wonder if that matters in practice. I reason that if we can't get $k$ down to say 256, we could as well use as a practical equivalent of a OWP a hash of $k$ bit (and same input size); it's most likely not a OWP, but it can't be computationally distinguished from that if the hash is secure.


texts: Exponential cipher theory misunderstanding

texts:
Say I pick modulus $m=2633$ and key $e=13$

My private key $d$ is $13$ inverse in $\bmod 2632$ which I need to compute

$(e,m)$ is my public key that anyone can use to encrypt message for me and then send it to me as:

encrypt message: "TH" ($T=19, H=07$) as $1907^{13} \bmod 2633$

but since $(e,m)$ is public anyone can compute my private $d$ using EEA

so where is the security? I know I do not understand this, could anyone explain?


texts:
I need to encrypt blocks of 16KiB with AES256. I have only one requirement to satisfy - If one day a hacker gets the data without the keys, he will not be able to decipher the data.

According to the design:

Each block will have a different random key
Blocks are differ from each other

Due to a space problem, i'm planning to use no salt and no IV.

Given 1 + 2, is it still safe to waive the salt and the IV?
Which mode should i use?

Thanks


texts: How to encrypt this using caesar cipher?

texts:
I recently had an exercise that read:

  Encrypt the message "easy question" using Caesar Cipher defined as:
  C=E(P)=(Pi+3) mod 26

What is this formula and how to solve it?


texts:
Good morning,

I state that I am not an expert in cryptography.

I'm studying the feasibility of a project which looks like requires a kind of cryptographic counter that behave similarly to the one in Katz-Myers-Ostrovsky2001 https://link.springer.com/chapter/10.1007/3-540-44987-6_6 but with a fundamental difference that I'm going to explain.

A brief contextualization.

The counter is embedded in a message m_0 generated at sender s_0 moving along a sequence of edges of a graph and it effectively contains the distance d from the sender (but this can alternatively be a TTL decrementing to zero).

At each node, d less than d_max is checked to let the node s_i decide if further propagate the message. If true, d is incremented by 1 and something not important for the question is computed on the payload, then the message m_i forwarded to s_i+1.

If d=d_max (or alternatively if TTL=0) a reply message is sent back to the original sender s_0.

The message is the first message going around the graph, imagine it like a proximity flooding/exploration. No information (keys or shared secrets) is shared between any node before nor using any means other than this message, except between two adjacent nodes but strictly limited to information about nodes involved in that the specific edge.

I noticed an approach based on timing like in Bojja-Fanti-Viswanath2017 https://arxiv.org/pdf/1701.04439.pdf but this cannot work in my case.

The fundamental difference.

A requisite of the project is bitwise unlinkability between message m_i and any messages:

m_i-k with k>=2
m_i+k with k>=2

the consequence is that I can not transmit the same pk0 along the message to be used in the transition algorithm, nor I can send sk0 to the end node and this invalidates the approach of the first paper.

How to count distance in a hidden but verifiable way?

I haven't found anything googling so I'm trying asking as last resort, at least to find a direction to move forward. Can be likely that I have missed a different common approach to solve the issue.


texts:
I have a question about multiplication of two points belong to elliptic curve. I know every think about adding and scalar multiplication but not about multiplication of two points. Is there any method for this?

The reason that I need this is that in paper "Attributed-based encryption for fine-grained access control of encrypted data", we need choose group G and then a point g as the generator of this group. Then in setup algorithm, we should calculate g to the power of t1, while t1 is a number. So it means that we should multiply g into itself for t1 times. If we choose an elliptic field, how could we do this multiplication?

Thanks


texts: Encrypting a 64-bit binary number to a text containing upper- and lowercase, and digits

texts:
I am making a tool that generates 16 character long password out of a 64-bit binary number. But I dont know how to make an encryption key for that, or where I can find one.

To show what i mean, here is an example with 8 bits:

I have the binary number: 10110111

The output could than look something like this:

t6Yli12q

And I want the password that gets generated from this: 10010000, to be completely differnt than the password that gets generated from this: 10010001.

Can anyone help me with this, or maybe redirect me to a site that says something about these types of encryption?

Note: I am very new to cryptography, so this might be simple for most of you, or maybe harder than I think.


texts: Is the product of two primes only factorisable by those two primes?

texts: The question is as per the subject line. Does the fundamental theorem of arithmetic imply (prove?) that if I multiply two primes, then those two primes are the only factors of the product? I.e. 17 x 23 = 391 and the only factors of 391 are 17 and 23. I have searched, but can't find an answer to this precise question.


texts: chacha20-poly1305 padding and length encoding

texts:
The AEAD construction for chacha20-poly1305 described in the IETF proposal encodes message lengths into the text that is to be hashed. The newer proposal goes further and pads associated data and plaintext to multiples of 16 bytes.

Can anyone explain what the purpose of that is? The chacha20-poly1305 implementation found in OpenSSH doesn't do anything like that, and as far as I can see, neither does NaCl. Those are still considered secure so I wonder what's going on.


texts: Explanation of the EPC Gen2 randomness standard's first rule

texts:
When we read PRNG requirements of the EPC standard, first rule (page 57 in this link) in the documentation;

  Probability of a single RN16: The probability that any RN16 drawn from
  the RNG has value RN16 = j, for any j, shall be bounded by 0.8/2^16 <
  P(RN16 = j) < 1.25/2^16.

Does that mean if the PRNG generates 2^16 16-bit numbers, each number should occur once? Basically it wants a perfect 16-bit entropy.

But if it is this way, even C#'s cryptographically secure PRNG cannot meet that requirement. So I'm wondering that I interpreted this requirement right.


texts: About ORAM initalization and running out of space

texts:
I have two questions about ORAM

Since at the beginning,the server allocates unused storage for ORAM cient,there are no user's data in the storage.if now client access the storage the server will know that client is writing data except that the client read empty block to achieve oblivious.some paper mention that using a third trust party to initialize the ORAM. or just deem that the client itself have finish initilization and upload the storage to server. so how ORAM client initialize the storage?
All papers I read about ORAM scheme fixed the capacity at the begin of setup,that's not fitting into the real situation. since client's data will increase with time. Are there any scheme to increase ORAM storage with time while maintaining oblivious?


texts: Best way to derive a MAC key without a salt

texts:
It's best to use separate keys for encryption and the MAC.
Most implementations tend to derive a larger key and split it in two (e.g. scrypt with an output of 32 + 64 = 96).
Alternatively, you can generate one key and then use HKDF to generate a subkey for the MAC key.

How can you derive a MAC key using the encryption key without a salt? Or how can you derive a salt (for HKDF) given an encryption key and a nonce?
I know you can use HKDF without a salt but a) that's not as strong and b) I want the MAC key to be unique despite the same encryption key.
Lets say I want the user to only pass in an encryption key and a random or counter nonce.


texts: Non-interactive zero-knowledge proof system for a language undecidable in polynomial time

texts:
I am studying through some material in an online course, and there is an exercise which I could not figure out. The problem is this:
Let $L$ be a language that is not decidable in polynomial time (that is, there is no efficient (possibly probabilistic) algorithm that on input $x$ outputs 1 if $x \in L$ and 0 otherwise). Show that there is no non-interactive zero knowledge proof system for $L$. That is, show that if a language $L$ has a proof system that consists of a single message from the prover to the verifier then $L$ is decidable by a polynomial-time algorithm.
Then there is a second part to the question which is worded the same, except it asks you to show there is no deterministic zero-knowledge proof system for $L$.
I was thinking that I could do a proof by contradiction, where I assume that there is such a proof system and then use the zero-knowledge property of that system to show there exists an efficient algorithm which simulates the single message from the prover to the verifier. And then you can use this simulation of the message in order to output 1 if $x \in L$ with probability 1, and output 0 if $x \not \in L$ with probability at least $1-negl(n)$. Finally, in order to make this probability large enough that we are satisfied, we can sequentially repeat the simulation as many times as needed.
Now, I'm not really sure if what I have thought up makes any sense, so please feel free to tell me if it does not! And I am not sure at all how to adapt this idea to the second part of the problem, assuming that what I have come up with resembles a solution to part one. Any suggestions would be greatly appreciated, thank you :)


texts: When does multiple OTP encryption become insecure if new keys are permuted?

texts:
I understand that OTP encryption fulfils perfect secrecy, meaning you can't decrypt the encrypted text to it's original plaintext (and know that this plaintext is indeed the original plaintext) unless you possess the OTP key.

Let's assume this:

Alice creates a truly random alphabetical stream of 10 characters (key).
The key is shared with Bob (we assume that it's secure and no one else can get knowledge of the key)
Now Alice can encrypt a text with length $\le$ key-length
Encrypted text is sent to Bob
Bob can decrypt the encrypted text with the key

Now the "new" part:

Alice again wants to sent a message to Bob by using OTP-encryption. But instead of creating a completely new truly random OTP key, Alice permutes the previously used OTP key. This permuted key is then used for further OTP encryption/decryption. The permuted key is checked with previous keys to ensure that no encryption happens with an identical key.

We assume that Bob always receives the new (permuted) key over a secure channel and no one else (ever) knows the key. We also assume that no one else knows any plaintext messages before/after encryption/decryption.

Example of keys:

$k_1 = \text{gubapqrytt}$ (truly random)

$k_2 = \text{permute}(k_1) = \text{ptyaqgtbur}$

$k_3 = \text{permute}(k_2) = \ldots$

Does this affect the security of OTP?
When is the first message vulnerable to decryption by an adversary?
Do all further keys (if none get leaked) still provide perfect secrecy?

EDIT:

We assume that all keys are kept secret and no keys will be leaked (no matter how unrealistic this might seem). I'm only concerned if this scheme would somehow be vulnerable to any known attacks, like frequency-analysis, since the key has always the same characters.


texts: Given $g,g^t$ in an RSA group modulo $N=pq$, is it hard to compute $g^{t^{-1}}$?

texts:
Suppose we have an RSA groug $G=\mathbb{Z}^{*}_{N}$, where $N=pq$ , where $p,q$ are primes. Let $g$ be a random element of $G$ and $t\in \mathbb{Z}^{*}_{N}$. Having $g$ and $g^t$, it seems to be very hard to find $g^{t^{-1}}$, supposing discrete logarithm problem (DLP) is hard. My question is that is this really hard?

In a prime order group, let's say in $\mathbb{Z}^{*}_p$ , $g^{t^{-1}}$ = $g^{p-2}$ : here we don`t have to face DLP, so finding $g^{t^{-1}}$ is easy.


texts: How to handle IKEv1 and IKEv2 diffie-hellman shared secret bits length not multiple of 8?

texts:
In Cryptographic Algorithm Validation Program for KDF document, here, page 9, it says "If a field size that is not a multiple of 8 bits, the shared secret is represented by a string of bytes that is padded with zeros on the left".
However, I get a valid input like this,
dhLength=4348
g^xy=ED6DAAE... (Total contains 1088 characters in hex, so 544 bytes, so 4352 bits)
where dhLength < length of g^xy, how to handle this situation, also g^xy is not started with padding 0. I tried to cut, pad 0 to extra long, erase 'E' to '0', results are all wrong.


texts: How can I find two strings $m_1$ and $m_2$, knowing that I know $m_1 \oplus m_2$?

texts:
Possible Duplicate:
  How does one attack a two-time pad (i.e. one time pad with key reuse)?

I recently started to follow the cryptography class of Dan Boneh on coursera.org and the first part is talking about stream ciphers.

In general, we have an encryption which works as follows:

$$c = E(k,m) = m \oplus k$$

and $$D(k,c)=c \oplus k = m \oplus k \oplus k = m \oplus 0 =m $$

Where $k$ is the key $m$ is the message and $c$ is the cypher.

For this method, the key should be used only once. Assuming the same $k$ is used twice to produce both $c_1=E(k,m_1)$ and $c_2=E(k,m_2)$, then we could do

$$c_1 \oplus c_2 = m_1 \oplus k \oplus m_2 \oplus k=m_1 \oplus \underbrace{k \oplus k}_0 \oplus m_2 = m_1 \oplus m_2 $$

Now the class claims that is messages are in English and encoded ASCII, knowing $m_1 \oplus m_2$ is sufficient to get $m_1$ and $m_2$. However, I have no idea how this is possible.

Can somebody help me out our provide me with a good book/resource where I could find the method?


texts: Size and usage of lookup table in cryptographic schemes

texts:
I would like to understand the typical size of a lookup table for software implementations of a cryptographic scheme.

What size is considered reasonable?
What make them (in)efficient?
Are there heuristics to determine (without implementing anything) if a table will become interesting?


texts: Multiplication encryption with a small number

texts:
Given a big number $x$(1024 bits) and a large prime $N$($N>x$), I want to encrypt it with a smaller number $y$(128 bits).
$$Enc(x) = xy \mod{N}.$$
Is it safe? If not, how do I evaluate its leakage?


texts: Implementing key mapping across different elliptic curves

texts:
From this answer I understood how to prove key equivalence across two elliptic curves. Now, I'm trying to figure out some more practical aspects of implementing this. Before jumping into questions, here is the setup:

The two elliptic curves are $g_1$ and $g_2$ of orders $q_1$ and $q_2$ such that $q_1 < q_2$. The generator points are $G_1$ and $G_2$.
I have a secret value $a$ which is a 256-bit integer (it would probably need to be smaller than $q_1$).
I calculate points $A_1 = a ⋅ G_1$ and $A_2 = a ⋅ G_2$

I would like to prove to someone that $A_1$ and $A_2$ map to the same number without revealing the value of $a$. To do this, I can:

Chose a random integer $r$ and calculate $T_1 = r ⋅ G_1$, $T_2 = r ⋅ G_2$, $u = H(G_1, G_2, A_1, A_2, T_1, T_2)$, and $v = r + a ⋅ u$, where $H$ is a hash function
Share the proof as $(A_1, A_2, T_1, T_2, v)$

The verifier can check the proof by computing $u$ and checking that $v ⋅ G_1 = T_1 + u ⋅ A_1$ and $v ⋅ G_2 = T_2 + u ⋅ A_2$.

My questions are:

How would I go about selecting the two elliptic curves? For example, one choice could be Curve25519 and Curve1174, but that would restrict the value of $a$ to approximately 248 bits. Another choice could be secp256k1 and secp256r1 and that should allow values of $a$ to be 255 bits (and it seems like the orders of these curves are also much closer together). Are there any other considerations?
How would I go about choosing the hash function $H$? For example, if the curves are secp256k1 and secp256r1, could I use Blake2b with 255-bit output to generate the value of $u$? Could I make the output smaller (e.g. 200 bits) and if so, what would be the downside of that?
If the curve orders are really close to each other (like they are for secp256k1 and secp256r1), could I restrict $r$ to 255-bit values? Or should I keep it at 512 bits? It seems to me that to hide $a$ effectively $r$ needs to be much bigger than $u$.


texts: What is largest prime factor in Diffie-Hellman?

texts:
I was reading the paper of A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by TAHER ELGAMAL to better understand ElGamal public-key scheme, and he stated that for any cryptosystem based on discrete logarithm problem, the prime $p$ should be chosen such that $p-1$ has at least one large prime factor.

My question is the following: how to determine if the largest prime factor of $p-1$ is in fact large?


texts: What are the major differences between SET and SSL?

texts: SET and SSL are usually used as secure payment protocols. What are the major differences between them? Which one is better?


texts: Trying to understand the use of ECC in TLS certificates

texts:
I was looking the certificate of this website: https://www.cloudflare.com that has an ECC based certification.

I'm just curious to know if is possible to understand which elliptic curve is used and which point is used.

Another thing: I don't understand why in the certificate there is a RSA 2048 public key and not an ECC key.


texts: How are random numbers for RSA generated?

texts:
The RSA public key encryption requires two very large prime numbers as part of its encryption process that serve as secrets. These are typically generated with cryptographically secure random number generators of some kind.

However, random number generators generate random bits; they don't specifically generate primes; and proving that a number is prime would require attempting to factor it -- the very problem that makes RSA hard.

How are the prime numbers found for use in RSA?


texts: zkSNARK and definition of Quadratic Span Program

texts: In zkSNARKs in a Nutshell, page 12, what exactly are $I_{free}$ and $V_{free}$? Why do we have $V_{free}$ but not $W_{free}$?


texts: Oblivious Polynomial Evaluation and Encoding Payload

texts:
I am trying to parse this paper. I think I do come to understand the general concepts go into this type of Private Set Intersection, based on Oblivious Polynomial Evaluation. I was able to produce a workable prototype based, with just the straight forward exponential El Gamal encryption.

The point-by-point of the protocol can be found in the section 4.2 PM Semi-Honest Protocol. What struck me that single remark in the step 2. where it says

  ... (One can also encrypt some additional payload data py by computing Enc(rP(y) + (y|py)). C obtains py iff y is in the intersection.)

I got quiet excited because that's what I was looking for, but the symbol '|' doesn't get explained and I couldn't find what is it supposed to be. Given that the idea is that in the case of a root P(y) evaluates to 0, and so ENC(rP(y) + y) = ENC(y). This means that anything I do with the added 'y' value will stop C (the client) to find the matching values with her own private set.

Is this some special property of the Paillier encryption I don't know about (I don't know this crypto-system very well yet), or is it something I can make work with using the exponential El Gamal encryption system?


texts: Proving/disproving a scheme's EAV-security using definitions

texts:
I have seen the equivalent definitions of an EAV-secure encryption scheme in Katz & Lindell, and now I am asked to show if certain encryption schemes are EAV-secure through a proof by reduction or creating a PPT-adversary violating the definition.
Suppose $\Pi = (Gen, Enc, Dec)$ is EAV-secure, ($Gen(1^n)$ returns a uniformly random n-bit string, that is, a key in this case). Defining $Enc'(k,m):=Enc(0^{|k|},m)$, that is, the encryption algorithm that always encrypts using only the key $0^{|k|}$. Is $\Pi'=(Gen,Enc',Dec')$ also EAV-secure?
One of the equivalent definitions of EAV-security states that no adversary can determine which of two messages, say $m_0, m_1$, that was encrypted, using a key $\tilde{k}\in \mathcal{K}$. This should hold for $\textit{any}$ such key $\tilde{k}$, even for $0^{|k|}$. But it does not seem to me that a scheme should work fine when using just the same key every single time. How does one go about proving/disproving the security in this case?


texts: Security model for privacy-preserving aggregation scheme.

texts:
Suppose that $S=(E,D)$ is an additively homomorphic encryption scheme. Now I want to design a protocol $P$ such that given inputs $x_1,x_2,..,x_n$, the adversary $A$ (who can decrypt) can only learn $\sum x_i$ and nothing else. To do that, $P$ first generates random values $r_1, r_2,..,r_n$ such that $\sum r_i = 0$. Then, $E(x_1+r_1)\times..\times E(x_n+r_n) = E(\sum x_i)$.

The trouble I have is when adversary has some domain knowledge of $x_i$. For example, if it knows that $x_i \geq 0$, and later decrypts $E(\sum x_i)$ to learn that $\sum x_i = 0$, it can learn that $x_i = 0$ for all $i$.

How could I formulate a security game that takes into account such attacks based on domain/auxiliary knowledge? Would IND-CPA security model be sufficient? How's about IND-CCA?

I've read the paper [1], but I don't think it addresses the domain/auxiliary knowledge.

[1] Shi et al. Privacy-preserving aggregation of Time-series Data (NDSS'11)


texts:
I understand that BEAST is a CPA using javascript injected onto the browser's webpage. Apparently the thing that BEAST exploits is the fact that the IVs are predictable. What I'm confused about is why this is a problem when IVs are public anyway?

i'm looking at the first answer here:
How can Cipher Block Chaining (CBC) in SSL be attacked? Aren't $IV_1$ and $IV_2$ public in TLS 1.2 as well? So why isn't BEAST allowed there? Is it because, when the malicious javascript encrypts messages for you, it uses a new, random IV each time (but not in TLS 1.0 or lower)? But doesn't this mean that BEAST will only verify you guessed a message correctly with quite low probability, and you only get one attempt for each message (because the IV keeps changing, even though it's predictable)?


texts: Why do we add error in the definition of LWE?

texts:
One of the various equivalent definitions of the LWE problem is the following:
Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (usually a discrete Gaussian distribution) and $s$ a secret vector from $\mathbb{Z}_q^n$.
We denote $\mathcal{L}_{s,\chi}$ the probability distribution over $\mathbb{Z}_q^n \times \mathbb{Z}_q$ obtained by choosing $a \in \mathbb{Z}_q^n$ uniformly at random, choosing $e$ uniformly at random from $\chi$ and considering it in $\mathbb{Z}_q$, and calculating $(a,b=(\langle a,s\rangle + e)) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.
The Search Learning With Errors is to recover $s$ from samples $(a,b)$ obtained from $\mathcal{L}_{s,\chi}$.
My questions is why do we add the error $e$? I suppose that it is for security reasons. In that case, how we would be able to obtain $s$ from $(a,b=(\langle a,s\rangle))$?
Since adding some error $e$ is a central block in a lot of lattice-based constructions, this could be a more general question. What is the point of adding this error?


texts:
In trying to understand this specific part of the RSA algorithm, I found this online:

  $$e \cdot d = 1 \pmod{(p-1)\cdot(q-1)}$$
  Therefore:
  $$e \cdot d \cdot d^{-1}= d^{-1} \cdot 1 \pmod{(p-1)\cdot(q-1)}$$

  Substituing in $d^{\phi((p-1)\cdot(q-1))} \mod{((p-1)\cdot(q-1))}\ $  for $1 \pmod{(p-1)\cdot(q-1)}$, we get:
  $$e\cdot1 = d^{\phi((p-1)\cdot(q-1))-1} \mod{(p-1)\cdot(q-1)}$$

I understand by Euler's theorem, that $d^{\phi(n)}$ = 1 mod $n$

What I don't understand is the substitution part.  Most descriptions I've found online either gloss over this part of RSA or go into Extended Euclidean Algorithm.  But this method seems to be the easiest way of calculating since it ends up just being modular math.

If I substitute, wouldn't that just leave me with...

$$e = d^{-1} \times d^{\phi(n)} = d^{\phi(n)-1}$$

without the mod part.


texts: Prefix property for variable length pseudo-random generators

texts:
I'm currently working through Katz & Lindell's Introduction to Modern Cryptography. In section 3.4.2, they introduce the definition of a variable output-length pseudorandom generator $G$. The definition of $G(s,1^l)$ is such that the output is of length $l$.

Using such a psuedo-random generator, they define a variable-length encryption scheme (here, called $\pi_{VarPRG}$) in the natural manner for variable length messages:

  Encryption: $Enc:\mathcal{K}\times\mathcal{M}\to\mathcal{C}$ where $C=Enc(K,M)=G(K,1^{|M|})\oplus M$

  Decryption: Inverse of encryption for the ciphertext length $|C|$.

However, they go on to include the side-condition:

  For all $s$, $l$, $l'$ with $l<l'$, the string $G(s,1^l)$ is a prefix of $G(s,1^{l'})$.

They claim this is a "technicality" of proving indistinguishable encryptions in the presence of an eavesdropper for the variable length encryption scheme defined above. After staring at this for the best part of an hour, I am not fully understanding where this subtlety comes into the proof. (It is, after all, a subtlety.)

My first attempt to gain some insight into the problem:

In the proof of $PrivK^{eav}_{\mathcal{A},\pi_{VarPRG}}(l)$ for the encryption scheme shown above, we suppose $G$ is a secure pseudo-random generator and then suppose, for contradiction, that $\pi_{VarPRG}$ is not secure in the presence of an eavesdropper. In other words, there exists some adversary $\mathcal{A}$ for which

$Pr(PrivK^{eav}_{\mathcal{A},\pi}(l)=1)\not\leq \frac{1}{2} + negl(l)$

We proceed by using the adversary $\mathcal{A}$ to build a (probabilistic, polynomial-time) distinguisher $\mathcal{D}$ for the variable output-length PRG $G$, and show that this contradicts the assumed pseudo-randomness of $G$.

All well so far. The adversary $\mathcal{A}$ will, when invoked, output two messages $m_0$ and $m_1$, which one assumes can be different lengths ($|m_0|\not=|m_1|$). At this point, I get stuck:

Where does the subtlety, noted above with regard to the prefix property of $G$ for $1^l<1^{l'}$, come into this?


texts: Security proof of partially blind signature (schnorr signature based)

texts:
I read a representative paper about partially blind signature.

Abe and Okamoto - "provably secure partially blind signature".

They suggested a partially blind signature scheme based on Schnorr signature.

In the security proof section, they proved that the scheme is secure against adaptive chosen message attack using ID reduction scheme.

They assume a single-info adversary, $U^{*}$ that violates unforgeability for infinitely many sizes.

And the machine ${M}$ is constructed by a forger ${U^*}$.

Firstly, ${M}$ select $b$ (0 or 1, randomly) and assigns $(y, z)=(g^{x}, z_{0}g^{\gamma})$ if $b=0$, or $(y, z)=(z_{0}g^{\gamma}, g^{w})$ if $b=1$.

$\gamma, x$ (or $w$) is chosend randomly.

Random oracle $F$ is defined so that it returns appropriate value of $z$ according to above selection.

Let's assume that $b=0$.

If $U^{*}$ is successful with probability at least $\eta$, then the author says we can find a random tape string for $U^{*}$ with probability at least 1/2 such that $U^{*}$ succeeds with probability $\eta/2$.

I cannot understand what 'finding a random tape' means.

Does it mean finding $\gamma$ and $x$?

Why is it 1/2 and $\eta/2$ ?

Below is a capture of the paper.

Thanks.


texts:
Are there any known good methods of performing authentication over the phone in a way that's not susceptible to replay attacks?

The specific scenario that comes to mind is having an automated call centre which verifies the identity through one or more questions. Since the phone line is not guaranteed to be secure (or the user may simply be in public), the calls can be eavesdropped.

One idea that came to mind would be something akin to CHAP - the user hears a challenge, mentally hashes it (per this CryptoSE Q&A, perhaps Blum's hash is a good candidate) and then speaks the solution out loud. Has something like this been attempted before and are there any known vulnerabilities?


texts: How fast can a wrong decryption key be detected using ECC?

texts: When can a decryption function detect that the ECC key I use for decryption is incorrect? Is it possible to do that during initialization, or does the complete message have to be decrypted to do that?


texts:
libsodium has a method for comparing two byte sequences in constant time.

Is the idea here to simply avoid early-out if a difference in the data is detected?

When I first heard of such a thing I imagined an operating-system sleep operation to round-up the runtime of the algorithm to some threshold, but this sounds very inefficient.


texts: Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

texts:
I am struggling to prove this claim:

I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that the elliptic curve $E:y^2=x^3+1$ over $\mathbb{F}_p$ contains precisely $p+1$ points.

I don't understand how many points will be on the curve. For each value of $x\in\{0,1,2,\ldots,p-1\}$ we will get a distinct result after computing $x^3+1$. But how does that tell me how many points will be on the curve?

For each point it can be paired with either two or zero $y$ values, right? But I don't know how many squares there are that are less than $p$.

I ask either for help explaining this, or ideally resources I could use to understand the theory behind this so that I can solve it myself.


texts: Achieving non-linearity in a block cipher using only, rotations, shifts, AND, OR, and XOR

texts:
It is supposedly difficult to introduce enough non-linearity in block ciphers based on modular addition, data-independent bitwise rotations, and XOR to make them secure against certain kinds of cryptanalysis even though addition is used because it introduces non-linearity into the design that XOR does not have. But what if we also use bitwise AND, bitwise OR, and bitwise shifts (a left bitwise shift fills a fixed-length bit string with zeroes on its left-hand side)? And let's toss modular addition into the flames since that actually does not run in constant time on some processors.

I figure that bitwise AND and bitwise OR can be used to introduce more non-linearity than modular addition. Additionally, though I'm not familiar with the details rotational cryptanalysis, I figured that bitwise shifts can help to thwart it since the for some inputs, the outputs of a function using rotations might be made equal with a rotation applied to one of them. Bitwise shifts would not suffer from this problem. As an example, consider that for inputs $x_0 = 0101$ and $x_1 = 1010$ the function $f(x) = (x \ggg 1) \oplus x$ will return $111$ in both instances. But, if $f(x) = (x \gg 1) \oplus x$, then the outputs will be $0111$ and $1111$, respectively.


texts:
I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're sets of the form $GF(p^n)$ for $n\geq1$ where $p$ is prime and $n$ is an integer. From what I can tell, they're defined as the following:

$GF(p^n) = [f(0) \bmod p, f(1) \bmod p, \dotsc, f(p^n-1) \bmod p,  f(p^n) \bmod p]$

for $f(x) = \sum_{i=0}^{n} \space x^ik_i$, i.e. an $n$-order polynomial with constants $K$.

I've seen mention that these fields are bijective, such that for an input set $A$ there is an output set $B$ containing the same values as $A$, but in a different order.

Is this correct? Does this have applications for creating s-boxes?

Update:
Thanks for the answers so far. I now understand that $GF(p^n)$ is an array of size-$n$ vectors, each element of which is computed as the result of some polynomial mod $p$, but I'm still not clear on the rest of it. I mostly understand how vector manipulation can be done on such a field, but I'm still non the wiser as to how I would use such a finite field, let alone impliment them in code. I don't really understand what $GF(p^n)$ looks like in terms of construction, which I guess is what I'm really looking for. If it's an array of vectors, each element of which is computed by some polynomial, how is the input to that polynomial decided? Is $GF$ a function, into which you provide such a value? Is the input value an integer, a vector, etc? If so, what's the meaning of the input value? How does the index of the vector in the set factor into the computation of its values?

For example:

$GF(p^n)[i] = \begin{bmatrix} v_0\\v_1\\v_2\\...\\v_{n-1} \end{bmatrix}$

Where $i$ is some index into the field, how are the vector elements $V$ computed? What inputs are provided?


texts:
To know, if D traces back to A by comparing two hashes on D and A, but also know that D and E are separate branches.

                     D
                    /
            C ----->
           /        \
A ----- > B          E

I think they would need to be in a order or need some information about the time in it.

Can we prove that an element in a fractal tree traces back to a certain point?


texts: What is a wide block cipher and why does it avoid birthday bound problems?

texts:
I've recently heard the claim that wide block ciphers avoid birthday bound problems. Trying to figure out what exactly "wide block encryption" is, a quick search turned up this paper which is trying to do the following:

  The focus of this paper is how to use a standard block cipher as a component
  to build a ”wide” block cipher, or, in other words, to build a secure PRP from
  another PRP operating on a smaller domain.

Also stating that

  The size of the wide block cipher is l=n∗m bits.

It specifically mentions IEEE P1619-2 (Wikipedia). But that standard seems to be paywalled. From the description on Wikipedia it sounds like it is related to disk encryption but that is not a real definition. It might just be a block cipher with a bigger block size but that seems pretty vague.

Could somebody please tell me what a wide block cipher is and why it avoids the birthday bound?


texts: Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate?

texts:
In the context of zk-SNARKS, we are given an arithmetic circuit $C$, public outputs $y_1, \ldots, y_n = \mathbf{y}$ and some public inputs $x_1, \ldots, x_ℓ$. The prover wants to prove knowledge of some extra secret inputs $s_1, \ldots, s_m$ such that if one were to evaluate the circuit $C$ on inputs $x_1…,x_ℓ,s_1,…,s_m$ the result would be $\mathbf{y}$.

In some application like in HALO, the recursion property depends on the size of the arithmetic circuit being evaluated. However it does not seem to be related to the security of the scheme, fixed at roughly 128bits. If so, given a certain security level $\lambda$, can one create a zk-SNARK with any circuit size? (granted that the circuit does verify the "valid assignments" we want provers to have)


texts: Reuse nonce with Salsa20 stream cipher with counter

texts:
It is often said to never use a nonce for more than one message when using a stream cipher. It seems this is to prevent something like this:
Taking advantage of one-time pad key reuse?
Yet what if I keep the same nonce, but increment the block counter depending on the amout of blocks exchanged so far? This should be the same thing as turning the whole exchange into one long message, thus not needing more than one IV.
By exchange I mean two people sending each other stuff.


texts: Safety when disclosing hashes of secrets used to calculate other secrets

texts:
In my application, I am generating a big random number and publishing a SHA256 hash of it. After the hash it published (but not the secret), anyone can submit any number, and the system will calculate and present them a SHA256 hash of the number derived by concatenating their number at the end of the secret number from my system (SHA256(A+B)). The result of that operation should not be guessable without the secret number.

I am wondering if there are any security concerns with this approach that I should be weary about, such as if the random number is of certain length, would that make the result guessable? Or is this approach cryptographically safe?


texts: How to generate a distributed private key?

texts:
Shamir's Secret Sharing scheme is really interesting but the pain point is that the secret is generated by one trusted party, then the shares are distributed to other peoples.

Is there any scheme using distributed key generation in order to:

Generate a public key using multiple private keys

Generate a private key using a threshold of shared private keys

The private key is generated in a distributed way

I learned about DKG ( https://github.com/dfinity/dkg/blob/master/example.js )


texts:
I am trying to understand the non-optimized known plaintext attack on A5/2 from Barkan, Bikan and Keller.

I don't understand the construction of the equation system:
$$S_{R4_1} * S_1 = k$$

Where $S$ is the system's matrix and $k=k_1||k_2||k_3||k_4$.

How do I create the system's matrix $S_{R4_1}$ and $S_1$?


texts: What would be a typical value for the security parameter of the Fully Homomorphic Encryption over the Integers scheme?

texts:
The parameters of the Fully Homomorphic Encryption scheme by Dijk et.al are chosen according to the value of the security parameter ${\lambda}$, section 3 of the aforementioned article.

What is the security parameter for this scheme ? It represents the bits of security the scheme has ? If so, what would be a secure value right now ?


texts: Generate RSA-2048 private key for a VERY fast decryption (don't care if it will be unsecure)

texts:
Given public standard RSA exponent e = 65537,
is there any (d, n) pairs so that RSA decryption becomes a trivial operation?

The modulus n must be no less than 2048-bit. The goal is to get a real certificate for some internal server that must send same data both via http and https. Certificate authorities will check modulus length. But some of them can possibly accept other e values so it can be a viable option too.

Note: security is not a factor at all, only simplicity\speed matters (trivial complexity will be an ideal).


texts: I am learning about ElGamal signature verification. During the signature generation one has to choose a k such that 1 < k < p − 1 and gcd(k, p − 1) = 1. I am using the notation from the Wikipedia site. Later it is used the inverse of k. I assume this is a modular inverse. Learning materials I have found does not state whether this is a modular inverse regarding p or p-1. Can somebody clarify this?


texts: Are the following schemes based on a pseudo-random permutation secure?

texts:
I am currently working on the following task:

Let F be a pseudorandom permutation.

Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses two random keys $k_1 , k_2  \in \{0, 1\}^n$. Encryption is done as $Enc_{k_1,k_2}(m) = F_{k1}( k_2 \oplus m)$  (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

Consider the encryption scheme where the message space is $\{0, 1\}^{n/2}$ and encryption of a message $m$ is done by choosing random $r \leftarrow \{0, 1\}^{n/2}$ , and then outputting the ciphertext $F_k(r ||m)$. (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

My current answers are:

This scheme has indistinguishable encryptions in the presence of an eavesdropper since $F$ is a PRP, and therefore $F_{k1}( k_2 \oplus m)$ will give a pseudorandom string. However I am not sure whether my intuition is correct.
The scheme should not be IND-CPA secure since encryption is deterministic.

This scheme is both IND-COA as well as IND-CPA secure. IND-COA since (as in 1.) $F$ is a PRP, and therefore $F_k(r ||m)$ will give a pseudorandom string. It's also IND-CPA secure as a random $r$ is used every time a message in encrypted.

Since I am not too confident about my solutions I appreciate any comments and/or corrections.


texts: How many unique elements are generated by a variation on the equation in DSA for r?

texts:
How many unique elements are generated from the following equation?

$$i = (g^x \bmod p) \bmod n $$

where:

$g$ has order $q$
$q$ and $p$ are prime numbers
$q\mathop{|}p-1$
$n$ is integer number more than 2 (could be even or odd number)

In part $g^x \bmod p$, it will generate $q$ unique numbers. But I am getting confused when the value is modulus-ed by $n$. Can someone help me?