filling array with rand numbers

[Malcolm McLean]

Eve? GCHQ? I have no idea what those refer to. Are they topical?

Alice and Bob are the people trying to communicate, and Eve is the eavesdropper, or enemy signals intelligence people wanting to know
what they are saying. GCHQ is our boys' eavesdropping centre, and also
the home of the electronic computer. (You can argue about whether the first
real computer was British or American, because of technicalities about the
memory, but the British version was first, and it was installed at what
became GCHQ).

High-quality encryption software is readily available, and it's easier
to use it than to roll your own low-quality encryption software.

The rand() based method is extremely easy to code. Maybe ten lines of C.

I suppose music "piracy" is one possible application of encryption, but
it's not what I had in mind.

There are lots of uses for encryption. Making automatic filtering and
monitoring too expensive to be practical is one of them.

 

[glen herrmannsfeldt]

(snip)

Depends on the identity of Eve. If you're a person of interest to GCHQ,
then you can be sure that a skilled programmer will be assigned
to your case, and pretty much the first thing he'll do is try
the standard Unix implementation of rand() with every seed.

Two men are walking through the woods and see a bear.
One start running. The other tells him he can't outrun the bear.
The first replies: "I don't have to outrun the bear, I only
have to outrun you!"

As for cryptography, you only have to do it well enough to
discourage those looking.

The usual rand() is probably good enough for card games, maybe
better than most people actually shuffle a deck.

-- glen

 

[osmium]

Can you really imagine someone spending more than a dozen years learning
C, and not having learned any more about it than Bill does? I have no
difficulty imagining that someone might have that much difficulty
learning C - I've met many people like that. What I find hard to imagine
that such a person would keep trying for so long despite their lack of
success.

Hell, I still don't understand magnetism. And I've been working on that
since I was six years old. How could I possibly understand a mind messed up
with chemicals? I took Paxil for a few days once, and it made me a believer
in the kind of thing that Bill has talked about.

I have always liked challenges and the older I get the longer my "do not
understand this" list gets. But I keep going bacl to the list. I see
something like that in Bill; but I have had better luck working on my list
that he
has had.

I also think programming is almost unique, having a seductive aura of
unleashed power. Also the instant gratification is rare in the things one
can actually do. And it's doable, you don't need a better lens, a bigger
planer, an electron microscope. Just you, your mind, and a cheap computer.

 

[Bill Cunningham]

Geoff wrote:

[snip]

His choice of key[] and txt[] for array names suggests some kind of
cryptographic experiment.

Yes. I placed r=rand(); into the for loop and it seems to work. The
encrypt() function and setkey() functions I would try next. The second
parameter of encrypt is 0 or 1 for decrypt or encrypt. 'man encrypt' on a
linux machine shows this. But encrypt is OT.

Bill

 

[Ike Naar]

This is decidedly not true if you are going to play card games FOR
REAL MONEY. You'll go broke quickly. Especially if it's over the
Internet where you can't stop gamblers from using computers. If
it's a game among friends for strip poker or pocket change stakes,
it's less of an issue. But watch out if one of the players seems
to spend as much time fiddling with his iPhone as he does with the
game, and keeps waiting for the phone before betting.

I'm pretty sure rand() (especially on a machine where unsigned is
16 bits) is not better than how most professional casino dealers
shuffle decks.

Burditt, please learn to quote.

 

[glen herrmannsfeldt]

This is decidedly not true if you are going to play card games FOR
REAL MONEY. You'll go broke quickly. Especially if it's over the
Internet where you can't stop gamblers from using computers. If
it's a game among friends for strip poker or pocket change stakes,
it's less of an issue. But watch out if one of the players seems
to spend as much time fiddling with his iPhone as he does with the
game, and keeps waiting for the phone before betting.

Yes, I meant people playing at home, and not for real money.
Even so, for a 32 or more bit rand() it would take some time
before you had enough data to figure it out. (Assume you have
the card sequence, but not the program source.)

I'm pretty sure rand() (especially on a machine where unsigned is
16 bits) is not better than how most professional casino dealers
shuffle decks.

Yes, again, I meant people playing at home with family or friends.
Most people are too lazy to shuffle enough times. Seems like one
could argue for at least log2(52) shuffle passes, maybe twice as
many as each isn't quite as good as one might hope. (And a perfect
shuffle will result in less randomness.)

-- glen

 

[BruceS]

Can you really imagine someone spending more than a dozen years learning
C, and not having learned any more about it than Bill does? I have no
difficulty imagining that someone might have that much difficulty
learning C - I've met many people like that. What I find hard to imagine
that such a person would keep trying for so long despite their lack of
success.

That's mostly what I see from Bill, but it goes further than that. He
seems to come up with questions that are extremely basic (and mostly not
really C issues), designed to get as many responses as possible. Some
of his posts also present him as doing things *far* beyond what other
posts would indicate was his capability. If he isn't trolling, he's
doing an admirable job of appearing to do so.

With all that said, sometimes a troll post has some value, in starting a
discussion that may help someone understand part of the language, or of
programming in general.

 

[Geoff]

Geoff wrote:

[snip]

His choice of key[] and txt[] for array names suggests some kind of
cryptographic experiment.

Yes. I placed r=rand(); into the for loop and it seems to work. The
encrypt() function and setkey() functions I would try next. The second
parameter of encrypt is 0 or 1 for decrypt or encrypt. 'man encrypt' on a
linux machine shows this. But encrypt is OT.

Use encrypt(text) and decrypt(msg) functions. There is no need to use
a single function named encrypt with two arguments to change it's
mode. This makes the interface more complex than it needs to be and
complicates the function. This kind of problem is good for
demonstrating the partitioning of the tasks into concise functions,
one of the first principles of C.

 

[Geoff]

Can you really imagine someone spending more than a dozen years learning
C, and not having learned any more about it than Bill does? I have no
difficulty imagining that someone might have that much difficulty
learning C - I've met many people like that. What I find hard to imagine
that such a person would keep trying for so long despite their lack of
success.

I don't believe Bill is a troll. I suspect he's a retired old
gentleman with nothing better to do with his time and an interest in
the topic and the challenge of programming. Whether he's medicated or
not is not for me to judge. Whether he learns or not is not my
responsibility nor do I feel obliged to reply to him or make him
learn. We all have our deficiencies and our strengths.

I also feel that anyone who feels he's a troll should ignore his posts
and simply behave like civil human beings and stop adding to the noise
in threads started by him. Those who troll the troll are trolls
themselves.

 

[glen herrmannsfeldt]

(snip)

That's mostly what I see from Bill, but it goes further than that. He
seems to come up with questions that are extremely basic (and mostly not
really C issues), designed to get as many responses as possible. Some
of his posts also present him as doing things *far* beyond what other
posts would indicate was his capability. If he isn't trolling, he's
doing an admirable job of appearing to do so.

I don't remember his other posts, and doing psychology in a C newsgroup
probably isn't a good idea, but maybe it is related to dyslexia.
Maybe he didn't realize that the assignment was outside the loop.

Or, maybe it isn't so obvious how C should work. While it seems
obvious that the assignment is done once when the statement is
outside the loop, maybe that isn't so obvious.

I was recently reading about how (at least one version of) ALGOL
allocates dynamic arrays. It seems that they are allocated when
first referenced, but to the size declared. In C99 terms:

double x[n];
n=10;
x[5]=5;

Now, it is obvious in C that can't work, as n is assigned after
the array is allocated, but it seems not so obvious in ALGOL.
(Then again, no-one would ever think of call-by-name in a
C context.)

With all that said, sometimes a troll post has some value, in starting a
discussion that may help someone understand part of the language, or of
programming in general.

-- glen

 

[Geoff]

Or, maybe it isn't so obvious how C should work. While it seems
obvious that the assignment is done once when the statement is
outside the loop, maybe that isn't so obvious.

It's a flaw in C that it permits the programmer to leave braces out of
loop statement bodies. This should have been a requirement from the
beginning since it now has to be defined as a best-practice. I imagine
Bill changed is program from

int main()
{
int i, r;
char key[64];
char txt[64] = { 0 };
srand(time(NULL));
r = rand();
for (i = 0; i < 64; i++)
key = r;
printf("%d%d\n", key[0], key[1]);
}

to

int main()
{
int i, r;
char key[64];
char txt[64] = { 0 };
srand(time(NULL));
for (i = 0; i < 64; i++)
r = rand();
key = r;
printf("%d%d\n", key[0], key[1]);
}

instead of

int main()
{
int i, r;
char key[64];
char txt[64] = { 0 };
srand(time(NULL));
for (i = 0; i < 64; i++)
{
r = rand();
key = r;
}
printf("%d%d\n", key[0], key[1]);
}

and as a result is as likely to misinterpret the garbage value of the
uninitialized members of key[] as his random values.

The problem with "teaching" in newsgroups is a simple one - it's
open-loop. You don't know whether what you are teaching is being
interpreted correctly without feedback.

This problem is compounded by topic drift and trolling and generalized
nit picking that's a direct result of people in the group who, on
occasion, seem to be occupied with proving how much smarter they are
or how extensive is their knowledge of minutiae. One former boss had a
name for this, he called it mental masturbation. In this newsgroup it
seems to be a group sport.

 

[Keith Thompson]

Burditt, please learn to quote.

He knows how; he just refuses to provide attributions, for reasons that
make no sense to me.

 

[osmium]

On Sun, 4 Aug 2013 23:00:22 -0700 (PDT), Malcolm McLean

42:13 -0700, Keith Thompson <[email protected]>


His choice of key[] and txt[] for array names suggests some kind of
cryptographic experiment.

It's possible to write a reasonable-strength encryption program with
srand(), rand and the exclusive or operator. But it's better to
implement
your own rand() to ensure portability.


Only for some extremely generous definitions of "reasonable"!

Almost all srand/rand implementations are LCGs, and have very small
seeds ("keys" - typically 32 bits), and brute forcing them is fairly
trivial. Even worse, LCG PRNGs have terrible cryptographic
properties, so brute forcing them is really doing it the hard way.
Usually simple frequency analysis will do the trick.

So that might keep your kid sister out of your diary, but no one else.

Let's focus on that brute force approach for a minute. One result is
atackatdawn another result is sueforpeace. Which result do you choose as
the proper "cracking" of the code? Or does brute force mean something
else?

Brute force in the context of encryption means trying all possible
keys to see which produces likely messages. For example, if you
intercepted a message encrypted with the described scheme sent between
two English speakers, you could simply try all 2**32 possible keys,
and filter out all of those keys that did not result in a large number
of the strings on contiguous characters match a list of the 10,000
most common English words.

Obviously a sufficiently long message is required to apply any
statistical technique.

If your key is actually as long or longer than the message (as it
would be in your example, where you have a single bit of message), you
have something along the lines of an OTP, which is provable secure.

If, OTOH, you're transmitted your one bit message with massive
redundancy, (say, by sending "attackatdawn" or "sueforpeace_" instead
of the single bit), and you have a short key, you again end up with a
very strong chance that the attacker can decode the message.

You misunderstood my question. There was not a one bit message. There were
enough bits in the encoded message to represent 12 characters. The computer
had a 15- bit byte and the native character code was 5-bit Baudot. A PRNG
generated a string of bits, a field of five bits were selected and XORed
against each plain text character. Many PRNG streams can be postulated and
they will produce many 12 character plain text messages. Postulate all
candidate PRNG streams (different constants and different seeds and
different five-bit fields) and number them. Let's say stream 123618236
yields atackatdawn and stream 0449852 yields sueforpeace. When used for
decoding, most of the streams produce garbage instead of English. There's a
big hint! The plain text was in English.

Now describe the brute force attack.

 

[Kenny McCormack]

He knows how; he just refuses to provide attributions, for reasons that
make no sense to me. But then again, very few things not mentioned in the
C standards documents make any sense to me. I have a very narrow view of
what is important in the world.

 

[Malcolm McLean]

On Mon, 5 Aug 2013 20:40:58 -0500, "osmium" <[email protected]>

Just try all the seeds (aka keys) and look for non-gibberish output.
By Kerckhoffs' principle, we know the type of PRNG, its constants, the
character encoding, the algorithm, etc.

In 1941 the British sent two commando units, a detachment of Royal Engineers,
some Norwegian volunteers, and a flotilla of supporting destroyers to
raid the Lofoten Isands. The raid was spectacular success, with about 200
Germans captured, and only only officer wounded. The real objective though,
which had to be kept secret, was the capture of a German Enigma machine.

Now had the Germans spotted the ships and elected to fight, the Enigma
machine would probably still have been captured, but the force would have
taken casualties, maybe heavy casualties. You can get enemy algorithms.
But it's not cheap.

 

[Geoff]

In 1941 the British sent two commando units, a detachment of Royal Engineers,
some Norwegian volunteers, and a flotilla of supporting destroyers to
raid the Lofoten Isands. The raid was spectacular success, with about 200
Germans captured, and only only officer wounded. The real objective though,
which had to be kept secret, was the capture of a German Enigma machine.

I don't believe that is true. At least I do not believe the real
objective was to obtain a machine. Post-raid, I expect the primary
goal would have been to keep the secret that they had captured a
military-grade machine.

Commercial Enigma machines could be bought on the open market before
1927. The Polish intercepted (accidentally) a model D machine and
duplicated it. They were breaking Enigma traffic by 1932 and shared
their work with the British.

Military Enigma machines differed from the commercial ones with the
addition of the plugboard. There were also models that added more
wheels or had a greater number to select from.

The flaw of Enigma was that a letter was never encrypted as itself.
The Germans also it used to encrypt weather reports which were always
prepared to a standard form. This enabled known-plaintext attacks. You
could simply slide a plaintext word across an encrypted message and if
the encrypted message encrypted the same letter twice you could slide
past that point in the message since it could never contain that word.

The British were manually decrypting Enigma messages before 1940. They
were using the Bombe by 1941 and the Americans had more than 120
machines by 1942 and could crack five 4-rotor messages before an
Enigma operator could decrypt one.

 

[osmium]

Just try all the seeds (aka keys) and look for non-gibberish output.
By Kerckhoffs' principle, we know the type of PRNG, its constants, the
character encoding, the algorithm, etc.

If you start to vary some of those things (and keep those variances
secret), that becomes part of the key. Lets say you vary the
multiplier in the LCG, so then the key is the seed plus the multiplier
(although randomly picking a multiplier is likely to produce a
particularly bad LCG). Then the brute force attack would just step
through all possible combinations of the seed and multiplier. At some
point the number of possible combinations becomes impractically large
to brute force.

Although if there's an LCG in the middle of all this, a more
sophisticated attack than brute force is almost certainly possible.

Thanks, that was very helpful. The thing I was trying to focus on was false
decoded results, especially with short messages. I really have no idea of
how many plain text messages one can expect to find in say 2^32 seeds. Are
there papers on that?

I would expect the "breaking" algorithm to focus on the first n characters
and see if they contain an English word or phrase. I would think n could be
as little as 7 or so. If this test is passed, decode some more of the
message, perhaps all of it, and let a human look at it. With ASCII in an
eight-bit byte, there will be very few surviving seeds with n as small as 7.

To slow down the codebreakers, make a few spelling mistakes in the first few
characters of the plain text message. The human recipient will handle the
problem fine, the computer attacker will have to guess at the actual message
length so he can offset the starting point of his test. Why not make 4096
bytes the minimum transmitted message length? If the attacker starts his
test too far out in the message, he will try to decode white noise or some
other artifact. The sender doesn't even have to tell anyone he has
introduced spelling errors. He can just accept the abuse he gets as a bad
typist.

I chose Baudot code in my "setup" because it will give a high concentration
of latin characters, tending to increase the load on the codebreaker.

I realize this is kind of pointless and there are better ways to provide
cryptographic security, I just think it's a lot of fun. Come to think of
it, a lot of fun things are pointless.

 

[glen herrmannsfeldt]

(snip on Enigma)

I don't believe that is true. At least I do not believe the real
objective was to obtain a machine. Post-raid, I expect the primary
goal would have been to keep the secret that they had captured a
military-grade machine.

Commercial Enigma machines could be bought on the open market before
1927. The Polish intercepted (accidentally) a model D machine and
duplicated it. They were breaking Enigma traffic by 1932 and shared
their work with the British.

Military Enigma machines differed from the commercial ones with the
addition of the plugboard. There were also models that added more
wheels or had a greater number to select from.

The flaw of Enigma was that a letter was never encrypted as itself.

Yes, the biggest mistake.

The Germans also it used to encrypt weather reports which were always
prepared to a standard form. This enabled known-plaintext attacks. You
could simply slide a plaintext word across an encrypted message and if
the encrypted message encrypted the same letter twice you could slide
past that point in the message since it could never contain that word.

As well as I remember it, though, they had to keep up with continuing
improvements. Each was an incremental change, which they then broke.
If they had to start with the final version, it might not have
been done.

The second mistake was confidence in its security.

The British were manually decrypting Enigma messages before 1940.
They were using the Bombe by 1941 and the Americans had more than 120
machines by 1942 and could crack five 4-rotor messages before an
Enigma operator could decrypt one.

-- glen

 

[glen herrmannsfeldt]

(snip regarding random numbers and card shuffling)

Relying on the secrecy of the algorithm is usually a bad idea (in
cryptography it's considered a fatal flaw - flawed PRNGs have done in
several cryptosystems). Poor quality RNGs have also caused some
online gambling losses to the "casinos". Money motivates people to
look for that stuff.

Yes, but it isn't likely in a family card game with everyone
sitting in the same room. If you see your brother check his
phone after every deal, you should get suspicious.

But assuming we do know the algorithm, you'd have enough
information to determine the seed of PRNG (assuming a 32 bit
seed) after about six face-up cards were dealt.

Say you use the usual algorithm of assigning a random number
to each card, and then sorting based on those numbers. Seems
to me that it would take more than six cards in that case.
Also, you assume that you get to see all the cards. In poker,
for example, you often don't see the losing hands. But I didn't
go all the way through the math to be sure.

And I doubt Nevada casinos will let you stand around typing
cards into your phone for even one deal.

-- glen

 

[Nobody]

Bill Cunningham:

Sjouke Burry:

Keith Thompson:

That doesn't do the same thing. If corrected, Bill's program
would set each element to a random integer from 0 to RAND_MAX.
Your suggestion would set each element to a value from 1 to n with
no repetitions.

*WHOOSH*

Let's go back to Bill's original post (emphasis mine):

If you just move the rand() inside the loop, there's no guarantee that all
of the numbers will actually be different.

At least, I think that's what Sjouke was getting at.

Tangentially related: http://xkcd.com/221/