Hashing and wear-le...
 
Notifications
Clear all

Hashing and wear-levelling  

Page 2 / 4
  RSS
trewmte
(@trewmte)
Community Legend

I should mention that wear-levelling is a fairly new technique, I believe (don't quote me on that) it has been first implemented around 2003.

Wear-levelling responds following wear-measurement. Wear-measurement appears to be made up of many parts.

Two of the earliest simple wear-levelling and reclaimation employed, I believe, was the design of Wu and Zwaenepoel [1994] and the other patented by Wells [1994].

*Wu and Zwaenepoel [1994] employ a simple form of wear leveling. When the erase count of the most worn-out unit is higher by 100 than that of the least wornout unit, the data on them is swapped.

*WU, M. AND ZWAENEPOEL, W. 1994. eNVy A nonvolatile,
main memory storage system. In Proceedings
of the 6th International Conference on
Architectural Support for Programming Languages
and Operating Systems. San Jose, CA.
86–97.

**Wells [1994] patented a reclamation policy that relies on a weighted combination of efficiency and wear leveling. The system selects the next unit to be reclaimed based on a score.

**WELLS, S. E. 1994. Method for wear leveling in a
flash EEPROM memory. US patent 5,341,339.
Filed November 1, 1993; Issued August 23, 1994;
Assigned to Intel.

[Updated] Reference sources added

ReplyQuote
Posted : 25/02/2009 4:08 pm
jaclaz
(@jaclaz)
Community Legend

A maybe "stupid" idea. ?

Using dsfo (part of the dsfok package) you get the MD5 hash while "dd-ing" the \\.\PHYSICALDRIVEx. (i.e. hashing the transferred data while transferring it)

IF the MD5 of the resulting image is the same, wouldn't it be correct to state that at the moment the MD5 was the same, and thus that the image is accurate? ?

jaclaz

ReplyQuote
Posted : 25/02/2009 4:20 pm
ecophobia
(@ecophobia)
Active Member

A maybe "stupid" idea. ?

Using dsfo (part of the dsfok package) you get the MD5 hash while "dd-ing" the \\.\PHYSICALDRIVEx. (i.e. hashing the transferred data while transferring it)

IF the MD5 of the resulting image is the same, wouldn't it be correct to state that at the moment the MD5 was the same, and thus that the image is accurate? ?

jaclaz

Not stupid at all, but
I would still want to know in advance if I am dealing with the device that produces different hash value. It is especially important if you are going to present / rely on the recovered/ deleted files. Some extra work has to be done to make sure the evidence found inside these deleted files is accurate. It may be possible to recover zip, word or rar files and be able to open it on one occasion, and not be able to replicate this after creating another image because of the new free space block being assembled from the different sectors this time. This is not so much an issue with jpeg and other ‘non container type’ files though.

ReplyQuote
Posted : 25/02/2009 4:52 pm
thefuf
(@thefuf)
Active Member

I have found another USB flash drive (pqi 1 GB) with same "problems" (block device gives different hash values every time, but files on a mounted filesystem give the same hash values). I took two images from this drive and hashed every 512-byte block. It seems that data is moving on the drive - some blocks are replaced with zeroes, some blocks with zeroes are replaced with data from other blocks. I can provide diffs if requested. Unfortunately, I cannot reproduce this after wiping the drive with zeroes / random data (everything is OK now, I'm getting the same hash values every time in all tests).

By the way, first diff is at offset (in bytes) 995376640 and the last is at 1010498560. Is it possible, that this area is reserved for wear-levelling and is visible by reading the block device? Any other theories? )

ReplyQuote
Posted : 26/02/2009 12:55 am
indur
(@indur)
Member

This is the same behavior that was reported at a DefCon talk last year, though the talk was about SSDs and not USB flash disks.

I agree that the only way for this behavior to exist is if the flash drive is made aware of the filesystem on top of the block device.

Some light Googling suggests that compact flash devices have additional commands beyond simply accessing them as block devices – for example, to "erase" whole CF blocks. Since USB should identify the device as a CF drive supporting these commands, a smart-enough driver could use them to provide "extra" information to the device (like "this block is unused now") that the device's wear-leveling can now take advantage of. (I've also seen mentions that the wear-leveling implementations vary greatly between vendors, so it makes sense you'd only see some USB disks have this behavior.) While it's speculation without looking more closely into the compact flash specs, this would be my guess as to how the USB disk is magically getting the information needed to alter unallocated space of its own accord.

As per the DefCon talk, there's no convenient way to stop this behavior – the wear leveler runs whenever the device is receiving power.

ReplyQuote
Posted : 26/02/2009 10:22 pm
ecophobia
(@ecophobia)
Active Member

Yes,

The issue does exist despite some people finding it hard to believe, and it is here to stay for some time. The only way to deal with this is through the correctly devices procedures that in general can be described as

1. Identifying the device with the specific wear-levelling behaviour (via hashing before and after the procedure for example).

2. Isolate the existing (not marked as deleted) from the deleted files. Verify the integrity of the existing files.

3. Deal with the deleted files in a way that the accurate and verifiable data can be presented in court.

——————————————————————————————
"Knowledge is dynamic in nature, today's knowledge may well become tomorrow's ignorance if an individual or organisation fails to update knowledge as environmental conditions change."

Turban, E., Leidner, D., Mclean, E., Wetherbe, J., Information Technology for Management Transforming Organizations in the Digital Economy. Wiley; 6 edition (March 5, 2007)
ReplyQuote
Posted : 27/02/2009 5:39 am
PaulSanderson
(@paulsanderson)
Senior Member

The issue does exist despite some people finding it hard to believe

Who is finding it hard to believe as I said above (and in private emails) I want to see some supporting evidence - not just an unsupported statement (as your initial one was) thrown onto the forum. As I have said all along I am willing to be proven wrong, I have been before and I will be again

While the issue *may* exist and weight of evidence is starting to show that it could - at the moment I have seen

one paper (TrueFFS) from a manufacturer that appears to refer to a wear levelling algorithm that is supported by installing a device driver - this is not in my mind the issue - although it is certainly something to be aware of. Good forensic practice would say that you don't install unknown drivers on your forensic PC though.

some articles about wear levelling in general – if you like traditional wear levelling

some anecdotal evidence taken from the internet, worth considering but there are no hard facts to back it up

some more recent evidence from Thefur that seems to support the argument - but as mentioned before I would still like to know whether he has checked whether he has a TrueFFs driver on his machine.

It took a bit of prompting but some of the articles posted by ecophobia do seem to indirectly support his claims (I wish they had been posted in one of his first four posts). But I do emphasise indirectly and to be 100% sure (and if we are going to potentially stand up in court and hand our hat on this then 100% is what we should be striving for). After a brief read the only substantive article that supports wear levelling based on file locations is the SAN disk one that also states that they don’t use this technique – although clearly that could change or others could. (I don’t consider the unsupported posts on other forums (or this one for that matter) as hard evidence – they just add a little to the weight of the evidence)

All media nowadays is shipped with defects that are mapped out transparently, USB flash drives are mass produced very cheaply and the scenarios seen so far could be explained by a defective device (I am not saying is supported – just saying could be). At the moment no one knows for sure but the weight of evidence does seem to be shifting towards wear levelling as discussed being the case.

But lets not forget that this is forensics and NO ONE should be taking what they read on an internet forum at face value but should verify the facts for themselves. This is what I am attempting to do here – this thread has been a bit emotive but it has stimulated further discussion and hopefully research.

To put it in perspective though, I have still not been able to reproduce this and if I had to stand up in court today and explain why a device returned a differing hash I would only be prepared to offer the above as a theory.

Please do not take this as a dig ecophobia but as far as I am concerned, this is still only a possibility, although an increasingly likely one.

I will keep trying, as work permits, to duplicate this; and as the famous saying goes “a mind is like a parachute – works best when it is open” and unlike some I am open to criticism – I tend to learn from it 

ReplyQuote
Posted : 27/02/2009 2:51 pm
jaclaz
(@jaclaz)
Community Legend

I am not so sure about points 2. and 3. in ecophobia's post.

Which method/tools/idea are you thinking about to deal with 3.?

As far as I can say, on an ordinary HD, there are two kinds of "deleted" files.

Actually deleted files, i.e. something that you can actually "undelete" with specific undelete tools, and "file remnants", i.e. something that may derive from a remnant of a partial overwrite or remnants from a previous filesystem/formatting.

Dealing with the first kind seems possible, but what about the second type.

@thefuf
@ecophobia

Can you run Chipgenius on the specific device(s) that shoew this behaviour so that we can try to trace the actual controller chip manufacturer and possibly find some more info?

http//www.boot-land.net/forums/index.php?showtopic=4661&st=0

Homepage
http//www.mydigit.cn/chipgenius.htm

Direct download
http//www.mydigit.cn/mytool/chipgenius.rar

jaclaz

ReplyQuote
Posted : 28/02/2009 12:32 am
thefuf
(@thefuf)
Active Member

Can you run Chipgenius on the specific device(s) that shoew this behaviour so that we can try to trace the actual controller chip manufacturer and possibly find some more info?

Device Name +[E]+Запоминающее устройство для USB(Generic USB Flash Disk USB Device)

PnP Device ID VID = 3538 PID = 0054
Serial Number 000000000004F7
Revision 0.00

Device Type Standard USB device - USB2.0 High-Speed

Chip Vendor USBest(??)
Chip Part-Number UT163

Product Vendor Generic
Product Model USB Flash Disk

Tools on Web ?http//bbs.mydigit.cn/read.php?tid=4345

@sandy771
I cannot find anything related to TrueFFS in my kernel config file.

ReplyQuote
Posted : 28/02/2009 1:10 am
trewmte
(@trewmte)
Community Legend

M-Systems developed and marketed software called TrueFFS, a block-mapping device driver that implements the FTL (Flash Translation Layer). M-Systems literature states that TrueFFS uses a wearleveling technique that combines randomness with erase counts. The literature claims that the use of randomness eliminates the need to protect the exact erase counts stored in each erase unit. The details of the wearleveling algorithm of TrueFFS are not described in the open literature or in patents. TrueFFS selects units for reclamation based on both the amount of invalid data, the number of erasures, and identification of static areas. TrueFFS also tries to cluster related blocks so that multiple blocks in the same unit are likely to become invalid together. This is done by trying to map contiguous logical blocks onto a single unit under the assumption that higherlevel software (i.e., a file system) attempts to cluster related data at the logical-block level.

DAN, R. AND WILLIAMS, J. 1997. A TrueFFS and FLite technical overview of M-Systems’ flash file systems. Tech. rep. 80-SR-002-00-6L Rev. 1.30,
M-Systems.

ReplyQuote
Posted : 28/02/2009 2:57 am
ecophobia
(@ecophobia)
Active Member

Can you run Chipgenius on the specific device(s) that show this behaviour so that we can try to trace the actual controller chip manufacturer and possibly find some more info?

These devices are still part of various ongoing investigations (as I mentioned previously), so I would not be able to plug them in directly to the Windows machine without the hardware write-blocker. I don’t think the tools jaclaz mentioned would work via the write-blocker. I don't trust windows registry tweaks to be used for write blocking, especially with troublesome devices like these. It would add extra complexity to the already difficult situation.

Anyone interested to find more information can get EagleTec 8Gb Turbo Series and 16GB PQI U310 USB flash drives and play with them. Hopefully they don’t have too many version revisions and have the same hardware throughout the world. I got nowhere when I tried to contact both manufacturers for clarifications.

ReplyQuote
Posted : 28/02/2009 8:09 am
jaclaz
(@jaclaz)
Community Legend

I don’t think the tools jaclaz mentioned would work via the write-blocker.

Of course it is NOT the case to risk contamination of devices ), though, from a purely logical standpoint, your stance does not hold. 😯

ChipGenius, like USBdeview and a number of similar tools are read only.

BUT

IF the writeblocker works, even if it they are not, no harm can be done to the device.

Thus trying the app is harmless.

"Thinking" that the tool would not work if used with the write-blocker puts you in the same category you attempted putting other members, those that "read and think" and do not experiment on the field. wink

@trewte
Yes, but TrueFFS is another thing, it is a "special" filesystem that adopts wear-leveling techniques at a higher level.

What ecophobia is talking about is a low-level mechanism inside the controller firmware, more similar to the algorithms that re-map bad sectors in conventional hard disks than to an actual filesystem implementation.

TRUEFFS documentation is widely available
http//www.texim-europe.com/promotion/119/trueffs%20product%20brief.pdf
http//www.dataio.com/pdf/NAND/MSystems/TrueFFS_Wear_Leveling_Mechanism.pdf
http//www-kryo.desy.de/documents/vxWorks/V5.4/trueffs/guide/index.html

jaclaz

ReplyQuote
Posted : 01/03/2009 4:02 pm
trewmte
(@trewmte)
Community Legend

@trewte
Yes, but TrueFFS is another thing, it is a "special" filesystem that adopts wear-leveling techniques at a higher level.

jaclaz, thanks firstly for the useful links and appreciate you coming back on this. I love learning new things. The information I am posting is not meant to agree with one side or the other, but various systems are being mentioned. I do not know every system on the market so I find it helpful if some notes are posted in the same thread about a particular system.

What ecophobia is talking about is a low-level mechanism inside the controller firmware, more similar to the algorithms that re-map bad sectors in conventional hard disks than to an actual filesystem implementation.

Moverover, some systems are being dismissed but the reasons for that are not always clear. Sandy771 mentioned above he didn't think TrueFFS was relevant and you have identified a reason.

Very interesting and, again, thanks.

ReplyQuote
Posted : 01/03/2009 4:38 pm
jaclaz
(@jaclaz)
Community Legend

@trewte
You are welcome. )

The actual point that a lot of people seem to be missing - mind you no offence intended - is that technology has evolved a lot since first "HD like" devices.

Many of us, including myself, learned how CHS worked in the old days and have difficulty in realizing that since IDE kind of drives appeared on the market there is no more ANY known - physical - correlation between geometry, sector addresses - no matter if CHS or LBA - and actual sector location on the device.

Anything is "translated" or "filtered" by the internal controller firmware of the device, of which there are no or very scarce information from the actual controller manufacturer.

To oversimplify, the controller holds a database of addresses that we think looks like this
A=Address
P=Placement

A P
1 1
2 2
3 3
4 4
5 5

but that for all we know may actually be like this

A P
1 418
2 12478
3 355
4 876
5 42

😯

…and we have NO way to know…

jaclaz

ReplyQuote
Posted : 01/03/2009 5:17 pm
ecophobia
(@ecophobia)
Active Member

jaclaz,
I haven't tried ChipsGenius but familiar with USBdeview and some other similar tools. To get them to work, you need to connect USB devices to the Windows operating systems which will in turn try to write to the newly connected devices by default. The tools may be read only, by Windows is NOT. Thus, trying the app is not harmless without write blocking them first.
These tools most certainly will work with the software write blockers/registry tweaks, but I am not sure about the hardware write blockers. I may give it a go sometime next week and let you know.

What ecophobia is talking about is a low-level mechanism inside the controller firmware, more similar to the algorithms that re-map bad sectors in conventional hard disks than to an actual file system implementation.

Yes.

Here some more links.
www.embeddedfreebsd.org/Documents/Intel-FTL.pdf
http//portal.acm.org/citation.cfm?id=1176887.1176911

The actual point that a lot of people seem to be missing - mind you no offence intended - is that technology has evolved a lot since first "HD like" devices.

Yes.

ReplyQuote
Posted : 01/03/2009 5:21 pm
Page 2 / 4
Share: