C - gets() function implementation help

[bartc]

The fact that no data has been sent to the processor doesn't mean you
can't read it on the screen. One might consider the screen as the
buffer where the data is held until Enter is pressed.

OK, so maybe there's a local processor which reads or scans the keyboard and
updates the display (unless your terminal is so old that it uses random
logic).

In that case, perhaps that can be considered the 'processor'. As far as the
main processor is concerned, it doesn't have a proper interactive device
attached, only something that might sporadically give a line of text.

I assume by conventional you mean PC.

Believe it or not, there are real security people who say that
displaying those cute little asterisks is a bad idea. It allows any
over-the-shoulder lurker to see how many characters are in your
password, thus making attempts to hack the password easier.

(Does it? What word am I thinking of at this minute? I'll give you a clue:
it's got 7 letters and not 6 or 8 or 9.

But maybe password input should allow extra, discarded, white space to fix
that.)

 

[Barry Schwarz]

OK, so maybe there's a local processor which reads or scans the keyboard and
updates the display (unless your terminal is so old that it uses random
logic).

In that case, perhaps that can be considered the 'processor'. As far as the
main processor is concerned, it doesn't have a proper interactive device
attached, only something that might sporadically give a line of text.

Since you get to define what you mean by proper, your assessment is
obviously correct.

However, in the context of this discussion, my counter-example serves
to show conclusively that the original description of how often the
processor executing the C code is interrupted by the user typing was
hardly universal.

(Does it? What word am I thinking of at this minute? I'll give you a clue:
it's got 7 letters and not 6 or 8 or 9.

So now my exhaustive attack no longer has to deal with any password
length other than 7. Considering only letters and numbers, a
6-character password can contain any of pow(6,36) possible values.
Similar values for the longer ones. By restricting my effort, you
have reduced my task by 99.988%, from 2.28556E34 to 2.65173E30.
(Calculation performed using Excel 2003 with default options.) A
ten-thousand fold reduction in effort meets my definition of easier.

 

[Malcolm McLean]

So now my exhaustive attack no longer has to deal with any password
length other than 7.  Considering only letters and numbers, a
6-character password can contain any of pow(6,36) possible values.
Similar values for the longer ones.  By restricting my effort, you
have reduced my task by 99.988%, from 2.28556E34 to 2.65173E30.
(Calculation performed using Excel 2003 with default options.)  A
ten-thousand fold reduction in effort meets my definition of easier.

Not really. 10^34 is the same as 10^30, if you can only submit one
password to the system at once. If you can try a billion passwords a
second, it's 10^21 versus 10^25 seconds. You'll be just as dead before
the shorter time is up than before the longer one is.

 

[Nick Keighley]

google for it. Basically gets() has no way to know how large the
buffer you called it with is. Hence a user can type charcaters until
the buffer overflows and then Bad Things Happen. I believe the latest
draft standard is removing gets() from the standard C library. And
about time too.

don't quote sigs- text that appears after "-- "

Thank you for your thorough advice.

For example a standard description of gets() function says:
The gets() function shall read bytes from the standard input stream,
stdin, into the array pointed to by s, until a <newline> is read or an
end-of-file condition is encountered. Any <newline> shall be discarded
and a null byte shall be placed immediately after the last byte read
into the array.

I would like to do the same. Some guy recommended me to use getc() and
a loop,
But I think I should to try to implement it without using standard
stdio.h function, just pure C programming, if you know what I mean....
What could you advice on that?

ask whoever set the assignment if this is what he intended. But I
doubt he intended the assignment to be as hard as that. You can't
write getc() completly in standard C. At some point you're going to
have to access the hardware and you can't do this in standard C. Plus
modern operating systems make direct access to the hardware quite
difficult (for very good reasons)

 

[Nick Keighley]

Presumably you are allowed getchar.
Simply read characters into the buffer passed to your mygets(),
reading them one by one with getchar(). Stop when getchar() returns
either EOF or a newline. terminate the buffer with a nul, not
forgetting to suppress the trailing newline.

As others have pointed  out, gets() will (probably) crash if you pass
it a buffer shorter than the line you read.

if yer lucky
gts() has been implicated in various security breaches

Given the specifications,
there's no way to prevent this behaviour, so think of it as an
undesireable feature rather than a bug.

I consider behaviour as bad as this to be a bug

 

[Keith Thompson]

Not really. 10^34 is the same as 10^30, if you can only submit one
password to the system at once. If you can try a billion passwords a
second, it's 10^21 versus 10^25 seconds. You'll be just as dead before
the shorter time is up than before the longer one is.

And if I have any *other* information, it's quite possible that
knowing your password is 7 characters makes an otherwise infeasible
attack feasible.

Consider a system that requires all passwords to be exactly 7
characters, no more, no less. Is such a system more or less secure
than a system that allows longer passwords?

 

[Phil Carmody]

If we have the same security expert in mind, he changed his mind
over such things radically a while back. A perfect example of why
Appeal to Authority really can be a logical fallacy.

So now my exhaustive attack no longer has to deal with any password
length other than 7. Considering only letters and numbers, a
6-character password can contain any of pow(6,36) possible values.
Similar values for the longer ones. By restricting my effort, you
have reduced my task by 99.988%, from 2.28556E34 to 2.65173E30.
(Calculation performed using Excel 2003 with default options.) A
ten-thousand fold reduction in effort meets my definition of easier.

If you'd be saving 99.988%, then you'd have been doing it wrong.

You've not indicated in what order you would perform your exhaustive
attack. Most sensible techniques will start with the lowest entropy
ones first. Therefore you'd not even start any 8- or 9- character ones
until you'd completed the 7-character ones. Therefore you can't count
the fact that you don't search >7-character passwords as a saving.

You can avoid searching shorter passwords, but that's a saving of 2.9%
(or 1.6% if you assume mixed case).

Phil

 

[Barry Schwarz]

If we have the same security expert in mind, he changed his mind
over such things radically a while back. A perfect example of why
Appeal to Authority really can be a logical fallacy.


If you'd be saving 99.988%, then you'd have been doing it wrong.

You've not indicated in what order you would perform your exhaustive
attack. Most sensible techniques will start with the lowest entropy
ones first. Therefore you'd not even start any 8- or 9- character ones
until you'd completed the 7-character ones. Therefore you can't count
the fact that you don't search >7-character passwords as a saving.

You can avoid searching shorter passwords, but that's a saving of 2.9%
(or 1.6% if you assume mixed case).

So a divide and conquer strategy where different resources are used in
parallel to test passwords of different lengths wouldn't be sensible.
Neither would one where the resource are split depending on some
initial sequence of characters. I thought I read an article some
years ago how a collaborative effort (along the lines of SETI) was
able to factor a very large composite number into its two large prime
constituents in a quite reasonable time frame. It seems that hacking
a password could achieve the same benefit. But, since I don't attempt
to hack passwords, I must allow for the possibility you're right.

 

[brian]

google for it. Basically gets() has no way to know how large the
buffer you called it with is. Hence a user can type charcaters until
the buffer overflows and then Bad Things Happen. I believe the latest
draft standard is removing gets() from the standard C library. And
about time too.




don't quote sigs- text that appears after "-- "




ask whoever set the assignment if this is what he intended. But I
doubt he intended the assignment to be as hard as that. You can't
write getc() completly in standard C. At some point you're going to
have to access the hardware and you can't do this in standard C. Plus
modern operating systems make direct access to the hardware quite
difficult (for very good reasons)

So what I was advised, is to use a loop and a getc() function from
stdio.h, some also advised to use pointers.
How would that work exactly?

 

[Phil Carmody]

So a divide and conquer strategy where different resources are used in
parallel to test passwords of different lengths wouldn't be sensible.
Neither would one where the resource are split depending on some
initial sequence of characters.

By length, nope, chopping off only a couple of % of the work isn't
divide and conquer. If you were going to not use a dictionary-
based attack you would split the work based on initial sequences of
characters, as each of the work packets would be expected to take
the same length of time, and you can get "embarassing parallelism".
Using a dictionary, you'd probably split on the word you're doping
the attempt with, and again it would be mostly embarassingly parallel.
(The transforms you'd apply to the word would mean that you'd
probably be testing duplicates, and so you'd have more overhead trying
to reduce that.)

I thought I read an article some
years ago how a collaborative effort (along the lines of SETI) was
able to factor a very large composite number into its two large prime
constituents in a quite reasonable time frame.

As someone closely involved in distributed factoring, I find the
reference to SETI annoying. People were doing distributed factoring
long before nonsense like SETI ever existed. (But the protocols,
being email based and requiring humans to step through the state
machine manually, have been honed a lot since those days.)

It seems that hacking
a password could achieve the same benefit. But, since I don't attempt
to hack passwords, I must allow for the possibility you're right.

These are all "embarassingly parallel" problems. It doesn't take
any experience of cracking passwords to model an attack on such a
problem. It's probably in the 101 class for distributed computing.

Phil

 

[Nick Keighley]

And if I have any *other* information, it's quite possible that
knowing your password is 7 characters makes an otherwise infeasible
attack feasible.

Consider a system that requires all passwords to be exactly 7
characters, no more, no less.  Is such a system more or less secure
than a system that allows longer passwords?

I remember someone mentioning a few facts about his cashcard pin
(things like no repeated numbers, no 3's or 4's and so on). After a
few of those I told him I could guess his pin in about 40 tries. He
looked terrified.

 

[Nick Keighley]

So what I was advised, is to use a loop and a getc() function from
stdio.h, some also advised to use pointers.
How would that work exactly?

it's getting very hard to answer this without actually writing the
program for you! Look up getc() (google will find you a page that
describes getc()). ignore the end-of-file stuff for the moment. How
are you going to test for a <newline>?

So in pseudo code:-

LOOP UNTIL newline
read character
stuff it in array

terminate string with nul character

Then convert each line into C. What C constructs repeatedly loops
while some condition is true?

You might find it use easier to arrays rather than pointers (some
pedant will point out that in this case they are the same thing- well
yes but they don't *look* the same)


good luck, happy programming!

 

[Nick Keighley]

Start off by finding out why gets() is an open invitation to adversaries
to stomp all over your system.

Once you know that, implementing gets() is easy - Just Say No.

which may not get him a passing mark in his course

 

[bartc]

Any outside knowledge about my password is too much.

I wasn't being too serious.

No thanks. What if a password actually contains whitespace?

Incidentally, I once used a system that would echo a dot for each
character of a password, but would echo a space for any spaces that
were actually part of the password.

That is actually a tremendous help. It gives the 'shape' of a phrase and is
a method I used all the time to help solve crossword clues, where there are
multiple words. (Example: the clue hints at a book or film title, the answer
is (1,7,2,5) and the letters so far are - ------- -- i----. Simple! (If not,
see below...))

--
Bartc

--









--












--











--







a passage to india

 

[Richard Bos]

That must suck for tetris. Or vi, or notepad. Or even a shell.
Or text entry in a browser window. Or keyboard shortcuts in
any gui program. Or basically almost anything.

Almost. It is, however, extremely useful for paying your salary. Never
underestimate the importance of mainframes; behind the scenes, they are
the machines the world runs on.

Richard

 

[Seebs]

Not unless it has internal linkage though?

External, I assume you mean?

It gets fussy. In practice, the right answer is "treat it as
completely reserved regardless and you'll make fewer mistakes".

-s

 

[Nick Keighley]

If that's the case, the course isn't worth passing.

this is simply nonsense.
It's a mistake, yes, but not a big enough mistake to invalidate the
entire course.
K&R for instance don't comment on gets()'s problem when they (very
briefly) mention it

 

[Andrew Poelstra]

this is simply nonsense.
It's a mistake, yes, but not a big enough mistake to invalidate the
entire course.

Yes, it is. Using gets() demonstrates a complete inability to reason
about buffers or their boundaries, and writing such a beast is even
worse.

I would fail this assignment because there is no way within the
bounds of the C language to do it correctly. For the same reason,
no legitimate course would ever have such an assignment.

K&R for instance don't comment on gets()'s problem when they (very
briefly) mention it

To their fault.

 

[Keith Thompson]

Yes, it is. Using gets() demonstrates a complete inability to reason
about buffers or their boundaries, and writing such a beast is even
worse.

Really? What if you're writing a conforming implementation of the
standard C library? In that case, you *have* to implement gets()
(unless you're only interested in conforming to the C201X standard --
you know, the one that doesn't exist yet).

I would fail this assignment because there is no way within the
bounds of the C language to do it correctly. For the same reason,
no legitimate course would ever have such an assignment.

Have you considered the possibility that the point of the assignment
is to demonstrate the danger of using gets()? Admittedly we've seen
no direct evidence of that but it's possible.

[...]

 

[Andrew Poelstra]

Really? What if you're writing a conforming implementation of the
standard C library? In that case, you *have* to implement gets()
(unless you're only interested in conforming to the C201X standard --
you know, the one that doesn't exist yet).

We had a discussion a while back about whether this is a conforming
implementation:

char *gets(char *buffer) {
fputs("Hey jerk!!", stderr);
exit(0);
return NULL;
}

Since in the general case, there is no way to guarantee buffer will
not be run, causing undefined behavior, and printing "Hey jerk" and
dying is well within the bounds of undefined behavior.

I don't remember where the group ended up on it, but that looks
perfectly okay to me.

Have you considered the possibility that the point of the assignment
is to demonstrate the danger of using gets()? Admittedly we've seen
no direct evidence of that but it's possible.

I have considered it, yes, but it doesn't seem like the OP
is at an appropriate skill level to be learning such things.