/* TODO: - don't use pfstatus (at least vprintf isn't portable) -- or maybe leave it in and see who complains - use consistent non-capitalization in error messages - add standard GNU copyleft comment - Add -s --size=N option, to force a size. I want this for wiping damaged floppies that would otherwise bobm out at the first I/O error. It should take -k and -M - Add -r/-R/--recursive - Add -i/--interactive - Reserve -d - Add -L - Move the _() into error() and replace it with N() everywhere. Error messages are by definition not performance-critical. - Deal with the amazing variety of gettimeofday() implementation bugs. (Sone systems use a one-arg form; still others insist that the timezone either be NULL or be non-NULL. Whee.) - Add an unlink-all option to emulate rm. */ /* * shred.c - by Colin Plumb. * * Do a secure overwrite of given files or devices, so that not even * very expensive hardware probing can recover the data. * * Although this process is also known as "wiping", I prefer the longer * name both because I think it is more evocative of what is happening and * because a longer name conveys a more appropriate sense of deliberateness. * * For the theory behind this, see "Secure Deletion of Data from Magnetic * and Solid-State Memory", on line at * http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html * * Just for the record, reversing one or two passes of disk overwrite * is not terribly difficult with hardware help. Hook up a good-quality * digitizing oscilloscope to the output of the head preamplifier and copy * the high-res digitized data to a computer for some off-line analysis. * Read the "current" data and average all the pulses together to get an * "average" pulse on the disk. Subtract this average pulse from all of * the actual pulses and you can clearly see the "echo" of the previous * data on the disk. * * Real hard drives have to balance the cost of the media, the head, * and the read circuitry. They use better-quality media than absolutely * necessary to limit the cost of the read circuitry. By throwing that * assumption out, and the assumption that you want the data processed * as fast as the hard drive can spin, you can do better. * * If asked to wipe a file, this also unlinks it, renaming it to in a * clever way to try to leave no trace of the original filename. * * Copyright 1997, 1998, 1999 Colin Plumb . This program * may be freely distributed under the terms of the GNU GPL, the BSD license, * or Larry Wall's "Artistic License" Even if you use the BSD license, * which does not require it, I'd really like to get improvements back. * * The ISAAC code still bears some resemblance to the code written * by Bob Jenkins, but he permits pretty unlimited use. * * This was inspired by a desire to improve on some code titled: * Wipe V1.0-- Overwrite and delete files. S. 2/3/96 * but I've rewritten everything here so completely that no trace of * the original remains. * * Thanks to: * Bob Jenkins, for his good RNG work and patience with the FSF copyright * paperwork. * Jim Meyering, for his work merging this into the GNU fileutils while * still letting me feel a sense of ownership and pride. Getting me to * tolerate the GNU brace style was quite a feat of diplomacy. * Paul Eggert, for lots of useful discussion and code. I disagree with * an awful lot of his suggestions, but they're disagreements worth having. * * Things to think about: * - Security: Is there any risk to the race * between overwriting and unlinking a file? Will it do anything * drastically bad if told to attack a named pipe or socket? */ /* The official name of this program (e.g., no `g' prefix). */ #define PROGRAM_NAME "shred" #define AUTHORS "Colin Plumb" #include #include #include /* For memcpy(), strerror() */ #include /* Used by pferror */ #include #include #if HAVE_CONFIG_H /* Default fileutils build */ # include # include "system.h" # include "xstrtoul.h" # include "closeout.h" # include "error.h" # include "quotearg.h" /* For quotearg_colon */ /* * error.h #defines __attribute__, but this is safer, because someone else's * preprocessor could decide that it would make a great reserved word. */ # if __GNUC__ < 2 # define attribute(x) # else # define attribute __attribute__ # endif #else /* !HAVE_CONFIG_H */ /* * Standalone build - this file compiles by itself without autoconf and * the like. No i18n, and I still have to write a stub for getopt_long, * but it's a lot less intertwingled than the usual GNU utilities. */ # include /* For ULONG_MAX etc. */ # include /* For strtoul, EXIT_FAILURE */ # include # include /* For O_RDONLY etc. */ # include /* For getpid(), etc. */ # include /* For struct timeval */ # include /* For struct stat */ # define GNU_PACKAGE "standalone" # define VERSION "2.0" /* Kind of arbitrary... */ # if __GNUC__ < 2 || __GNUC__ == 2 && __GNUC_MINOR__ < 5 || __STRICT_ANSI__ # define attribute(x) # else # define attribute __attribute__ # if __GNUC__ == 2 && __GNUC_MINOR__ < 7 /* The __-protected forms were introduced in GCC 2.6.4 */ # define __format__ format # define __printf__ printf # endif # endif /* Reasonable default assumptions for time-getting */ # ifndef HAVE_GETTIMEOFDAY # define HAVE_GETTIMEOFDAY 1 /* Most systems have it these days */ # endif # ifdef CLOCK_REALTIME # ifndef HAVE_CLOCK_GETTIME # define HAVE_CLOCK_GETTIME 1 # endif # endif # ifndef O_NOCTTY # define O_NOCTTY 0 /* This is a very optional frill */ # endif # ifndef S_IWUSR # ifdef S_IWRITE # define S_IWUSR S_IWRITE # else # define S_IWUSR 0200 # endif # endif /* Variant convert-to-unsigned-long function that accepts metric suffixes */ enum strtol_error { LONGINT_OK, LONGINT_INVALID, LONGINT_INVALID_SUFFIX_CHAR, LONGINT_OVERFLOW }; static int xstrtoul(char const *ptr, char const **end, int base, unsigned long *res, char const *valid_suffixes) { char *end_ptr; char const *p; static char const metric_suffixes[] = "kMGTPEZY"; int decimal_flag; unsigned long n; char c; errno = 0; *res = n = strtoul(ptr, &end_ptr, base); if (end) *end = end_ptr; if (errno) return LONGINT_OVERFLOW; if (ptr == end_ptr) return LONGINT_INVALID; c = *end_ptr; if (!c) return LONGINT_OK; /* Now deal with metric-style suffixes */ if (!valid_suffixes) valid_suffixes = ""; if (!strchr (valid_suffixes, c)) return LONGINT_INVALID_SUFFIX_CHAR; decimal_flag = 0; switch (c) { case 'b': if (n > ULONG_MAX/512) return LONGINT_OVERFLOW; n *= 512; break; case 'B': if (n > ULONG_MAX/102412) return LONGINT_OVERFLOW; n *= 1024; break; case 'c': break; case 'K': c = 'k'; goto def; case 'm': c = 'M'; /*FALLTHROUGH*/ def:default: p = strchr (metric_suffixes, c); if (!p) return LONGINT_INVALID_SUFFIX_CHAR; /* * If valid_suffixes contains '0', then xD (decimal) and xB (binary) * are allowed as "supersuffixes". Binary is the default. */ if (strchr (valid_suffixes, '0')) { if (end_ptr[1] == 'B') end_ptr++; else if (end_ptr[1] == 'D') { decimal_flag = 1; end_ptr++; } } /* Now do the scaling */ p++; if (decimal_flag) do { if (n > ULONG_MAX/1000) return LONGINT_OVERFLOW; n *= 1000; } while (--p > metric_suffixes); else do { if (n > ULONG_MAX/1024) return LONGINT_OVERFLOW; n *= 1024; } while (--p > metric_suffixes); } /* Final wrapup */ if (end) *end = end_ptr+1; /* Extra suffix is allowed if it's expected */ else if (end_ptr[1]) return LONGINT_INVALID_SUFFIX_CHAR; *res = n; return LONGINT_OK; } /* Dummy i18n stubs */ # define _(x) x # define N_(x) x # define setlocale(x,y) (void)0 # define bindtextdomain(x,y) (void)0 # define textdomain(x) (void)0 /* * Print a message with `fprintf (stderr, FORMAT, ...)'; * if ERRNUM is nonzero, follow it with ": " and strerror (ERRNUM). * If STATUS is nonzero, terminate the program with `exit (STATUS)'. */ static void error (int status, int errnum, const char *format, ...) attribute ((__format__ (__printf__, 3, 4))); static void flushstatus (void); extern char const *program_name; static void error (int status, int errnum, const char *format, ...) { va_list ap; if (!errnum) errnum = errno; flushstatus(); /* Make it look pretty */ if (program_name) { fputs(program_name, stderr); fputs(": ", stderr); } va_start(ap, format); vfprintf(stderr, format, ap); va_end(ap); if (errnum) { fputs(": ", stderr); fputs(strerror(errnum), stderr); } putc('\n', stderr); if (status) exit(status); } /* * GNU programs actually check for failure closing standard output. * This seems unnecessary, until your shell script starts hitting * ENOSPC and doing bizarre things with zero-length files. */ static void close_stdout (void) { if (ferror (stdout)) error (EXIT_FAILURE, 0, _("write error")); if (fclose (stdout) != 0) error (EXIT_FAILURE, errno, _("write error")); } /* * Quote the argument (including colon characters) into the buffer. * Return the buffer size used (including trailing null byte.) * If this is larger than the bufsize, it is an estimate of the space * needed. */ static size_t quotearg_colon_buf(char const *arg, char *buf, size_t bufsize) { /* Some systems don't have \a or \e, so this is ASCII-dependent */ static char const escaped[] = "\7\b\33\f\n\r\t\v"; static char const escapes[] = "abefnrtv"; int c; size_t pos = 0; char const *p; while ((c = (unsigned char)*arg++) != 0) { if (isprint(c)) { if (strchr("\\:", c)) /* Anything else we should quote? */ if (pos++ < bufsize) *buf++ = '\\'; } else { if (pos++ < bufsize) *buf++ = '\\'; p = strchr(escaped, c); /* c is never 0, so this is okay */ if (p) { c = escapes[p-escaped]; } else { if (isdigit((unsigned char)*arg)) c += 256; /* Force 3-digit form if followed by a digit */ if (c > 077) if (pos++ < bufsize) *buf++ = "0123"[c>>6 & 3]; if (c > 07) if (pos++ < bufsize) *buf++ = "01234567"[c>>3 & 7]; c = "01234567"[c & 7]; } } if (pos++ < bufsize) *buf++ = c; } if (pos++ < bufsize) *buf++ = 0; return pos; } /* Quote metacharacters in a filename */ char const * quotearg_colon(char const *arg) { static char *buf = 0; size_t bufsize = 0; size_t newsize; while ((newsize = quotearg_colon_buf(arg, buf, bufsize)) > bufsize) { buf = realloc(buf, newsize); if (!buf) error(EXIT_FAILURE, 0, _("out of memory")); bufsize = newsize; } return buf; } #endif /* ! HAVE_CONFIG_H */ /* Some systems don't support symbolic links */ #ifndef S_ISLNK # define S_ISLNK(mode) 0 #endif #define DEFAULT_PASSES 25 /* Default */ /* How often to update wiping display */ #define VERBOSE_UPDATE 150*1024 struct Options { int allow_devices; /* -d flag: Allow operations on devices */ int force; /* -f flag: chmod() files if necessary */ size_t n_iterations; /* -n flag: Number of iterations */ int remove_file; /* -p flag (inverted): remove file after shredding */ off_t size; /* -s flag: size of file */ int verbose; /* -v flag: Print progress (goes to 2) */ int exact; /* -x flag: Do not round up file size */ int zero_fill; /* -z flag: Add a final zero pass */ }; static struct option const long_opts[] = { {"device", no_argument, NULL, 'D'}, {"exact", required_argument, NULL, 'x'}, {"force", no_argument, NULL, 'f'}, {"iterations", required_argument, NULL, 'n'}, {"preserve", no_argument, NULL, 'p'}, {"size", required_argument, NULL, 's'}, {"verbose", no_argument, NULL, 'v'}, {"zero", required_argument, NULL, 'z'}, {GETOPT_HELP_OPTION_DECL}, {GETOPT_VERSION_OPTION_DECL}, {NULL, 0, NULL, 0} }; /* Global variable for error printing purposes */ char const *program_name; /* Initialized before any possible use */ void usage (int status) { if (status != 0) fprintf (stderr, _("Try `%s --help' for more information.\n"), program_name); else { printf (_("Usage: %s [OPTIONS] FILE [...]\n"), program_name); printf (_("\ Delete a file securely, first overwriting it to hide its contents.\n\ \n\ -D, --device allow operation on devices (devices are never removed)\n\ -f, --force change permissions to allow writing if necessary\n\ -n, --iterations=N Overwrite N times instead of the default (%d)\n\ -p, --preserve do not remove file after overwriting\n\ -s, --size=N shred this many bytes (suffixes like k, M accepted)\n\ -v, --verbose show progress (-vv to leave progress on screen)\n\ -x, --exact do not round file sizes up to the next full block\n\ -z, --zero add a final overwrite with zeros to hide shredding\n\ - shred standard output (NOTE: conflicts with -v)\n\ --help display this help and exit\n\ --version print version information and exit\n\ \n\ FIXME maybe add more discussion here?"), DEFAULT_PASSES); puts (_("\nReport bugs to .")); close_stdout (); } exit (status); } #if ! HAVE_FDATASYNC # define fdatasync(fd) -1 #endif /* * -------------------------------------------------------------------- * Bob Jenkins' cryptographic random number generator, ISAAC. * Hacked by Colin Plumb. * * We need a source of random numbers for some of the overwrite data. * Cryptographically secure is desirable, but it's not life-or-death * so I can be a little bit experimental in the choice of RNGs here. * * This generator is based somewhat on RC4, but has analysis * (http://ourworld.compuserve.com/homepages/bob_jenkins/randomnu.htm) * pointing to it actually being better. I like it because it's nice * and fast, and because the author did good work analyzing it. * -------------------------------------------------------------------- */ #if ULONG_MAX == 0xffffffff typedef unsigned long word32; #else # if UINT_MAX == 0xffffffff typedef unsigned word32; # else # if USHRT_MAX == 0xffffffff typedef unsigned short word32; # else # if UCHAR_MAX == 0xffffffff typedef unsigned char word32; # else # error No 32-bit type available! # endif # endif # endif #endif /* Size of the state tables to use. (You may change ISAAC_LOG) */ #define ISAAC_LOG 8 #define ISAAC_WORDS (1 << ISAAC_LOG) #define ISAAC_BYTES (ISAAC_WORDS * sizeof (word32)) /* RNG state variables */ struct isaac_state { word32 mm[ISAAC_WORDS]; /* Main state array */ word32 iv[8]; /* Seeding initial vector */ word32 a, b, c; /* Extra index variables */ }; /* This index operation is more efficient on many processors */ #define ind(mm, x) *(unsigned *)((char *)(mm) + ( (x) & (ISAAC_WORDS-1)<<2 )) /* * The central step. This uses two temporaries, x and y. mm is the * whole state array, while m is a pointer to the current word. off is * the offset from m to the word ISAAC_WORDS/2 words away in the mm array, * i.e. +/- ISAAC_WORDS/2. */ #define isaac_step(mix, a, b, mm, m, off, r) \ ( \ a = ((a) ^ (mix)) + (m)[off], \ x = *(m), \ *(m) = y = ind ((mm), x) + (a) + (b), \ *(r) = b = ind ((mm), (y) >> ISAAC_LOG) + x \ ) /* * Refill the entire R array, and update S. */ static void isaac_refill (struct isaac_state *s, word32 r[ISAAC_WORDS]) { register word32 a, b; /* Caches of a and b */ register word32 x, y; /* Temps needed by isaac_step() macro */ register word32 *m = s->mm; /* Pointer into state array */ a = s->a; b = s->b + (++s->c); do { isaac_step (a << 13, a, b, s->mm, m, ISAAC_WORDS / 2, r); isaac_step (a >> 6, a, b, s->mm, m + 1, ISAAC_WORDS / 2, r + 1); isaac_step (a << 2, a, b, s->mm, m + 2, ISAAC_WORDS / 2, r + 2); isaac_step (a >> 16, a, b, s->mm, m + 3, ISAAC_WORDS / 2, r + 3); r += 4; } while ((m += 4) < s->mm + ISAAC_WORDS / 2); do { isaac_step (a << 13, a, b, s->mm, m, -ISAAC_WORDS / 2, r); isaac_step (a >> 6, a, b, s->mm, m + 1, -ISAAC_WORDS / 2, r + 1); isaac_step (a << 2, a, b, s->mm, m + 2, -ISAAC_WORDS / 2, r + 2); isaac_step (a >> 16, a, b, s->mm, m + 3, -ISAAC_WORDS / 2, r + 3); r += 4; } while ((m += 4) < s->mm + ISAAC_WORDS); s->a = a; s->b = b; } /* * The basic seed-scrambling step for initialization, based on Bob * Jenkins' 256-bit hash. */ #define mix(a,b,c,d,e,f,g,h) \ ( a ^= b << 11, d += a, \ b += c, b ^= c >> 2, e += b, \ c += d, c ^= d << 8, f += c, \ d += e, d ^= e >> 16, g += d, \ e += f, e ^= f << 10, h += e, \ f += g, f ^= g >> 4, a += f, \ g += h, g ^= h << 8, b += g, \ h += a, h ^= a >> 9, c += h, \ a += b ) /* The basic ISAAC initialization pass. */ static void isaac_mix (struct isaac_state *s, word32 const seed[ISAAC_WORDS]) { int i; word32 a = s->iv[0]; word32 b = s->iv[1]; word32 c = s->iv[2]; word32 d = s->iv[3]; word32 e = s->iv[4]; word32 f = s->iv[5]; word32 g = s->iv[6]; word32 h = s->iv[7]; for (i = 0; i < ISAAC_WORDS; i += 8) { a += seed[i]; b += seed[i + 1]; c += seed[i + 2]; d += seed[i + 3]; e += seed[i + 4]; f += seed[i + 5]; g += seed[i + 6]; h += seed[i + 7]; mix (a, b, c, d, e, f, g, h); s->mm[i] = a; s->mm[i + 1] = b; s->mm[i + 2] = c; s->mm[i + 3] = d; s->mm[i + 4] = e; s->mm[i + 5] = f; s->mm[i + 6] = g; s->mm[i + 7] = h; } s->iv[0] = a; s->iv[1] = b; s->iv[2] = c; s->iv[3] = d; s->iv[4] = e; s->iv[5] = f; s->iv[6] = g; s->iv[7] = h; } #if 0 /* Provided for reference only; not used in this code */ /* * Initialize the ISAAC RNG with the given seed material. * Its size MUST be a multiple of ISAAC_BYTES, and may be * stored in the s->mm array. * * This is a generalization of the original ISAAC initialization code * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES, * it is identical. */ static void isaac_init (struct isaac_state *s, word32 const *seed, size_t seedsize) { static word32 const iv[8] = { 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8, 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119}; int i; # if 0 /* The initialization of iv is a precomputed form of: */ for (i = 0; i < 7; i++) iv[i] = 0x9e3779b9; /* the golden ratio */ for (i = 0; i < 4; ++i) /* scramble it */ mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]); # endif s->a = s->b = s->c = 0; for (i = 0; i < 8; i++) s->iv[i] = iv[i]; if (seedsize) { /* First pass (as in reference ISAAC code) */ isaac_mix (s, seed); /* Second and subsequent passes (extension to ISAAC) */ while (seedsize -= ISAAC_BYTES) { seed += ISAAC_WORDS; for (i = 0; i < ISAAC_WORDS; i++) s->mm[i] += seed[i]; isaac_mix (s, s->mm); } } else { /* The no seed case (as in reference ISAAC code) */ for (i = 0; i < ISAAC_WORDS; i++) s->mm[i] = 0; } /* Final pass */ isaac_mix (s, s->mm); } #endif /* Start seeding an ISAAC structire */ static void isaac_seed_start(struct isaac_state *s) { static word32 const iv[8] = { 0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8, 0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119 }; int i; #if 0 /* The initialization of iv is a precomputed form of: */ for (i = 0; i < 7; i++) iv[i] = 0x9e3779b9; /* the golden ratio */ for (i = 0; i < 4; ++i) /* scramble it */ mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]); #endif for (i = 0; i < 8; i++) s->iv[i] = iv[i]; /* We cound initialize s->mm to zero, but why bother? */ /* s->c gets used for a data pointer during the seeding phase */ s->a = s->b = s->c = 0; } /* Add a buffer of seed material */ static void isaac_seed_data(struct isaac_state *s, void const *buf, size_t size) { unsigned char *p; size_t avail; size_t i; avail = sizeof(s->mm) - (size_t)s->c; /* s->c is used as a write pointer */ /* Do any full buffers that are necessary */ while (size > avail) { p = (unsigned char *)s->mm + s->c; for (i = 0; i < avail; i++) p[i] ^= ((unsigned char const *)buf)[i]; buf = (char const *)buf + avail; size -= avail; isaac_mix(s, s->mm); s->c = 0; avail = sizeof(s->mm); } /* And the final partial block */ p = (unsigned char *)s->mm + s->c; for (i = 0; i < size; i++) p[i] ^= ((unsigned char const *)buf)[i]; s->c = (word32)size; } /* End of seeding phase; get everything ready to prodice output. */ static void isaac_seed_finish(struct isaac_state *s) { isaac_mix (s, s->mm); isaac_mix (s, s->mm); /* Now reinitialize c to start things off right */ s->c = 0; } #define ISAAC_SEED(s,x) isaac_seed_data(s, &(x), sizeof(x)) #if __GNUC__ >= 2 && (__i386__ || __alpha__ || _ARCH_PPC) /* * Many processors have very-high-resolution timer registers, * The timer registers can be made inaccessible, so we have to deal with the * possibility of SIGILL while we're working. */ static jmp_buf env; static void sigill_handler(int signum) { (void)signum; longjmp(env, 1); /* Trivial, just return an indication that it happened */ } static void isaac_seed_machdep(struct isaac_state *s) { void (*oldhandler)(int); /* This is how one does try/except in C */ oldhandler = signal(SIGILL, sigill_handler); if (setjmp(env)) /* ANSI: Must be entire controlling expression */ { (void)signal(SIGILL, oldhandler); } else { # if __i386__ word32 t[2]; __asm__ __volatile__ ("rdtsc" : "=a" (t[0]), "=d" (t[1])); # endif # if __alpha__ unsigned long t; __asm__ __volatile__ ("rpcc %0" : "=r" (t)); # endif # if _ARCH_PPC word32 t; __asm__ __volatile__ ("mfspr %0,22" : "=r" (t)); # endif # if __mips /* Code not used because this is not accessible from userland */ word32 t; __asm__ __volatile__ ("mfc0\t%0,$9" : "=r" (t)); # endif # if __sparc__ /* This doesn't compile on all platforms yet. How to fix? */ unsigned long t; __asm__ __volatile__ ("rd %%tick, %0" : "=r" (t)); # endif (void)signal(SIGILL, oldhandler); isaac_seed_data(s, &t, sizeof(t)); } } #else /* !(__i386__ || __alpha__ || _ARCH_PPC) */ /* Do-nothing stub */ # define isaac_seed_machdep(s) (void)0 #endif /* !(__i386__ || __alpha__ || _ARCH_PPC) */ /* * Get seed material. 16 bytes (128 bits) is plenty, but if we have * /dev/urandom, we get 32 bytes = 256 bits for complete overkill. */ static void isaac_seed (struct isaac_state *s) { isaac_seed_start(s); { pid_t t = getpid (); ISAAC_SEED (s, t); } { pid_t t = getppid (); ISAAC_SEED (s, t); } { uid_t t = getuid (); ISAAC_SEED (s, t); } { gid_t t = getgid (); ISAAC_SEED (s, t); } { #if HAVE_GETHRTIME hrtime_t t = gethrtime (); ISAAC_SEED (s, t); #else # if HAVE_CLOCK_GETTIME /* POSIX ns-resolution */ struct timespec t; clock_gettime (CLOCK_REALTIME, &t); # else # if HAVE_GETTIMEOFDAY struct timeval t; gettimeofday (&t, (struct timezone *) 0); # else time_t t; t = time((time_t *)0); # endif # endif #endif ISAAC_SEED (s, t); } isaac_seed_machdep(s); { char buf[32]; int fd = open ("/dev/urandom", O_RDONLY | O_NOCTTY); if (fd >= 0) { read (fd, buf, 32); close (fd); isaac_seed_data(s, buf, 32); } else { fd = open ("/dev/random", O_RDONLY | O_NONBLOCK | O_NOCTTY); if (fd >= 0) { /* /dev/random is more precious, so use less */ read (fd, buf, 16); close (fd); isaac_seed_data(s, buf, 16); } } } isaac_seed_finish(s); } /* Single-word RNG built on top of ISAAC */ struct irand_state { word32 r[ISAAC_WORDS]; unsigned numleft; struct isaac_state *s; }; static void irand_init (struct irand_state *r, struct isaac_state *s) { r->numleft = 0; r->s = s; } /* * We take from the end of the block deliberately, so if we need * only a small number of values, we choose the final ones which are * marginally better mixed than the initial ones. */ static word32 irand32 (struct irand_state *r) { if (!r->numleft) { isaac_refill (r->s, r->r); r->numleft = ISAAC_WORDS; } return r->r[--r->numleft]; } /* * Return a uniformly distributed random number between 0 and n, * inclusive. Thus, the result is modulo n+1. * * Theory of operation: as x steps through every possible 32-bit number, * x % n takes each value at least 2^32 / n times (rounded down), but * the values less than 2^32 % n are taken one additional time. Thus, * x % n is not perfectly uniform. To fix this, the values of x less * than 2^32 % n are disallowed, and if the RNG produces one, we ask * for a new value. */ static word32 irand_mod (struct irand_state *r, word32 n) { word32 x; word32 lim; if (!++n) return irand32 (r); lim = -n % n; /* == (2**32-n) % n == 2**32 % n */ do { x = irand32 (r); } while (x < lim); return x % n; } /* * Maintain a status line on stdout. This is done by using CR and * overprinting a new line when it changes, padding with trailing blanks * as needed to hide all of the previous line. (Assuming that the return * value of printf is an accurate width.) * FIXME: we can't assume that */ static int status_visible = 0; /* Number of visible characters */ static int status_pos = 0; /* Current position, including padding */ /* * Print a new status line, overwriting the previous one. * attribute() expands to nothing on non-gcc compilers. */ static void pfstatus (char const *,...) attribute ((__format__ (__printf__, 1, 2))); static void pfstatus (char const *fmt,...) { int new; /* New status_visible value */ va_list ap; /* If we weren't at beginning, go there. */ if (status_pos) putchar ('\r'); va_start (ap, fmt); new = vprintf (fmt, ap); va_end (ap); if (new >=0) { status_pos = new; while (status_pos < status_visible) { putchar (' '); status_pos++; } status_visible = new; } fflush (stdout); } /* Leave current status (if any) visible and go to the next free line. */ static void flushstatus (void) { if (status_visible) { putchar ('\n'); /* Leave line visible */ fflush (stdout); status_visible = status_pos = 0; } else if (status_pos) { putchar ('\r'); /* Go back to beginning of line */ fflush (stdout); status_pos = 0; } } /* * Fill a buffer with a fixed pattern. * * The buffer must be at least 3 bytes long, even if * size is less. Larger sizes are filled exactly. */ static void fillpattern (int type, unsigned char *r, size_t size) { size_t i; unsigned bits = type & 0xfff; bits |= bits << 12; ((unsigned char *) r)[0] = (bits >> 4) & 255; ((unsigned char *) r)[1] = (bits >> 8) & 255; ((unsigned char *) r)[2] = bits & 255; for (i = 3; i < size / 2; i *= 2) memcpy ((char *) r + i, (char *) r, i); if (i < size) memcpy ((char *) r + i, (char *) r, size - i); /* Invert the first bit of every 512-byte sector. */ if (type & 0x1000) for (i = 0; i < size; i += 512) r[i] ^= 0x80; } /* * Fill a buffer with random data. * size is rounded UP to a multiple of ISAAC_BYTES. */ static void fillrand (struct isaac_state *s, word32 *r, size_t size) { size = (size + ISAAC_BYTES - 1) / ISAAC_BYTES; while (size--) { isaac_refill (s, r); r += ISAAC_WORDS; } } /* * Generate a 6-character (+ nul) pass name string * FIXME: allow translation of "random". */ #define PASS_NAME_SIZE 7 static void passname (unsigned char const *data, char name[PASS_NAME_SIZE]) { if (data) sprintf (name, "%02x%02x%02x", data[0], data[1], data[2]); else memcpy (name, "random", PASS_NAME_SIZE); } /* * Do pass number k of n, writing "size" bytes of the given pattern "type" * to the file descriptor fd. Name, k and n are passed in only for verbose * progress message purposes. If n == 0, no progress messages are printed. * * If *sizep == -1, the size is unknown, and it will be filled in as soon * as writing fails. */ static int dopass (int fd, char const *qname, off_t *sizep, int type, struct isaac_state *s, unsigned long k, unsigned long n) { off_t size = *sizep; off_t offset; /* Current file posiiton */ off_t thresh; /* Offset to print next status update */ size_t lim; /* Amount of data to try writing */ size_t soff; /* Offset into buffer for next write */ ssize_t ssize; /* Return value from write() */ #if ISAAC_WORDS > 1024 word32 r[ISAAC_WORDS * 3]; /* Multiple of 4K and of pattern size */ #else word32 r[1024 * 3]; /* Multiple of 4K and of pattern size */ #endif char pass_string[PASS_NAME_SIZE]; /* Name of current pass */ if (lseek (fd, 0, SEEK_SET) == (off_t)-1) { error (0, errno, _("%s: cannot rewind"), qname); return -1; } /* Constant fill patterns need only be set up once. */ if (type >= 0) { lim = sizeof (r); if ((off_t) lim > size && size != (off_t)-1) { lim = (size_t) size; } fillpattern (type, (unsigned char *) r, lim); passname ((unsigned char *) r, pass_string); } else { passname (0, pass_string); } /* Set position if first status update */ thresh = 0; if (n) { pfstatus (_("%s: pass %lu/%lu (%s)..."), qname, k, n, pass_string); thresh = VERBOSE_UPDATE; if (thresh > size && size != (off_t)-1) thresh = size; } offset = 0; for (;;) { /* How much to write this time? */ lim = sizeof (r); if ((off_t) lim > size - offset && size != (off_t)-1) { lim = (size_t) (size - offset); if (!lim) break; } if (type < 0) fillrand (s, r, lim); /* Loop to retry partial writes. */ for (soff = 0; soff < lim; soff += ssize) { ssize = write (fd, (char *) r + soff, lim - soff); if (ssize <= 0) { if ((ssize == 0 || errno == EIO || errno == ENOSPC) && size == (off_t)-1) { /* Ah, we have found the end of the file */ *sizep = thresh = size = offset + soff; break; } else { error (0, errno, _("%s: error writing at offset %lu"), qname, (unsigned long)(offset+soff)); /* * I sometimes use shred on bad media, before throwing it * out. Thus, I don't want it to give up on bad blocks. * This code assumes 512-byte blocks and tries to skip * over them. It works because lim is always a multiple * of 512, except at the end. */ if (errno == EIO && soff % 512 == 0 && lim >= soff+512 && size != (off_t)-1) { if (lseek (fd, SEEK_CUR, 512) != (off_t)-1) { soff += 512; continue; } error (0, errno, _("%s: lseek"), qname); } return -1; } } } /* Okay, we have written "lim" bytes. */ offset += soff; /* Time to print progress? */ if (offset >= thresh && n) { if (size != (off_t)-1) pfstatus (_("%s: pass %lu/%lu (%s)...%lu/%lu K"), qname, k, n, pass_string, (unsigned long)((offset+1023) / 1024), (unsigned long)((size+1023) / 1024)); else pfstatus (_("%s: pass %lu/%lu (%s)...%lu K"), qname, k, n, pass_string, (unsigned long)((offset+1023) / 1024)); thresh += VERBOSE_UPDATE; if (thresh > size && size != (off_t)-1) thresh = size; /* * Force periodic syncs to keep displayed progress accurate * FIXME: Should these be present even if -v is not enabled, * to keep the buffer cache from filling with dirty pages? * It's a common problem with programs that do lots of writes, * like mkfs. */ if (fdatasync (fd) < 0 && fsync (fd) < 0) { error (0, errno, _("%s: fsync" ), qname); return -1; } } } /* Force what we just wrote to hit the media. */ if (fdatasync (fd) < 0 && fsync (fd) < 0) { error (0, errno, _("%s: fsync" ), qname); return -1; } return 0; } /* * The passes start and end with a random pass, and the passes in between * are done in random order. The idea is to deprive someone trying to * reverse the process of knowledge of the overwrite patterns, so they * have the additional step of figuring out what was done to the disk * before they can try to reverse or cancel it. * * First, all possible 1-bit patterns. There are two of them. * Then, all possible 2-bit patterns. There are four, but the two * which are also 1-bit patterns can be omitted. * Then, all possible 3-bit patterns. Likewise, 8-2 = 6. * Then, all possible 4-bit patterns. 16-4 = 12. * * The basic passes are: * 1-bit: 0x000, 0xFFF * 2-bit: 0x555, 0xAAA * 3-bit: 0x249, 0x492, 0x924, 0x6DB, 0xB6D, 0xDB6 (+ 1-bit) * 100100100100 110110110110 * 9 2 4 D B 6 * 4-bit: 0x111, 0x222, 0x333, 0x444, 0x666, 0x777, * 0x888, 0x999, 0xBBB, 0xCCC, 0xDDD, 0xEEE (+ 1-bit, 2-bit) * Adding three random passes at the beginning, middle and end * produces the default 25-pass structure. * * The next extension would be to 5-bit and 6-bit patterns. * There are 30 uncovered 5-bit patterns and 64-8-2 = 46 uncovered * 6-bit patterns, so they would increase the time required * significantly. 4-bit patterns are enough for most purposes. * * The main gotcha is that this would require a trickier encoding, * since lcm(2,3,4) = 12 bits is easy to fit into an int, but * lcm(2,3,4,5) = 60 bits is not. * * One extension that is included is to complement the first bit in each * 512-byte block, to alter the phase of the encoded data in the more * complex encodings. This doesn't apply to MFM, so the 1-bit patterns * are considered part of the 3-bit ones and the 2-bit patterns are * considered part of the 4-bit patterns. * * * How does the generalization to variable numbers of passes work? * * Here's how... * Have an ordered list of groups of passes. Each group is a set. * Take as many groups as will fit, plus a random subset of the * last partial group, and place them into the passes list. * Then shuffle the passes list into random order and use that. * * One extra detail: if we can't include a large enough fraction of the * last group to be interesting, then just substitute random passes. * * If you want more passes than the entire list of groups can * provide, just start repeating from the beginning of the list. */ static int const patterns[] = { -2, /* 2 random passes */ 2, 0x000, 0xFFF, /* 1-bit */ 2, 0x555, 0xAAA, /* 2-bit */ -1, /* 1 random pass */ 6, 0x249, 0x492, 0x6DB, 0x924, 0xB6D, 0xDB6, /* 3-bit */ 12, 0x111, 0x222, 0x333, 0x444, 0x666, 0x777, 0x888, 0x999, 0xBBB, 0xCCC, 0xDDD, 0xEEE, /* 4-bit */ -1, /* 1 random pass */ /* The following patterns have the frst bit per block flipped */ 8, 0x1000, 0x1249, 0x1492, 0x16DB, 0x1924, 0x1B6D, 0x1DB6, 0x1FFF, 14, 0x1111, 0x1222, 0x1333, 0x1444, 0x1555, 0x1666, 0x1777, 0x1888, 0x1999, 0x1AAA, 0x1BBB, 0x1CCC, 0x1DDD, 0x1EEE, -1, /* 1 random pass */ 0 /* End */ }; /* * Generate a random wiping pass pattern with num passes. * This is a two-stage process. First, the passes to include * are chosen, and then they are shuffled into the desired * order. */ static void genpattern (int *dest, size_t num, struct isaac_state *s) { struct irand_state r; size_t randpasses; int const *p; int *d; size_t n; size_t accum, top, swap; int k; if (!num) return; irand_init (&r, s); /* Stage 1: choose the passes to use */ p = patterns; randpasses = 0; d = dest; /* Destination for generated pass list */ n = num; /* Passes remaining to fill */ for (;;) { k = *p++; /* Block descriptor word */ if (!k) { /* Loop back to the beginning */ p = patterns; } else if (k < 0) { /* -k random passes */ k = -k; if ((size_t) k >= n) { randpasses += n; n = 0; break; } randpasses += k; n -= k; } else if ((size_t) k <= n) { /* Full block of patterns */ memcpy (d, p, k * sizeof (int)); p += k; d += k; n -= k; } else if (n < 2 || 3 * n < (size_t) k) { /* Finish with random */ randpasses += n; break; } else { /* Pad out with k of the n available */ do { if (n == (size_t) k-- || irand_mod (&r, k) < n) { *d++ = *p; n--; } p++; } while (n); break; } } top = num - randpasses; /* Top of initialized data */ /* assert (d == dest+top); */ /* * We now have fixed patterns in the dest buffer up to * "top", and we need to scramble them, with "randpasses" * random passes evenly spaced among them. * * We want one at the beginning, one at the end, and * evenly spaced in between. To do this, we basically * use Bresenham's line draw (a.k.a DDA) algorithm * to draw a line with slope (randpasses-1)/(num-1). * (We use a positive accumulator and count down to * do this.) * * So for each desired output value, we do the following: * - If it should be a random pass, copy the pass type * to top++, out of the way of the other passes, and * set the current pass to -1 (random). * - If it should be a normal pattern pass, choose an * entry at random between here and top-1 (inclusive) * and swap the current entry with that one. */ randpasses--; /* To speed up later math */ accum = randpasses; /* Bresenham DDA accumulator */ for (n = 0; n < num; n++) { if (accum <= randpasses) { accum += num - 1; dest[top++] = dest[n]; dest[n] = -1; } else { swap = n + irand_mod (&r, top - n - 1); k = dest[n]; dest[n] = dest[swap]; dest[swap] = k; } accum -= randpasses; } /* assert (top == num); */ memset (&r, 0, sizeof (r)); /* Wipe this on general principles */ } /* * The core routine to actually do the work. This overwrites the first * size bytes of the given fd. Returns -1 on error, 0 on success with * regular files, and 1 on success with non-regular files. */ static int do_wipefd (int fd, char const *qname, struct isaac_state *s, struct Options const *flags) { size_t i; struct stat st; off_t size; /* Size to write, size to read */ unsigned long n; /* Number of passes for printing purposes */ int *passarray; n = 0; /* dopass takes n -- 0 to mean "don't print progress" */ if (flags->verbose) n = flags->n_iterations + ((flags->zero_fill) != 0); if (fstat (fd, &st)) { error (0, errno, _("%s: fstat"), qname); return -1; } /* Check for devices */ if (!S_ISREG (st.st_mode) && !flags->allow_devices) { error (0, 0, _("%s: not a regular file; use -D to enable operations on devices"), qname); return -1; } /* Allocate pass array */ passarray = malloc (flags->n_iterations * sizeof (int)); if (!passarray) { error (0, 0, _("unable to allocate storage for %lu passes"), (unsigned long) flags->n_iterations); return -1; } size = flags->size; if (size == (off_t)-1) { size = st.st_size; if (!size && !S_ISREG(st.st_mode)) size = (off_t)-1; /* "Unknown size" */ else if (st.st_blksize && !(flags->exact)) size += st.st_blksize - 1 - (size-1) % st.st_blksize; /* round up */ } /* Schedule the passes in random order. */ genpattern (passarray, flags->n_iterations, s); /* Do the work */ for (i = 0; i < flags->n_iterations; i++) { if (dopass (fd, qname, &size, passarray[i], s, i + 1, n) < 0) { memset (passarray, 0, flags->n_iterations * sizeof (int)); free (passarray); return -1; } if (flags->verbose > 1) flushstatus (); } memset (passarray, 0, flags->n_iterations * sizeof (int)); free (passarray); if (flags->zero_fill) if (dopass (fd, qname, &size, 0, s, flags->n_iterations + 1, n) < 0) return -1; if (!S_ISREG (st.st_mode)) return 1; /* Not a regular flag, maybe don't unlink */ /* Okay, now deallocate the data */ if (flags->remove_file && ftruncate (fd, 0) < 0) { error (0, errno, _("%s: error truncating"), qname); return -1; } return 0; /* Regular file */ return !S_ISREG (st.st_mode); } /* A wrapper with a little more checking for fds on the command line */ static int wipefd (int fd, char const *qname, struct isaac_state *s, struct Options const *flags) { int fd_flags = fcntl (fd, F_GETFL); if (fd_flags < 0) { error (0, errno, _("%s: fcntl"), qname); return -1; } /* Ugly, but I think it's portable... */ if ((fd_flags & (O_RDONLY | O_WRONLY | O_RDWR)) == O_RDONLY) { error (0, 0, _("%s: cannot shred read-only file descriptor"), qname); return -1; } if (fd_flags & O_APPEND) { error (0, 0, _("%s: cannot shred append-only file descriptor"), qname); return -1; } if (fd == 1 && flags->verbose) error (EXIT_FAILURE, 0, _("%s: can't wipe stdout and print verbose messages to it"), qname); return do_wipefd (fd, qname, s, flags); } /* --- Name-wiping code --- */ /* Characters allowed in a file name - a safe universal set. */ static char const nameset[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_+=%@#."; /* * This increments the name, considering it as a big-endian base-N number * with the digits taken from nameset. Characters not in the nameset * are considered to come before nameset[0]. * * It's not obvious, but this will explode if name[0..len-1] contains * any 0 bytes. * * This returns the carry (1 on overflow). */ static int incname (char *name, unsigned len) { char const *p; if (!len) return -1; p = strchr (nameset, name[--len]); /* If the character is not found, replace it with a 0 digit */ if (!p) { name[len] = nameset[0]; return 0; } /* If this character has a successor, use it */ if (p[1]) { name[len] = p[1]; return 0; } /* Otherwise, set this digit to 0 and increment the prefix */ name[len] = nameset[0]; return incname (name, len); } /* * Repeatedly rename a file with shorter and shorter names, * to obliterate all traces of the file name on any system that * adds a trailing delimiter to on-disk file names and reuses * the same directory slot. Finally, unlink it. * The passed-in filename is modified in place to the new filename. * (Which is unlinked if this function succeeds, but is still present if * it fails for some reason.) * * The main loop is written carefully to not get stuck if all possible * names of a given length are occupied. It counts down the length from * the original to 0. While the length is non-zero, it tries to find an * unused file name of the given length. It continues until either the * name is available and the rename succeeds, or it runs out of names * to try (incname() wraps and returns 1). Finally, it unlinks the file. * * The unlink() is Unix-specific, as ANSI-standard remove() has more * portability problems with C libraries making it "safe". rename() * is ANSI-standard. * * To force the directory data out, we try to open() the directory and * invoke fdatasync() on it. This is rather non-standard, so we don't * insist that it works, just fall back to a global sync() in that case. * This is fairly significantly Unix-specific. Of course, on any * filesystem with synchronous metadata updates, this is unnecessary. */ static int wipename (char *oldname, struct Options const *flags) { char *newname, *base; /* Base points to filename part of newname */ char const *qname = 0; unsigned len; int err; int dir_fd; /* Try to open directory to sync *it* */ newname = strdup (oldname); /* This is a malloc */ if (!newname) { error (0, 0, _("malloc failed")); return -1; } if (flags->verbose) { qname = quotearg_colon(oldname); pfstatus (_("%s: removing"), qname); } /* Find the file name portion */ base = strrchr (newname, '/'); /* Temporary hackery to get a directory fd */ if (base) { *base = '\0'; dir_fd = open (newname, O_RDONLY | O_NOCTTY); *base = '/'; } else { dir_fd = open (".", O_RDONLY | O_NOCTTY); } base = base ? base + 1 : newname; len = strlen (base); while (len) { memset (base, nameset[0], len); base[len] = 0; do { struct stat st; if (lstat (newname, &st) < 0 && rename (oldname, newname) == 0) { if (dir_fd < 0 || (fdatasync (dir_fd) < 0 && fsync (dir_fd) < 0)) sync (); /* Force directory out */ if (qname) { /* * People seem to understand this better than talking * about renaming oldname. newname doesn't need * quoting because we picked it. */ pfstatus (_("%s: renamed to `%s'"), qname, newname); if (flags->verbose > 1) flushstatus (); } memcpy (oldname + (base - newname), base, len + 1); break; } } while (!incname (base, len)); len--; } free (newname); err = unlink (oldname); if (dir_fd < 0 || (fdatasync (dir_fd) < 0 && fsync (dir_fd) < 0)) sync (); close (dir_fd); if (qname) { if (!err && flags->verbose) pfstatus (_("%s: removed"), qname); } return err; } /* * Finally, the function that actually takes a filename and grinds * it into hamburger. Returns 1 if it was not a regular file. * * FIXME * Detail to note: since we do not restore errno to EACCES after * a failed chmod, we end up printing the error code from the chmod. * This is actually the error that stopped us from proceeding, so * it's arguably the right one, and in practice it'll be either EACCESS * again or EPERM, which both give similar error messages. * Does anyone disagree? */ static int wipefile (char *name, struct isaac_state *s, struct Options const *flags) { int err, fd; fd = open (name, O_WRONLY | O_NOCTTY); if (fd < 0) { if (errno == EACCES && flags->force) { if (chmod (name, S_IWUSR) >= 0) /* 0200, user-write-only */ fd = open (name, O_WRONLY | O_NOCTTY); } else if (errno == ENOENT && memcmp (name, "/dev/fd/", 8) == 0) { /* We accept /dev/fd/# even if the OS doesn't support it */ unsigned long num; char *p; num = strtoul (name+8, &p, 10); /* If it's completely decimal with no leading zeros... */ if (!*p && num < INT_MAX && ((num && name[8] != '0') || !name[9])) { return wipefd ((int)num, quotearg_colon (name), s, flags); } } } if (fd < 0) { if (!flags->force) return 0; error (0, errno, _("Unable to open `%s'"), name); return -1; } err = do_wipefd (fd, quotearg_colon (name), s, flags); close (fd); /* * Wipe the name and unlink - regular files only, no devices! * (wipefd returns 1 for non-regular files.) */ if (err == 0 && flags->remove_file) { err = wipename (name, flags); if (err < 0) error (0, 0, _("Unable to delete file `%s'"), name); } return err; } int main (int argc, char **argv) { struct isaac_state s; int err = 0; struct Options flags; char **file; int n_files; int c; int i; program_name = argv[0]; setlocale (LC_ALL, ""); bindtextdomain (PACKAGE, LOCALEDIR); textdomain (PACKAGE); isaac_seed (&s); memset (&flags, 0, sizeof flags); /* By default, remove each file after sanitization. */ flags.remove_file = 1; flags.n_iterations = DEFAULT_PASSES; flags.size = (off_t)-1; while ((c = getopt_long (argc, argv, "Dfn:ps:vxz", long_opts, NULL)) != -1) { switch (c) { case 0: break; case 'D': flags.allow_devices = 1; break; case 'f': flags.force = 1; break; case 'n': { unsigned long int tmp; if (xstrtoul (optarg, NULL, 10, &tmp, NULL) != LONGINT_OK || (word32) tmp != tmp || ((size_t) (tmp * sizeof (int)) / sizeof (int) != tmp)) { error (1, 0, _("invalid number of passes: %s"), optarg); } flags.n_iterations = (size_t)tmp; } break; case 'p': flags.remove_file = 0; break; case 's': { unsigned long int tmp; if (xstrtoul (optarg, NULL, 0, &tmp, "cbBkMG0") != LONGINT_OK) { error (1, 0, _("invalid file size: %s"), optarg); } flags.size = tmp; } break; case 'v': flags.verbose++; break; case 'x': flags.exact = 1; break; case 'z': flags.zero_fill = 1; break; case_GETOPT_HELP_CHAR; case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS); default: usage (1); } } file = argv + optind; n_files = argc - optind; if (n_files == 0) { error (0, 0, _("missing file argument")); usage (1); } for (i = 0; i < n_files; i++) { if (strcmp (file[i], "-") == 0) { if (wipefd (1, quotearg_colon (file[i]), &s, &flags) < 0) err = 1; } else { /* Plain filename - Note that this overwrites *argv! */ if (wipefile (file[i], &s, &flags) < 0) err = 1; } flushstatus (); } /* Just on general principles, wipe s. */ memset (&s, 0, sizeof (s)); close_stdout (); exit (err); } /* * vim:sw=2:sts=2: */