Wear-Leveling-Algorithmus zur Verteilung der Schreibzugriffe in USB-Sticks

[Micki Müller]

Hallo,

ich bin mir nicht sicher, ob ich mit meiner Frage in der richtigen
Gruppe gelandet bin. Falls nicht, bin ich dankbar für Tipps, wo die
Frage besser aufgehoben wäre.

Es geht um den Wear-Leveling-Algorithmus, der in Flash-Speichermedien
Schreibzugriffe so gleichmäßig auf alle Zellen verteilen soll, dass
keine über Gebühr belastet wird und es zu einem zu schnellen Verschleiß
kommt.

Dieser Algorithmus soll aber laut Wikipedia standardmäßig in der
Firmware der USB-Stick-Controller enthalten sein und die Ursache dafür
sein, dass sicheres Löschen von Dateien durch mehrfaches Überschreiben
der entsprechenden Blöcke auf dem USB-Stick nicht mehr möglich ist, weil
die Schreibzugriffe eben nicht durch Programme auf Anwendungsebene auf
bestimmte Blöcke gelenkt werden können.

s. a.

http://de.wikipedia.org/wiki/Flash-Speicher#Defektmanagement_durch_So
ftware
http://de.wikipedia.org/wiki/Wear-Leveling#Verschlei.C3.9F_und_Ausfal
lvorhersage
http://de.wikipedia.org/wiki/Solid_State_Drive#Sicheres_L.C3.B6schen_
und_Defragmentierung

Ist das soweit richtig bzw. Standard?

Ich habe jetzt mal ein paar Versuche mit vier verschiedenen
USB-Sticks gemacht und mittels des Freeware-Tools Secure Eraser
http://www.ascomp.de/index.php?php=prog&prog=secureeraser
einzelne Dateien sicher gelöscht (durch dreimaliges oder 35-maliges
(Gutmann-Methode) Überschreiben). Würde oben Gesagtes zutreffen,
müssten die Dateien aber, überwiegend jedenfalls, wiederherstellbar
sein. Dies ist mir allerdings mit 4 verschiedenen
(Freeware-)Datenrettungsprogrammen nicht gelungen. Allerdings waren
die Dateinamen der sicher gelöschten Dateien alle lesbar.

Trotzdem widersprechen meine Testergebnisse der (verbreiteten?) Meinung,
dass sicheres Löschen durch Überschreiben auf USB-Sticks aufgrund des
Wear-Leveling-Algorithmus nicht möglich sei bzw. nur in der Form möglich
sei, dass man den gesamten Stick komplett überschreiben muss.

Daher meine Frage: Ist die Implementierung des Wear-Leveling-Algorithmus
Standard in USB-Sticks? Kann er eventuell auf Anwendungsebene durch
Programme wie Secure Eraser beeinflusst werden?

Viele Grüße,
Micki

[Michael Baeuerle]

Post by Micki Müller
[...]
Trotzdem widersprechen meine Testergebnisse der (verbreiteten?) Meinung,
dass sicheres Löschen durch Überschreiben auf USB-Sticks aufgrund des
Wear-Leveling-Algorithmus nicht möglich sei

Das ist aber so, jedenfalls wenn man "sicheres loeschen" so definiert,
dass alle geloeschten Daten n-mal physisch ueberschrieben wurden. Der
Wear-Leveling-Algorithmus (dessen genaue Funktionsweise in den meisten
Faellen nicht dokumentiert ist) aendert aber das Mapping der logischen
zu den physischen Blocks, d.h. die zu loeschenden Daten koennen physisch
nachher durchaus noch vorhanden sein.

Das heisst nicht, dass sie auf einfache Art ueber das USB-Interface
zugaenglich sein muessen, aber sie sind eben ggf. weniger als n-mal oder
auch gar nicht ueberschrieben worden und was physisch noch vorhanden ist
koennte prinzipiell irgendwie wiederhergestellt werden und ist damit
nicht "sicher geloescht".

Post by Micki Müller
bzw. nur in der Form möglich
sei, dass man den gesamten Stick komplett überschreiben muss.

Selbst das einmalige Ueberschreiben aller logischen Blocks garantiert
nicht zwangsweise "sicheres loeschen" aller dort gespeicherten Daten
wenn der Wear-Leveling-Algorithmus mit Reservekapazitaet arbeitet (d.h.
wenn es auch ohne Defektmanagement schon mehr physische als logische
Blocks gibt). Wie oft man das ganze wiederholen muesste damit jeder
physische Block mindestens einmal beschrieben wurde kann man auch nicht
wissen wenn der Algorithmus nicht dokumentiert ist.

Post by Micki Müller
Daher meine Frage: Ist die Implementierung des Wear-Leveling-Algorithmus
Standard in USB-Sticks?

Ja.

Post by Micki Müller
Kann er eventuell auf Anwendungsebene durch
Programme wie Secure Eraser beeinflusst werden?

Prinzipiell schon, da haben vielleicht auch manche Controller
undokumentierte Befehle dafuer. Eine Standardmethode die mit jedem Stick
funktionieren wuerde gibt es AFAIK nicht.


PS:
Prinzipiell gilt das alles auch fuer Speicherkarten und SSDs sofern sie
mit NAND-Flash arbeiten (was wohl seit vielen Jahren bei 100% der
Consumerware der Fall ist).


Micha

[Micki Müller]

Hallo Micha,

Post by Michael Baeuerle

Post by Micki Müller
[...]
Trotzdem widersprechen meine Testergebnisse der (verbreiteten?) Meinung,
dass sicheres Löschen durch Überschreiben auf USB-Sticks aufgrund des
Wear-Leveling-Algorithmus nicht möglich sei

Das ist aber so, jedenfalls wenn man "sicheres loeschen" so definiert,
dass alle geloeschten Daten n-mal physisch ueberschrieben wurden. Der
Wear-Leveling-Algorithmus (dessen genaue Funktionsweise in den meisten
Faellen nicht dokumentiert ist) aendert aber das Mapping der logischen
zu den physischen Blocks, d.h. die zu loeschenden Daten koennen physisch
nachher durchaus noch vorhanden sein.

Aha, d.h. es handelt sich schon um mehr als um das bloße Löschen des
Verweises im Inhaltsverzeichnis, wie beim einfachen Löschen einer Datei.

Post by Michael Baeuerle
Das heisst nicht, dass sie auf einfache Art ueber das USB-Interface
zugaenglich sein muessen, aber sie sind eben ggf. weniger als n-mal oder
auch gar nicht ueberschrieben worden und was physisch noch vorhanden ist
koennte prinzipiell irgendwie wiederhergestellt werden und ist damit
nicht "sicher geloescht".

Verstehe. In der Wikipedia unter

http://de.wikipedia.org/wiki/Solid_State_Drive#Sicheres_L.C3.B6schen_und_Defragmentierung

steht dazu:

"Um dieses Sicherheitsleck zu nutzen und auf die so gelöschte Datei
zugreifen zu können, müsste aber das Laufwerk geöffnet und der
Controller gegen einen ausgetauscht werden, der alle Blöcke ausliest.
Zudem fehlt die Information, welche Blöcke zu einer durch
„Überschreiben“ gelöschten Datei in welcher Reihenfolge gehören."

D. h. um auf die physikalisch noch vorhandenen Daten zugreifen zu
können, müsste man vertiefte Hardwarekenntnisse und Bastelfähigkeiten haben.

Post by Michael Baeuerle

Post by Micki Müller
bzw. nur in der Form möglich
sei, dass man den gesamten Stick komplett überschreiben muss.

Selbst das einmalige Ueberschreiben aller logischen Blocks garantiert
nicht zwangsweise "sicheres loeschen" aller dort gespeicherten Daten
wenn der Wear-Leveling-Algorithmus mit Reservekapazitaet arbeitet (d.h.
wenn es auch ohne Defektmanagement schon mehr physische als logische
Blocks gibt). Wie oft man das ganze wiederholen muesste damit jeder
physische Block mindestens einmal beschrieben wurde kann man auch nicht
wissen wenn der Algorithmus nicht dokumentiert ist.

Ah so. Interessant.

Post by Michael Baeuerle

Post by Micki Müller
Daher meine Frage: Ist die Implementierung des Wear-Leveling-Algorithmus
Standard in USB-Sticks?

Ja.

Ah, danke. Wichtige Info.

Post by Michael Baeuerle

Post by Micki Müller
Kann er eventuell auf Anwendungsebene durch
Programme wie Secure Eraser beeinflusst werden?

Prinzipiell schon, da haben vielleicht auch manche Controller
undokumentierte Befehle dafuer. Eine Standardmethode die mit jedem Stick
funktionieren wuerde gibt es AFAIK nicht.

Verstehe.

Post by Michael Baeuerle
Prinzipiell gilt das alles auch fuer Speicherkarten und SSDs sofern sie
mit NAND-Flash arbeiten (was wohl seit vielen Jahren bei 100% der
Consumerware der Fall ist).

Ja, ist mir klar. Ich hatte jetzt speziell auf USB-Sticks hin gefragt,
weil ich die gerade zum Testen zur Hand hatte.

Danke, Micha, für deine Antwort!

Gruß,
Micki

[Michael Baeuerle]

Post by Micki Müller

Post by Michael Baeuerle

Post by Micki Müller
[...]
Trotzdem widersprechen meine Testergebnisse der (verbreiteten?) Meinung,
dass sicheres Löschen durch überschreiben auf USB-Sticks aufgrund des
Wear-Leveling-Algorithmus nicht möglich sei

Das ist aber so, jedenfalls wenn man "sicheres loeschen" so definiert,
dass alle geloeschten Daten n-mal physisch ueberschrieben wurden. Der
Wear-Leveling-Algorithmus (dessen genaue Funktionsweise in den meisten
Faellen nicht dokumentiert ist) aendert aber das Mapping der logischen
zu den physischen Blocks, d.h. die zu loeschenden Daten koennen physisch
nachher durchaus noch vorhanden sein.

Aha, d.h. es handelt sich schon um mehr als um das bloße Löschen des
Verweises im Inhaltsverzeichnis, wie beim einfachen Löschen einer Datei.

Entfernen aus dem Inhaltsverzeichnis ist das "normale" Loeschen. Du
schriebst "sicheres" Loeschen, irgendwas darueberhinaus sollte da also
schon passieren. Alles was das Attribut "sicher" verdient muss IMHO
zumindest versuchen die Daten zu ueberschreiben.

Post by Micki Müller
[Wikipedia]
| "Um dieses Sicherheitsleck zu nutzen und auf die so gelöschte Datei
| zugreifen zu können, müsste aber das Laufwerk geöffnet und der
| Controller gegen einen ausgetauscht werden, der alle Blöcke ausliest.
| Zudem fehlt die Information, welche Blöcke zu einer durch
| "überschreiben" gelöschten Datei in welcher Reihenfolge gehören."
D. h. um auf die physikalisch noch vorhandenen Daten zugreifen zu
können, müsste man vertiefte Hardwarekenntnisse und Bastelfähigkeiten haben.

Genau. Ein normaler User der sowas z.B. bei EBay kauft wird an keine
Daten mehr herankommen wenn du zum Loeschen einmal alle logischen Blocks
des Mediums ueberschrieben hast (sowohl bei Festplatten als auch bei
Flash-Medien).

Speziell der Hersteller des Controllers hat aber ziemlich sicher
Moeglichkeiten alle physisch vorhandenen Daten auszulesen. Ob daraus
dann noch was interessantes rekonstruiert werden kann ist eine andere
Frage, aber die Moeglichkeit besteht.


Micha

[Micki Müller]

Post by Michael Baeuerle

Post by Micki Müller

Post by Michael Baeuerle

Post by Micki Müller
[...]
Trotzdem widersprechen meine Testergebnisse der (verbreiteten?) Meinung,
dass sicheres Löschen durch überschreiben auf USB-Sticks aufgrund des
Wear-Leveling-Algorithmus nicht möglich sei

Das ist aber so, jedenfalls wenn man "sicheres loeschen" so definiert,
dass alle geloeschten Daten n-mal physisch ueberschrieben wurden. Der
Wear-Leveling-Algorithmus (dessen genaue Funktionsweise in den meisten
Faellen nicht dokumentiert ist) aendert aber das Mapping der logischen
zu den physischen Blocks, d.h. die zu loeschenden Daten koennen physisch
nachher durchaus noch vorhanden sein.

Aha, d.h. es handelt sich schon um mehr als um das bloße Löschen des
Verweises im Inhaltsverzeichnis, wie beim einfachen Löschen einer Datei.

Entfernen aus dem Inhaltsverzeichnis ist das "normale" Loeschen. Du
schriebst "sicheres" Loeschen, irgendwas darueberhinaus sollte da also
schon passieren. Alles was das Attribut "sicher" verdient muss IMHO
zumindest versuchen die Daten zu ueberschreiben.

Was ich meinte, war:

Das Löschen von Daten durch n-maliges Überschreiben bedeutet auf
Flashmedien zwar nicht, dass die Daten physisch überschrieben sind, da
hier der Wear-Leveling-Algorithmus ggf. andere als die ursprünglichen
Blöcke ansteuert. Aber es findet sozusagen ein logisches Überschreiben
statt, so dass die Daten auch nicht wie beim normalen Löschen (wo nur
der Eintrag im Inhaltsverzeichnis gelöscht wird) wiederherstellbar sind.

Hab ich das so richtig verstanden?

Gruß,
Micki

[Micki Müller]

Post by Michael Baeuerle

Post by Micki Müller

Post by Michael Baeuerle

Post by Micki Müller
[...]
Trotzdem widersprechen meine Testergebnisse der (verbreiteten?) Meinung,
dass sicheres Löschen durch überschreiben auf USB-Sticks aufgrund des
Wear-Leveling-Algorithmus nicht möglich sei

Das ist aber so, jedenfalls wenn man "sicheres loeschen" so definiert,
dass alle geloeschten Daten n-mal physisch ueberschrieben wurden. Der
Wear-Leveling-Algorithmus (dessen genaue Funktionsweise in den meisten
Faellen nicht dokumentiert ist) aendert aber das Mapping der logischen
zu den physischen Blocks, d.h. die zu loeschenden Daten koennen physisch
nachher durchaus noch vorhanden sein.

Aha, d.h. es handelt sich schon um mehr als um das bloße Löschen des
Verweises im Inhaltsverzeichnis, wie beim einfachen Löschen einer Datei.

Entfernen aus dem Inhaltsverzeichnis ist das "normale" Loeschen. Du
schriebst "sicheres" Loeschen, irgendwas darueberhinaus sollte da also
schon passieren. Alles was das Attribut "sicher" verdient muss IMHO
zumindest versuchen die Daten zu ueberschreiben.

Was ich meinte, war:

Das Löschen von Daten durch n-maliges Überschreiben bedeutet auf
Flashmedien zwar nicht, dass die Daten physisch überschrieben sind, da
hier der Wear-Leveling-Algorithmus ggf. andere als die ursprünglichen
Blöcke ansteuert. Aber es findet sozusagen ein logisches Überschreiben
statt, so dass die Daten auch nicht wie beim normalen Löschen (wo nur
der Eintrag im Inhaltsverzeichnis gelöscht wird) durch simple Nutzung
von Datenrettungsprogrammen auf Anwendungsebene wiederherstellbar sind.

Hab ich das so richtig verstanden?

Gruß,
Micki

[Michael Baeuerle]

Post by Micki Müller
Das Löschen von Daten durch n-maliges Überschreiben bedeutet auf
Flashmedien zwar nicht, dass die Daten physisch überschrieben sind, da
hier der Wear-Leveling-Algorithmus ggf. andere als die ursprünglichen
Blöcke ansteuert. Aber es findet sozusagen ein logisches Überschreiben
statt, so dass die Daten auch nicht wie beim normalen Löschen (wo nur
der Eintrag im Inhaltsverzeichnis gelöscht wird) durch simple Nutzung
von Datenrettungsprogrammen auf Anwendungsebene wiederherstellbar sind.
Hab ich das so richtig verstanden?

Jein. Das gilt fuer die gaengigen Rettungsprogramme der folgenden beiden
Kategorien:

1)
Es wird versucht wie beim alten "UNDELETE.EXE" die
geloeschten/verstuemmelten Verzeichniseintraege wiederherzustellen. Dazu
muss das Dateisystem noch vorhanden und funktionsfaehig sein.

2)
Es wird am Dateisystem vorbei auf dem Raw-Device nach Merkmalen
bestimmter Dateitypen gesucht und dann versucht die Daten zu
extrahieren. Das geht auch mit kaputtem Dateisystem, "PhotoRec" macht
das z.B. so.

Programme dieser beiden Kategorien benoetigen alle die Daten in den
logischen Blocks, retten also schon nach einmaligem Ueberschreiben aller
logischen Blocks gar nichts mehr.

Ein Herstellertool das auf die reservierten physischen Blocks zugreifen
kann arbeitet aber ggf. auch auf Anwendungsebene (mit ausreichenden
Rechten kann eine Anwendung direkt mit dem Controller kommunizieren wenn
das dessen Hersteller so vorgesehen hat). Der Controller muss nicht
zwangsweise ausgebaut werden, die Anwendungsebene ist also nicht das
Kriterium. Die potentielle Gefahr aus dieser Richtung duerfte aber
extrem gering sein weil undokumentierte Hintertueren benutzt werden
muessen die bei jedem Controller anders sein duerften. Ein generisches
Tool wie die oben genannten wird es dafuer also nicht geben und die
Hersteller werden ihre eigenen Tools auch kaum veroeffentlichen (da sie
schon um die Algorithmen so ein Geheimnis machen).


Micha

[Michael Limburg]

Post by Michael Baeuerle
Selbst das einmalige Ueberschreiben aller logischen Blocks garantiert
nicht zwangsweise "sicheres loeschen" aller dort gespeicherten Daten
wenn der Wear-Leveling-Algorithmus mit Reservekapazitaet arbeitet
(d.h. wenn es auch ohne Defektmanagement schon mehr physische als
logische Blocks gibt). Wie oft man das ganze wiederholen muesste damit
jeder physische Block mindestens einmal beschrieben wurde kann man
auch nicht wissen wenn der Algorithmus nicht dokumentiert ist.

a) Es gibt nicht _den_ Algorithmus, noch geben Hersteller bekannt, wie
dieser arbeitet und meist auch nicht, ob es überhaupt einen gibt.
b) Um in 1. Näherung Aufschluß darüber zu bekommen, ob es überhaupt
Resevekapazität gibt, kann man ja mal den tatsächlich vorhandenen
Speicherplatz mit der Kapazität üblicher Flash-Chips vergleichen.

Post by Michael Baeuerle

Post by Micki Müller
Daher meine Frage: Ist die Implementierung des
Wear-Leveling-Algorithmus Standard in USB-Sticks?

Ja.

Gewagte Aussage, das behaupten ja nicht mal alle Hersteller.

Michael

[Michael Baeuerle]

Post by Michael Limburg

Post by Micki Müller
Daher meine Frage: Ist die Implementierung des
Wear-Leveling-Algorithmus Standard in USB-Sticks?

Ja.

Gewagte Aussage, das behaupten ja nicht mal alle Hersteller.

Vielleicht weil es mittlerweile selbstverstaendlich ist. Die Chips haben
so wenig Schreibzyklen, da kommt man doch ohne auf keinen gruenen Zweig
(speziell mit FAT Dateisystem). Und die Datenblaetter der Controller
sind ja teilweise der bessere Witz: 3 Seiten lang (Seite 1: Featurelist,
Seite 2: Pinout, Seite 3: Liste der unterstuetzten Flash-Chips). SGS
Thomson ist da mit den 34 Seiten beim ST72681 schon eine ruehmliche
Ausnahme ... aber auch da zum Thema "Wear-Leveling" nur ganze 6 Zeilen.
Das ist alles hochgeheim.


Micha

[Wolfgang Ottenweller]

Hallo,

Post by Micki Müller
die Ursache dafür
sein, dass sicheres Löschen von Dateien durch mehrfaches Überschreiben
der entsprechenden Blöcke auf dem USB-Stick nicht mehr möglich ist

Du willst also nicht den ganzen Stick sicher löschen, sondern einzelne
Dateien?

Dann nehmen wir mal ein Extrembeispiel:

Die Datei ist einen Block groß und viele (oder alle) anderen Blöcke
unbelegt, die Datei soll durch 30-faches Überschreiben "sicher" gelöscht
werden.

Der Controller stelle fest, daß der aktuelle genutzte Block
überdurchschnittlich genutzt wurde und verwendet beim Neuschreiben der
Datei einen anderen Block, bei jedem weiteren "Überschreiben" erneut
einen anderen Block (um die Blöcke gleichmäßig abzunutzen).

Jetzt hast Du 30 Blöcke gelöscht, der eine der unbedingt gelöscht werden
sollte ist aber unverändert.

Weniger gefährlich wird es, wenn man zum "sicheren" Löschen den gesamten
Stick mit Datenmüll vollschreibt, jetzt könnten alte Daten nur noch in
als defekt ausgelagerten Blöcken zu finden sein.

Gruß, Wolfgang

[Richard W. Könning]

Post by Wolfgang Ottenweller
Weniger gefährlich wird es, wenn man zum "sicheren" Löschen den gesamten
Stick mit Datenmüll vollschreibt, jetzt könnten alte Daten nur noch in
als defekt ausgelagerten Blöcken zu finden sein.

Falsch, der Wear-Leveling-Algorithmus kann auf einer Blockmenge
operieren, die größer als die nach außen angebotene Kapazität ist,
d.h. alte Daten können in Blöcken sein, die später wieder verwendet
werden (aber erst dann zugreifbar sind, wenn sie mit neuen Daten
überschrieben wurden).
Ciao,
Richard