Question: How to modify classic strategy pattern in case when each ConcreteStrategy talks to DataStorage? There are different types of data storage and the interface depends on the concrete strategy.

Answer: 
Make your strategies dependent on DataStorage via constructor injection. Then each strategy can use DataStorage as they please.

If DataStorage implements many interfaces, make each strategy dependent on that particular interface.
Remember that pattern is just general thing. You can do whatever you need to make that pattern work in your situation. You can combine your strategy with Factory, Memento, etc. Right now everybody talks about "injecting". But using interfaces has been around for long time. 

```
public class ConcreteStrategy : IStrategy 
{
    protected IDatastorage _dataStrorage;
} 

```

This should do it